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 条
  • [41] Development of advanced computational simulation of two-dimensional plate-like crystals: A comparison with population balance model
    Alharby, Tareq Nafea
    Alanazi, Muteb
    ARABIAN JOURNAL OF CHEMISTRY, 2023, 16 (07)
  • [42] Dosimetric Comparison of Two-Dimensional (2D) vs. Three-Dimensional (3D) Planning for Bone Metastases
    Potter, A. E.
    Holwell, M.
    Fitzpatrick, D.
    Bezjak, A.
    McLean, M.
    Levin, W.
    Dinniwell, R.
    Zurawel-Balaura, L.
    Wong, R.
    INTERNATIONAL JOURNAL OF RADIATION ONCOLOGY BIOLOGY PHYSICS, 2009, 75 (03): : S505 - S505
  • [43] Numerical Comparison between Iterative and Noniterative Coupled Simulations for Surface Water Flow and Solute Transport with Unstructured Grid in Two-Dimensional Basin Fertigation
    Dai, Wei
    Zhang, Shaohui
    Xu, Di
    Bai, Meijian
    Li, Yinong
    JOURNAL OF IRRIGATION AND DRAINAGE ENGINEERING, 2019, 145 (01)
  • [44] High-performance imaging with an advanced non-imaging lens based on full-path optical diffraction calculation in two-dimensional space
    Liu, Yingli
    Dai, Yijie
    Shen, Fanqi
    Yang, Lin
    Ding, Zhanghao
    Zheng, Zhenrong
    Wu, Rengmao
    Xu, Liu
    OPTICS EXPRESS, 2022, 30 (07) : 11014 - 11025
  • [45] Comparison of custom cutting guides based on three-dimensional computerized CT-scan planning and a conventional ancillary system based on two-dimensional planning in total knee arthroplasty: a randomized controlled trial
    Sariali, Elhadi
    Kajetanek, Charles
    Catonne, Yves
    INTERNATIONAL ORTHOPAEDICS, 2019, 43 (11) : 2529 - 2538
  • [46] Comparison of custom cutting guides based on three-dimensional computerized CT-scan planning and a conventional ancillary system based on two-dimensional planning in total knee arthroplasty: a randomized controlled trial
    Elhadi Sariali
    Charles Kajetanek
    Yves Catonné
    International Orthopaedics, 2019, 43 : 2529 - 2538
  • [47] Modeling of ultrasonic waves by the finite-difference method in the time domain: A two-dimensional problem: Optimal algorithms, analysis of errors, and absorbing ranges near the grid boundaries
    V. A. Barkhatov
    Russian Journal of Nondestructive Testing, 2009, 45 : 410 - 424
  • [48] Modeling of Ultrasonic Waves by the Finite-Difference Method in the Time Domain: A Two-Dimensional Problem: Optimal Algorithms, Analysis of Errors, and Absorbing Ranges near the Grid Boundaries
    Barkhatov, V. A.
    RUSSIAN JOURNAL OF NONDESTRUCTIVE TESTING, 2009, 45 (06) : 410 - 424
  • [49] Dosimetric Comparison between Three-Dimensional Magnetic Resonance Imaging-Guided and Conventional Two-Dimensional Point A-Based Intracavitary Brachytherapy Planning for Cervical Cancer
    Ren, Juan
    Yuan, Wei
    Wang, Ruihua
    Wang, Qiuping
    Li, Yi
    Xue, Chaofan
    Yan, Yanli
    Ma, Xiaowei
    Tan, Li
    Liu, Zi
    PLOS ONE, 2016, 11 (09):
  • [50] A comparison of two-dimensional prediction tracing and a virtual reality patient methods for diagnosis and treatment planning of orthognathic cases in dental students: a randomized preliminary study
    Sakowitz, Scott M.
    Inglehart, Marita R.
    Ramaswamy, Vidya
    Edwards, Sean
    Shoukri, Brandon
    Sachs, Stephen
    Kim-Berman, Hera
    VIRTUAL REALITY, 2020, 24 (03) : 399 - 409