The Theory of Search Games and Rendezvous

Steve Alpern, Shmuel Gal (auth.)0-306-48212-6, 0-7923-7468-1

Search Theory is one of the original disciplines within the field of Operations Research. It deals with the problem faced by a Searcher who wishes to minimize the time required to find a hidden object, or “target. ” The Searcher chooses a path in the “search space” and finds the target when he is sufficiently close to it. Traditionally, the target is assumed to have no motives of its own regarding when it is found; it is simply stationary and hidden according to a known distribution (e. g. , oil), or its motion is determined stochastically by known rules (e. g. , a fox in a forest). The problems dealt with in this book assume, on the contrary, that the “target” is an independent player of equal status to the Searcher, who cares about when he is found. We consider two possible motives of the target, and divide the book accordingly. Book I considers the zero-sum game that results when the target (here called the Hider) does not want to be found. Such problems have been called Search Games (with the “ze- sum” qualifier understood). Book II considers the opposite motive of the target, namely, that he wants to be found. In this case the Searcher and the Hider can be thought of as a team of agents (simply called Player I and Player II) with identical aims, and the coordination problem they jointly face is called the Rendezvous Search Problem.

---

Table of contents :
Front Matter….Pages i-xv
Front Matter….Pages 1-1
Introduction to Search Games….Pages 3-6
Front Matter….Pages 7-7
General Framework….Pages 9-12
Search for an Immobile Hider….Pages 13-43
Search for a Mobile Hider….Pages 45-77
Miscellaneous Search Games….Pages 79-97
Front Matter….Pages 99-99
General Framework….Pages 101-105
On Minimax Properties of Geometric Trajectories….Pages 107-122
Search on the Infinite Line….Pages 123-144
Star and Plan Search….Pages 145-162
Front Matter….Pages 163-163
Introduction to Rendezvous Search….Pages 165-172
Elementary Results and Examples….Pages 173-178
Front Matter….Pages 179-179
Rendezvous Values of a Compact Symmetric Region….Pages 181-189
Rendezvous on Labeled Networks….Pages 191-205
Asymmetric Rendezvous on an Unlabeled Circle….Pages 207-221
Rendezvous on a Graph….Pages 223-234
Front Matter….Pages 235-235
Asymmetric Rendezvous on the Line (ARPL)….Pages 237-249
Other Rendezvous Problems on the Line….Pages 251-275
Rendezvous in Higher Dimensions….Pages 277-290
Back Matter….Pages 291-319