Call for Paper - January 2023 Edition
IJCA solicits original research papers for the January 2023 Edition. Last date of manuscript submission is December 20, 2022. Read More

The A-r-Star (Ar) Pathfinder

Print
PDF
International Journal of Computer Applications
© 2013 by IJCA Journal
Volume 67 - Number 8
Year of Publication: 2013
Authors:
Daniel Opoku
Abdollah Homaifar
Edward Tunstel
10.5120/11417-6753

Daniel Opoku, Abdollah Homaifar and Edward Tunstel. Article: The A-r-Star (Ar) Pathfinder. International Journal of Computer Applications 67(8):32-44, April 2013. Full text available. BibTeX

@article{key:article,
	author = {Daniel Opoku and Abdollah Homaifar and Edward Tunstel},
	title = {Article: The A-r-Star (Ar) Pathfinder},
	journal = {International Journal of Computer Applications},
	year = {2013},
	volume = {67},
	number = {8},
	pages = {32-44},
	month = {April},
	note = {Full text available}
}

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.