Search and Rescue Games: Games on Trees and Graphs

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.
Master Thesis
Applied Mathematics