NOTA BENE1: il seguente articolo è stato adattato da un formato esterno a quello wiki: è possibile visualizzare il sorgente in formato HTML.
NOTA BENE2: questo articolo è stato fornito dal rispettivo autore in ILQOSL, ma il mantainer tecnico è il ServizioSegnaPosto, prego contattare quest'ultimo per il cambio di gestione e rimuovere poi questo avviso.
Al fine di ampliare il campo di impiego dei robot, tanto nel contesto della ricerca quanto nel contesto industriale, è necessario conferire loro un elevato grado di autonomia, che comporta la capacità da parte di questi sistemi di operare in ambienti non strutturati. Per questo motivo, il robot deve mostrarsi in grado di interagire coerentemente con il proprio ambiente, sia estraendo una descrizione sintetica e robusta degli oggetti che lo circondano, mediante le informazioni fornitegli dal proprio apparato sensoriale, sia utilizzando in maniera idonea questa descrizione per le proprie attività di pianificazione
del moto a breve ed a lungo termine.
Questo capitolo si occuperà del processo di costruzione della mappa, comunemente chiamato map-building, di un ambiente non strutturato ed inizialmente sconosciuto.
Tale necessità è abbastanza evidente per i veicoli autonomi che devono esplorare luoghi di cui mancano completamente informazioni a priori, come un fondale marino o la superficie di un pianeta, ma anche per robot mobili che operano in fabbriche o in ambienti potenzialmente ostili e pericolosi, come miniere e centrali nucleari, è fondamentale la capacità di saper gestire eventi inaspettati non appena si verificano.
In letteratura possiamo individuare due diversi paradigmi di map-building. Il primo ad essere implementato è stato il cosiddetto paradigma geometrico e si fonda sull’idea di rappresentare l’ambiente per mezzo di un insieme di elementi geometrici, come segmenti di rette o altre primitive (si veda in proposito [45]), ottenuti elaborando le informazioni sensoriali. I vantaggi di questo approccio risiedono principalmente nella maneggevolezza delle mappe che vengono generate, che possono essere direttamente passate a moduli di alto livello, come il pianificatore di moto globale, ed alla facilità di riconoscimento di landmark, naturali o posti ad-hoc nell’ambiente operativo, che risultano utili nell’ambito delle procedure di localizzazione.
Il paradigma geometrico risulta idoneo principalmente per operazioni in ambienti ben strutturati, in cui è possibile determinare a priori il tipo e la forma degli ostacoli che il robot può incontrare. Questo fatto rende la qualità della mappa generata strettamente dipendente dalla topologia dell’ambiente in cui il robot si muove e dalla validità o meno in tale ambiente delle assunzioni empiriche adottate.
Un problema piuttosto grave di questo approccio è poi costituito dal fatto che esso richiede una determinazione spesso precoce del tipo e dei parametri della primitiva da creare nella mappa e questo lo rende vulnerabile alla presenza di rumore sulle misure iniziali.
Suddividendo lo spazio operativo in una matrice G di celle ed associando ad ogni cella C un insieme di valori che ne descrivono lo stato di occupazione, si ottiene una griglia di occupazione; tale griglia ha dimensione pari o inferiore a quella dello spazio operativo. Disponendo ad esempio di sensori in grado di fornire non solo la distanza, ma anche l’altezza dal suolo degli ostacoli, è possibile utilizzare una griglia tridimensionale per tenere conto di questa informazione. Durante il moto del robot, lo stato di occupazione di ciascuna cella viene aggiornato utilizzando le informazioni che i sensori rendono via via disponibili.
Il primo punto di forza di questo approccio consiste nel fatto che la griglia si presta a rappresentare oggetti di qualunque forma e non richiede alcun tipo di ipotesi iniziale riguardante l’ambiente operativo. Inoltre, poiché non è richiesto alcun tipo di decisione precoce riguardante la primitiva che descrive un determinato oggetto, la griglia di occupazione risulta essere più robusta a misure “erratiche” da parte dei sensori. Un terzo pregio è costituito dal fatto che la griglia di occupazione è sostanzialmente una rappresentazione di “basso livello” dell’ambiente e pertanto risulta semplice aggiornare lo stato di ciascuna cella con i dati forniti da dispositivi diversi, come sonar e scanner laser, operando così una fusione delle informazioni disponibili.
Figura 1 - Idea di base delle griglie di occupazione
Indicando con n la dimensione del campo di occupazione O(x), ovvero l’insieme delle coordinate spaziali continue x(_ x1,_ x2,……,xn) su cui è definita la griglia, e con N1,_ N2,……,Nn il numero di celle C allocate lungo ciascuna direzione della griglia, il numero totale di celle sarà:
Equazione 1
Dall’equazione (Eq. 1) si nota immediatamente come il principale difetto della griglia di occupazione sia il massiccio quantitativo di memoria che richiede per descrivere ambienti di estensioni significative conservando una buona risoluzione spaziale.
In questo caso particolare la mappa ha dimensione n = 2 ed ha, per comodità, forma quadrata.
Figura 3.2 – Esempio di griglia a due dimensioni
Lo spazio nel quale si suppone di fare muovere il robot viene posto ad un massimo di 50metri per ogni direzione. Le celle hanno tutte la stessa dimensione (100mm x 100mm) da cui ne consegue che la griglia di occupazione avrà dimensioni
Equazione 2
e
Equazione 3
e la quantità di memoria effettivamente occupata è:
nel caso in cui di prenda come unità fondamentale della singola cella il byte
Equazione 4
e nel caso di una word (2byte)
Equazione 5
che come si può constatare per un qualunque PC è una quantità davvero irrisoria di memoria da utilizzare. Se però si volesse una risoluzione spaziale decisamente migliore il quantitativo della memoria usata, come già detto prima, crescerebbe radicalmente.
L’ambiente nel quale il robot verrà inserito viene descritto grazie a una mappa dinamica destinata alla navigazione.
La zona circostante viene rappresentata, come già detto, in un modello che consiste in una griglia quadrata, suddivisa in celle, che divide il pavimento in distretti.
Figura 3.3 – Rappresentazione dei muri in una griglia di occupazione
Ciascuna cella ha un corrispondente valore in una matrice che rappresenta la certezza o l’assenza di un ostacolo in quella posizione. Lo spazio occupato è rappresentato da valori positivi, lo spazio libero da valori negativi e allo spazio inesplorato corrispondono, invece, valori nulli.
Figura 3.4 – Esempio costruzione di una mappa con griglie di occupazione
E’ descritto qui di seguito il modulo che procura una percezione di 360° intorno al robot. Dal quale, dopo una trasformazione delle coordinate, attraverso la posizione e l’orientamento del robot e dei suoi sensori, queste misure vengono direttamente trasferite nella mappa del robot. Per ciascuna acquisizione il valore della cella corrispondente viene incrementato, con valori che rappresentano la certezza della presenza di un ostacolo in quella posizione. I valori delle celle comprese tra il centro del robot e l’oggetto vengono decrementati di 1. La posizione della cella incrementata con le coordinate dello spazio circostante (xobst, yobst) può essere calcolata conoscendo ciò che è stato misurato dalla posizione centrale del robot (xm, ym, θm), la posizione del vettore (xs, ys, θs) del sensore riportata dal sistema di coordinate locali del robot con origine nel centro di quest’ultimo, la distanza ds dall’ostacolo misurata dal sensore, svolgendo la relazione:
Figura 3.5 – Posizionamento del robot in una griglia di occupazione
Equazione 6
dove:
(dsens, θsens) sono rispettivamente la distanza alla quale il sensore rileva l’ostacolo e l’angolo del sensore rispetto all’asse x del robot;
(xobst, yobst) sono le coordinate cartesiane dell’ostacolo calcolato;
La mappa potrebbe contenere alcune cella errate, risultanti da alcune false misurazioni.
Queste celle errate, di solito, vengono cancellate grazie ad ulteriori e continue acquisizioni di dati da parte del robot.
Figura 3.6 – Individuazione delle celle da aggiornare
La traversabilità di una mappa da per ogni singola cella la distanza di quest’ultima dall’ostacolo più vicino ad essa. Questa cella ha un valore con il quale si quantifica la misura della traversabilità. E’ importante notare che due fattori influenzano la traversabilità:
la distanza dell’ostacolo più vicino;
il tipo di terreno, cioè esplorato o inesplorato.
Un’area perciò può avere una bassa traversabilità perché inesplorata oppure perché è chiusa da un ostacolo.
La mappa di traversabilità si ottiene usando una trasformazione a tappeto su tutte le celle della mappa fino a quel momento acquisita. Con quest’ultimo si crea un diagramma di Voronoi [67] che serve a pianificare percorsi per cella base. Questo metodo massimizza la distanza dagli ostacoli, ma non ottimizza necessariamente la lunghezza del percorso: infatti, a volte, rende il percorso più esteso per renderlo più sicuro, cioè a una certa distanza dagli ostacoli.
Viene spiegato qui di seguito come opera il metodo.
Per prima cosa la griglia viene segnata con degli “1” che si trovano in tutte le celle della mappa che corrispondono ai punti occupati dagli ostacoli.
Figura 3.7 – Primo stadio della costruzione di una mappa di traversabiltà
In questa formulazione i valori inferiori indicano valori di minore traversabilità. Per esempio “1” significa che la cella è completamente occupata e quindi non attraversabile.
Invece, valori maggiori di 1 indicano che è possibile attraversare quella cella o quell’area.
Questo vuol dire che la mappa contiene a priori un’informazione sulla traversabilità di aree non ostacolate. In essa sono indicati infatti dei valori per ciascuna cella corrispondente al punto sulla mappa ed è quindi possibile sapere il suo grado di traversabilità. Per marcare invece aree inesplorate vengono usate dei valori di traversabilità bassa, così che il robot ne stia alla larga.
Dopo aver fatto la selezione iniziale si può usare l’algoritmo mostrato in figura 3.10 che viene spiegato anche qui di seguito con l’ausilio di alcune figure.
Dopo aver inizializzato la mappa di traversabilità con tutti “1”, sulle otto posizioni adiacenti, se libere, vengono messi dei “2” per indicare che la distanza dall’ostacolo più vicina e appunto 2.
Figura 3.8 – Secondo stadio della costruzione di una mappa di traversabilità
A questo punto per ogni “2” messo sulla mappa, per ognuna della quattro posizioni adiacenti, se libere, viene messo un “3”. Allo stesso modo per il “3” vengono messi dei “4” e per il “4” vengono messi dei “5” nelle quattro posizioni adiacenti. A questo punto in tutte le altre celle della mappa vengono messi dei “5”. Si poteva benissimo continuare per numeri di traversabilità superiori, ma per questa applicazione è sufficiente fermarsi a questo punto.
Figura 3.9 – mappa di traversabilità completa
Nella pagina successiva viene mostrata una bozza dell’algoritmo usato per ricavare una griglia di traversabilità.
Figura 3.10 – Algoritmo di traversabilità
Nell’algoritmo standard fronte d’onda la cella rappresentante il punto goal è segnata con “1” e tutte quelle non occupate vicine sono segnate con “2”; tutte quelle non occupate vicine al “2” sono segnate con “3”, ecc, fino a che il punto di partenza è raggiunto.
Figura 3.11 – Inizializzazione di una mappa col metodo del Fronte D’onda
Figura 3.12 – Costruzione di una mappa col metodo del Fronte D’onda
Questo metodo produce un tracciato che è ottimale per la sua lunghezza, ma che tende a costeggiare i siti degli ostacoli. Questo problema si può alleviare “accrescendo” gli ostacoli di un certo importo e garantendo poi una distanza minima da essi. Quindi questo metodo è insoddisfacente, non da completa garanzia e può essere necessario calcolare il rischio e tenere molto spazio da un ostacolo. Similmente l’approccio di base fronte d’onda non può distinguere i vari tipi di terreno, fattori importanti che influenzano la traversabilità.
Figura 3.13 – Percorso del robot sulla mappa
Un metodo per evitare aree incerte o inesplorate come ostacoli può essere attaccare delle etichette ad esse. Tuttavia anche questo procedimento è insoddisfacente per esplorare nuove aree perché non da un percorso significativo dal punto di vista economico della lunghezza.
Usare la griglia di traversabilità permette la pianificazione invece, di informazione su una regione come navigabile mentre si genera il percorso stesso tracciato. Diversamente dall’algoritmo standard fronte d’onda, dove è la lunghezza del percorso il criterio di ottimalizzazione; il criterio di ottimalizzazione della griglia di traversabilità è la combinazione di lunghezza è traversabilità.
Figura 3.14 – Metodo del Fronte d’Onda
Il campo potenziale finale viene costruito usando una combinazione di trasformazioni fronde d’onda e di griglia di traversabilità. La trasformazione parte dal goal e progredisce fino a che non s’incontra il punto di partenza o fino alla fine se si vuole completare la mappa.
Figura 3.15 – mappa costruita col metodo dei Campi Potenziali
Figura 3.16 – Percorso lontano dagli ostacoli
Iniziando dalla griglia costruita col metodo del fronte d’onda, si cercano partendo dalla posizione dell’obiettivo da fare raggiungere al robot (“1”), tutti i valori scritti in precedenza con questo metodo; prima tutti i “2” poi tutti i “3” e così via fino al completamento della mappa. Per ognuna di queste celle cercate, se la traversabilità è minore di un certo valore (MINT) viene calcolato il cubo della differenza tra MINT e la traversabilità appena letta per quella cella. Questo valore viene aggiunto a quello letto nella griglia del fronte d’onda e scritto nella griglia dei campi di potenziale. Altrimenti se la traversabilità non è minore viene semplicemente ricopiato il numero appena letto.
Alla fine di tutto questo procedimento si ottiene il risultato mostrato nelle figure precedenti.
L’algoritmo per calcolare il campo potenziale è mostrato al fondo di questo paragrafo, nelle figure 3.15, 3.16, 3.17.
Si noti in particolar modo la funzione calcTrav() che rappresenta la sostanziale differenza tra l’algoritmo Fronte d’onda e l’algoritmo Campi Potenziali.
Come si vede dalla figura 3.13 il robot partendo dalla cella contrassegnata col numero “25” seguirà il tracciato in verde con i numeri decrescenti fino a giungere alla posizione contrassegnata col numero “1”. Si noti ancora che il robot segue un percorso che lo tiene lontano dagli ostacoli rilevati in precedenza e in questo caso nel mezzo del corridoio.
Volendo fare ancora un’ulteriore modifica e far seguire al robot percorsi in diagonale sulle celle, è possibile, seguendo il percorso in verde e puoi quello in rosa, ridurre ancora la lunghezza del percorso ottimale (vedi figura 3.17).
Figura 3.17 – Il percorso più breve
Nella pagina seguente sono mostrate le funzioni di base per costruire una mappa con il metodo dei campi potenziali partendo da una griglia di traversabilità e una griglia dei fronti d’onda.
Figura 3.18 – Metodo campiPotenziali
Figura 3.19 – Metodo che scrive nelle quattro celle adiacenti
Figura 3.20 – metodo che ricava e calcola la traversibità per i campi potenziali
Nota: nel caso rappresentato nelle figure precedenti, MINT = 4; cioè si vuole che il robot stia distante almeno 3 caselle, cioè 30cm, da qualunque ostacolo.
