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.
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.
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 ...
Tan, Ko-Cheng (Monterey, California. Naval Postgraduate School, 1996-06);Motion planning and control of a Nomad 200 mobile robot are studied in this thesis. The objective is to develop a motion planning and control algorithm that is able to move the robot from an initial configuration (position ...