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.