Investigation and implementation of an algorithm for computing optimal search paths
Caldwell, James F., Jr.
Eagle, James N.
Rosenthal, Richard E.
MetadataShow full item record
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.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Rhoden, Christopher A. (Monterey, California. Naval Postgraduate School, 1994-06);The Simplex algorithm, developed by George B. Dantzig in 1947 represents a quantum leap in the ability of applied scientists to solve complicated linear optimization problems. Subsequently, its utility in solving finite ...
Huang, Jo-Wen (Monterey, California: Naval Postgraduate School, 2017-06);With the development and advancement in the technology of control and multi-robot systems, robot agents are likely to take over mine countermeasure (MCM) missions one day. The path planning coverage algorithm is an essential ...
Zyda, Michael J. (Monterey, California. Naval Postgraduate School, 1984-09); NPS-52-84-013We present in this study the architectural specification and feasibility determination for a real-time contour display generator. We begin by examining a recently reported, highly decomposable algorithm for contour surface ...