Global Path Planning Algorithm in a Two-Dimensional Environment with Polygonal Obstacles on the Class of Piecewise Polygonal Trajectories

The paper discusses a motion planner with increased performance in relation to a number of common planning algorithms for maps with obstacles of complex shapes. An algorithm is substantiated for searching for the optimal path in terms of length in the class of piecewise broken curves on a special graph that combines some characteristic points of each obstacle. An estimate of the improved upper bound on the complexity of the algorithm as a function of the number of obstacles is given. Theoretical calculations are confirmed by the results of numerical simulation.