Jeux de policiers et voleurs : modèles et applications
|Advisor:||Laviolette, François; Desharnais, Josée|
|Abstract:||Cops and robbers games have been studied for the last thirty years in computer science and mathematics. As in general pursuit evasion games, pursuers (cops) seek to capture evaders (robbers), however here the players move in turn and are constrained to move on a discrete structure. It is always assumed that players know the exact location of their adversary, in other words the game is played with perfect information. The first definition of a cops and robbers game dates back to Nowakowski and Winkler  and, independantly, Quilliot . This first definition presents a game opposing a single cop against a lone robber, both with constraints on their speed. Extensions were gradually formulated such as increasing the number of cops and the speed of the players. In 2014, Bonato and MacGillivray  presented a general characterization of cops and robbers games in order for them to be globally studied. However, their model does not take into account stochastic events that may occur such as the robbers moving in a random fashion. In this thesis, a novel model that includes stochastic elements is presented. Furthermore, we present in this thesis a concrete application of cops and robbers games in the form of a method of resolution of a problem from search theory. Although cops and robbers games assume perfect information, this hypothesis cannot be maintained in search problems. It appears however that cops and robbers games can be viewed as constraint relaxations of search problems. This point of view is made use of in the conception of an upper bound on the objective function of a search problem that is a applied in a branch and bound method.|
|Document Type:||Mémoire de maîtrise|
|Open Access Date:||24 April 2018|
|Collection:||Thèses et mémoires|
All documents in CorpusUL are protected by Copyright Act of Canada.