CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Probabilistic Multi Robot Path Planning in Dynamic Environments: A Comparison between A* and DFS

by Safaa H. Shwail, Alia Karim, Scott Turner
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 82 - Number 7
Year of Publication: 2013
Authors: Safaa H. Shwail, Alia Karim, Scott Turner
10.5120/14130-2251

Safaa H. Shwail, Alia Karim, Scott Turner . Probabilistic Multi Robot Path Planning in Dynamic Environments: A Comparison between A* and DFS. International Journal of Computer Applications. 82, 7 ( November 2013), 29-34. DOI=10.5120/14130-2251

@article{ 10.5120/14130-2251,
author = { Safaa H. Shwail, Alia Karim, Scott Turner },
title = { Probabilistic Multi Robot Path Planning in Dynamic Environments: A Comparison between A* and DFS },
journal = { International Journal of Computer Applications },
issue_date = { November 2013 },
volume = { 82 },
number = { 7 },
month = { November },
year = { 2013 },
issn = { 0975-8887 },
pages = { 29-34 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume82/number7/14130-2251/ },
doi = { 10.5120/14130-2251 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:57:10.730879+05:30
%A Safaa H. Shwail
%A Alia Karim
%A Scott Turner
%T Probabilistic Multi Robot Path Planning in Dynamic Environments: A Comparison between A* and DFS
%J International Journal of Computer Applications
%@ 0975-8887
%V 82
%N 7
%P 29-34
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In this paper, a probabilistic roadmap planner algorithm with the multi robot path planning problem have been proposed by using the A* search algorithm in a dynamic environment. The whole process consists of two phases. In the first phase: Preprocessing phase, the work space is converted into the configuration space, constructing a probabilistic roadmap graph in the free space, and finding the optimal path for each robot using a global planner that avoids the collision with the static obstacles. The second phase: Moving phase, moves each robot in a prioritized manner from its starting point to its ending point through a near optimal path with avoiding collision with the moving obstacles and the other robots. A comparison has been done with the depth first algorithm to see the difference. The simulation results shows that choosing A* search algorithm affect positively the speed of the two phases together in comparison to the depth first search algorithm.

References
  1. P. Svestka and M. H. Overmars, "Coordinated path planning for multiple robots," Robotics and Autonomous Systems, Elsevier, pp. 125-152, 1998.
  2. S. Carpin and E. Pagello, "An experimental study of distributed robot coordination," Robotics and Autonomous Systems, Elsevier, pp. 129-133, 2009.
  3. J. P. van den Berg and M. H. Overmars, "Roadmap-Based Motion Planning in Dynamic Environments," IEEE TRANSACTIONS ON ROBOTICS, vol. 21, no. 5, pp. 885-897, 2005.
  4. J. C. Latombe, Robot Motion Planning, Kluwer Academic Publishers, 1991.
  5. J. E. Hopcroft, J. T. Schwartz and M. Sharir, "On the complexity of motion planning for multiple independent objects; PSPACE hardness of the "warehouseman's problem"," The International Journal of Robotics Research, vol. 3, no. 4, pp. 76-88, 1984.
  6. S. M. LaValle, PLANNING ALGORITHMS, Cambridge University Press, 2006.
  7. P. Velagapudi, K. Sycara and P. Scerri, "Decentralized prioritized planning in large multirobot teams," Taipei, 2010.
  8. K. Fujimura, "Time-Minimum Routes in Time-Dependent Networks," IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, vol. 11, no. 3, pp. 341-351, 1995.
  9. J. T. Schwartz and M. Sharir, "On the piano movers' problem: III. Coordinating the motion of several independent bodies: the special case of circular bodies moving amidst polygonal barriers," The International Journal of Robotics Research, vol. 2, no. 3, pp. 46-75, 1983.
  10. D. Parsons and J. Canny, "A Motion Planner for Multiple Mobile Robots," Cincinnati, OH, 1990.
  11. J. Barraquand and J. -C. Latombe, "Robot Motion Planning: A Distributed Representation Approach," The International Journal of Robotics Research, vol. 10, no. 6, pp. 628-649, 1991.
  12. R. Luna and K. E. Bekris, "Efficient and Complete Centralized Multi-Robot Path Planning," IEEE/RSJ International Conference on Intelligent Robots and Systems, 2011.
  13. S. J. Buckley, "Fast Motion Planning for Multiple Moving Robots," Scottsdale, AZ, 1989.
  14. J. P. van den Berg and M. H. Overmars, "Prioritized motion planning for multiple robots," 2005.
  15. M. Bennewitz, W. Burgard and S. Thrun, "Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots path planning techniques for teams of mobile robots," Robotics and Autonomous Systems, vol. 41, no. 2-3, pp. 89-99, 2002.
  16. P. Velagapudi, K. Sycara and P. Scerri, "Decentralized prioritized planning in large multirobot teams," Taipei, 2010.
  17. M. Erdmann and T. Lozano-Perez, "On multiple moving objects," 1986.
  18. S. S. Chiddarwar and N. R. Babu, "Conflict free coordinated path planning for multiple robots using a dynamic path modification sequence," Robotics and Autonomous Systems, Elsevier, pp. 508-518, 2011.
  19. T. Fraichard and I. Rhone-Alpes, "Trajectory Planning in a Dynamic Workspace: a 'State-Time Space' Approach," Advance Robotics, vol. 1, no. 13, pp. 75-94, 1999.
  20. L. E. Kavraki, P. Svestka and J. -C. Latombe, "Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces," IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, vol. 12, no. 4, pp. 566-580, 1996.
  21. M. Ryan, "Multi-Robot Path-Planning with Subgraphs," Australia, 2006.
  22. M. Ryan, "Graph Decomposition for Efficient Multi-robot Path Planning," San Francisco, CA, USA, 2007.
  23. M. Ryan, "Constraint-based multi-robot path planning," IEEE International Conference on Robotics and Automation, 2010.
  24. A. Stentz, "Optimal and Efficient Path Planning for Partially-Known Environments," IEEE International Conference on Robotics and Automation, 1994.
  25. A. Stentz, "The Focussed D* Algorithm for Real-Time Replanning," International Joint Conference on Artificial Intelligence, 1995.
Index Terms

Computer Science
Information Sciences

Keywords

Multi-robot path planning decoupled planning A* Depth First Search (DFS).

Powered by PhDFocusTM