Investigation and implementation of an algorithm for computing optimal search paths
Loading...
Authors
Caldwell, James F., Jr.
Subjects
Optimal Search Paths
Frank Wolfe Method
Branch-and-Bound
Search
Optimal Search
Frank Wolfe Method
Branch-and-Bound
Search
Optimal Search
Advisors
Eagle, James N.
Date of Issue
1987-09
Date
September 1987
Publisher
Language
en_US
Abstract
A moving target is detected at long range with an initial position given by a probability distribution on a grid of N cells. Also located on the grid is a searcher, constrained by speed, who must find an optimal search path in order to minimize the probability of target survival by time T. A branch-and- bound algorithm designed by Professors Eagle and Yee of the Naval Postgraduate School in Monterey, California, is successfully implemented in order to solve this problem. Within the algorithm, the problem is set up as a nonlinear optimization of a convex objective function subject to the flow constraints of an acyclic N x T network. Lower bounds are obtained via the Frank-Wolfe method of solution specialized for acyclic networks. This technique relies on linearization of the objective function to yield a shortest path problem that is solvable by dynamic programming. For each iteration, the lower bound can be found by use of a Taylor first order approximation. Implementation of this algorithm is accomplished by the use of a Fortran program which is run for several test cases. The characteristics of the solution procedure as well as program results are discussed in detail. Finally, some real world applications along with several questions requiring further research are proposed.
Type
Thesis
Description
Series/Report No
Department
Department of Operations Research
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
87 p.: ill.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
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.