Stanford Cart & CMU Rover Mariarosaria Ambrosino di Miccio50/54 Domenico Perfetto50/62 Corso di...

Stanford Cart & CMU Rover

Mariarosaria Ambrosino di Miccio 50/54Domenico Perfetto 50/62

Corso di Sistemi per il Governo dei Robot

Prof. E. Burattini

Giugno 2004

Mariarosaria Ambrosino di Miccio – Domenico Perfetto 2

Stanford Cart & CMU Rover

• Descrizione di Stanford Cart

• Esempi di esecuzione

• Discussione dei limiti e delle scelte progettuali

• Descrizione di CMU Rover

• Discussione sul progetto

• Idea di implementazione alternativa

Giugno 2004


Stanford CartStanford Cart è un progetto nato

nel laboratorio di Intelligenza Artificiale di Stanford nel 1973, il suo ideatore fu Hans P. Moravec.

Il progetto di Cart alla nascita è stato supportato dalla Defense Advanced Research Projects Agency, dalla National Science Foundation e dalla National Aeronautics and Space Administration e successivamente nel 1981 il progetto fu supportato dal Carnegie-Mellon University Robotica Institute.

Giugno 2004


Nicchia EcologicaCart si muove all’interno di un ambiente disordinato in cui sono posti ostacoli di varia natura.Il suo obiettivo è quello di raggiungere il “goal” evitando gli ostacoli che incontra nel suo tragitto, sulla base di un modello costruito grazie alle informazioni acquisite.Il percorso è sicuro per cammini brevi, ma lento: Cart si sposta di circa un metro ogni 10 - 15 minuti.

Giugno 2004


Subroutine Il programma che consente a Cart di spostarsi

all’interno dell’ambiente è organizzato in più subroutine:

• Interest Operator

• Correlator

• Camera Solver

• Navigator

Giugno 2004


Camera Calibration

nell’immagine rispetto alla loro posizione in un’ideale camera di lunghezza focale unitaria, e un altro polinomio che converte i punti da una camera ideale ai punti nell’immagine.Questi polinomi sono adoperati per rettificare le posizioni degli oggetti percepiti nelle successive immagini.

Il percorso di Cart inizia con la calibratura della camera. Il programma digitalizza l’immagine in un array di punti, localizzando i punti e le croci, e costruendo un polinomio bidimensionale che rappresenta la posizione dei punti

Giugno 2004


Acquisizione delle immagini (1)

Ogni volta che Cart si ferma il suo computer controlla l’itinerario e attiva un meccanismo che fa scorrere la camera catturando 9 immagini da sinistra a destra lungo un asse trasversale di 52cm, ad una distanza di 6.5 cm di spazio l’una dall’altra.

Giugno 2004


Acquisizione delle immagini (2)

1 2 3

4 5 6

7 8 9

Giugno 2004


Memorizzazione delle immaginiOgni immagine digitalizzata nel codice visivo di Cart, è registrata insieme ad una piramide di immagini, formata da miniature della figura originale: partendo dall’immagine iniziale si crea la miniatura le cui dimensioni linearisono ridotte per potenze di due facendo la media di 4 pixel in uno, si procede allo stesso modo partendo da questa immagine ridotta creandone una seconda ancora più piccola, continuando fino ad arrivare al vertice della piramide con una dimensione fissata.

Giugno 2004


Interest Operator (1)

L’interest operator si occupa della localizzazione di parti di immagini chiamate features.

Una feature è un punto in un mondo tridimensionale, che viene individuato esaminando ampie zone di punti nelle immagini.

La feature è giudicata “buona” se può essere localizzata in modo non ambiguo in differenti viste di una scena.

Giugno 2004



L’interest operator sceglie 30 o più features all’interno di un’immagine: l’idea è di selezionare un insieme di features “buone” relativamente uniformi nell’immagine, così che alcune di esse possano essere selezionate su ogni oggetto visibile mentre altre, le cui aree sono prive di struttura o hanno dei bordi semplici, sono scartate.

La varianza direzionale viene misurata su piccole finestre quadrate: viene calcolata la somma della differenza dei quadrati dei pixel adiacenti per le quattro direzioni (orizzontale, verticale e le due diagonali) per ogni finestra, e la misura di interesse delle finestre è il minimo di queste quattro somme.

