Optimizing the A* search algorithm for mobile robotic devices

3rd International Conference "Cognitive Robotics"

计算机科学

Maneev, V.V.^1 ; Syryamkin, M.V.^1

National Research Tomsk State University, Tomsk, Russia^1

关键词: Algorithm for solving;    Breadth-first search;    Depth first search;    Dijkstra's algorithms;    Dynamic environments;    Mobile autonomous robotics;    Optimization method;    Path-finding algorithms;   

Others  :  https://iopscience.iop.org/article/10.1088/1757-899X/516/1/012054/pdf
DOI  :  10.1088/1757-899X/516/1/012054

学科分类：计算机科学（综合）

来源: IOP

【 摘 要 】

The purposes of this article are to analyze the pathfinding algorithms used to search and calculate the trajectory of movement of mobile autonomous robotic devices and to search for optimization methods in order to reduce the load on computing and memory units of the mobile devices. This paper analyzes the basic pathfinding algorithms including breadth-first search, depth-first search, Dijkstra's algorithm, greedy best-first search, and the A∗algorithm, considers principles of their work, and proposes optimization methods. This work results in a new approach for using the A∗ algorithm for solving problems associated with pathfinding in real dynamic environments. The proposed approach speeds up the process of path calculation and the choice of the movement direction and reduces the requirements for computing power of autonomous mobile devices.