An Improved A* Algorithm for Searching Infinite Neighbourhoods
XIN Yu1,2, LIANG Huawei2, DU Mingbo1,2, MEI Tao2, WANG Zhiling2, JIANG Ruhai2
1. Department of Automation, University of Science and Technology of China, Hefei 230027, China;
2. Institute of Advanced Manufacturing Technology, Hefei Institutes of Physical Science, Chinese Academy of Science, Hefei 230027, China
The paths obtained by conventional A* algorithm in grid map are usually not the optimal solutions, which have many turning nodes. To solve these problems, an improved A* algorithm is presented. In this method, the number of searchable neighbourhood is extended to infinite (basic A* algorithm has 8 discrete searchable neighbourhoods), and the search direction can be arbitrary. As a result, the path produced by the improved A* is much shorter and the number of turning nodes is greatly reduced. The proposed method is implemented on our self-developed unmanned vehicle, Intelligent Pioneer. The vehicle experiments and its good performance in the Intelligent Vehicle Future Challenge of China show that the resulting path of our method is more optimal, which observably improves the driving efficiency and stationarity of the unmanned vehicles.
[1] Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107. [2] Stentz A. Optimal and efficient path planning for partially-known environments[C]//IEEE International Conference on Robotics and Automation. Piscataway, USA: IEEE, 1994: 3310-3317.[3] Koenig S, Likhachev M. D* Lite[C]//AAAI/IAAI. Menlo Park, USA: American Association for Artificial Intelligence, 2002: 476-483.[4] Stentz A. The focussed D* algorithm for real-time replanning[C]//Proceedings of International Joint Conference on Artificial Intelligence. San Mateo, USA: Morgan Kaufmann Publishers, 1995: 1652-1659.[5] Yap P. Grid-based path-finding[M]//Advances in Artificial Intelligence. Berlin, Germany: Springer-Verlag, 2002: 44-55.[6] Botea A, Müller M, Schaeffer J. Near optimal hierarchical path-finding[J]. Journal of Game Development, 2004, 1(1): 7-28.[7] Reynolds C W. Steering behaviors for autonomous characters [C]//Game Developers Conference. 1999: 763-782.[8] Montemerlo M, Becker J, Bhat S, et al. Junior: The Stanford entry in the urban challenge[J]. Journal of Field Robotics, 2008, 25(9): 569-597. [9] Ferguson D, Stentz A. Field D*: An interpolation-based path planner and replanner[M]//Robotics Research. Berlin, Germany: Springer-Verlag, 2007: 239-253.[10] Mei T, Liang H, Kong B, et al. Development of 'Intelligent Pioneer' unmanned vehicle[C]//IEEE Intelligent Vehicles Symposium. Piscataway, USA: IEEE, 2012: 938-943.[11] Forrest A R. Interactive interpolation and approximation by Bezier polynomials[J]. Computer-aided Design, 1990, 22(9): 527-537.
