CONCLUSIONI E
SVILUPPI FUTURI
126 CONCLUSIONI E SVILUPPI FUTURI
Il lavoro di questa tesi si è concentrato sullo sviluppo di quattro diversi metodi per l’assegnamento dei robot alla successiva posizione da raggiungere nell’ambito dell’esplorazione autonoma di un ambiente inizialmente sconosciuto. Elemento chiave ai fini del suddetto assegnamento è la strategia di esplorazione adottata per stabilire il valore di utilità dei punti candidati ad essere i prossimi raggiunti nel processo esplorativo; in particolare due sono state le strategie utilizzate: la strategia VISSER e la strategia MCDM.
L’obiettivo è stato valutare quale fosse la versione (dove per versione si intende un metodo di assegnamento associato a una specifica strategia di esplorazione) in grado di mappare, in un tempo prefissato, la maggior area possibile di un ambiente a priori sconosciuto.
Nel capitolo precedente sono stati illustrati e commentati approfonditamente i risultati derivanti dalle simulazioni dei quattro metodi di assegnamento robot/frontiera nelle due strategie VISSER e MCDM. Qui proponiamo una sintesi delle conclusioni alle quali si è giunti attraverso questa tesi.
Le conclusioni possono essere interpretate a partire dai tre interrogativi posti all’inizio del lavoro di tesi, ossia:
1. “Considerando l’assegnamento che tiene conto della reale distanza tra ogni coppia robot/frontiera, la mancanza di coordinamento all’interno del team riduce le performance in termini di mapping?”
2. “Gli algoritmi che prevedono l’assegnamento basato sulle utilità ideali e l’assegnamento random sono caratterizzati da una minore complessità computazionale derivante dal fatto che, nel primo, l’assegnamento avviene semplicemente sulla base del valore di utilità ideale; nel secondo caso, invece, avviene in modo completamente casuale. Questo significa che il tempo necessario per giungere ad una decisione di assegnamento ad ogni step esplorativo è inferiore rispetto a quello richiesto ai metodi basati sull’utilità reale. D’altro canto in tali algoritmi l’utilità di ogni punto è “approssimata” (addirittura nel metodo 4 tali punti non vengono nemmeno valutati) e questo porta ad assegnamenti non ottimali, diversamente da quanto avviene per i metodi basati sull’utilità reale. La minore complessità computazionale di tali
127 CONCLUSIONI E SVILUPPI FUTURI
algoritmi ha effetti incisivi in termini di mapping tale da bilanciare gli effetti di un assegnamento robot/frontiera meno preciso?”
3. “La strategia MCDM è da ritenersi competitiva se confrontata con la strategia VISSER?”
Sulla base dei dati raccolti e delle osservazioni discusse nel Capitolo 5, possiamo concludere quanto segue:
Per quanto riguarda il primo interrogativo possiamo concludere che, al contrario di quanto ci si aspettava, la mancanza di coordinamento e quindi l’assegnamento di ogni robot alla sua migliore frontiera senza considerare gli altri robot, risulta essere una scelta vincente nel caso di assegnamenti basati sull’utilit{ reale. Nell’implementazione con strategia MCDM le performance di questo metodo sono praticamente le stesse dell’analogo metodo caratterizzato dal coordinamento; è con la strategia VISSER che si denotano delle leggere differenze (soprattutto nell’area FREE) dove la mancanza di coordinamento tende ad essere leggermente migliore in termini di maggiore copertura dell’ambiente.
Per quanto concerne, invece, il secondo punto, possiamo affermare che i due metodi caratterizzati dall’assegnamento sulla base dell’utilit{ ideale e dall’assegnamento random, mostrano globalmente le peggiori performance sia nella versione VISSER che nella versione MCDM. Inoltre, soprattutto nella strategia VISSER, si nota come questi due metodi siano molto vicini in termini di andamento. Da questo possiamo concludere che l’elemento chiave ai fini della massima copertura dell’ambiente risiede nel calcolo dell’utilit{: i metodi che effettuano gli assegnamenti robot/frontiera basandosi su valori più approssimati di utilità o addirittura senza prendere in considerazione alcun criterio portano alle peggiori performance. Da qui si evince che il criterio fondamentale per garantire il massimo mapping è il costo reale di cammino, in quanto unico criterio discriminante tra l’utilit{ ideale e quella reale. In termini più generali si può affermare che l’elemento chiave non è da ricercarsi primariamente nell’assegnamento robot/frontiera quanto nella modalità sulla base della quale avviene calcolata l’utilità: più l’utilit{ è calcolata attraverso stime precise (considerando più informazioni e/o
128 CONCLUSIONI E SVILUPPI FUTURI
usando valori reali anziché approssimati), più gli assegnamenti sono tali da garantire, al termine della simulazione, la maggiore copertura dell’ambiente.
Per quanto riguarda, invece, il terzo quesito, possiamo affermare che, per ogni metodo, la strategia MCDM si è sempre dimostrata la migliore rispetto alla strategia VISSER. Da questo possiamo concludere che l’aggregazione di criteri secondo MCDM risulta essere una buona scelta per garantire una migliore copertura di un ambiente a priori sconosciuto.
Un interessante studio futuro potrebbe essere quello di effettuare gli assegnamenti partendo direttamente da una matrice di utilità reale: anziché (come nel metodo 1 e nel metodo 3) calcolare l’utilit{ reale solo della coppia corrispondente alla migliore utilità ideale, calcolare direttamente tutte le utilità reali e, sulla base di queste, procedere subito all’assegnamento.
Il problema legato a questo approccio è che ad ogni iterazione, il path planning, anziché essere eseguito, nella peggiore delle ipotesi, tante volte quante sono i robot, verrebbe sempre eseguito |numero dei robot| * |numero di frontiere| volte. Questo approccio richiederebbe, però, un utilizzo decisamente superiore delle risorse del sistema. Da qui la necessità di utilizzare adeguati strumenti hardware e software. Potrebbe essere tuttavia utile capire se questo impiego ulteriore di risorse è compensato da un incremento in termini di prestazioni.
Un altro aspetto da sottolineare è la mancanza di una documentazione che illustri, anche in termini generali, la struttura e il funzionamento del controllore UvARescue2009, almeno nei suoi elementi base. Inoltre anche il codice è molto scarno di commenti e questo rende la lettura e la comprensione del controllore decisamente complicata. Sarebbe utile quindi realizzare un manuale per permettere agli sviluppatori un approccio più semplice e soprattutto chiaro in vista di futuri lavori di sviluppo ed ottimizzazione.
130 BIBLIOGRAFIA
[1] S. Thrun, "Exploration and model building in mobile robot domains", IEEE International Conference on Neural Networks, p. 175 – 180, 1993.
[2] M. Pfingsthorn, “RoboCup Rescue Virtual Robots: Wireless Simulation Server Documentation”, 2008.
[3] F. Amigoni, N Basilico, “Exploration Strategies based on Multi-Criteria Decision Making for an Autonomous Mobile Robot”, Fourth European Conference on Mobile Robots, p. 259-264, 2009.
[4] A. Visser, A. SLAMet, “Including communication success in the estimation of information gain for multi-robot exploration”, 6th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks and Workshops, p. 680 – 687, 2008.
[5] H. Gonzalez-Banos, J.C. Latombe, “Navigation Strategies for Exploring Indoor Environments”. The International Journal of Robotics Research, p. 829 – 848, 2002.
[6] M. Pfingsthorn, B. Slamet, A. Visser, N. Vlassis, “UvA Rescue Team 2006 RoboCup Rescue - Simulation League”.
[7] A. Visser, B. SLAMet, T. Schmits, “Design decision of the UvA Rescue 2007 Team”.
[8] A. Visser, T. Schmits, S. Roebert, J. de Hoog, “Amsterdam Oxford Joint Rescue Forces Team Description Paper Virtual Robot competition Rescue Simulation League RoboCup 2008”.
[9] A. Visser, H. Nijhuis, J. de Hoog, “Amsterdam Oxford Joint Rescue Forces Team Description Paper Virtual Robot competition Rescue Simulation League RoboCup 2009”.
131 BIBLIOGRAFIA
[10] M. W. M. G. Dissanayake, P. Newman, S. Clark, and H. F. DurrantWhite, “A solution to the simultaneous localization and map building (SLAM) problem”, Transaction on Robotics and Automation, p. 229 – 241, 2001.
[11] S. Thrun, “Learning metric-topological maps for indoor mobile robot navigation”, Artificial Intelligence, p. 21 – 71, 1998.
[12] W. Burgard, D. Fox, M. Moors, R. Simmons, and S. Thrun, “Collaborative Multi- Robot Exploration”, IEEE International Conference on Robotics and Automation, p. 476 – 481, 2000.
[13] P. Newman, M. Bosse, J. Leonard, “Autonomous feature-based exploration”, IEEE International Conference on Robotics and Automation, p. 1234 – 1240, 2003.
[14] J.Wang, S. Balakirsky, “USARSim V3.1.3”.
[15] N. Basilico, “USARSim/MOAST: a game-based 3D simulation framework for mobile robots”, presentazione per il Politecnico di Milano.
[16] B. Yamauchi, “Frontier-Based Exploration Using Multiple Robots”, 2nd International Conference on Autonomous Agents, p. 47 – 53, 1998.
[17] P. Newman, J. Leonard, J. D. Tardos, and J. Neira, “Explore and return: experimental validation of real-time concurrent mapping and localization”, IEEE International Conference on Robotics and Automation, p. 1802 – 1809, 2002.
[18] M. W. M. G. Dissanayake, P. Newman, H. F. Durrant Whyte, S. Clark, and M. Csorba, “An experimental and theoretical investigation into simultaneous localization and map building", 6th International Symposium on Experimental Robotics, p. 265 – 274, 1999.
132 BIBLIOGRAFIA
[19] J. Guivant and E. Nebot, “Optimization of the simultaneous localization and map building algorithm for real time implementation”, IEEE Transactions on Robotic and Automation, p. 242 – 257, 2001.
[20] P. Newman, J.Leonard, J.D. Tardòs, and J.Neira, “Explore and return:
Experimental validation of real time concurrent mapping and localization”, IEEE International Conference on Robotics and Automation, p. 1802 – 1809, 2002.
[21] R. Rikoski, J. Leonard, and P. Newman, “Stochastic mapping frameworks”, IEEE International Conference on Robotics and Automation, p. 426 - 433 , 2002. [22] D. Hahnel, D. Schulz, and W. Burgard, “Map building with mobile robots in
populated environments”, IEEE International Conference on Intelligent Robots and Systems, p. 496 - 501, 2002.
[23] S. Thrun, “A probabilistic online mapping algorithm for teams of mobile robots,” International Journal of Robotics Research, p. 335-363, 2001.
[24] A. Elfes, “Sonar-based real-world mapping and navigation”, IEEE Journal of Robotics and Automation, p. 249-265, 1987.
[25] S. Thrun, “Robotic mapping: A survey”, Exploring Artificial Intelligence in the New Millennium, p. 1 – 35, 2003.
[26] B. Yamauchi, “A Frontier-Based Approach for Autonomous Exploration”, IEEE International Symposium on Computational Intelligence, Robotics and Automation, p. 146 – 151, 1997.
[27] H. Gonzalez-Banos, E. Mao, J.C. Latombe, T.M. Murali, and A. Efrat, “Planning Robot Motion Strategies for EfficientModel Construction”, 9th International Symposium on Robotics Research, p. 345–352, 1999.
133 BIBLIOGRAFIA
[28] Sebastian Thrun, Wolfram Burgard and Dieter Fox, “Probabilistic Robotics”, ed. MIT Press.
[29] G. Gini e V. Cagliotti, “Robotica”, ed. Zanichelli, 2003.
[30] www.robocup.org [31] www.jointrescueforces.eu [32] www.sourceforge.net [33] www.en.wikipedia.org/wiki/Urban_search_and_rescue [34] www.usar.org.uk [35] www.intrescue.org [36] www.usarsim.sourceforge.net/wiki/index.php/RoboCup_Rescue_Virtual_ Robot_Competition [37] www.robocuprescue.org/wiki/index.php?title=VRCompetitions [38] www.robocuprescue.org/ [39] www.robocuprescue.org/virtualsim.html
Appendice A:
DATI DELLE PROVE
SPERIMENTALI
136 DATI DELLE PROVE SPERIMENTALI
A.1 – Confronto tra strategie A.1.1 – Metodo 4
Area FREE
137 DATI DELLE PROVE SPERIMENTALI
Area SAFE
138 DATI DELLE PROVE SPERIMENTALI
Area CLEAR
139 DATI DELLE PROVE SPERIMENTALI
A.1.2 – Metodo 3: confronto VISSER vs MCDM
Area FREE
140 DATI DELLE PROVE SPERIMENTALI
Area SAFE
141 DATI DELLE PROVE SPERIMENTALI
Area CLEAR
142 DATI DELLE PROVE SPERIMENTALI
A.1.3 – Metodo 2: confronto VISSER vs MCDM
Area FREE
143 DATI DELLE PROVE SPERIMENTALI
Area SAFE
144 DATI DELLE PROVE SPERIMENTALI
Area CLEAR
145 DATI DELLE PROVE SPERIMENTALI
A.1.4 – Metodo 1: confronto VISSER vs MCDM
Area FREE
146 DATI DELLE PROVE SPERIMENTALI
Area SAFE
147 DATI DELLE PROVE SPERIMENTALI
Area CLEAR
148 DATI DELLE PROVE SPERIMENTALI
A.2 – Confronto tra metodi
A.2.1 – Strategia VISSER
149 DATI DELLE PROVE SPERIMENTALI
A.2.2 – Strategia MCDM
Appendice B:
MANUALE
D’INSTALLAZIONE E
D’USO
152 MANUALE D’INSTALLAZIONE E D’USO
B.1 – Installazione
Per poter utilizzare UvARescue2009 e necessario prima di tutto installare Unreal Tournament 2004, USARSim, Image Server e WSS; una volta installati tutti i componenti necessari, si può passare ad installare il controllore. Le seguenti istruzioni sono per i S.O. Microsoft Windows, tuttavia le prestazioni migliori si hanno su Microsoft Windows XP in quanto Unreal Tournament può portare a problemi di compatibilità con versioni di Windows successive a XP.
1- UNREAL TOURNAMENT 2004
E' necessario comprare il videogioco per intero. Per installarlo inserire il DVD e seguire le semplici istruzioni che compaiono a video. La directory in cui installare il gioco è “C:\UT2004”.
Prima di procedere all’installazione di USARSim, occorre installare la patch ufficiale del gioco (versione numero 3369) reperibile dal sito di Unreal Tournament: http://www.unrealtournament2003.com/news/viewbd8c.html?id=2988.
2- USARSIM
USARSim e i componenti necessari si possono reperire dal sito sourceforge.net attraverso il link http://sourceforge.net/projects/usarsim/files/. Vi sono molte versioni di USARSim rilasciate per Unreal Tournament; in questa guida si fa riferimento alla versione 3.1.
scaricare l'eseguibile “USARSimFull_3.1.zip”;
installare l’eseguibile in C:\UT2004 seguendo gli step e sostituendo eventualmente i file già presenti qualora richiesto;
scaricare ed installare sempre in C:\UT2004 due eseguibili: “AAA_MapBaseFiles_V3.1.zip” e “DM-RoboCup06Worlds_V3.1.zip” esattamente in questo ordine: il primo contiene dei file necessari al secondo eseguibile che contiene le mappe;
sempre dal sito cui sopra seguire il percorso “Tools/3.1” e scaricare il file “ImageSrv_3.1.zip”;
estrarre la cartella ImageSrv ed incollarla in C:\UT2004.
Dal sito http://sourceforge.net/scm/?type=cvs&group_id=145394 scaricare il tool WSS. La cartella contenente l’eseguibile può essere messa in qualunque
153 MANUALE D’INSTALLAZIONE E D’USO
path;
installare Visual Studio 2005 o superiore.
3- UVARESCUE2009
Il controllore UvARescue2009 utilizzato in questa tesi si può scaricare dal sito www.jointrescueforces.eu seguendo il link “Download”. Sempre sul sito sono fornite nel dettaglio tutte le informazioni necessarie per l’installazione; qui vengono riportati solamente i passi essenziali:
scaricare il file .zip contenente il codice della versione 2007 (UvARescue2007.zip);
estrarre i file contenuti nell'archivio in una cartella, per comodità nominarla per comodità AOJRF2008;
dalla stessa pagina scaricare il file .zip della versione 2008 (AOJRF2008.zip);
estrarre i file sempre nella cartella AOJRF2008 precedentemente rinominata, sostituendo tutti i file omonimi (quando richiesto) e rinominare la cartella in AOJRF2009;
scaricare, sempre dalla stessa pagina, il file .zip della versione 2009 (AOJRF2009.zip);
estrarre i file nella cartella AOJRF2009, sostituendo tutti i file;
nella cartella AOJRF2009 eliminare il file “UvA Rescue.sln” e aprire “UvARescue.sln” (si tratta di un file Soluzione di Visual Studio) impostando UsarCommander come progetto d’avvio. A questo punto si aprirà Visual Studio e si è pronti per la compilazione; compilando in sequenza UsarLib, UsarClient e UsarCommander verranno generati due eseguibili: “UsarClient.exe” e “UsarCommander.exe”.
Il primo si trova in \..\Usar\UsarClient\bin\Release; il secondo in \..\Usar\UsarCommander\bin\Release.
B.2 – Utilizzo
Dopo aver compilato si è pronti per mandare in esecuzione. La procedura da seguire è la seguente:
154 MANUALE D’INSTALLAZIONE E D’USO
è possibile eseguire in modalità debug (premendo il tasto F5) o lanciando direttamente l’eseguibile UsarCommander.exe dal path in cui è stato creato in fase di compilazione: verr{ aperta l’interfaccia del controllore come mostrato in Figura 3.1.
configurare ogni robot: premendo sul pulsante “+” verr{ aggiunto un robot; premendo successivamente sul pulsante “ingranaggio” si aprir{ la finestra Agent Configuration (Figura 3.3) per la configurazione delle caratteristiche. Spuntare l’opzione “Spawn from commander” solo per il robot ComStation. Salvare in un file .cfg (nella mia tesi si chiama AC.cfg) nella cartella \..\Usar\UsarClient\bin\Release. La configurazione di ogni robot deve risiedere nello stesso file;
configurare il team premendo sul pulsante “globo azzurro” in basso a destra: verrà aperta una form (Figura 3.4) nella quale andranno inseriti gli indirizzi IP e le porte del Localhost, dell’USARSim, dell’Image Serve e del WSS. Questo perché i quattro componenti potrebbero essere locati su macchine diverse. Le porte sono fissate a 3000 per l’USARSim, 5003 per l’Image Server e 50000 per il WSS. E’ possibile definire in questa form il tempo di backup dei dati; nella mia tesi i dati sono stati raccolti ogni 30 secondi. Salvare infine la configurazione in un file .cfg (nella mia tesi si chiama TC.cfg) nella cartella \..\Usar\UsarClient\bin\Release.
Far partire la simulazione premendo sull’interfaccia del controllore il pulsante “V” verde. A questo punto si è pronti per inserire i robot nell’ambiente seguendo la procedura seguente:
Far partire l'Image Server “UT2004\ImageSrv\Release\ImageSrv.exe” impostando “UT Client Mode”, “Port: 5003” e selezionando il nome di un file mappa di USARSim (o di Unreal): i file mappa si trovano nella cartella UT2004/maps ed hanno estensione “.ut2” che non va riportata. A fronte della richiesta di cercare “ut2003.exe”, premere “Start” e selezionare “UT2004.exe” presente nella directory “UT2004/System”;
Far partire il WSS impostando “listen on port”: 50000” e premere “Start”;
155 MANUALE D’INSTALLAZIONE E D’USO
posizionarsi nella cartella in cui si trova UsarClient.exe e i due file di configurazione .cfg (AC.cfg e TC.cfg);
In ognuno dei prompt digitare la seguente riga di comando: “UsarClient.exe -n nomeRobot -ac AC.cfg -tc TC.cfg” dove nomeRobot è il nome dato al robot in fase di configurazione (es. Robot1) mentre AC.cfg e TC.cfg sono i nomi dei due file di configurazione (dei robot e del team). Prima di premere invio, eseguire il passo successivo;
tornare sull’interfaccia del controllore e premere il pulsante “orologio” per far partire la simulazione vera e propria: compariranno dei pulsanti “fulmine”, uno per ogni robot: premerli uno di seguito all’altro a partire dal robot ComStation.