Le features sono scelte laddove la misura di interesse ha un massimo locale.

Giugno 2004



Giugno 2004



Quando una feature è scelta, il suo aspetto viene memorizzato con una serie di immagini selezionate dalla sequenza delle immagini ridotte.

Da ogni figura ridotta viene estratta una sottoimmagine 6x6 contenete il massimo locale della misura di interesse (la feature). Dato che le immagini ridotte hanno un livello di risoluzione sempre meno dettagliato salendo lungo la piramide avremo che l’immagine sul vertice copre un angolo di visuale più ampio con una risoluzione minore rispetto a tutte le altre; scendendo di un livello rispetto al vertice la risoluzione dell’immagine risulterà raddoppiata avendo un livello di dettaglio maggiore. Continuando in questo modo avremo che alla base della piramide il livello di risoluzione è molto alto e l’angolo di visuale è diminuito, otteniamo così uno zoom della feature.

Giugno 2004



Il risultato finale è una serie di immagini 6x6, che iniziano con una confusa interpretazione dell’intera immagine, gradualmente zoomate in espansioni lineari delle immagini che danno il primo piano netto della feature.

Giugno 2004


CorrelatorIl Correlator permette di conoscere la collocazione in tre

dimensioni delle features dalle loro posizioni in due dimensioni in due o più immagini.

Data una descrizione della feature prodotta dall’interest operator da un’immagine, il Correlator trova il miglior match con un’immagine diversa da quella di partenza: l’area presa in considerazione può essere sia l’intera immagine che una piccola parte di essa.

La strategia di riduzione delle immagini inizia al livello di riduzione 16, in questo livello la finestra 6x6 copre circa un settimo dell’area totale dell’immagine. La zona di descrizione 6x6 è spostata pixel per pixel sull’immagine di destinazione 16x16, ed il coefficiente di correlazione è calcolato per ogni posizione di prova. La posizione che fa il miglior match è memorizzata. Si prosegue trovando il miglior in tutte le immagini fino ad arrivare all’immagine nella dimensione originale.

Giugno 2004


Slider Stereo (1)

in tutte le nove immagini: esso considera ognuna delle 36 possibili coppie di immagini (9 valori presi due alla volta) e registra la distanza stimata della feature in un istogramma. Ogni misurazione aggiunge una piccola curva normale all’istogramma. La bontà della feature è indicata dall’ampiezza del picco nell’istogramma: se il picco è situato sotto una certa soglia la feature è scartata.

Dopo il passo di correlazione il programma “conosce” la posizione della feature

Giugno 2004


Slider Stereo (2)

Giugno 2004


Motion StereoLo slider stereo determina la distanza delle features per

determinare la nuova posizione di Cart, a questo passo il programma conosce la nuova posizione in 3D delle features relative alla camera, dalla vecchia alla nuova posizione.

Il programma elimina i match incorretti nelle correlazioni creando una matrice in cui l’elemento (i, j) è il valore assoluto della differenza, in termini di distanza, tra i punti i e j nel primo e nel secondo sistema di coordinate diviso per l’errore atteso. Ogni riga di questa matrice è sommata, dando un’indicazione di come ogni punto sia in disaccordo con tutti gli altri punti. L’idea è che le posizioni corrette siano in accordo con tutte quelle corrette e in disaccordo solo con quelle sbagliate.

Il punto peggiore è cancellato, e i suoi effetti sono rimossi dai rimanenti punti nelle somme delle righe. Questo pruning si ripete fino a quando l’errore peggiore rientra nei limiti dell’errore atteso. Dopo il pruning, il programma ha un numero di punti che va da dieci a venti che sono memorizzati nel suo modello del mondo

Giugno 2004


Path Planning (1)

Il sistemo visivo di Cart modella gli oggetti come un semplice insieme di features. Se sono trovate abbastanza features su ogni oggetto questo modello è adeguato per pianificare un percorso che gli consenta di arrivare alla destinazione senza collisioni. Le features nel modello tridimensionale di Cart possono essere pensate come delle ellissoidi fuzzy, le cui dimensioni riflettono l’incertezza del programma relativa alla loro posizione. Tutti gli oggetti visibili sono modellati come insiemi di sovrapposizioni di ellissoidi approssimate a cerchi per semplificare il problema.

