Search games and rendezvous problems have received growing attention in computer science within the past few years. Rendezvous problems emerge naturally, for instance, to optimize performance and convergence of mobile robots. This gives a new algorithmic point of view to the theory. Furthermore, modern topics such as the spreading of gossip or disease in social networks have lead to new challenging problems in search and rendezvous.
Search Theory: A Game Theoretic Perspective introduces the first integrated approach to Search and Rendezvous from the perspectives of biologists, computer scientists and mathematicians. This contributed volume covers a wide range of topics including rendezvous problems and solutions, rendezvous on graphs, search games on biology, mobility in governed social networks, search and security, and more. Most chapters also include case studies or a survey, in addition to a chapter on the future direction of Search and Rendezvous research.
This book targets researchers and practitioners working in computer science, mathematics and biology as a reference book. Advanced level students focused on these fields will also find this book valuable as a secondary text book or reference.
Author(s): Shmuel Gal (auth.), Steve Alpern, Robbert Fokkink, Leszek Gąsieniec, Roy Lindelauf, V.S. Subrahmanian (eds.)
Edition: 1
Publisher: Springer-Verlag New York
Year: 2013
Language: English
Pages: 303
Tags: Math Applications in Computer Science; Artificial Intelligence (incl. Robotics); Game Theory, Economics, Social and Behav. Sciences; Mathematical and Computational Biology; Mathematics in the Humanities and Social Sciences
Front Matter....Pages i-viii
Front Matter....Pages 1-1
Search Games: A Review....Pages 3-15
Search Games for an Immobile Hider....Pages 17-27
Tools to Manage Search Games on Lattices....Pages 29-58
Network Coloring and Colored Coin Games....Pages 59-73
Open Problems on Search Games....Pages 75-81
Front Matter....Pages 83-83
Some Cinderella Ruckle Type Games....Pages 85-103
The Cardinality of the Sets Involved in Lattice Games....Pages 105-118
Effective Search for a Naval Mine with Application to Distributed Failure Detection....Pages 119-133
The Value of the Two Cable Ambush Game....Pages 135-154
How to Poison Your Mother-in-Law, and Other Caching Problems....Pages 155-163
Front Matter....Pages 165-165
Rendezvous Problem....Pages 167-174
Deterministic Symmetric Rendezvous in Arbitrary Graphs: Overcoming Anonymity, Failures and Uncertainty....Pages 175-195
Gathering Asynchronous and Oblivious Robots on Basic Graph Topologies Under the Look-Compute-Move Model....Pages 197-222
Ten Open Problems in Rendezvous Search....Pages 223-230
Front Matter....Pages 231-231
Interactions Between Searching Predators and Hidden Prey....Pages 233-248
A Discrete Search-Ambush Game with a Silent Predator....Pages 249-266
A Model of Partnership Formation with Friction and Multiple Criteria....Pages 267-293
Applications of Search in Biology: Some Open Problems....Pages 295-303
