Strategic allocation of multiple defensive resources in environments in presence of an alarm system

In recent years, the application of Algorithmic Game Theory to problems concerning the physical security of environments is gaining more and more attention in the Artificial Intelligence scientific community. The security scenario is modeled as an adversarial game between 2 players, called Security Games. Here, a Defender places his resources to protect targets present in the environment, and an Attacker attempts to steal or damage the same targets. Moreover, the Attacker can observe the movements and the mixed strategy of the Defender and then best responds to it. In this work, we deal with Security Games in which the Defender is supported by wide range sensors that raise an alarm signal whenever an intruder is detected. He can also rely on multiple mobile resources able to patrol the environment. The drawback of this alarm system is the spatially uncertainty of each sensor, i.e., we know the presence of the attacker but not his exact position. It has been proved that, with an alarm system not affected by false positive or missed detections, the best action of the Defender is to stay still and waits for a signal. We study the problem of computing the best placement of resources in order to maximize the target's protection. We devise three heuristics, to solve this problem and make the algorithm scalable to real-world applications. We then analyze situations in which the Defender wants to assure perfect protection of the environment, being able to save every possible target under attack. First, we prove that, in this case, the complexity of computing the minimum number of resources the Defender needs is NP-hard, and then we propose two formulations to find the solution. The former handles alarm systems consisting of one signal, while the latter deals with multiple signals. We experimentally evaluate the results and the scalability of each proposed algorithm in several real-world inspired instances.

Negli ultimi anni, le nuove dinamiche politico-sociali hanno fatto si che l'applicazione della Teoria dei Giochi Algoritmica a problemi riguardanti la sicurezza fisica di ambienti assumesse sempre più importanza all'interno della comunità scientifica di Intelligenza Artificiale. Lo scenario di sicurezza è modellato come un gioco tra due avversari, chiamato Security Games, in cui un Difensore posiziona strategicamente le sue risorse con l'obiettivo di proteggere target dell'ambiente e un Attaccante prova a rubare o a danneggiare gli stessi. Inoltre, l'Attaccante è in grado di osservare i movimenti e le strategie miste del Difensore prima di effettuare la sua mossa. In questo lavoro, il Difensore può contare su più risorse in grado di pattugliare l'ambiente ed è supportato da sensori ad ampio raggio in grado di segnalare la presenza del intruso. Ciascun sensore può, però, essere affetto da una incertezza di tipo spaziale, i.e., il segnale non da informazioni dettagliate riguardo la posizione dell'Attaccante. Sappiamo che, con un sistema di allarme non affetto da falsi positivi o falsi negativi, la strategia migliore che il Difensore può seguire è quella di rimanere fermo e aspettare un segnale. Sapendo ciò, studiamo il problema di posizionare nel miglior modo le risorse così da massimizzare la protezione dei target. Proponiamo inoltre tre euristiche per risolvere questo problema e rendere l'algoritmo applicabile a situazioni reali. Analizziamo poi giochi nel quale il Difensore vuole assicurare una perfetta protezione dell'ambiente, salvando ogni possibile target sotto attacco. Affrontiamo il problema, dapprima dimostrando che è NP-difficile trovare il numero minimo di risorse necessarie ad assicurare una perfetta protezione, poi proponendo due formulazioni per trovare la soluzione. La prima gestisce allarmi composti da un solo segnale mentre la seconda si occupa del caso generale con più segnali. Infine, abbiamo valutato sperimentalmente, in diversi ambienti simil-reali, i risultati e la scalabilità degli algoritmi proposti.