Localizzazione e simultanea Localizzazione e simultanea mappatura nella navigazione mappatura nella navigazione robotica mediante Algoritmi robotica mediante Algoritmi

GeneticiGenetici

UNIVERSITÀ DEGLI STUDI DI TRIESTE FACOLTÀ DI INGEGNERIA Dipartimento di Elettrotecnica, Elettronica ed Informatica Tesi di Laurea in SISTEMI OPERATIVI

Laureando: Lorenzo Zampese

Relatore: Enzo MUMOLO

Correlatore: Massimiliano NOLICH

Anno Accademico 2007-2008

ObiettiviObiettivi

Creare ambiente di sviluppo/testing per Creare ambiente di sviluppo/testing per algoritmi di tipo Simultaneous Localization algoritmi di tipo Simultaneous Localization And MappingAnd Mapping

(SLAM) per robot mobili(SLAM) per robot mobili

Integrazione/test Genetic Look-up based Integrazione/test Genetic Look-up based AlgorithmAlgorithm for Scan Matching (Glasm) for Scan Matching (Glasm)

Sviluppo e test di un algoritmo per Sviluppo e test di un algoritmo per l’esplorazione e mappatura (ad esempio: l’esplorazione e mappatura (ad esempio: ricerca dei “varchi” tra gli ostacoli).ricerca dei “varchi” tra gli ostacoli).

Sviluppo del lavoroSviluppo del lavoro Installazione di un simulatore client-server di Installazione di un simulatore client-server di

robot mobili (Player-Stage) per testare robot mobili (Player-Stage) per testare algoritmi di tipo SLAM in ambiente Linuxalgoritmi di tipo SLAM in ambiente Linux

Creazione di un “client” SLAM per Player-Creazione di un “client” SLAM per Player-Stage,Stage,

integrazione di una libreria per Glasm, integrazione di una libreria per Glasm, implementazione algoritmo esplorazioneimplementazione algoritmo esplorazione

Analisi dati su prove “indipendenti”Analisi dati su prove “indipendenti”

Analisi mappe prodotte da esplorazioneAnalisi mappe prodotte da esplorazione

Il simulatore robotico Player Il simulatore robotico Player StageStage

ClientPLAYER

STAGE(mondi a 2D)

ROBOT REALE

GAZEBO(mondi a 3D)

tcp/udp

simulazione interfacce del robot

simulazione degli ambienti

Cliente

Programma scritto in- C- C++- Java- Pyton-…

Algoritmo di Scan MatchingAlgoritmo di Scan Matching

Ricerca trasformazione ottimale che Ricerca trasformazione ottimale che realizza la corrispondenza di un realizza la corrispondenza di un oggetto rispetto a un altro (locale e oggetto rispetto a un altro (locale e globale)globale)

Basata su ricerca corrispondenze tra 2 Basata su ricerca corrispondenze tra 2 scansioni di dati sensoriali quali laserscansioni di dati sensoriali quali laser

Applicazioni nella localizzazione dei Applicazioni nella localizzazione dei robot, e computer-visionrobot, e computer-vision

Algoritmo di Scan Matching: Algoritmo di Scan Matching: risultati sperimentalirisultati sperimentali

Esempio errori di localizzazione : Esempio errori di localizzazione :

Glasm e odometria RealeGlasm e odometria Reale

Esplorazione di ambienti Esplorazione di ambienti sconosciutisconosciuti

Problema 1Problema 1: ricostruire la mappa : ricostruire la mappa dell’ambiente dai dati sensoriali (laser)dell’ambiente dai dati sensoriali (laser)

Problema 2Problema 2: Localizzazione del robot : Localizzazione del robot all’interno dell’ambienteall’interno dell’ambiente

Problema 3Problema 3: come determinare il : come determinare il percorso utile per realizzare percorso utile per realizzare l’esplorazionel’esplorazione

Il modello cognitivo Il modello cognitivo utilizzatoutilizzato

SENSE ACTPLAN

Compiti dei blocchi:* Sense: Percezione* Plan: Modellazione-Pianificazione* Act: controllo motori

L'algoritmo di esplorazioneL'algoritmo di esplorazioneInizio

Esiste “varco” inesplorato ?

E’ la posizione di partenza ?

Fine

Back tracking

No

SiNo

Si

Scegli “varco” di ampiezza maggiore e che conduce il più

lontano possibile

Sposta robot

Registra dati(posizione, ambiente)

Risultati sperimentaliRisultati sperimentali Esplorazione con odometro ideale, e Esplorazione con odometro ideale, e

realereale

ConclusioniConclusioni

Il corretto funzionamento del Il corretto funzionamento del programma è stato verificato programma è stato verificato utilizzando diversi ambientiutilizzando diversi ambienti

Tutti gli algoritmi di scan-matching Tutti gli algoritmi di scan-matching hanno un “accumulo di errori”.hanno un “accumulo di errori”.

Glasm realizza la localizzazione con Glasm realizza la localizzazione con un errore inferiore rispetto ad altri un errore inferiore rispetto ad altri algoritmi, e può essere ulteriormente algoritmi, e può essere ulteriormente miglioratomigliorato

L’algoritmo di esplorazione proposto L’algoritmo di esplorazione proposto è validoè valido

IntroduzioneIntroduzione

Robotica e dispositivi mobiliRobotica e dispositivi mobili Molte possibilità di sviluppo, Molte possibilità di sviluppo,

aspettative e interesse tecnico aspettative e interesse tecnico scientificoscientifico

Un classico problema aperto: Un classico problema aperto: Simultaneous Localization And Simultaneous Localization And Mapping (SLAM)Mapping (SLAM)

La simulazione effettuataLa simulazione effettuata

nelle prove di local-scan-matching, nelle prove di local-scan-matching, Glasm migliora sensibilmente le Glasm migliora sensibilmente le stime odometrichestime odometriche

L’algoritmo di esplorazione realizza L’algoritmo di esplorazione realizza con successo la mappaturacon successo la mappatura

Il tipico problema dell’accumulo Il tipico problema dell’accumulo d’errori, richiede l’ottimizzazione nel d’errori, richiede l’ottimizzazione nel numero di spostamenti da compierenumero di spostamenti da compiere

Un Sistema roboticoUn Sistema robotico

PC

MicrocontrolloreSensore di prossimità

Sensore di temperatur

a

Sensore di contatto

Sensore di orientamen

to

Sensore odometrico

Attuatori

Sensori e attuatori (1)Sensori e attuatori (1)

SensoriSensori– Di prossimità (Ultrasonici, laser)Di prossimità (Ultrasonici, laser)– Di contatto (Bumper)Di contatto (Bumper)– Odometrici (Encoder ottici Odometrici (Encoder ottici

incrementali)incrementali) AttuatoriAttuatori

– Motori a corrente continuaMotori a corrente continua