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

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F22%3APU147638" target="_blank" >RIV/00216305:26210/22:PU147638 - isvavai.cz</a>

Result on the web

<a href="https://mendel-journal.org/index.php/mendel" target="_blank" >https://mendel-journal.org/index.php/mendel</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.13164/mendel.2022.2.097" target="_blank" >10.13164/mendel.2022.2.097</a>

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

J_SC - Article in a specialist periodical, which is included in the SCOPUS database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Mendel Journal series

ISSN

1803-3814

e-ISSN

—

Volume of the periodical

28

Issue of the periodical within the volume

2

Country of publishing house

CZ - CZECH REPUBLIC

Number of pages

11

Pages from-to

97-107

UT code for WoS article

—

EID of the result in the Scopus database

2-s2.0-85145971181