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

• P. Svestka and M. H. Overmars, "Coordinated path planning for multiple robots," Robotics and Autonomous Systems, Elsevier, pp. 125-152, 1998.
• S. Carpin and E. Pagello, "An experimental study of distributed robot coordination," Robotics and Autonomous Systems, Elsevier, pp. 129-133, 2009.
• 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.
• J. C. Latombe, Robot Motion Planning, Kluwer Academic Publishers, 1991.
• 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.
• S. M. LaValle, PLANNING ALGORITHMS, Cambridge University Press, 2006.
• P. Velagapudi, K. Sycara and P. Scerri, "Decentralized prioritized planning in large multirobot teams," Taipei, 2010.
• K. Fujimura, "Time-Minimum Routes in Time-Dependent Networks," IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, vol. 11, no. 3, pp. 341-351, 1995.
• 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.
• D. Parsons and J. Canny, "A Motion Planner for Multiple Mobile Robots," Cincinnati, OH, 1990.
• 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.
• R. Luna and K. E. Bekris, "Efficient and Complete Centralized Multi-Robot Path Planning," IEEE/RSJ International Conference on Intelligent Robots and Systems, 2011.
• S. J. Buckley, "Fast Motion Planning for Multiple Moving Robots," Scottsdale, AZ, 1989.
• J. P. van den Berg and M. H. Overmars, "Prioritized motion planning for multiple robots," 2005.
• 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.
• P. Velagapudi, K. Sycara and P. Scerri, "Decentralized prioritized planning in large multirobot teams," Taipei, 2010.
• M. Erdmann and T. Lozano-Perez, "On multiple moving objects," 1986.
• 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.
• 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.
• 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.
• M. Ryan, "Multi-Robot Path-Planning with Subgraphs," Australia, 2006.
• M. Ryan, "Graph Decomposition for Efficient Multi-robot Path Planning," San Francisco, CA, USA, 2007.
• M. Ryan, "Constraint-based multi-robot path planning," IEEE International Conference on Robotics and Automation, 2010.
• A. Stentz, "Optimal and Efficient Path Planning for Partially-Known Environments," IEEE International Conference on Robotics and Automation, 1994.
• A. Stentz, "The Focussed D* Algorithm for Real-Time Replanning," International Joint Conference on Artificial Intelligence, 1995.