Global path planning based on a bidirectional alternating search A* algorithm for mobile robots. (June 2022)

• Record Type: Journal Article
• Authors: Li, Changgeng; Huang, Xia; Ding, Jun; Song, Kun; Lu, Shiqing
• Is Part Of: Computers & industrial engineering. Volume 168(2022)
• Publication Date: 2022-06
• Subjects: Mobile robots -- Global path planning -- A* algorithm -- Bidirectional alternating search -- Bézier curves; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.108123
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: A bidirectional alternating search (BAS) strategy is introduced into the A* algorithm which improves the search efficiency. The improved heuristic function overcomes the shortcomings of the BAS-A* algorithm. The filtering function and Bézier curves is employed to reduce the turning angle, path length and smooth the path. The practicability of the proposed algorithm is validated on the TurtleBot3 Waffle Pi mobile robot. Abstract: While the A* algorithm has been widely investigated and applied in path planning problems, it has outstanding issues such as long calculation time, large turning angles, and the unsmoothed path in large task spaces. Aiming at overcoming these problems, an improved A* algorithm is proposed in this work. First, a bidirectional alternating search (BAS) strategy is introduced into the A* algorithm; the forward and backward path lists use the current path node in the opposite list as the target node to alternately search for paths until the paths meet, which improves the search efficiency of the algorithm. Then, the heuristic function is weighted via exponential attenuation, which overcomes the shortcomings of the BAS-A* algorithm. Finally, the filtering function of path nodes is introduced to reduce redundant nodes in the path, thereby effectively reducing the turning angle. Moreover, the use of Bézier curves fulfills the requirements of smooth path planning, which is critical for the motion control of mobile robots. Simulations of path planning on maps of different sizes were performed, and the proposed algorithm was compared with that of the A* algorithm, the genetic algorithm (GA) and the simulated annealing algorithm (SA) in terms of the computation time, path length, and turning angle. The results reveal that the proposed algorithm can solve the robot path planning problem more efficiently and smoothly than the other algorithms mentioned above. Additionally, the practicability of the proposed algorithm is validated on the TurtleBot3 Waffle Pi mobile robot.