Algoritmi di visione stereo/omnidirezionale per la navigazione di robot autonomi

INTRODUZIONE
Field), la cui peculiarit a risiede nell’integrazione di due concetti noti: Certainty Grids
nella rappresentazione degli ostacoli e Potential Fields per la navigazione vera e pro-
pria. Attraverso un insieme di forze attrattive e repulsive  e stato possibile forzare il
robot a seguire la traiettoria pi u consona al raggiungimento dell’obbiettivo mantenen-
do entro i limiti imposti gli angoli di pitch e di roll, mentre con l’utilizzo della matrice
di certezze  e stato possibile in uenzarne la traiettoria in modo pi  u o meno netto indi-
cando con diversi gradi di sicurezza gli ostacoli individuati dall’algoritmo di visione.
Il metodo utilizzato per rendere sicuro il cammino percorso da Caretta in ambienti
esterni  e denominato RSNOE (Reactive Safe Navigation in Outdoor Environment), ed
 e stato studiato anche all’Universit a di Genova [12]; esso si innesta nel metodo VFF
sfruttandone le caratteristiche e ampliandone le possibilit a, modi cando la traiettoria
del robot attraverso due nuove forze governate dai dati acquisiti dall’inclinometro.
L’algoritmo utilizzato per sfruttare il sensore visivo  e invece frutto delle conoscenze
sviluppate negli ultimi anni all’Universit a di Parma e fa uso di una tecnica non ricor-
siva per individuare gli ostacoli presenti sul percorso; a tal  ne sfrutta le informazioni
derivanti da due telecamere, una tradizionale posta frontalmente e una omnidireziona-
le, le immagini delle quali vengono invertite prospetticamente.
La parte di progetto relativa invece al sensore GPS non  e stata purtroppo del tutto rea-
lizzata a causa della scarsa autonomia delle batterie e dell’errore eccessivo presente
nel segnale, che poteva essere diminuito solamente attraverso il ricorso ad un sistema
differenziale, attualmente non disponibile.
Dopo una prima parte in cui viene presentato il lavoro precedentemente svolto all’U-
niversit a di Genova sul quale si innesta la nostra tesi, vengono descritte le basi ma-
tematiche degli algoritmi utilizzati, gli scopi perseguiti e le soluzioni considerate per
ciascuna parte del progetto. Segue poi la parte di implementazione e codi ca dove
 e posta particolare attenzione all’integrazione del nostro lavoro nel sistema ETHNOS
