COMBINATORIAL MOTION PLANNING FOR A DUBINS VEHICLE WITH PRECEDENCE CONSTRAINTS
Conference Paper
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
This paper considers a combinatorial motion planning problem of finding a shortest tour for a Dubins vehicle that must visit a given set of targets and return to its initial depot while satisfying the motion constraints of the vehicle and the precedence constraints. Precedence constraints restrict the sequence in which a Dubins vehicle visits the given set of targets by imposing a partial ordering on the sequence in which the targets must be visited. This problem arises in applications involving fixed wing, Unmanned Aerial Vehicles (UAVs) where the vehicles have fuel and motion constraints. A fixed wing UAV may be modeled as a Dubins vehicle that can travel at a constant speed and has an upper bound on its turning rate. This is a difficult problem because it couples the combinatorial problem of optimally visiting a set of targets with the path planning problem of finding the shortest path that satisfies the motion constraints given the sequence in which the targets must be visited. In this paper, the sequence in which the targets must be visited is obtained by solving the combinatorial problem using a split dual algorithm. Using this sequence, the path planning problem is solved using Dynamic Programming. Computational results are given to corroborate the performance of the algorithms.
name of conference
ASME 2009 Dynamic Systems and Control Conference, Volume 2