Giugno 2004


Path Planning (2)

Il programma converte il problema nella ricerca di un percorso minimo all’interno di un grafo. Un percorso ottimo consiste o nel creare un tragitto rettilineo fra la partenza e la destinazione oppure nel realizzare una serie di segmenti tangenziali tra i cerchi e gli archi connessi.

La distanza minima in questo spazio può essere trovata con un algoritmo la cui complessità è O(n3).

Tale procedura spesso fa un’approssimazione rapida di ogni ostacolo in soli due vertici: uno per ogni direzione della circumnavigazione.

Il percorso riportato sul grafo consiste di semplici linee connesse da archi tangenti, questo tipo di percorso è adatto a Cart, che è in grado di sterzare allo stesso modo di un’automobile.

Giugno 2004


Path ExecutionUna volta che il percorso per giungere alla destinazione è stato

scelto, una parte di esso viene eseguita inviando i comandi a Cart.

La routine di esecuzione del path esegue 75 cm del percorso e poi si arresta. L’immagine vista dalla camera fa una panoramica da un lato all’altro del campo visivo. Cart ha un ampio obiettivo angolare che copre orizzontalmente 60 gradi. I 75 cm, combinati con il limite radiale per la sterzata (5 m) di Cart, risulta uno spostamento massimo del campo visivo di 15 gradi, un quarto dell’intera immagine.

Alla fine il programma calcola un percorso che porta a termine questo movimento con due archi di raggio uguale ma di differente lunghezza: la traiettoria risultante ha generalmente una forma ad “S”. A partire da questa traiettoria vengono generati i movimenti dei motori. Il programma poi adopera un simulatore per prendere in considerazione la risposta motoria di guida e di sterzata, per raffinare iterativamente la soluzione

Giugno 2004


Esperimenti

Giugno 2004


Esempio di un percorso di Cart (1)

Cart

Campo Visivo 60° Features

Goal

Giugno 2004


Esempio di un percorso di Cart (2)

Giugno 2004


Cart Testing

D:\Documenti\Universit<E0>\Robot\Relazione\Cart.final2.mov

Giugno 2004


Problemi (1)

• Oggetti in movimento durante la pianificazione

• Oggetti in movimento durante lo scatto delle foto

• Oggetti lucidi o riflettenti

• Oggetti trasparenti

• Oggetti dello stesso colore parzialmente sovrapposti

• Oggetti dello stesso colore dello sfondo

Giugno 2004


Problemi (2)

• Fallisce se gli elementi sono privi di dettagli ad alto contrasto

• Evidenzia poche Features per ogni oggetto• La variazione della luminosità determina un cattivo

funzionamento• Piccoli errori nelle misurazioni creano errori irreversibili• Se gli oggetti escono fuori dal campo visivo possono

essere “dimenticati”• Concetto di autonomia assente• Mancanza di altri sensori• Incapacità di ripresa dopo un errore • Pochi esperimenti• Esperimenti troppo simili• Raggio di sterzata troppo elevato

Giugno 2004


CMU RoverDopo le scarse prestazioni ottenute da Stanford Cart, il

team di Hans P. Moravec iniziò a sviluppare un sistema di robot mobile molto elaborato grazie a un contratto dell’Ufficio di Ricerche Navali.

Il progetto CMU Rover si focalizza quindi nel creare robots con ampie capacità locomotive e che usassero la visione.

Rover era il nome del primo robot sviluppato dal gruppo del CMU nell’ambito di tale programma.

Successivamente CMU Rover divenne il nome del progetto stesso e il robot fu ribattezzato Pluto.

Giugno 2004


Pluto: Specifiche (1)

La forma, dimensione, sistema di guida e le capacità elaborative on-board e esterne di Rover sono scelti per massimizzare la flessibilità del sistema.

• 3 ruote sterzanti individualmente per dargli 3 gradi di libertà nel piano.

• Una TV Camera montata su un supporto regolabile, basculante e scorrevole.

• Sonar a lungo raggio; Sonar a infrarosso a corto raggio e Bumper disposti intorno al robot.

• Shaft Encoder (uno per ogni ruota) con la risoluzione di 1/4000 di giro.

