PORTALE DELLA DIDATTICA

Ricerca CERCA
  KEYWORD

Game theory and AI for target search problems

estero Thesis abroad


keywords ALGORITHMS, ARTIFICIAL INTELLIGENCE, DRONES, GRAPHS

Reference persons FABIO FAGNANI

External reference persons SARA BERNARDINI (ROYAL HOLLOWAY, LONDON)

Research Groups Analisi e controllo di sistemi dinamici

Description 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à.

See also  teoria dei giochi ed intelligenza artificiale.pdf 

Required skills Conoscenza di base di probabilità e di linguaggi di programmazione: java, phyton o equivalenti.

Notes 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.  


Deadline 22/11/2019      PROPONI LA TUA CANDIDATURA




© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
Contatti