Turn Constrained Path Planning Problems
Victor M. Roman · Digital Scholarship - UNLV (University of Nevada Reno) · 2020
We consider the problem of constructing multiple disjoint paths connecting a source point s to a target point t in a geometric graph. We require that the paths do not have any sharp turn angles. We present a review of turn constrained path planning algorithms and also algorithms for constructing disjoint paths. We then combine these techniques and present an O(nlogn) time algorithm for constructing a pair of edge disjoint turn constrained paths connecting two nodes in a planar geometric graph. We also consider the development of a turn constrained shortest path map in the presence of polygonal obstacles. Prototype implementations of the proposed algorithms are also presented. These problems have application for trajectory planning for unmanned aerial vehicles (UAV).