• Una antenna radio.• Una stazione fissa di elaborazione.

≈ 1

metr

o

≈ 55 cm

90 Kg

Giugno 2004


Pluto: Specifiche (2)

Rover è assemblato su 3 livelli:1. Ruote2. Motori e Sensori3. Componenti Elettronici (Processori)

Le elaborazioni on-board e il controllo dell’hardware sono affidate a una serie di processori, ad ognuno dei quali è affidato un compito specifico.Ogni motore è dotato di un processore Motorola con della RAM Hitachi (CMOS per ridurre i consumi). I motori sono controllati operando una modulazione di fase e di ampiezza.La stazione di elaborazione fissa è costituita da un host computer VAX 11/780, un array di processori ST-100 (100 milioni di op. f.p. /sec) e da un dispositivo per acquisizione e generazione di dati analogici ad alte prestazioni appositamente progettato.

Giugno 2004


Architettura GerarchicaLa struttura elaborativa di Pluto può essere rappresentata sfruttando

l’architettura deliberativa proposta dal Rensselaer Polythecnic Istitute che prevede una gerarchia a tre livelli: Organization, Coordination e Execution

Questo approccio è molto interessante perché evidenzia il principio della specializzazione dei moduli man mano che si discende lungo la gerarchia e mostra il semplice schema di comunicazione tra i moduli appartenenti ai vari livelli.

Giugno 2004


Architettura di RoverNell’organization level saranno eseguiti i compiti a più alto livello: pianificazione, interpretazione delle immagini, rappresentazione del mondo e pianificazione dei percorsi.

Il coordination level integra i vari sottosistemi hardware e sono eseguiti i compiti di coordinamento dei sensori e degli attuatori dalle unità (Controller, Simulator e Conductor).

Nell’execution level ci sono i

moduli che gestiscono e manovrano

direttamente l’hardware.

Giugno 2004


Unità elementari (1)

Nell’execution level ci sono le unità dedicate al controllo a più basso livello dell’hardware.

Comunication si occupa della comunicazione con la stazione fissa che esegue le computazioni più onerose.

Sonar controlla i sonar Polaroid che circondano il robot permettendo la navigazione evitando gli ostacoli.

Camera controlla i movimenti del supporto della Tv camera che manda le immagini alla stazione fissa.

Giugno 2004


Unità elementari (2)

Il modulo Utility controlla lo stato di “salute” del robot monitorando parametri vitali come il livello di carica delle batterie e la temperatura dei motori. Inoltre Utility controlla anche la potenza di quei sistemi che sono definiti non essenziali come la TV camera e il trasmettitore.

Proximity gestisce l’ultima linea di difesa contro le collisioni utilizzando i sonar IR a corto raggio e i bumper.

Giugno 2004


Elaborazioni on-boardI motori sono assistiti dal Conductor che li coordina per

ottenere i movimenti del robot desiderati.Il Simulator accede agli shaft encoders e mantiene una

stima della posizione del robot istante per istante.

I risultati della simulazione sono comparati nel Conductor con la posizione desiderata prodotta dal Controller. Il Conductor aggiusta le velocità e le posizioni dei motori nel tentativo di portare il Simulator in linea con la posizione richiesta dal Controller.

Giugno 2004


Elaborazioni ad alto livelloL’elaborazione ad alto livello, eseguita dalla base fissa, è effettuata in maniera pressoché identica a Stanford Cart. A parte alcuni perfezionamenti negli algoritmi, sono promessi progressi dovuti quasi esclusivamente all’hardware.

Cart impiegava fino a 15 minuti per pianificare l’avanzamento di circa un metro.

Questo tempo può essere suddiviso in tre intervalli approssimativamente uguali:1. II primi cinque minuti sono necessari per digitalizzare, pre-trattare e

inviare alla base fissa le nove immagini acquisite dalla TV camera.2. I secondi cinque minuti sono spesi per i compiti di visione a basso

livello, riducendo e filtrando le immagini. In seguito vengono applicati gli operatori Interest e Correlator e effettuato il pruning dei risultati.

3. Gli ultimi cinque minuti sono sfruttati per compiti di alto livello come il mantenimento del modello del mondo, pianificazione del percorso e la generazione della documentazione grafica di ciò che il programma “pensa”.

