A two-stage algorithm for generating a set of Pareto-optimal trajectories of an object

Abstract

A two-stage algorithm is proposed for generating trajectories and parameters of the object's motion based on searching for a set of Pareto-optimal paths from the initial vertex to the terminal vertex. The features of graph construction in the first and second stages of the algorithm are described. At the first stage, the set of vertices of the graph uniformly cover the area of the object's motion, and the edges connect only the nearest neighboring vertices. At the second stage, the set of vertices of the graph includes only those vertices through which the paths constructed in the first stage pass. For this set of vertices, a complete graph is constructed: the edges connect each vertex to all the others. An algorithm for constructing a set of Pareto-optimal characteristics of graph paths is described. The two-stage approach allows to significantly reduce the calculation time in comparison with the application of the described algorithm for a complete graph in one stage. Two variants of the algorithm are considered. The first algorithm requires a longer calculation time, but allows to obtain more trajectories that are diverse. In particular, it is possible to obtain trajectories of different classes, for example, avoiding obstacles from different sides, etc. For the case when time for calculations is not enough, an abridged algorithm is proposed. The results of computational experiments are presented.