CFP last date
22 April 2024
Reseach Article

The A-r-Star (Ar) Pathfinder

by Daniel Opoku, Abdollah Homaifar, Edward Tunstel
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 67 - Number 8
Year of Publication: 2013
Authors: Daniel Opoku, Abdollah Homaifar, Edward Tunstel
10.5120/11417-6753

Daniel Opoku, Abdollah Homaifar, Edward Tunstel . The A-r-Star (Ar) Pathfinder. International Journal of Computer Applications. 67, 8 ( April 2013), 32-44. DOI=10.5120/11417-6753

@article{ 10.5120/11417-6753,
author = { Daniel Opoku, Abdollah Homaifar, Edward Tunstel },
title = { The A-r-Star (Ar) Pathfinder },
journal = { International Journal of Computer Applications },
issue_date = { April 2013 },
volume = { 67 },
number = { 8 },
month = { April },
year = { 2013 },
issn = { 0975-8887 },
pages = { 32-44 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume67/number8/11417-6753/ },
doi = { 10.5120/11417-6753 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:24:09.602962+05:30
%A Daniel Opoku
%A Abdollah Homaifar
%A Edward Tunstel
%T The A-r-Star (Ar) Pathfinder
%J International Journal of Computer Applications
%@ 0975-8887
%V 67
%N 8
%P 32-44
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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.
  2. 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.
  3. Dechter, R. and Pearl, J. 1985. Generalized best-first search strategies and the optimality of A*. J. ACM 32 (3), 505-536.
  4. 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.
  5. 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.
  6. Botea, A. , Muller, M. , and Schaeffer, J. 2004. Near optimal hierarchical path-finding. Computers and Games 3, 33–38.
  7. 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.
  8. 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.
  9. 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.
  10. Stentz, A. 1995. Optimal and efficient path planning for unknown and dynamic environments. International Journal of Robotics & Automation 10 (3), 89-100.
  11. 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.
  12. Stentz, A. 1995. The Focussed D* algorithm for real-time replanning. In Proceedings of the International Joint Conference on Arti?cial Intelligence.
  13. Koenig, S. and Likhachev, M. 2002. D*lite. In Proceedings of the Eighteenth National Conference on Artificial Intelligence, Edmonton, Alberta, Canada, 476-483.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. Schroeder, W. J. , Zarge, J. A. , and Lorensen, W. E. 1992. Decimation of triangle meshes. SIGGRAPH Comput. Graph. 26(2), 65-70.
  19. 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.
  20. 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.
  21. Michel, O. 2004. Webots: professional mobile robot simulation. International Journal of Advanced Robotic Systems 1 (1), 39-42.
Index Terms

Computer Science
Information Sciences

Keywords

Pathfinder Path Planning A-r-Star A-infinity-Star Multi-resolution Path Smoothing