An Efficient Path Planning Algorithm for Mobile Robots

摘要

This paper applies the ${A}^{*}$ algorithm commonly used in game development to mobile robot path planning. Although the ${A}^{*}$ algorithm is characterized by optimality, simplicity, and flexibility and it has been widely used in path planning, it also has some disadvantages such as redundant points, large memory overhead, and long computing time. In order to improve efficiency and overcome these disadvantages, this paper first combines the Jump Point Search (JPS) and the ${A}^{*}$ algorithm, and proposes the ${A}^{*}$ algorithm, which reduces the redundant points in the search process and improves the efficiency of path planning. Inspired by the bidirectional search algorithm, the $BJ{A}^{*}$ algorithm is proposed based on the $J{A}^{*}$ algorithm and the improved bidirectional search algorithm, which further improves the speed of the path planning. The simulation results show that the $BJ{A}^{*}$ algorithm is an efficient path planning algorithm for mobile robots, especially in large scenes and scenes requiring high real-time performance.