I tre intervalli di elaborazione sono ora ridotti

rispettivamente a meno di un secondo, circa tre

secondi e a pochi secondi, per un tempo totale

di circa 10 secondi contro i quindici minuti di

Cart.

w

Proprio in queste ultime operazioni c’è l’unico miglioramento software sostanziale nell’algoritmo di minimo percorso che ora sfrutta la sparsità della matrice degli archi del grafo.

Giugno 2004


Considerazioni sull’architettura

w

Si può notare che i due livelli più bassi (Coordination e Execution) sono implementati sul robot e tutti i loro elementi comunicano attraverso una linea seriale condivisa con una velocità di 256 kiloboud. Il livello più generale è implementato sulla base fissa di elaborazione. Questa situazione fa sì che i livelli Organization e Coordination comunichino attraverso l’antenna, cioè è il modulo Comunication che si occupa di “portare” le informazioni dal livello Organization al livello Coordination.

Giugno 2004


Analisi Condizioni (1)

TASK:

• Il compito del robot è di raggiungere un punto nell’ambiente definito “Goal” partendo da un punto qualsiasi della sua nicchia ecologica.

• Il goal deve essere descritto in qualche modo in base alle caratteristiche distintive riconoscibili dal sistema percettivo del robot.

• Prendendo come riferimento il progetto di Moravec verrà considerato il caso in cui viene data al robot una posizione relativa del goal. Per un caso più generale sarà considerato l’eventualità che ciò non avvenga, cioè che il robot non abbia nessuna informazione sulla posizione del goal.

Giugno 2004



ROBOT:

• Piattaforma di Pluto: una TV Camera, dei sonar, dei sensori InfraRosso a corto raggio, dei bumper e shaft encoder.

• Sistema motorio: tre motori indipendenti collegati a tre ruote.

• Moravec non ci fornisce informazioni su come sono distribuiti i sonar e gli altri sensori, ma dato il sistema di movimento di cui è dotato il robot supponiamo di disporre 8 sonar intorno al robot (uno ogni 45°), così come i bumper. 8 sensori IR a corto raggio vengono disposti come i sonar ma sfasati di 22,5°.

Giugno 2004



AMBIENTE:

• Il robot si muove in una stanza senza particolari limitazioni.

• Ostacoli presenti nell’ambiente facilmente distinguibili dal goal dato che è previsto un sistema di elaborazione della visione a basso livello on-board.

• Se il robot conosce una stima della posizione relativa del goal, si può pensare di provare il robot in un ambiente composto anche da stanze diverse.

w

(Esempio: se si usa il colore come discriminante gli ostacoli non devono essere di colori simili al goal; lo stesso per la forma.).

Giugno 2004


Architettura ReattivaAlla luce di queste condizioni sembra adeguata un’architettura

reattiva, i cui behavior sono coordinati adoperando i campi di potenziale.

Giugno 2004


Descrizione Behavior (1)

Collide ( Sensors_Array ) Releaser: Always On

Percept: Collision

Perceptual Schema: Read_Collide( Sensors_Array )

Motor Schema: Stop_Robot( Collision )

RunAway ( Sensor ) Releaser: Always On

Percept: Obstacle_AngleObstacle_StrenghtRotation__Verse

Perceptual Schema: Extract_Obstacle( Sensor )Rotation( MoveToGoal.GetGoalAngle() )

Motor Schema: PFields.Repulsion( Obstacle_Angle, Obstacle_Strenght )PFields.Tangential( Obstacle_Angle, Obstacle_Strenght, Rotation_Verse )

Giugno 2004



NoStopping ( ) Releaser: Always On

Percept: VObstacle_AngleVObstacle_StrenghtRotation__Verse

Perceptual Schema: VObstacle( )Rotation( MoveToGoal.GetGoalAngle() )

Motor Schema: PFields.Tangential( VObstacle_Angle, VObstacle_Strenght, Rotation_Verse )

MoveToGoal ( Goal_Description , [Goal_Position_Valued] ) Releaser: Always On

Percept: Goal_AngleGoal_Strenght /* Costant */Toward_Goal

Perceptual Schema: Extract_Goal( Goal_Description, [Goal_Position_Valued] )Is_Goal_Near ( Goal_Description, [Goal_Position_Valued] )

