Combined Optimal Control and Combinatorial Optimization for Searching and Tracking Using an Unmanned Aerial Vehicle

Abstract

Combined searching and tracking of objects using Unmanned Aerial Vehicles (UAVs) is an important task with many applications. One way to approach this task is to formulate path-planning as a continuous optimal control problem. However, such formulations will, in general, be complex and difficult to solve with global optimality. Therefore, we propose a two-layer framework, in which the first layer uses a Traveling-Salesman-type formulation implemented using combinatorial optimization to find a near-globally-optimal path. This path is refined in the second layer using a continuous optimal control formulation that takes UAV dynamics and constraints into consideration. Searching and tracking problems usually trade-off, often in a manual or ad-hoc manner, between searching unexplored areas and keeping track of already known objects. Instead, we derive a result that enables prioritization between searching and tracking based on the probability of finding a new object weighted against the probability of losing tracked objects. Based on this result, we construct a new algorithm for searching and tracking. This algorithm is validated in simulation, where it is compared to multiple base cases as well as a case utilizing perfect knowledge of the positions of the objects. The simulations demonstrate that the algorithm performs significantly better than the base cases, with an improvement of approximately 5-15%, while it is approximately 20-25% worse than the perfect case.