gi a esistente. Il lavoro  e stato corredato inoltre da una serie di test simulati e con il
robot in movimento, sia in ambienti esterni che interni, al  ne di veri care la corret-
tezza matematica degli algoritmi implementati e la loro applicabilit a a situazioni reali.
In ne, viene presentata una sezione conclusiva, nella quale si indicano i vantaggi e gli
svantaggi degli approcci seguiti e alcuni possibili sviluppi futuri del lavoro svolto.
2
Capitolo 2
Il Robot Caretta
In questo capitolo vengono descritte le nozioni di base da cui si  e sviluppato il lavoro.
Considereremo dapprima la struttura del robot Caretta da un punto di vista hardware
e meccanico, utilizzando questi dati come punto di partenza per alcune considerazioni
di tipo cinematico sulla possibilit a del robot di seguire particolari traiettorie, sull’iner-
zia che la sua massa comporta e sulle sue capacit a di non ribaltarsi in funzione della
sua geometria. Seguir a una sezione sul sistema ETHNOS, l’ambiente in cui  e stato
sviluppato gran parte del software implementato per la navigazione, con una breve de-
scrizione sul metodo di comunicazione adottato tra i vari oggetti all’interno del robot
che gestiscono i dati provenienti dai differenti sensori. In ne, si mostrer  a il sistema allo
stato in cui si trovava prima del nostro intervento, considerando quali parti del software
preesistente sono state riutilizzate su Caretta e quali invece sono state eliminate.
2.1 La struttura del robot
Il robot Caretta  e stato costruito dall’universit a di Genova nell’ambito di un proget-
to parzialmente  nanziato dall’ Agenzia Spaziale Italiana. La struttura  e stata pensata
per poter effettuare test in ambienti esterni e su super ci non necessariamente piane.
A bordo sono presenti due batterie da 12V per automobile collegate in serie per ali-
mentare i due motori indipendenti, a magneti permanenti, responsabili del movimento
delle due ruote posteriori. I motori sono alimentati a 24V in corrente continua e dotati
3
IL ROBOT CARETTA
di un encoder a 1024 tacche. Le quattro ruote del robot sono in gomma vulcanizzata,
in particolare le due motrici presentano un battistrada di 5mm per rendere pi u agevole
il movimento su terreni accidentati; mentre su super ci lisce e piane Caretta  e capace
di raggiungere la velocit a di 2m/sec, quando si trova su un terreno erboso la velocit a
massima  e circa dimezzata. Le ruote anteriori hanno una capacit a di sterzo di 360o
che permette a Caretta, in virt u del fatto che i motori sono indipendenti, di ruotare su
se stesso. Il robot  e largo 65cm e lungo 98cm con un peso di circa 40Kg senza equi-
paggiamento aggiuntivo a bordo. Data la forma, non esiste un effettivo limite di pitch
perch·e i motori non sono in grado di erogare la potenza necessaria per spingere Caretta
lungo pendii con pendenza superiore ai 50o; per quanto riguarda il roll dalle prove em-
piriche effettuate  e emerso un limite intorno ai 25o, spingendosi oltre tale valore non  e
pi u possibile mantenere una traiettoria rettilinea perch·e le ruote anteriori sono libere di
muoversi e trascinano il robot a valle. Nella  gura 2.1  e mostrato il robot in ambiente
esterno equipaggiato con l’inclinometro FAS-A di cui si parler a dettagliatamente nel
Capitolo 3 mentre in  gura 2.2 si pu o osservare Caretta con a bordo il sensore HOPS
trattato anch’esso nel capitolo successivo.
Figura 2.1: Il Robot Caretta Equipaggiato con inclinometro FAS-A
A bordo del robot  e presente un computer in formato pc104 con un processore
4
IL ROBOT CARETTA
Figura 2.2: Il Robot Caretta Equipaggiato con sensore omnidirezionale/fronale
intel celeron@500MHz ed un sistema operativo basato su kernel linux 2.2 installato
in una  ash memory per motivi di sicurezza; il computer  e dotato di una scheda di
rete da 10Mb con la quale comunica verso l’esterno e di una scheda di comunicazione
Echelon connessa con i controller dei motori. Per questioni di sicurezza  e presente
un pulsante di arresto immediato dei motori ed un joystick connesso anch’esso alla
scheda Echelon che permette di bypassare eventuali comandi errati mandati dall’ela-
boratore, riprendendo il controllo del sistema. Durante i nostri test  e stato installato
anche un alimentatore per PC in continua a 24V, responsabile di fornire la tensione di
12V al sensore di visione e all’inclinometro e di alimentare un secondo PC in formato
industriale con adattatore ATX: questo secondo computer  e delegato ai soli compiti di
acquisizione immagini ed elaborazione e verr a chiamato nel seguito barbone. Barbo-
ne  e dotato di processore intel Pentium III@800MHz, 256MB di sdRam Pc100, due
framegrabber basati su chipset Brooktree 878, due schede di rete da 100Mb connesse
a bridge e un disco  sso slim da 6.4GB; il sistema operativo installato  e Mandrake
5
IL ROBOT CARETTA
Linux 9.0.
2.2 L’ambiente di sviluppo
In questa sezione prenderemo in considerazione ETHNOS, l’ambiente software sul
quale abbiamo implementato tutto il sistema di navigazione e visione del robot Caret-
ta. Si mostreranno brevemente i concetti che lo ispirano e le peculiarit a; sar a inoltre
dato risalto al sistema di comunicazione in modo da rendere pi u agevole la lettura dei
successivi capitoli.
2.2.1 Il sistema Ethnos
Sotto l’acronimo ETHNOS si nasconde un’architettura sviluppata con l’intento di ri-
solvere problematiche legate alla progettazione di sistemi robot complessi nei quali sia
necessaria una coordinazione delle attivit a da svolgere. Tutto il sistema  e stato svi-
luppato in ANSI C++ sotto Linux (precisamente, sotto la distribuzione Red Hat 5.2
con Kernel 2.0.36) utilizzando primitive per la gestione delle thread. In particolare,
ETHNOS:
1. Garantisce la possibilit a di sviluppare diversi moduli interconnessi, fornendo un
protocollo di comunicazione tra i processi.
2. Sempli ca la progettazione di architetture real-time, occupandosi della schedu-
lazione dei processi.
3. Offre la possibilit a di distribuire il carico computazionale su calcolatori differenti
senza la necessit a di gestire direttamente la comunicazione.
Le entit a fondamentali nel sistema ETHNOS sono solamente due: il Kernel e gli
Esperti.
Un esperto  e un programma che esegue ripetutamente la stessa porzione di codice de-
stinata a risolvere uno speci co compito. Esso comunica con altri esperti grazie all’a-
iuto del Kernel, ed  e grazie a questo interscambio di dati che le varie attivit a necessarie
6
IL ROBOT CARETTA
al corretto funzionamento del robot vengono coordinate. Esistono tre differenti tipi di
esperti:
1. Periodici : eseguono il loro compito seguendo una precisa scadenza temporale
2. Sporadici : eseguono il proprio compito in seguito al veri carsi di taluni eventi
3. Di Background : eseguono il proprio compito solamente se non  e in esecuzione
un esperto appartenente alle prime due classi descritte
Esiste in ne un’ultima classe di esperti, detta di subscheduling, capace di schedu-
lare a sua volta esperti periodici o sporadici.
Il Kernel si interfaccia con lo scheduler del sistema operativo gestendo le priorit a degli
esperti e le loro comunicazioni. L’algoritmo di scheduling utilizzato  e il Rate Mono-
tonic, che imposta le priorit a dei processi in modo inversamente proporzionale al pe-
riodo, senza tuttavia considerare eventuali relazioni armoniche tra i periodi che ne au-
menterebbero l’ef cienza. La condizione di schedulabilit  a viene considerata attraverso
il fattore di utilizzazione del processore
U =
n
∑
i=1
Ci
Ti
< 0.69 (2.1)
dove con Ci si intende il tempo di esecuzione dell’esperto i-esimo, con Ti il suo
periodo. Dopo aver effettuato questo test di schedulabilit a, il Kernel passa il controllo
agli esperti che eseguono in modo sequenziale il codice a loro riservato.
La gestione della comunicazione avviene secondo una tecnica af dabile e trasparente,
effettuando un broadcasting dell’informazione. In particolare:
1. ogni esperto che vuole ricevere un certo messaggio ne fa richiesta al Kernel
2. ogni esperto che decide di condividere un messaggio lo passa al Kernel, senza
preoccuparsi di conoscerne la destinazione
Appare evidente come un interscambio di dati ef ciente sia legato alla suddivisione
dei messaggi in tipi, in altre parole una sorta di etichette legate ai dati da scambiare che
ne identi cano la funzione e il contenuto. Nel caso il sistema robot sia distribuito su
7
IL ROBOT CARETTA
pi u processori ETHNOS rende completamente trasparente il sistema di comunicazione
gestendolo attraverso uno scambio di dati tra i due kernel operanti su macchine distinte.
2.2.2 Gli Esperti
Gli esperti sono oggetti derivati dalla classe ETExpert contenente tre funzioni virtuali.
Per costruire un vero e proprio esperto, la classe derivata deve dunque contenere il
codice di tali funzioni. Esse sono:
1. Init() che contiene la procedura di inizializzazione (eseguita una sola volta).
2. DoYourDuty(int wc) che contiene il codice da eseguire ogni volta che il con-
trollo viene passato all’esperto. La variabile wc, durante la normale esecuzione
di valore nullo, viene passata a uno durante l’analisi di schedulabilit a.
3. Close() che contiene il codice da eseguire al termine dell’esecuzione (eseguita
una sola volta).
L’appartenenza dell’esperto alle classi prima indicate,  e determinata dai parametri
passati al costruttore della classe ETExpert e dalle operazioni effettuate nella funzione
Init(). In particolare:
1. Gli esperti periodici necessitano come parametro del costruttore il periodo di
attivazione in microsecondi.
2. Per gli esperti sporadici  e necessario speci care nel costruttore un tempo mini-
mo che deve intercorrere tra due esecuzioni successive e nella funzione Init() i
messaggi alla cui ricezione l’esperto deve attivarsi.
3. Per gli esperti di background si deve speci care nel costruttore che l’esper-
to deve avere la priorit a pi u bassa, estromettendolo in tal modo dall’analisi di
schedulabilit a.
L’esperto viene inserito nel sistema informando il Kernel della sua presenza tramite
la funzione AddExpert e attivato con ActivateExpert; da questo momento sar a il kernel
8
IL ROBOT CARETTA
stesso ad occuparsi di gestirne la schedulazione e la comunicazione con altri esperti.
I messaggi che l’esperto scambia con il kernel sono in genere costituiti da un header
in cui se ne indica tipo e lunghezza, seguito da un campo dati. Attraverso la classe
ETMessage  e possibile gestirne la creazione, la lettura e la scrittura.
Ogni esperto contiene una lista locale in cui sono presenti tutti i messaggi disponibili
al momento per la lettura. Ogni volta che il kernel riceve un messaggio di cui l’esperto
ha fatto richiesta, lo accoda a tale lista; sar a l’esperto stesso a decidere quali messaggi
leggere e quali scartare a seconda delle sue esigenze. Si noti che ETHNOS garantisce
solamente che ogni messaggio prodotto venga recapitato a tutti gli esperti che ne hanno
fatto richiesta, ma il coordinamento delle attivit a globali degli esperti non viene gestito
in alcun modo.
In ne, se si rendesse necessario un  tto scambio di dati a velocit  a elevata tra due
esperti, ETHNOS rende disponibile una comunicazione privilegiata tramite puntatori
che scavalca il protocollo basato sui messaggi precedentemente descritto.
2.2.3 Il Kernel
Il kernel deriva dalla classe C++ ETDispatch che fornisce le primitive per la gestione
degli esperti. Una volta chiamata la funzione DoYourDuty il sistema viene diretta-
mente controllato dal kernel e qualsiasi comunicazione con l’utente deve essere gestita
attraverso gli esperti, unici oggetti autorizzati a produrre e condividere messaggi.
Per capire se un insieme di esperti  e schedulabile, il kernel compie ripetute chiamate
alla funzione DoYourDuty di ogni esperto per avere un tempo approssimato di esecu-
zione e applicare l’algoritmo Rate Monotonic. Se l’insieme di esperti risulta essere
non schedulabile il kernel passa di nuovo il controllo al sistema operativo, altrimenti
d a il via alla sessione di lavoro di ETHNOS.
Il kernel deve:
1. Gestire in modo ef ciente gli esperti e coordinarne l’attivit  a.
2. Gestire in modo ef ciente lo scambio di messaggi, rendendo trasparente agli
esperti il sistema distribuito di cui fanno parte.
9
IL ROBOT CARETTA
Come gi a accennato, la comunicazione in ETHNOS  e di tipo broadcast piuttosto
che point-to-point. Per evitare rallentamenti e inutili occupazioni di memoria, tutti i
messaggi vengono immessi in un’area di memoria condivisa a cui gli esperti possono
accedere, ma che non possono modi care. Se si rendesse necessario modi care un
messaggio, l’esperto deve copiarlo nella sua lista locale.
In breve, esistono due tipi di liste:
1. Globale: di tipo condiviso, nella quale i messaggi sono memorizzati in modo
non omogeneo senza considerarne il tipo. Ogni volta che il kernel riceve un mes-
saggio controlla che qualche esperto ne abbia fatto richiesta. In caso affermativo
inserisce il messaggio in questa lista, altrimenti lo scarta a priori.
2. Locale: per ogni esperto, che contiene i riferimenti a quegli elementi della lista
globale che servono all’esperto.
2.3 Il Software preesistente
Il nostro software si innesta su una architettura ETHNOS preesistente realizzata all’U-
niversit a di Genova. Da questo punto di vista, nel corso della tesi sono stati inseriti
nuovi esperti capaci di interfacciarsi con i sensori studiati, scambiare informazioni
tra loro e interagire con gli esperti gi a presenti sul robot. La gerarchia del sistema
inizialmente si presentava come in  gura 2.3.
Tra le varie strade percorribili per modi care il software in modo che rispondesse
alle nostre esigenze,  e stata scelta quella che garantiva la massima libert a di azione:
sono stati mantenuti invariati gli esperti riguardanti l’interfaccia utente e quelli di con-
trollo diretto sui motori, mentre sono stati sostituiti integralmente tutti quelli relativi al
movimento del robot.
L’architettura ha dunque preso la forma di  gura 2.4.
Si noti che l’esperto BLINDNAV  e stato completamente sostituito e con esso XMO-
DEL. Il primo aveva il compito di gestire i movimenti del robot verso nuovi target,
il secondo quello di piani care una traiettoria da seguire per completare la missione
af data, ma senza considerare alcun tipo di ostacolo. La scelta di non utilizzare i due
10
IL ROBOT CARETTA
Figura 2.3: Il sistema prima del nostro intervento
Figura 2.4: Il sistema dopo il nostro intervento
11
IL ROBOT CARETTA
esperti  e stata dettata anche dalla volont a di costruire un sistema totalmente reattivo,
senza alcun tipo di piani cazione del moto, cosa che tali esperti non garantiscono.
I messagi all’esperto MOTION, responsabile della comunicazione con i motori, pri-
ma erano esclusivamente provenienti da XMODEL, mentre ora diventano dunque to-
talmente a carico dei nuovi esperti, che diventano i responsabili di qualsiasi tipo di
movimento impresso al robot.
I due sistemi si con gurano quindi in modo del tutto parallelo e indipendente.
2.3.1 Gli esperti preesistenti
Di seguito si elencheranno gli esperti che sono stati mantenuti dopo le nostre modi -
che, ognuno corredato da una sommaria spiegazione riguardo al suo funzionamento.
1. HOSTAPPL :  e responsabile dell’avvio di tutti i driver del sistema, nonch·e
del settaggio delle variabili di rete per il corretto funzionamento dei control-
lori ECHELON. Si tratta dell’esperto di livello pi u basso e non  e stato in alcun
modo modi cato. Il codice dell’esperto  e contenuto nel  le hostappl.C.
2. INTERFACER : questo esperto gestisce i comandi che l’utente pu o impartire
al robot attraverso un’interfaccia testuale. Inizialmente presentava solamente la
possibilit a di inviare comandi elementari di jog e speed oltre a nuovi target attra-
verso l’utilizzo degli algoritmi presenti negli esperti BLINDNAV e XMODEL;
in seguito  e stato pesantemente modi cato e reso in grado di dialogare con l’in-
terfaccia java realizzata per la tesi, rendendo cos tutto il sistema molto pi  u user
friendly. Il codice dell’esperto  e contenuto nel  le intcont.C.
3. MOTION :  e responsabile del dialogo diretto con i motori. Riceve messaggi
di tipo MOTIONRQST da INTERFACER e invia il corrispondente comando ai
controllori ECHELON. Si tratta di un esperto di basso livello e dunque non  e
stato necessario modi carlo per la nostra applicazione, se non nella rimozione
di un  ltro passabasso che, in realt  a,  e stato solamente sostituito da un altro
equivalente inglobato nei nostri esperti. Il codice si trova nel  le motion.C.
12
IL ROBOT CARETTA
4. LOCALIZE : questo esperto riceve le informazioni direttamente dai controllori
ECHELON sulla posizione corrente del robot e le invia al nostro esperto pi u
importante ADJPATH; in base alle informazioni ricevute, sar a quest’ultimo a
calcolare in modo reattivo la traiettoria che il robot dovr a seguire per evitare
eventuali pericoli. Il codice si trova nel  le localize.C
2.3.2 Organizzazione del sistema
La versione di ETHNOS utilizzata da Caretta  e la 4.8.8 compilata su una distribuzione
Red Hat 6.0 avente un kernel 2.2; poich·e ETHNOS non  e un sistema free  e stato ne-
cessario compilare il software su di una macchina equivalente, poich·e su distribuzioni
troppo differenti si veri cavano non solo problemi in fase di compilazione ma anche
problemi in fase di esecuzione aventi l’effetto di rendere il robot Caretta instabile. Per
compilare il sistema ci si  e dunque af dati ad una distribuzione Linux Mandrake 7.0
(Air) con un kernel 2.2 del tutto equivalente.
Da un punto di vista pratico, l’organizzazione delle directory  e stata lasciata del tutto
intatta, cercando di integrarsi il pi u possibile con il sistema gi a presente.
I  le eseguibili si trovano tutti nella directory bin, mentre gli esperti, a seconda del
loro compito, sono suddivisi in sottodirectory all’interno della cartella experts. Anche
gli esperti da noi aggiunti seguono la stessa logica d’ordine.
Il kernel di Caretta si avvale di alcuni importanti  le di con gurazione che sono sta-
ti attentamente modi cati perch ·e il sistema funzionasse adeguatamente. Tutti sono
presenti nella directory bin dell’albero precedentemente descritto. In particolare:
1. NVCONFIG.TBL : contiene particolari variabili di rete utilizzate dai control-
lori ECHELON. Teoricamente non sarebbe necessario modi carne il contenuto
in alcun modo;  e stato tuttavia riscontrato un problema che af igge il sistema
quando avviene un crash mentre si opera da remoto su  le system di rete: il
risultato  e la corruzione di tale  le che deve essere sostituito con una copia di
backup precedentemente salvata. Il problema era gi a presente prima delle nostre
modi che e comunque  e stato ritenuto di poco conto dato che il robot dovrebbe
13
IL ROBOT CARETTA
essere in grado di operare del tutto autonomamente.
2. DEFAULT.CNF : contiene i nomi di tutti gli esperti presenti nel sistema, indi-
cando al kernel quali attivare e quali no. Come gi a precisato, oltre agli esper-
ti sviluppati nel corso della tesi che descriveremo nel prossimo capitolo, sono
rimasti attivi solo gli esperti descritti in precedenza.
3. PERIODS.INI : contiene i periodi di attivazione di tutti gli esperti presenti nel
sistema in microsecondi.
Nella directory app/caretta si trova il codice principale dell’eseguibile, dal nome
staffapp.C; in particolare, la funzione di questo  le  e quella di kernel ETHNOS: de-
cide quali esperti mandare in esecuzione e quali invece estromettere dallo scheduling;
le principali modi che apportate ad esso riguardano l’inserimento dei nuovi esperti
immessi nel sistema.
All’avvio di ogni sessione ETHNOS si presenta all’utente un men u di scelta nel quale
l’applicazione chiede quali esperti avviare;  e possibile scegliere di effettuare un avvio
totale, con gurare manualmente il sistema dando conferma o diniego per ogni singo-
lo esperto presente su Caretta, oppure af darsi al  le DEFAULT.CNF, gi a descritto in
precedenza, settato in modo appropriato per la tesi, opzione che  e stata utilizzata nel-
la quasi totalit a del lavoro svolto. In ne, dopo che l’utente ha indicato a Caretta di
entrare in modalit a ETHNOS, viene effettuato il test di schedulabilit a dell’insieme di
esperti precedentemente scelto: se il test va a buon  ne Caretta  e pronto per una nuova
sessione di lavoro, altrimenti ETHNOS ripasser a il controllo al sistema operativo. La
 gura 2.5 mostra la distribuzione della struttura software del progetto.
14
IL ROBOT CARETTA
Figura 2.5: Distribuzione della struttura Software
15