In the process of robot pathfinding, the traditional A* algorithm has the numerous nodes to traverse, which leads to a long search time and too many search nodes in the path planning. In order to solve this problem, this paper proposes to improve the A* algorithm to improve its search efficiency. The improved algorithm adopts a bidirectional search method, which starts from both the starting point and the ending point of the path, and when they converge, the entire search of the algorithm is completed. Under a 100 × 100 grid graph robot path simulation environment, the improved algorithm reduces the search time by 1.0 s and the search nodes by 35 nodes compared with the traditional A* algorithm. These results demonstrate that the improved algorithm significantly outperforms the traditional A* algorithm in terms of operational efficiency.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An Improved A* Algorithm Based on Bidirectional Search

  • Guangjie Xu,
  • Zimo Tian,
  • Senwu Cai,
  • Xuansen He

摘要

In the process of robot pathfinding, the traditional A* algorithm has the numerous nodes to traverse, which leads to a long search time and too many search nodes in the path planning. In order to solve this problem, this paper proposes to improve the A* algorithm to improve its search efficiency. The improved algorithm adopts a bidirectional search method, which starts from both the starting point and the ending point of the path, and when they converge, the entire search of the algorithm is completed. Under a 100 × 100 grid graph robot path simulation environment, the improved algorithm reduces the search time by 1.0 s and the search nodes by 35 nodes compared with the traditional A* algorithm. These results demonstrate that the improved algorithm significantly outperforms the traditional A* algorithm in terms of operational efficiency.