| KEYWORD |
Teoria dei giochi ed intelligenza artificiale per problemi di target search
Tesi all'estero
Parole chiave ALGORITMI DI OTTIMIZZAZIONE, DRONI, GRAFI, INTELLIGENZA ARTIFICIALE
Riferimenti FABIO FAGNANI
Riferimenti esterni SARA BERNARDINI (ROYAL HOLLOWAY, LONDON)
Gruppi di ricerca Analisi e controllo di sistemi dinamici
Descrizione Il search-and-tracking è il problema nel quale un agente in fuga (target) si muove in un ambiente per raggiungere la sua destinazione, mentre un altro agente, l’osservatore, cerca di trovarlo e inseguirlo fino alla sua destinazione. Si pensi, per esempio, al caso di un drone di sorveglianza che vola sopra un’ambia regione geografica e che cerca di scoprire un criminale che in macchina sta cercando di raggiungere il suo nascondiglio il prima possibile.
Nel momento in cui l’osservatore perde contatto con il target, una possibile procedura di search si può costruire nel modo seguente. Prima si selezionano una famiglia di luoghi strategici dove si ritiene più probabile che il target passerà ed in essi si costituiscono i flight pattern che l’osservatore dovrà eseguire per ritrovarlo. Quindi si cerca la sequenza di pattern che l’osservatore dovrebbe attuare massimizzando un funzionale utilità che può rappresentare ad esempio la probabilità di ritrovare il target o la velocità con la quale avviene il ritrovamento.
Una delle principali difficoltà nel risolvere il problema di massimo sopra è dovuto al fatto che le dislocazioni geografiche dei pattern, i vincoli sui tempi per le loro esecuzioni (essendo il target in movimento), i tempi necessari per l’osservatore di andare da un pattern ad un altro, pongono una serie di vincoli sulle sequenze dei pattern ammissibili la cui descrizione è di complessità esponenziale nel numero dei pattern della famiglia scelta.
In questa tesi si vuole modellare il problema della descrizione delle famiglie ammissibili di pattern attraverso la teoria dei grafi introducendo un grafo in cui i nodi sono i pattern stessi e un arco tra due nodi indica che essi sono incompatibili, cioè uno stesso drone non può eseguirli entrambi a causa dei vincoli temporali e spaziali. Le famiglie ammissibili in questo modo corrispondono a sottoinsiemi di nodi che formano un cosiddetto insieme indipendente. Il problema originale di ottimizzazione della funzione utilità diviene così naturalmente definito sul nuovo dominio degli insiemi indipendenti e così trasformato in un puro problema di ottimizzazione combinatoria. Obbiettivo della tesi è fornire metodi per la risoluzione di questo problema con vari gradi di difficoltà.
Vedi anche teoria dei giochi ed intelligenza artificiale.pdf
Conoscenze richieste Conoscenza di base di probabilità e di linguaggi di programmazione: java, phyton o equivalenti.
Note La tesi sarà co-supervisionata dalla Prof.ssa Sara Bernardini (http://www.cs.rhul.ac.uk/home/sara/) dell’università Royal Holloway di Londra (https://www.royalholloway.ac.uk/home.aspx) e potrà essere in parte sviluppata in detta sede.
Scadenza validita proposta 22/11/2019
PROPONI LA TUA CANDIDATURA