Applicazioni di intelligenza
artificiale LS
Manni
Tiziano
0000279932
 Realizzare un sistema di sorveglianza in ambiente
dinamico.
 Stabilire una rete di goal all’interno dell’ambiente che
ciascun robot dovrà raggiungere (punti strategici).
 Uso di un framework basato sull’algoritmo di AntColony
Optimization in grado di trovare il percorso hamiltoniano
ottimo tra i vari goal distribuiti all’interno dell’ambiente.
 AntColony: per l’implementazione generale
dell’algoritmo di ant colony
 AntColony4TSP: per l’implementazione dell’algoritmo
specifico per la risoluzione di problemi di TSP (commesso
viaggiatore).
 SentrySystem: per adattare AntColony4TSP ai nostri
scopi.
 Implementazione generale dell’algoritmo di ant colony
optimization:
 Le formiche si muovono in modo indipendente decidendo il
nodo sul quale muoversi sulla base delle informazioni
accumulate lungo il tragitto: comunicazione avviene grazie
alla scia di feromoni lasciati lungo il cammino dalle
formiche stesse.
 La colonia:


inizializza il sistema creando le formiche
interviene sulla scia di feromoni depositate applicando delle
politiche (ES: evaporazione dei feromoni nel tempo).
 Estensione di ant colony per la risoluzione del problema
del commesso viaggiatore (TSP):
 Ogni formica decide il prossimo goal da esplorare con due
modalità (scelta con probabilità configurabile):

Inseguimento:

Esplorazione
sulla base delle informazioni contenute localmente a ciascun
goal.
 Estensione di ant colony per la risoluzione del problema
del commesso viaggiatore (TSP):
 Quando la formica avrà visitato tutti i goal del grafo
aggiorna il livello di feromoni percorrendo il cammino al
contrario depositando
 Estensione di ant colony per la risoluzione del problema
del commesso viaggiatore (TSP):
 La colonia, quando tutte le formiche hanno terminato,
aggiorna il livello di feromoni lasciato lungo tutti gli archi
del grafo seguendo questa politica:
 Per adattare ant colony for TSP si è dovuto applicare
alcune modifiche:
 ad ogni formica è associato un robot che si muove in
simultanea alla formica stessa.
 Quando la formica finisce la sua esplorazione riparte ad
esplorare da capo il grafo.
 Sviluppo di un algoritmo per il posizionamento
intelligente dei goal.
 Sviluppo di strategie per rimpiazzare i goal non
raggiungibili e garantire sempre una coperture di tutte le
zone.
 Analisi intelligente dei cambiamenti dell’ambiente (in
caso di grossi cambiamenti dell’ambiente occorrerebbe
azzerare il sistema per farlo ripartire).