COMBINATORIAL MOTION PLANNING FOR A DUBINS VEHICLE WITH PRECEDENCE CONSTRAINTS Conference Paper uri icon

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

published proceedings

  • PROCEEDINGS OF THE ASME DYNAMIC SYSTEMS AND CONTROL CONFERENCE 2009, PTS A AND B

author list (cited authors)

  • Oberlin, P., Rathinam, S., & Darbha, S.

citation count

  • 2

complete list of authors

  • Oberlin, Paul||Rathinam, Sivakumar||Darbha, Swaroop

publication date

  • January 2010