Path Optimization for the Resource-Constrained Searcher
Abstract
We formulate and solve a discrete-time path-optimization problem where a single searcher, operating in a discretized 3-dimensional airspace, looks for a moving target in a finite set of cells. The searcher is constrained by maximum limits on the consumption of several resources such as time, fuel, and risk along any path. We develop a specialized branch-and-bound algorithm for this problem that utilizes several network reduction procedures as well as a new bounding technique based on Lagrangian relaxation and network expansion. The resulting algorithm outperforms a state-of-the-art algorithm for solving time-constrained problems and also is the first algorithm to solve multi-constrained problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2008
- Accession Number
- ADA486719
Entities
People
- H. Sato
- J. O. Royset
Organizations
- Naval Postgraduate School