AN ALGORITHM FOR PATH PLANNING IN A TWO-DIMENSIONAL ENVIRONMENT WITH POLYGONAL OBSTACLES ON A CLASS OF PIECEWISE POLYLINE TRAJECTORIES

Abstract

An urgent problem of developing algorithms for automatic path planning is the increase in
computational costs with an increase in the complexity of the operating environment. Graphic
planning methods, in particular the method of visibility diagrams, are not without this drawback.
As the number of obstacles increases, the complexity of a visibility graph increases, and this
growth is very fast. Therefore, techniques for reducing the complexity of the visibility graph become
the most important task. This article proposes a hybrid algorithm based on the method of
visibility diagrams and Bug algorithms. The method of path planning proposed in this article
combines a graph algorithm with Bug algorithms, which allows you to build a special graph with
nodes in the form of characteristic obstacle points. In this case, the Bug algorithm is a step in the
iterative optimization process on the graph, which allows for a finite number of steps to come to
an optimal solution on a class of piecewise polyline curves. The proposed method solves the problem
of global path search. Unlike the classical methods of line-of-sight diagrams, it significantly
reduces the dimension of the graph due to a special selection of a limited number of characteristic
points of the corresponding obstacles. The article develops and theoretically substantiates the
proposed method. The calculated relations of the algorithm are given. The optimality of the obtained
trajectory is justified. The analytical relations are confirmed by the results of numerical
modeling in various environments filled with polygonal obstacles. It is shown that in order to pave
the way for maze-type scenes with one common type of obstacles, the algorithm under consideration
is 10% superior to the optimal Dijkstra algorithm.