Search and Rescue Games
Games on Trees and Graphs
D.M.L. Ha (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Robbert Fokkink – Mentor (TU Delft - Applied Probability)
J.F. Brethouwer – Mentor (TU Delft - Applied Probability)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
In this thesis report we consider a search and rescue problem in which one or multiple targets/objects are hidden in some playing field, and must be rescued/found by a searcher. The targets are for example: earthquake survivors, lost hikers or prisoners held by an adversary, and are hidden in some section of the play field. Searching any of the sections of the play field has a certain probability of failing; the searcher might get lost, trapped or captured herself. The goal is to find the search that maximises the probability of finding all targets, and to find the hiding spot that minimises it. We define and solve the search and rescue game on a play field for which movement between any two section of the play field is always possible. We also define and solve the game played on a tree for which movement is limited by the tree structure. Due to the complexity of this game, we restrict ourselves to one target. Finally, we extend the game by replacing the play field with specific types of graphs that are not trees. For some of these graphs, we have found (partial) solutions.