Research on Path Planning by a Tangent Point Search

When traditional path planning algorithms are used for path searching for Automated Guided Vehicles (AGVs) in static environments, they usually encounter the difficulties of excessive search nodes, high memory consumption, and long running time. To tackle these problems, this paper proposes a tangent point search algorithm based on quadtree grid environment modeling. The algorithm establishes a weighted graph by extracting key cell points and then uses the Dijkstra algorithm for path planning. In the scenarios of different map sizes, A* algorithm, Rapidly-exploring Random Trees (RRT) algorithm, Dijkstra algorithm, and a Dijkstra algorithm with a tangent point search (DA+TPS) were simulated and analyzed. The results show that among the four algorithms, the DA+TPS has the shortest route length and minimum search time. The comparison demonstrates that the proposed method can effectively reduce the number of search nodes, speed up the search process, and reduce redundant nodes in the path, thus reducing the number of turns for AGVs.

I. Introduction

Path planning is an important research direction in the field of artificial intelligence, which involves finding the optimal path from the starting point to the target point. With the rapid development of applications such as autonomous driving, robot navigation, and logistics management, efficient and accurate path planning algorithms have become crucial for achieving autonomous navigation and optimizing resource utilization [1]. Performing path planning in grid maps is a common and challenging task. Although many path planning algorithms have been proposed and applied in grid maps, there are still some challenges that need to be addressed. Among them the choice of cell size is a significant factor limiting algorithm performance. A too large cell size results in severe loss of map details, while a too small cell size increases the number of cells and consequently significantly increases the algorithm's running time. To address this challenge, many scholars have made corresponding improvements based on classical algorithms. Liang Yu proposed a heuristic search algorithm based on the Dijkstra algorithm, which introduces an estimation function to estimate the path cost [2]. This improvement can plan the shortest path based on shortening response time. Korf introduced a fusion of the A* algorithm and the iterative deepening algorithm to optimize state deduplication and evaluation sorting, thereby improving algorithm efficiency [3]. Harabor et al. proposed the Jump Point Search (JPS) algorithm based on the A* algorithm's path planning strategy, which reduces the large number of intermediate nodes generated during the search process, thereby reducing the computational load for global path planning [4]. Song Yongjie et al. proposed an improved Bi-RRT algorithm suitable for Automated Guided Vehicles (AGVs) global path planning, combining the probability p target bias strategy with the cost estimation idea in the A* algorithm to form a dual-target bias strategy to obtain a better path [5]. Xia Qingsong utilized the ant colony algorithm to develop a novel heuristic function for path planning [6]. This function drives the robot along the shortest path by taking into account the distance from the current node to the endpoint and the angle between the local path and the Euclidean path from the starting point to the endpoint, thus enhancing algorithm convergence.