Realistic models for adversarial patrolling and optimization algorithms

In the last decade Game Theory played a fundamental role in the Artificial Intelligence and Operations Research communities. In the present work we employ some of the tools provided by this science in order to solve a real-world problem belonging to the class of the so called Patrolling Games. With this term we denote all those games that employ one or more resources, human or robotic, to guard some valuable targets dislocated within an area. In this kind of games the main characters are an attacker, who tries to break into the area and to reach one of the targets, and a defender, whose purpose is preventing the criminal having success by coordinating the resources at his disposal. The problem we deal with in this work is supposed to be solved using robotic patrollers to guard a huge area for a certain time lapse, while we assume that the attacker can look at the movements of the robots before deciding how to act. Therefore, we firstly formulate the problem as a Leader-Follower game and, starting from the representation of the environment through a graph, we try to compute the best strategy for the defender when there’s an attacker able to look at his moves. Afterwards, we introduce some approximations: first of all making the robots move in squads, then building the strategies for the defender as sequences of pre-computed cycles on the graph. Before applying the algorithms produced this way to the real case that we want to solve, they are tested on some trial instances in order to ascertain their scalabiliy. After this phase, the same algorithms are modified, to best adapt them to the real environment, and then they are directly tested on it, for a limited amount of time, in order to choose the one to employ in the final resolution of the problem on the whole time frame. Finally, we use the chosen algorithm to solve the problem and we make some final considerations.

Nell'ultimo decennio la Teoria dei Giochi ha assunto un ruolo fondamentale nella comunità scientifica di Intelligenza Artificiale e in quella di Ricerca Operativa. In questo lavoro sfrutteremo alcuni risultati di tale scienza per risolvere un problema reale appartenente alla categoria dei Patrolling Games. Con questo termine sono indicati quei giochi che prevedono l'impiego di una o più risorse, umane o robotiche, per sorvegliare degli obiettivi sensibili dislocati all'interno di un'area. In questo tipo tipo di giochi i protagonisti sono un attaccante, che cerca di far breccia all'interno dell’area e di raggiungere uno degli obiettivi, e un difensore, il cui compito è quello di impedire che ciò accada coordinando le risorse a sua disposizione. Il problema che affrontiamo in questo lavoro prevede l'utilizzo di pattugliatori robotici per sorvegliare un'area di grandi dimensioni per un certo lasso di tempo, mentre assumiamo che l'attaccante possa osservare i movimenti dei robot prima di decidere come agire. Pertanto, inizialmente formuliamo il problema come un gioco Leader-Follower in cui cerchiamo di costruire, a partire dalla rappresentazione mediante un grafo della zona, la miglior strategia per il difensore, in presenza di un attaccante in grado di osservarne le mosse. Dopodiché, introduciamo delle approssimazioni: prima facendo muovere i robot in squadre e, successivamente, costruendo le strategie per il difensore come sequenze di cicli sul grafo calcolati a priori. Gli algoritmi così generati, prima di essere applicati al caso reale che vogliamo risolvere, sono valutati su dei grafi di prova, per accertarne principalmente la scalabilità. Terminata questa fase, gli stessi algoritmi sono prima modificati, per adattarli al meglio alle caratteristiche dell'ambiente reale, e poi applicati direttamente ad esso, per un tempo limitato, al fine di selezionare quello con cui andare ad effettuare la risoluzione definitiva su tutto l'arco di tempo necessario. Per concludere, l'algoritmo scelto viene utilizzato per risolvere il problema e vengono fatte alcune considerazioni finali.