Construction of a three-dimensional UAV movement planner when the latter moves in conditions of difficult terrain

Abstract

Abstract. The construction of high-speed algorithms for planning the routes of robotic platforms in a three-dimensional mapped environment is an urgent task. Known methods of planning based on cellular decomposition of the field of motion in a three-dimensional formulation are severely limited in speed.

This article proposes a method for planning the movement of robotic platforms in this environment, combining the use of the well-known Dijkstra algorithm for constructing a two-dimensional projection curve with subsequent projection reconstruction and multi-stage correction of the target spatial piecewise polyline curve. The restoration of the original spatial curve by its two-dimensional projection onto the horizontal plane is performed on the basis of a given discrete elevation map of the motion area, and the specified adjustment is made taking into account the requirements, firstly, the minimality of the total length of the final piecewise polyline, and, secondly, taking into account the specified known kinematic limitations of the apparatus.

The algorithm for the synthesis of a spatial curve is detailed for the common case when obstacles are represented in the form of rectangular cylinders with polygonal generators.

The effectiveness of the developed global scheduler algorithm is confirmed by the results of numerical modeling.