Search and evasion games
Loading...
Authors
Schroeder, Roger Glenn
Subjects
Advisors
Date of Issue
1966-06
Date
1966-06
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
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.
Type
Technical Report
Description
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.
Series/Report No
Department
Identifiers
NPS Report Number
Naval Postgraduate School (U.S.) Technical report/Research paper ; no. 68.
Sponsors
NA
Funder
Format
32 p. : ill. ; 29 cm.
Citation
Distribution Statement
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.