Search and evasion games
Schroeder, Roger Glenn
MetadataShow full item record
This research was part of the author's Ph. D. dissertation. The dissertation advisor, Dr. A. Charnes of Northwestern University, offered valuable advice and guidance. In addition, this work was undertaken while the author participated in the U. S. Naval Junior Line Officer Advanced Scientific Educational Program.","We develop some two-person zero-sum game formulations of search and evasion problems. By employing a game theoretic approach, we allow the hider, as well as the searcher, to choose a strategy. This is in contrast to most search models which assume a stationary or passive hider. Both non-sequential. and sequential search games are investigated. Some interesting aspects of the non- sequential game and an example of an antisubmarine search problem are given. The sequential games consist of a sequence of moves. When the players move, they not only determine a payoff but also the probability that the game terminates before the next move. When at most a finite number of moves is allowed, we prove that a solution may be found by solving a recursive sequence of matrix games. When the number of moves is not bounded, the game is characterized by a special type of non-linear program. The solution to this program can be approximated by successive perturbations of a related linear program. Finally, we obtain the result that a pair of strategies minimaxes the expected duration of the game if and only if these strategies also maximin the probability of termination in one step.
This research was part of the author's Ph. D. dissertation. The dissertation advisor, Dr. A. Charnes of Northwestern University, offered valuable advice and guidance. In addition, this work was undertaken while the author participated in the U. S. Naval Junior Line Officer Advanced Scientific Educational Program.
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.
NPS Report NumberNaval Postgraduate School (U.S.) Technical report/Research paper ; no. 68.
Showing items related by title, author, creator and subject.
Vanderplaats, G.N. (1984-10);A new general-purpose optimization program for engineering design is described. ADS-1 (Automated Design Synthesis - Version 1) is a FORTRAN program for solution of nonlinear constrained optimization problems. The program ...
Smith, Douglas R. (Monterey, California. Naval Postgraduate School, 1980-02); NPS-52-80-004This paper investigates the conditions under which a discrete optimization problem can be formulated as a dynamic program. Following the terminology of (Karp and Held 1967), a discrete optimization problem is formalized ...
Cole, Walter Bacon (Monterey, California. Naval Postgraduate School, 1980-09);Two computer programs were developed in advanced BASIC to perform numerical optimization of a user supplied design problem on the Hewlett Packard 9845A desktop computer. An executive program, OPCON, provides the interactive ...