STUDY OF PATH PLANNING METHODS IN TWO-DIMENSIONAL MAPPED ENVIRONMENTS

Boris Gurenko; nizar hamdan; Vichislav Pshikhopov; Mikhail Medvedev; Dimitry Brosalin

Boris Gurenko Joint stock Company «Scientific-Design bureau of Robotics and Control Systems», Taganrog city, Rostov Region, Russia
nizar hamdan Joint stock Company «Scientific-Design bureau of Robotics and Control Systems», Taganrog city, Rostov Region, Russia
Vichislav Pshikhopov Joint stock Company «Scientific-Design bureau of Robotics and Control Systems», Taganrog city, Rostov Region, Russia
Mikhail Medvedev Joint stock Company «Scientific-Design bureau of Robotics and Control Systems», Taganrog city, Rostov Region, Russia
Dimitry Brosalin Joint stock Company «Scientific-Design bureau of Robotics and Control Systems», Taganrog city, Rostov Region, Russia

Keywords: Motion planning, two-dimensional environment, random tree method, optimiza-tion of planning algorithms, comparative analysis.

Abstract

The article studies the problem of motion planning in two-dimensional mapped environments. The review and analysis of known planning algorithms based on Voronoi diagrams, probabilistic road maps, rapidly growing random trees, Dijkstra algorithms, A*, D* and their modifications, artificial potential fields, and intelligent heuristics are carried out. Based on the analysis, it is concluded that classical methods in dynamic environments require significant costs in terms of calculation time and the amount of memory used. The conclusion is made about the relevance of the development of algorithms that increase the efficiency of known planning methods. In this regard, this article is devoted to the development of a modified algorithm for rapidly growing random trees and the study of its effectiveness in comparison with known methods. The article presents a modified algorithm for rapidly growing random trees, characterized in that when checking for a path to a new potential node of the tree, the path to some area near the specified node is checked. This reduces the number of nodes in the tree under construction. The developed algorithm is first compared with the traditional algorithm of fast-growing random trees. The comparison criteria are the trajectory calculation time, the amount of memory required, the path length, and the percentage of situations in which the trajectory to the target point was successfully found. Next, the developed algorithm is compared with the planning algorithms of other classes. The study uses representative samples of numerical experiments and various environments that differ in the density of obstacles and the presence of mazes. A study of planning algorithms using the results of experiments on a ground-based wheeled robot is also being conducted. Based on the results of numerical and real experiments, conclusions are drawn about the advantages and disadvantages of the developed algorithm of motion planning and the feasibility of its application in various environments.