Design and implementation of an optimal algorithm for solving visibility-based pursuit evasion games

A pursuit-evasion game is a non-cooperative game in which a pursuer tries to detect or capture an adversarial evader. We study a pursuit-evasion game which takes place in a known polygonal environment. The goal of the pursuer is to capture the evader by moving onto its location. The players can know each others’ locations only if they can “see” each other – i.e., if the line segment connecting their locations lies entirely inside the polygonal environment. The complexity of representing the information available to the players at a given time makes solving pursuit-evasion games with visibility limitations difficult. We represent the state of the game using an efficient visibility-based decomposition of the environment paired with a more classical grid-based decomposition. The optimal players’ strategies are computed using Minimax search improved with some speedup techniques that preserve optimality. We show that our approach is complete for a rash evader, which hides from the pursuer and does not move from its hiding location when the pursuer is not visible. Simulations in realistic indoor environments show the viability of using the proposed approach, compared to a Monte Carlo Tree Search.

Il pursuit-evasion è un gioco non cooperativo in cui un pursuer cerca di individuare e catturare un evader. La versione del gioco di pursuit-evasion preso in considerazione in questa tesi si svolge in un ambiente poligonale noto. L’obiettivo del pursuer è di catturare l’evader muovendosi nel suo stesso punto. I giocatori possono conoscere la loro reciproca posizione solo se sono in grado di “vedersi” – cioè, se il segmento che unisce la loro ubicazione corrente è contenuto interamente all’interno dell’ambiente poligonale. La complessità necessaria a rappresentare l’informazione disponibile ai giocatori in un dato istante di tempo rende di difficile risoluzione i giochi di pursuit-evasion con visibilità limitata. In questa tesi, lo stato del gioco è rappresentato efficientemente tramite una decomposizione basata sulla visibilità, accoppiata con una più classica basata su griglia. Le strategie ottime dei giocatori sono calcolate usando una ricerca Minimax con l’aggiunta di diversi metodi che ne aumentano la velocità senza sacrificare l’ottimalità. Viene mostrato che l’approccio proposto è completo per un rash evader, il quale usa una strategia che consiste nel nascondersi dal pursuer e rimanere fermo fintantoché il pursuer non diventi visibile. Sono state eseguite diverse simulazioni in ambienti realistici per valutare la bontà del metodo proposto, includendo un confronto con un approccio basato su Monte Carlo Tree Search.