Sorvegliare e proteggere obiettivi sensibili utilizzando un sistema di allarme spazialmente imperfetto

In recent years, the use of Game Theory techniques has gained more and more importance in the Artificial Intelligence scientific community. In the present work, the tools offered by this science are used to formulate and solve a new kind of game, which can be put in the class of the so called Security Games. With these terms we denote all those games that are used to model environments with valuable targets to be protected. In these situations we have two main characters: an attacker, that tries to violate the security policies to damage a target, and a defender, whose aim is preventing the criminal having success. In our case, the defender is supported by a mobile robotic guard and an alarm system in order to surveil and protect the different areas of the environment. We also assume that the attacker can look at the behavior of the guard before acting. So, assuming that the environment is divided in areas, first we want to understand which is the best response of the defender when it receives a signal generated by the system. This situation is formulated using a zero-sum game. Then we want to know which is the best behavior for the defender while no attack is taking place. In this case, we adopt a Leader-Follower game. We support the obtained results with some experimental evaluations, that show the scalability of the proposed algorithm and confirming the theoretical complexity. To assess the quality of the solution, we analyzed our algorithm and compared it w.r.t. a simpler but more efficient heuristic algorithm. We also analyze what happens if the alarm system is affected by a given percentage of false negatives, i.e. the system could not generate any signal even though an attack is occurring, showing that the best response is not always the one that came first to your mind.

Negli ultimi anni l'utilizzo della Teoria dei Giochi ha assunto sempre più importanza nella comunità scientifica di Intelligenza Artificiale. Nel presente lavoro, gli strumenti che tale scienza mette a disposizione sono stati utilizzati per formulare e risolvere un nuovo tipo di gioco, facente parte della categoria dei Security Games. Con tale appellativo intendiamo tutti quei giochi che vengono utilizzati per modellare un ambiente nel quale sono dislocati obiettivi sensibili che devono essere protetti. In questo scenario abbiamo due protagonisti: un attaccante, che cerca di violare le misure di sicurezza al fine di danneggiare uno degli obiettivi, e un difensore, il cui compito è impedire che il malvivente riesca nella sua impresa. Nel nostro caso, abbiamo una guardia robotica mobile e un sistema di allarme a supporto del difensore per sorvegliare e proteggere le aree dell'ambiente mentre assumiamo che l'attaccante possa osservare il comportamento della guardia prima di attaccare. Dunque, supponendo di avere l'ambiente suddiviso in aree, ci proponiamo dapprima di capire come il difensore debba reagire nel caso in cui riceva un segnale di allarme. Tale situazione viene formulata con un gioco a somma zero. Successivamente, vogliamo capire quale sia il miglior comportamento per il difensore quando non è in corso alcun attacco. In questo caso invece facciamo riferimento ad un gioco Leader-Follower. Supportiamo i risultati ottenuti con valutazioni sperimentali che mostrano la scalabilità dell'algoritmo proposto e confermano la complessità teorica trovata durante lo studio. Per verificare la qualità della soluzione trovata, abbiamo anche effettuato un confronto con un'euristica più semplice ma al contempo più efficiente. Analizziamo inoltre cosa accade se si introduce una determinata percentuale di falsi negativi, i.e. il sistema non genera alcun segnale di allarme anche se è in corso un attacco, mostrando che la miglior risposta non è necessariamente quella che può essere suggerita dall'intuito.