Decomposition Methods for Moving Target Search
Abstract
Airborne search and rescue missions are of incredible importance to save the lives of missing persons. Such missions must be planned carefully in order to optimize the chances of survival. However, planning must be conducted within a small time frame so as net to waste time. The target of the search is often likely to move, which significantly complicates the problem. The reason for the increased complexity is that the search reward at time k does not only depend on the observation made at time k, but on all observations made up until time k. In other words, the rewards over time are inseparable and, hence, state-of-the-art shortest path planning algorithms become inapplicable. A pilot who is faced with such a complex task in a stressful situation is prone to planning a suboptimal search trajectory. Coordinating a team of cooperating aerial platforms is especially difficult. Automation of search trajectory optimization is therefore the aim of this dissertation. Three novel problems are considered in this thesis: single platform search under kinematical constraints, single platform search under kinematical and resource constraints and strategy optimization for a team of heterogeneous cooperating platforms with shared resources. A mixed integer linear problem (MILP) formulation is proposed as well as a decomposition method for solving each problem. Computational experiments and simulations show that each proposed model and algorithm is applicable and efficient for solving its considered problem. The first problem variation is solved much faster using the proposed generalization of a branch and bound algorithm compared to solving the MILP formulation using a commercial solver. To solve the second problem variation, a Benders decomposition algorithm is developed for more efficient optimization of the proposed MILP formulation. This algorithm significantly reduces the computation times for solving the problem with scarce resources.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 11, 2017
- Accession Number
- AD1057489
Entities
People
- Manon Raap
Organizations
- Helmut Schmidt University