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 journalArticleResearchpeer-review

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

Motion planning
Robots

Keywords

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

Cite this

@article{83cf0a4a1ebb47c08c193020d5d897f0,
title = "Probabilistic multi robot path planning in dynamic environments: a comparison between A* and DFS",
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",
keywords = "A*, Depth First Search (DFS), Multi-robot, decoupled planning, path planning",
author = "Shwail, {Safaa H} and Alia Karim and Turner, {Scott J}",
year = "2013",
month = "11",
day = "15",
doi = "10.5120/14130-2251",
language = "English",
volume = "82",
pages = "29--34",
journal = "International Journal of Computer Applications",
number = "7",

}

Probabilistic multi robot path planning in dynamic environments: a comparison between A* and DFS. / Shwail, Safaa H; Karim, Alia; Turner, Scott J.

In: International Journal of Computer Applications, Vol. 82, No. 7, 15.11.2013, p. 29-34.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

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

AU - Shwail, Safaa H

AU - Karim, Alia

AU - Turner, Scott J

PY - 2013/11/15

Y1 - 2013/11/15

N2 - 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

AB - 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

KW - A

KW - Depth First Search (DFS)

KW - Multi-robot

KW - decoupled planning

KW - path planning

U2 - 10.5120/14130-2251

DO - 10.5120/14130-2251

M3 - Article

VL - 82

SP - 29

EP - 34

JO - International Journal of Computer Applications

JF - International Journal of Computer Applications

IS - 7

ER -