Detail publikace

Explanation and Speedup Comparison of Advanced Path-planning Algorithms Presented on Two-dimensional Grid

ŠOUSTEK, P. MATOUŠEK, R. DVOŘÁK, J. MAŇÁKOVÁ, L.

Originální název

Explanation and Speedup Comparison of Advanced Path-planning Algorithms Presented on Two-dimensional Grid

Typ

článek v časopise ve Scopus, Jsc

Jazyk

angličtina

Originální abstrakt

Path planning or network route planning problems are an important issue in AI, robotics, or computer games. Appropriate implementation and knowledge of advanced and classical path-planning algorithms can be important for both autonomous navigation systems and computer games. In this paper, we compare advanced path planning algorithms implemented on a two-dimensional grid. Advanced path planning algorithms, including pseudocode, are introduced. The experiments were performed in the Python environment, thus with a significant performance margin over C++ or Rust implementations. The main focus is on the speedup of the algorithms compared to a baseline method, which was chosen to be the well-known Dijkstra’s algorithm. All experiments correspond to trajectories on a two-dimensional grid, with variously defined constraints. The motion from each node corresponds to a Moore neighborhood, i.e., it is possible in eight directions. In this paper, three well-known path planning algorithms are described and compared: the Dijkstra, A* and A* /w Bounding Box. And two advanced methods are included, namely Jump Point Search (JPS), incorporated with the Bounding Box variant (JPS+BB), and Simple Subgoal (SS). These advanced methods clearly show their advantage in the context of the speed up of solution time.

Klíčová slova

Path planning, Route planning, JPS algorithm, Subgoal algorithm, A* algorithm, Dijkstra's algorithm

Autoři

ŠOUSTEK, P.; MATOUŠEK, R.; DVOŘÁK, J.; MAŇÁKOVÁ, L.

Vydáno

20. 12. 2022

Nakladatel

Brno University of Technology

Místo

Brno, Czech republic

ISSN

1803-3814

Periodikum

Mendel Journal series

Ročník

28

Číslo

2

Stát

Česká republika

Strany od

97

Strany do

107

Strany počet

11

URL

https://mendel-journal.org/index.php/mendel

BibTex

@article{BUT182793,
  author="Petr {Šoustek} and Radomil {Matoušek} and Jiří {Dvořák} and Lenka {Maňáková}",
  title="Explanation and Speedup Comparison of Advanced Path-planning Algorithms Presented on Two-dimensional Grid",
  journal="Mendel Journal series",
  year="2022",
  volume="28",
  number="2",
  pages="97--107",
  doi="10.13164/mendel.2022.2.097",
  issn="1803-3814",
  url="https://mendel-journal.org/index.php/mendel"
}