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 special- ized 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 net- work 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.
Description
Naval Research Logistics
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
Optimal search for the wake of a moving target when searcher motion is constrained
Guthe, Douglas Burden, Jr. (Monterey, California. Naval Postgraduate School, 1983-09);A method for determining the optimal or near-optimal search path for the wake of a moving target when the searcher's motion is constrained is presented. The problem uses a Markov action model in discrete time and space ... -
Efficient algorithms for budget-constrained Markov decision processes
Caramanis, Constantine; Dimitrov, Nedialko B. Dimitrov; Morton, David P. (2014);Discounted, discrete-time, discrete state-space, discrete action-space Markov decision rocesses (MDPs) form a classical topic in control, game theory, and learning, and as a result are widely applied, increasingly, in ... -
On the Steady State Performance of Frequency Domain LMS Algorithms
Feuer, Arie; Cristi, Roberto (1993);The use of the fast Fourier transform (FFT) in the implementation of the least mean square (LMS) algorithm in the frequency domain results in several types of algorithms, two of which can be classified as constrained and ...