Two-dimensional path finding subject to geometric constraints

Abstract

The trajectory planning on a plane is considered as the problem of finding a path in a graph of a special form. Algorithms that are able to solve this problem in the case of geometric constraints, more precisely, under the assumptions that the trajectory is composed of a sequence of straight segments such that the angle between the adjacent segments does not exceed a given threshold, are analyzed. This statement is important for the development of effective navigation methods for unmanned vehicles. A novel algorithm for solving this problem is proposed, and the results of theoretical and experimental studies are presented. The experimental results confirm that the proposed algorithm can be used in practice for planning the trajectory of low-flying unmanned multirotor aerial vehicles in an urban area. They also show that the proposed algorithm significantly exceeds other available algorithms in terms of the number of successfully accomplished tasks.