TY - JOUR AU - Petr Soustek AU - Radomil Matousek AU - Jiri Dvorak AU - Lenka Manakova PY - 2022/12/20 Y2 - 2024/03/28 TI - Explanation and Speedup Comparison of Advanced Path-planning Algorithms Presented on Two-dimensional Grid JF - MENDEL JA - mendel VL - 28 IS - 2 SE - Research articles DO - 10.13164/mendel.2022.2.097 UR - https://mendel-journal.org/index.php/mendel/article/view/209 AB - 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. ER -