Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (8): 231-237.DOI: 10.3778/j.issn.1002-8331.2002-0016

Previous Articles     Next Articles

Research on Improved A* Algorithm of Bidirectional Search Mechanism

KONG Jili, ZHANG Pengkun, LIU Xiaoping   

  1. School of Modern Post, Beijing University of Posts and Telecommunications, Beijing 100876, China
  • Online:2021-04-15 Published:2021-04-23



  1. 北京邮电大学 现代邮政学院,北京 100876


Aiming at the problems of high memory occupancy and low computing efficiency of A* algorithm in large-scale environment, an improved A* algorithm is proposed. Firstly, a bidirectional search mechanism is introduced. It searches with the original starting point, the end point and the oppositecurrent point as the target point, so that the AGV path optimization has directionality. Secondly, the evaluation function is optimized. It selects the appropriate weight coefficient for the evaluation function, so as to improve the calculation efficiency of path optimization. In order to verify the effectiveness of the improved A* algorithm, it is programmed in Matlab platform and simulated in different sizes of grid map with obstacles. The simulation results show that the number of nodes traversed by the improved A* algorithm is less, the calculation efficiency is higher and the shortest path can be obtained.

Key words: bidirectional search, improved A* algorithm, path optimization



关键词: 双向搜索, 改进A*算法, 路径寻优