Finding Good Dubins Tours for UAVs Using Particle Swarm Optimization
Richard J. Kenefic · Journal of Aerospace Computing Information and Communication · 2008
Unmanned aerial vehicles (UAVs) perform important surveillance functions on the battlefield. When a set of fixed targets for surveillance is known a priori it is desirable to find a minimum length tour subject to the kinematic constraints of the UAV and the terrain and threat constraints of the environment. The UAV path planning problem can be reduced to the traveling salesman problem (TSP) or the vehicle routing problem (VRP), both of which are known to be NP-hard. The problem of finding an optimal tour subject to kinematic constraints, the Dubins vehicle problem (DVP), is also NP-hard and several heuristics have recently been proposed. In this paper several instances of the DVP are posed and solved with a heuristic and the particle swarm optimization method. The particle swarm optimization (PSO) results are compared to another standard optimization method, and the best configurations found for these instances are reported.