Path Optimization for the Resource-Constrained Searcher
MetadataShow full item record
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.
Naval Research Logistics
RightsThis 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.
Showing items related by title, author, creator and subject.
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 ...
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 ...
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 ...