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

被引:0
|
作者
Soustek P. [1 ]
Matousek R. [1 ]
Dvorak J. [1 ]
Manakova L. [1 ]
机构
[1] Institute of Automation and Computer Science, Brno University of Technology
来源
Mendel | 2022年 / 28卷 / 02期
关键词
A[!sup]∗[!/sup] algorithm; Dijkstra’s algorithm; JP S algorithm; Path planning; Route planning; Subgoal algorithm;
D O I
10.13164/mendel.2022.2.097
中图分类号
学科分类号
摘要
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. © 2022, Brno University of Technology. All rights reserved.
引用
收藏
页码:97 / 107
页数:10
相关论文
共 50 条
  • [31] Needle path planning and steering in a three-dimensional non-static environment using two-dimensional ultrasound images
    Vrooijink, Gustaaf J.
    Abayazid, Momen
    Patil, Sachin
    Alterovitz, Ron
    Misra, Sarthak
    INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH, 2014, 33 (10): : 1361 - 1374
  • [32] Dosimetric comparison of two-dimensional versus three-dimensional intracavitary brachytherapy in locally advanced cervical cancer
    Klisarovska, Violeta
    Smichkoska, Snezhana
    Chakalaroski, Petar
    Krstevska, Valentina
    Dimitrovska, Nadica
    Stefanovski, Zoran
    Lazarova, Emilija
    SRPSKI ARHIV ZA CELOKUPNO LEKARSTVO, 2018, 146 (3-4) : 157 - 162
  • [33] Enhancing Transjugular Intrahepatic Portosystemic Shunt Puncture by Using Three-dimensional Path Planning Based on the Back Projection of Two Two-dimensional Portographs
    Adamus, Ralf
    Pfister, Marcus
    Loose, Reinhard W. R.
    RADIOLOGY, 2009, 251 (02) : 543 - 547
  • [34] Collision-free path planning for a diamond-shaped robot using two-dimensional cellular automata
    Tzionas, PG
    Thanailakis, A
    Tsalides, PG
    IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 1997, 13 (02): : 237 - 250
  • [35] A hybrid two-dimensional path planning model based on frothing construction algorithm and local fast marching method
    Yu, Chong
    Qiu, Qiwen
    Chen, Xiong
    COMPUTERS & ELECTRICAL ENGINEERING, 2013, 39 (02) : 475 - 487
  • [36] A novel approach using a two-dimensional wavelet transform in ball grid array (BGA) substrate conducting path inspections
    Yeh, CH
    INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2003, 21 (03): : 223 - 233
  • [38] Comparison of the efficiencies of image compression algorithms based on separable and nonseparable two-dimensional Haar wavelet bases
    Belov A.M.
    Pattern Recogn. Image Anal., 2008, 4 (602-605): : 602 - 605
  • [39] Comparison of three-versus two-dimensional pre-operative planning for total hip arthroplasty
    Crutcher, James P.
    Hameed, Daniel
    Dubin, Jeremy
    Mont, Michael A.
    Mont, Michael
    JOURNAL OF ORTHOPAEDICS, 2024, 47 : 100 - 105
  • [40] Two-dimensional potential problems:: Accuracy through advanced integration algorithms and C1 continuous boundary elements
    Pereda, J
    Garrido, JA
    Lorenzana, A
    BOUNDARY ELEMENTS XXII, 2000, 8 : 155 - 164