Probabilistic multi robot path planning in dynamic environments: a comparison between A* and DFS

Safaa H Shwail, Alia Karim, Scott J Turner

Research output: Contribution to JournalArticle

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
Original languageEnglish
Pages (from-to)29-34
Number of pages6
JournalInternational Journal of Computer Applications
Volume82
Issue number7
DOIs
Publication statusPublished - 15 Nov 2013

    Fingerprint

Keywords

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

Cite this