Tecniche algoritmiche e strumenti software per lo studio di patrolling security games

Lo studio di tecniche per il pattugliamento di un ambiente mediante l’utilizzo di robot mobili autonomi è un’area dell’Intelligenza Artificiale oggetto di crescente interesse nell’ambito della ricerca scientifica per le molteplici applicazioni reali. Lo scopo della presente tesi è quello di formulare in primis dei modelli e dei metodi matematici che siano computazionalmente trattabili e allo stesso tempo abbastanza evoluti da descrivere situazioni reali, in secundis implementare una soluzione software completa che permetta, oltre che la creazione e risoluzione dei giochi, anche la valutazione, comparazione e condivisione dei risultati strategici ottenuti. L’inapplicabilità computazionale dei metodi proposti in letteratura ci ha spinto a formulare delle tecniche che permettessero di semplificare il problema. Il primo approccio considerato è quello di ridurre la grandezza del gioco attraverso la rimozione delle strategie dominate di entrambi i giocatori. Malgrado tale metodo diminuisca drasticamente la grandezza del problema, la risoluzione di situazioni realistiche resta ancora complessa. Una tecnica efficace per la riduzione di giochi di grandi dimensioni è la strategia astratta. L’idea di base dietro il concetto di astrazione è quella di raggruppare insieme più azioni in una singola macro azione, permettendoci di ridurre la dimensione del gioco. La tipologia più interessante di astrazione è quella senza perdita di informazione, in quanto ci permette di trovare soluzioni ottimali; tuttavia, per problemi molto grandi, tali astrazioni continuano a produrre giochi troppo complessi per poter essere facilmente risolti; per tutti questi casi, rilassiamo i vincoli necessari a preservare l’informazione, formulando astrazioni del gioco definite come astrazioni con perdita di informazione, la cui soluzione tuttavia non è garantito essere ottimale. La possibilità di risolvere istanze del problema di pattugliamento sempre più complesse e comparare le prestazioni delle strategie stesse al variare di parametri ha reso necessario lo sviluppo di uno strumento software che facilitasse, oltre che la creazione stessa dei patrolling setting, anche l’interpretazione delle strategie prodotte, altrimenti di difficile comprensione.