News Release

Research on AGV task path planning based on improved A* algorithm

Peer-Reviewed Publication

Beijing Zhongke Journal Publising Co. Ltd.

Comparison of improvement effect.

image: Compared with the traditional algorithm and other improved algorithms in many complex scenarios, the performance of path planning results is improved significantly. view more 

Credit: Beijing Zhongke Journal Publising Co. Ltd.

Research Background

In recent years, global car ownership has increased year by year, leading to road traffic safety and vehicle congestion conditions are not optimistic. With the support of a new round of scientific and technological revolution and industrial change, Intelligent vehicles have become the strategic competitive highland of the world's automobile powers. At the same time, as an important part of the Intelligent Transportation System (ITS), Smart cars are also an effective means to solve problems such as traffic safety and traffic congestion. From the key technical level, intelligent driving technology can be divided into three parts: environmental perception, positioning mapping, and planning control. The planning module in planning control is vividly called the brain of intelligent driving, which determines the future driving behavior of autonomous vehicles and generates trajectory information by integrating valuable information from upstream modules. In this process, the safety, comfort, and efficiency of driving are ensured.

With the background of artificial intelligence, the large-scale promotion and application of intelligent manufacturing, and the AGV of the car-like site which is closely related to intelligent vehicles as an important medium, has been continuously applied to many fields such as factory workshops, logistics warehouses, production, and processing, and has good development prospects. Path planning has always been an indispensable part of automatic guided vehicles, planning a safe and feasible path with low complexity can effectively improve the execution efficiency of AGV tasks. Compared with the genetic algorithm and RRT algorithm, the A* algorithm has higher path optimization efficiency and better effect for general static scenes in practical applications. However, the traditional A* algorithm still has room for improvement in many complex scenes in the manufacturing field, and the final path it finds is prone to high complexity, such as too wide expansion range, long path finding time, many paths turns, and uneven corners. In view of the above problems, many scholars have also conducted some studies: Guo et al. proposed A method integrating Bezier curves to further optimize the path, aiming at the problems of many broken lines and large turning angles in the path planning of A* algorithm, but lacked strategies to improve the pathfinding speed and reduce the number of unnecessary turning points. Cao et al. made improvements to the problem that there were many turning points in the final path searched and reduced the number of turns by judging that the search method of direction points of the parent node was given priority at the same cost. However, there was a problem that nodes in the actual subsequent path that tended to be far from the task point could not complete the optimization. Aiming at path planning in large-scale scenarios, Chen et al. proposed an improved A* algorithm of bidirectional search mechanism to improve the time efficiency of wayfinding, but the steering cost of AGV was not considered. Xing et al. proposed an application method of A* algorithm path planning based on a complex parking environment, which made the planned path more feasible, but did not consider the actual turning Angle smoothing of the traffic path.

Based on the general complex environment and indoor application scenarios of AGV, this paper uses the grid method to model the complex environment map and SLAM(Simultaneous Localization and Mapping) algorithm to construct the map under the indoor empty scene respectively to conduct the path planning experiment. On the basis of the A* algorithm, the path optimization method of inflection point backtracking is proposed to reduce the number of unnecessary turns. The expansion mode, the number of turning points, and the smoothness of the turning path are improved and optimized respectively in the path node expansion process and the initial path backtracking process. Through simulation experiments, the final improved algorithm can increase the search speed of the AGV task path, further improve the efficiency of node expansion, reduce the number of unnecessary turns, and increase the feasibility of the actual path.

 

Results and Significance

Based on the general complex environment and indoor application scenarios of AGV, this study uses software to construct a complex environment map using the grid method and the SLAM (Simultaneous Localization and Mapping) algorithm to construct a map in an indoor open scene, which is used for follow-up path planning experiments. Based on the traditional A* algorithm, this study improves and optimizes its expansion mode, number of turning points, and smoothness of the turning path in the process of path node expansion and initial path backtracking. The contributions of this study can be summarized as follows.

We introduced the estimated weight in the cost function and used the occupation node marker in node expansion to reduce the number of extended nodes and the path-finding time in the case of many obstacles with random distribution. We also propose a path optimization method for inflection point backtracking to reduce unnecessary turns, redundant path segments, and integrated Bezier curves to smooth the path. Finally, the applicability of the improved algorithm was verified through simulation experiments.

Simulation results show that the improved algorithm proposed in this paper is superior to traditional methods and can help AGV improve task execution efficiency by planning paths with low complexity and smoothness. In addition, the scheme provides a new solution for the global path planning of unmanned vehicles.

At the same time, there are several aspects that should be the focus of future development, including whether the planning algorithm can cope with multiple scenarios and maintain good applicability and robustness, whether it can meet the requirements of planning security and stability in complex and narrow scenarios, and whether it can consider the perceived uncertainty and control constraints for planning.


Disclaimer: AAAS and EurekAlert! are not responsible for the accuracy of news releases posted to EurekAlert! by contributing institutions or for the use of any information through the EurekAlert system.