STUDY OF PATH PLANNING METHODS IN TWO-DIMENSIONAL MAPPED ENVIRONMENTS

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 of 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 is made by 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.