Sampling-Based Roadmap Methods for a Visual Reconnaissance UAV* Conference Paper uri icon


  • This article considers a path planning problem for a single fixed-wing aircraft performing a reconnaissance mission using EO (Electro-Optical) camera(s). A mathematical formulation of the general aircraft visual reconnaissance problem for static ground targets in terrain is given and it is shown, under simplifying assumptions, that it can be reduced to what we call the PVDTSP (Polygon-Visiting Dubins Traveling Salesman Problem), a variation of the famous TSP (Traveling Salesman Problem). Two algorithms are developed to solve the PVDTSP. They fall into the class of algorithms known as sampling-based roadmap methods because they operate by sampling a finite set of points from a continuous state space in order to reduce a continuous motion planning problem to planning on a finite discrete graph. The first method is resolution complete, which means it provably converges to a nonisolated global optimum as the number of samples grows. The second method achieves slightly shorter computation times by using approximate dynamic programming, but consequently is only guaranteed to converge to a nonisolated global optimum modulo target order. Numerical experiments indicate that, for up to about 20 targets, both methods deliver good solutions suitably quickly for online purposes. Additionally, both algorithms allow trade-off of computation time for solution quality and are shown extensible to handle wind, airspace constraints, any vehicle dynamics, and open-path (vs. closed-tour) problems. Copyright 2010 by the American Institute of Aeronautics and Astronautics, Inc. All rights reserved.

name of conference

  • AIAA Guidance, Navigation, and Control Conference

published proceedings

  • AIAA Guidance, Navigation, and Control Conference

author list (cited authors)

  • Obermeyer, K., Oberlin, P., & Darbha, S.

citation count

  • 32

complete list of authors

  • Obermeyer, Karl||Oberlin, Paul||Darbha, Swaroop

publication date

  • August 2010