Motor Schema: PFields.CostantAttraction( Goal_Angle, Goal_Strenght, Toward_Goal )

Giugno 2004



Goal ( Goal_Description ) Releaser: Always On

Percept: Goal_Achieved

Perceptual Schema: Verify_Goal( Goal_Description )

Motor Schema: Victory_Behavior( Goal_Achieved )

Giugno 2004


Campi di Potenziale: Repulsivo

PFields.Repulsion( Obstacle_Angle, Obstacle_Strenght )

If (Obstacle_Strenght > MINSTRENGHT)Vector.Direction = Obstacle_Angle + 180°Vector.Magnitude = Obstacle_Strenght –

MINSTRENGHTElse

Vector.Magnitude = 0End If

Return Vector;

Giugno 2004


Campi di Potenziale: Tangenziale

PFields.Tangential( Obstacle_Angle, Obstacle_Strenght, Rotation_Verse )If (Obstacle_Strenght > MINSTRENGHT)

If (Rotation_Verse = Dx)Vector.Direction = Obstacle_Angle + 90°

ElseVector.Direction = Obstacle_Angle - 90°

End IfVector.Magnitude = Obstacle_Strenght –

MINSTRENGHTElse

Vector.Magnitude = 0End If

Return Vector;

Giugno 2004


Campi di Potenziale: AttrattivoPFields.CostantAttraction( Goal_Angle,

Goal_Strenght, Toward_Goal )If (Goal_Strenght > 0)

Vector.Direction = Goal_AngleIf (Toward_Goal =0)

Vector.Magnitude = MAXSTRENGHTElse

Vector.Magnitude = K * MAXSTRENGHTEnd If

ElseVector.Magnitude = 0

End IfReturn Vector;

Giugno 2004


Esempi (1)

Goal

Ostacolo

Robot

Giugno 2004


Esempi (2)

Goal

Ostacolo

Robot

Giugno 2004


Esempi (3)

Goal

Ostacolo

Robot

Giugno 2004


Considerazioni su Rover• La piattaforma di Rover sembra molto adeguata per

un sistema robotico reattivo.

• Non abbiamo prove che Pluto sia stato effettivamente realizzato.– il coordinamento dei motori e delle ruote crea problemi.– è instabile ed è soggetto a oscillazioni incontrollate e

“pericolose”.

• Contestabile la scelta progettuale di non aver nessuna gestione della visione on-board .

• Limitata autonomia

Giugno 2004


Bibliografia[1] “The Stanford Cart and The CMU Rover” – Hans P. Moravec – The

Robotics Institute Carnegie-Mellon University (Pittsburgh) – February 1983

http://www.frc.ri.cmu.edu/~hpm/project.archive/robot.papers/1983/ieee83.mss

[2] “Three Degrees for a Mobile robot” – Hans P. Moravec – The Robotics Institute Carnegie-Mellon University (Pittsburgh) – February 1984

http://www.frc.ri.cmu.edu/~hpm/project.archive/robot.papers/1984/asme84.mss

[3] “Towards Autonomous Vehicles” – H.P. Moravec et al. -The Robotics Institute Carnegie-Mellon University (Pittsburgh) – June 985

http://www.frc.ri.cmu.edu/~hpm/project.archive/robot.papers/1984/rr84.mss

[4] “Robots that Rove” – H.P. Moravec et al. -The Robotics Institute Carnegie-Mellon University (Pittsburgh) – August 1985http://www.frc.ri.cmu.edu/~hpm/project.archive/general.articles/1986/rove2.mss

[5] “Behavior-Based Robotics” – Ronald C. Arkin – The MIT Press, Cambridge (Massachusetts) – Book 1998

[6] Appunti corso di “Sistemi per il Governo dei Robot” – Prof. Ernesto Burattini – Università degli studi di Napoli Federico II - 2004







http://www.frc.ri.cmu.edu/~hpm/project.archive/general.articles/1986/rove2.mss







Stanford Cart & CMU Rover Mariarosaria Ambrosino di Miccio50/54 Domenico Perfetto50/62 Corso di...

Documents

Transcript of Stanford Cart & CMU Rover Mariarosaria Ambrosino di Miccio50/54 Domenico Perfetto50/62 Corso di...