The A-r-Star (Ar) Pathfinder

Abstract

This paper presents a variant of the A-Star (A^*) pathfinder for robot path planning calledA_r^* (pronounced A-r-Star)and demonstrates that the A_r^*algorithm outperforms A^* in a uniformly gridded sparse world and gives performance matching that of A^* in a uniformly gridded cluttered world. This algorithm is simple to implement and understand. It alsohighlights the performance advantages of theA_r^*algorithm and proves its properties experimentally and analytically (where appropriate). Some challenges affecting the performance of A_r^*have been presented and some solutions to these challenges have been developed and implemented. The performance of A_r^*has been compared toA^*running on both uniform and multi-resolution grids of different world scenarios. Results show that on a sparse high-resolution uniform grid worldA_r^*'s search speed scales well and it outperforms A^* by an exponential factor.

References

• Cikes, M. , Dakulovic, M. , and Petrovic, I. 2011. The path planning algorithms for a mobile robot based on the occupancy grid map of the environment; A comparative study. In Proceedings of the XXIII International Symposium on Information, Communication and Automation Technologies, 1-8.
• Hart, P. E. , Nilsson, N. J. , and Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4 (2), 100-107.
• Dechter, R. and Pearl, J. 1985. Generalized best-first search strategies and the optimality of A*. J. ACM 32 (3), 505-536.
• Kambhampati, S. and Davis, L. S. 1986. Multiresolution path planning for mobile robots. IEEE Journal of Robotics and Automation 2 (3) (Sep 1986), 135-145.
• Verwer, B. J. H. 1990. A multiresolution work space, multiresolution configuration space approach to solve the path planning problem. In Proceedings of the IEEE International Conference on Robotics and Automation 2103, 2107-2112.
• Botea, A. , Muller, M. , and Schaeffer, J. 2004. Near optimal hierarchical path-finding. Computers and Games 3, 33–38.
• Fredman, M. L. and Willard, D. E. 1993. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences 47 (3), 424-436.
• Cowlagi, R. V. and Tsiotras, P. 2012. Multi-resolution path planning: theoretical analysis, efficient implementation, and extensions to dynamic environments. In Proceedings of the49th IEEE Conference on Decision and Control. 1384-1390.
• Daniel, K. , Nash, A. , Koenig, S. , and Felner, A. 2010. "Theta*: any-angle path planning on grids. Journal of Artificial Intelligence Research 39, 533-579.
• Stentz, A. 1995. Optimal and efficient path planning for unknown and dynamic environments. International Journal of Robotics & Automation 10 (3), 89-100.
• Stentz, A. 1994. Optimal and efficient path planning for partially-known environments. In Proceedings of the IEEE International Conference on Robotics and Automation 3314, 3310-3317.
• Stentz, A. 1995. The Focussed D* algorithm for real-time replanning. In Proceedings of the International Joint Conference on Arti?cial Intelligence.
• Koenig, S. and Likhachev, M. 2002. D*lite. In Proceedings of the Eighteenth National Conference on Artificial Intelligence, Edmonton, Alberta, Canada, 476-483.
• Ferguson, D. and Stentz, A. 2007. Field D*: an interpolation-based path planner and replanner. In Thrun, S. , Brooks, R. and Durrant-Whyte, H. , eds. , Robotics Research. Springer Tracts in Advanced Robotics,Springer Berlin Heidelberg, 239-253.
• Carsten, J. , Ferguson, D. , and Stentz, A. 2006. 3D Field D: improved path planning and replanning in three dimensions. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. 3381-3386.
• Shih-Ying, C. , Tsui-Ping, C. , and Zhi-Hong, C. 2012. An efficient theta-join query processing algorithm on MapReduce framework. In Proceedings of the International Symposium on Computer, Consumer and Control . 686-689.
• Aizawa, K. and Tanaka, S. 2009. A constant-time algorithm for finding neighbors in quadtrees. IEEE Transactions on Pattern Analysis and Machine Intelligence 31 (7), 1178-1183.
• Schroeder, W. J. , Zarge, J. A. , and Lorensen, W. E. 1992. Decimation of triangle meshes. SIGGRAPH Comput. Graph. 26(2), 65-70.
• Huang, C. T. and Mitchell, O. R. 1994. A Euclidean distance transform using grayscale morphology decomposition. IEEE Transactions on Pattern Analysis and Machine Intelligence 16 (4), 443-448.
• Chung, K. -L. , Huang, H. -L. , and Lu, H. -I. 2004. Efficient region segmentation on compressed gray images using quadtree and shading representation. Pattern Recognition 37 (8), 1591-1605.
• Michel, O. 2004. Webots: professional mobile robot simulation. International Journal of Advanced Robotic Systems 1 (1), 39-42.

Index Terms

Keywords