Patrolling security games : allarmi spazialmente e funzionalmente imperfetti

Private Ryan is on patrol in a military base, located in enemy territory. He has been told that an enemy squad is about to attack the camp, with the objective to destroy some important resources, like the ammunition depot, the headquarters or the communication tower. How should the soldier choose his patrolling path to best defend these sensitive targets? This problem is related to many field of interest: artificial intelligence, multiagent system and, overall, game theory. In particular, this problem can be modeled with a Patrolling Security Game, where a defender and an attacker must, respectively, defend or attack some targets. Every target is a node on a graph, and has a value and a deadline, i.e. the time needed to be destroyed, and is linked to the other targets by some arcs, whose weights depend on the distance or the time needed to be reached. In our thesis we want to extend this model introducing some sensors that will send an alarm signal to the defender if a target is under attack. To make them more realistic, the sensors are affected by spatial and functional uncertainty. To be more precise, they cover more targets at once, so a single signal cannot be reconducted to a single target, but to the whole set, and they could not send an alarm signal, even if one of the targets is under attack, in the % of the cases. We will then show that the problem to find an optimal patrolling route is NP-HARD, so we will analyze the scalability of the exact algorithm, and we will propose some heuristics to solve the problem in polynomial time, analyzing their losses with respect to the exact one.

Il soldato Ryan è di pattuglia in una base militare, posizionata in territorio nemico. L’intelligence ha scoperto che una squadra di guastatori è stata incaricata di infiltrarsi nella base e di distruggere dei possibili edifici chiave, quali il deposito di munizioni, il quartier generale, e la sala radio. Quale percorso dovrebbe scegliere il soldato, per proteggere al meglio gli obiettivi sensibili? Questo problema rientra sotto molti campi. Intelligenza artificiale, sistemi multiagente ma, soprattutto, teoria dei giochi. In particolare, si può modellare il problema come un Patrolling Security Game, ovvero un particolare gioco nel quale il difensore e l’attaccante devono, rispettivamente, difendere o attaccare determinati obiettivi. Ogni obiettivo è rappresentato come un nodo su un grafo, con un valore e un tempo necessario per l’attacco, ed è collegato agli altri obiettivi tramite degli archi pesati in base alla distanza o al tempo necessario per raggiungerli. Lo scopo della tesi è estendere suddetta categoria di giochi introducendo dei sensori di rilevamento, che mandano un segnale di allarme al difensore in caso di attacco. Per rendere più realistico il modello, i sensori sono affetti da un’incertezza spaziale (ovvero coprono una grossa area, e dunque l’allarme non è riconducibile a un singolo target, bensì ad un insieme di target) e un’incertezza funzionale (è presente una percentuale di falso negativo, ovvero l’allarme potrebbe non scattare durante un attacco nel % dei casi). Come verrà poi mostrato, il problema di trovare la migliore strategia di pattugliamento è NP-HARD, e verrà dunque analizzata la scalabilità dell’algoritmo di risoluzione esatta. Verranno inoltre proposte diverse euristiche per risolvere in tempo polinomiale il problema, verificandone la perdita di valore rispetto all’algoritmo esatto e il risparmio di effort computazionale.