Sampling-Based Path Planning for a Visual Reconnaissance Unmanned Air Vehicle

This paper considers a path planning problem for a single fixed-wing aircraft performing a reconnaissance mission using one or more electro-optical cameras. The aircraft visual reconnaissance problem for static ground targets in terrain is formulated as a polygon-visiting Dubins traveling salesman problem, a variation of the famous traveling salesman problem. Two algorithms for solving the polygon-visiting Dubins traveling salesman problem are developed. They fall into the class of algorithms known as sampling-based road map 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 called a roadmap. Under certain technical assumptions, the algorithms are resolution complete, which means the solution returned provably converges to a global optimum as the number of samples grows. The first algorithm is resolution complete under slightly milder assumptions, but the second algorithm achieves faster computation times by a novel roadmap construction. Numerical experiments indicate that, for up to about 20 targets, both algorithms deliver very good solutions suitably quickly for online purposes. Additionally, the algorithms allow tradeoff of computation time for solution quality and are shown to be highly extensible.