L’algoritmo di ricerca, una volta concluse le operazioni di ottimizzazione del percorso, restituirà il path migliore da far seguire all’utente, sotto forma di una successione di nodi. Essi, proprio per le caratteristiche con cui il grafo è stato costruito, saranno facilmente ri-mappabili, in modo da poter attuare opportunamente una strategia di controllo e guidare l’utente all’interno dell’edificio.
Viene in ultimo proposta un’ulteriore alternativa. Essendo il campione di soggetti con cui sono stati effettuati preliminarmente i test in numero ridotto, si è pensato di introdurre un ulteriore parametro di customizzazione. È possibile richiedere che la
traiettoria, attualmente formata da una spezzata, venga ad essere smussata. Ciò non è emerso dalle richieste espresse in fase preliminare, ma secondo altri studi ([69, 61]) tale traiettoria potrebbe risultare più confortevole per l’utente. In particolare l’operazione è effettuata attraverso un’interpolazione tramite le curve cubiche di Bézier.
I punti per l’interpolazione della curva sono quattro e di seguito descritti. Definiamo come segmento1 quello congiungente il nodo precedente e quello in esame e come segmento2quest’ultimo ed il successivo. Vengono utilizzati il punto mediano e quello localizzato nell’ultimo quarto del segmento1 ed il punto mediano e quello localizzato nel primo quarto del segmento2. Viene mostrato un esempio in Figura 4.16.
Figura 4.16:Calcolo curve cubiche di Bézier: P0e P1rispettivamente punti mediano ed a 3/4
del segmento genitore-nodo attuale; P2 e P3 rispettivamente punti mediano ed
Capitolo 5
Risultati dell’algoritmo di Motion
Planning
L’algoritmo di motion planning sviluppato è stato testato sulle planimetrie del polo principale di Ingegneria dell’Università di Pisa, sito in via Diotisalvi.
L’edificio consta di sei piani interni. Le immagini originali sono state fornite dagli uffici tecnici dell’Università stessa in formato CAD. Sono state ottenuti gli input alla pianificazione attraverso la procedura descritto in appendice.
Vengono di seguito riportati i risultati inserendo dei nodi di partenza e d’arrivo con l’unico scopo di mostrare degli esempi di quanto implementato.
(a)
(b)
(c)
Figura 5.1: a) Pianta del piano terra dell’edificio principale di Ingegneria a Pisa; b) suddivisione dell’immagine; c) esempio di cammino calcolato.
(a)
(b)
(c)
Figura 5.2: a) Pianta del primo piano dell’edificio principale di Ingegneria a Pisa; b) suddivisione dell’immagine; c) esempio di cammino calcolato.
(a)
(b)
(c)
Figura 5.3: a) Pianta del secondo piano dell’edificio principale di Ingegneria a Pisa; b) suddivisione dell’immagine; c) esempio di cammino calcolato.
(a)
(b)
(c)
Figura 5.4: a) Pianta del terzo piano dell’edificio principale di Ingegneria a Pisa; b) suddivisione dell’immagine; c) esempio di cammino calcolato.
(a)
(b)
(c)
Figura 5.5: a) Pianta del quarto piano dell’edificio principale di Ingegneria a Pisa; b) suddivisione dell’immagine; c) esempio di cammino calcolato.
(a)
(b)
(c)
Figura 5.6: a) Pianta del quinto piano dell’edificio principale di Ingegneria a Pisa; b) suddivisione dell’immagine; c) esempio di cammino calcolato.
(a)
(b)
(c)
Figura 5.7: a)Pianta del seminterrato dell’edificio principale di Ingegneria a Pisa; b) suddi- visione dell’immagine; c) esempio di cammino calcolato, caso multi-goal senza
(a) (b)
(c)
Figura 5.8:Sono mostrati tre diversi cammini ottenuti utilizzando diversi criteri. a) cammi- no multi-goal migliore secondo i parametri impostati; b) smoothing del cammino cammino precedente; c) ottenuto seguendo una priorità di goal. Il punto indicato con 0 è il nodo di partenza.
Uno degli obiettivi principali dell’algoritmo è stato quello di preservare la connetti- bilità, pur prestando attenzione alle richieste degli utenti. Infatti, rispetto alle prove effettuate, di cui qui viene riportato solo qualche esempio, un primo e sostanziale ri- sultato è che la ricerca porta sempre, ove esista, a trovare un percorso compatibile con i vincoli di sicurezza imposti.
Ne è un esempio la Figura 5.9 in cui, senza l’introduzione delle correzioni sul rileva- mento dei nodi sui lati prima descritti, non è possibile trovare un collegamento tra i nodi di start e goal, nonostante sia evidente come sussista una soluzione. Il controllo ulteriore implementato, consente di inserire opportunamente dei nodi per preservare la connettibilità, come precedentemente mostrato nell’esempio di Figura 5.4. Nono- stante in questo ambito di ricerca il planning di alto livello sia studiato relativamente meno rispetto all’equivalente di basso livello, alcuni esempi specifici vengono sfruttati per un puntuale confronto.
Naturale punto di partenza comune è stato la scelta della modalità con cui generare il grafo. In particolare, parlando di planning indoor, è spesso utilizzata la scelta di una suddivisione in celle. Come tale suddivisione venga effettuata è differente ed in base alla metodologia cambierà anche il risultato delle traiettorie possibili. Le alternative sviluppate sono diverse: si va da suddivisione in celle approssimata [6]; a suddivisioni esatti, come in [64, 51, 69]. Facendo una distinzione iniziale, quindi, tra suddivisione approssimata ed esatta è possibile notare anche da questi studi come il percorso gene- rato a partire dal primo metodo risulti essere maggiormente frastagliato. Inoltre, in [6] vengono riportati anche degli esempi in cui questa tecnica, affinata per la ricerca di un percorso sicuro, possa fallire. In particolare in questo studio sono state proposte due metodologie atte entrambe a dar peso principale alla sicurezza del percorso trovato, come descritto nel Capitolo 4. Questa idea di fondo è la stessa su cui si basa il presente lavoro. La differenza sostanziale sta nel fatto che la presente tesi ha sviluppato questo aspetto andando direttamente a pesare i nodi in base alla distanza dell’ostacolo ed im- ponendo dei vincoli direttamente sulla determinazione degli archi del grafo. I metodi implementati nell’articolo in questione, invece, non soddisfano appieno gli obietti-
Figura 5.9:Errore nel calcolo del path, causato da una perdita di connettibilità nel grafo. Nel dettaglio si nota, come i vincoli imposti non consentissero né di connettere le due celle, né di inserire il nodo sul lato. Aggiungendo ulteriori controlli nel software il problema è stato ovviato.
vi di partenza. Se da un lato il punto di congiunzione risulta essere primariamente trovare un percorso sicuro, non essendo la ricerca presentata basata su una piantina per il movimento di una persona, presenta delle limitazioni più stringenti rispetto a quanto necessario, portando in alcuni casi a possibili perdite di connettibilità. Infatti,
un edificio non presenterà mai un corridoio ove non sia possibile passare, mentre il metodo di suddivisione proposto potrebbe portare a formare delle celle che, qualora troppo vicine ai muri non verrebbero prese in considerazione. L’alternativa proposta di pesare la vicinanza agli ostacoli porta in questo studio a privilegiare il passaggio sulle celle di dimensione maggiore, ma ciò genera dei cammini troppo tortuosi ed una minor flessibilità rispetto a quanto desiderato.
Gli studi che si basano su decomposizione esatta dello spazio, usano anche tecniche differenti tra loro. Si passa da decomposizioni orizzontali [64], a triangolari [51], fino all’utilizzo del metodo Arrangement [69]. La cosa da notare innanzitutto è come tutti questi esempi, così come proposto nella presente tesi, partano da una pianta del luogo. Nel primo di questi, l’algoritmo implementato presenta un numero ridotto di nodi del grafo. Ciò corrisponde ad un minor numero di alternative che porta ad un percorso con delle curvature in contrasto con quanto desiderato in fase di progettazione. Lo studio [51] parte appunto da una suddivisione triangolare dello spazio, a cui è af- fiancata la tecnica dei potenziali. In fase di ricerca, il percorso stesso viene riportato nella zona centrale rispetto agli ostacoli più vicini. Nella presente tesi ci si è posti sotto delle ipotesi più rilassate. Se da un lato, infatti, posizionarsi sempre al centro rispetto agli ostacoli porta sicuramente a trovarsi nella situazione più sicura, ciò potrebbe non essere richiesto in ampi spazi aperti. Inoltre, tale soluzione presenta dei collegamenti che richiedano dei repentini cambi di orientazione. Infine, un aspetto molto interes- sante proposto è quello dell’introduzione dei così detti "nodi di gruppo". Essi sono dei nodi che per l’appunto raggruppano l’informazione di una serie di ostacoli che si tro- vano su una stessa linea. Risulta essere un soddisfacente espediente per condensare l’informazione non perdendo dettagli utili al planning.
Quanto invece riportato in [69] è una tecnica che fin qui non è stata descritta. Il me- todo Arrangement porta a suddividere esattamente lo spazio andando a prolungare i lati degli ostacoli stessi. Da ciò deriva una generazione di celle di forme miste. Si fa notare come tale metodo, negli esempi riportati, avrebbe condotto allo stesso risulta- to della doppia-suddivisione implementata. Esso sembra, però, maggiormente duttile
di fronte a forme geometriche non rettangolari nell’immagine. Quanto qui proposto, risulta avere anche altre due similitudini che sono quelle di considerare l’oggetto del planning come contornato da una box ed effettuare uno smoothing del cammino. A tal proposito va ricordato come nell’algoritmo implementato, questa sia solo una opzione qualora venga richiesta dall’utente.
In ultimo si vuol sottolineare lo studio riportato in [60]. L’algoritmo sviluppato in questo caso, risulta strutturato opportunamente per soggetti non vedenti che debba- no muoversi all’interno di un supermercato. Presenta la similitudine di voler mini- mizzare il numero di curve da sottoporre all’utente. Ciò viene fatto assegnando un costo alla richiesta di rotazione. A differenza dell’algoritmo implementato in questa tesi, però, presenta esclusivamente angoli di rotazione di 90°, condizione che si è ten- tato di evitare. Di contro, è presente un interessante spunto per il futuro. Essendo la pianificazione basata su un’immagine del luogo, ma avendo altresì a che fare con un ambiente dinamico, è stata introdotta la possibilità di un replanning. Qualora il per- corso sull’immagine trovato, vada a scontrarsi con una variazione o un temporaneo interrompimento di un arco, l’algoritmo ricalcola un percorso alternativo.
Diversi altri sono le alternative di planning proposte ed interessanti, ma spesso rispon- denti a particolari richieste, come [50], e quindi non reputate utili ad un confronto con quanto proposto.
Capitolo 6
Algoritmo di Localizzazione
6.1
Considerazioni preliminari
La localizzazione studiata in questo elaborato è diretta alla guida di una persona non vedente lungo un cammino in ambienti interni. Come spesso sottolineato in prece- denza l’obiettivo è quello di conoscere la posa dell’utente in un sdr globale. Questo consentirà di utilizzare il percorso calcolato dal motion planning come riferimento da essere seguito, affinché venga raggiunta la posizione desiderata dall’utente.
Per giungere allo scopo di rendere l’operazione facilmente replicabile, è necessario utilizzare delle informazioni di uso comune. Mantenere la sensoristica on-board risul- ta un altro obiettivo fondamentale. Queste due caratteristiche svincolano il sistema da particolari restrizioni per il suo funzionamento. Così facendo si vuol massimizzare la fruibilità del risultato prodotto, rendendo il dispositivo indipendente da adeguamenti degli edifici od esperimenti preliminare da condurre in loco per ottenere conoscenze suppletive.
Inoltre, è importante tenere in considerazione l’aspetto estetico e di ingombro, in quanto il sistema andrà indosso ad un individuo. Ciò richiede di ponderare ocula- tamente eventuali aggiunte di nuove componenti. Valutando come il progetto sia stu- diato per essere un aiuto per le persone, va prestata attenzione affinché non diventi
invece un limite sociale.
È stato più volte ribadito come il GPS, principale strumento di localizzazione outdoor, non possa essere utilizzato all’interno degli edifici, a causa del netto deterioramento del segnale. Le principali proposte atte a sopperire a questa mancanza, prevedono l’in- stallazione di sensori nell’ambiente, come nel caso di antenne UWB[57] o RFID[9, 32]. Spesso, l’alternativa viene trovata nell’utilizzo di sensori inerziali. La stima derivante, però, non risulta sufficientemente precisa per attuare una guida efficace. Altre pro- poste prevedono l’utilizzo delle camere anche in fase di localizzazione. In particolare la visual odometry è uno strumento molto utilizzato per ottenere dati di posa. An- che in questo caso, il risultato ottenuto tende ad avere un errore eccessivo. I dati di una IMU e della telecamera possono anche essere combinati per la tecnica della vi- sual inertial odometry, con risultati migliorativi rispetto all’utilizzo dei due sensori individualmente. La stima derivante dai dati odometrici tende comunque a crescere, richiedendo mezzi di saltuaria ricalibrazione. Per tale operazione viene spesso propo- sto di usare dei marker riconoscibili direttamente attraverso un’analisi delle immagini della camera. Essi possono anche essere utilizzati indipendentemente, direttamente per la localizzazione[78]. Anche questa soluzione richiede, però, l’installazione e la preventiva localizzazione di tali contrassegni. Un’ultima alternativa proposta è quella di sfruttare il rilevamento di alcuni specifici oggetti nell’ambiente. I dati della loro posizione possono essere spesso estratti direttamente dalla piantina del luogo, come numeri sulle porte, posizioni degli estintori o uscite d’emergenza. Tale operazione richiede delle informazioni non sempre presenti e degli algoritmi di preprocessing dell’immagine di alto livello. Inoltre, questo metodo è poco robusto a variazioni del- l’ambiente.
In questa tesi viene proposto un metodo che sia completamente indipendente da strut- ture ed installazioni esterne e che richieda l’utilizzo di scarne informazioni. In parti- colare, avendo a disposizione la mappe degli edifici, la localizzazione attuata è di tipo map based, in modo da usare questa stima per correggere la localizzazione data dalla visual inertial dometry. Si è quindi optato per non utilizzare altri sensori al di fuori
della camera, dotata di un’IMU on-board, che verrà di seguito descritta.
L’algoritmo di localizzazione è sviluppato nell’ambiente Robotic Opereting Sistem (ROS) ed ha sfruttato dei pacchetti specifici, di cui viene data una descrizione. Successiva- mente verrà specificato come questi siano stati interconnessi, al fine di localizzare la camera lungo il percorso effettuato.