Alcuni concetti chiave del corso di robotica

APPROCCIO CONTINUO

Michele Piffari – V Anno ROBOTICA – A.A. 19/20

Questo rappresenta il cosidetto certainity grid, a cui si assegna, ad ogni posizione

continua un valore (certainty value) continuo di probabilità.

Per semplificare l’approccio, si va a discretizzare in celle (occupancy grid) il campo

visivo, assegnando ad ognuna un certo valore di probabilità.

Il modello probabilistico, prevede, come primo approccio, semplice ma comunque

,

efficace, di assegnare una distribuzione normale a quelli che sono i parametri

dove il primo rappresenta la distanza misurata dal sonar, mentre il secondo

rappresenta lo spostamento angolare rispetto all’asse a 0° passante per il sonar. Questi

parametri presentano un’incertezza intrinseca, la quale viene definita tramite valori di

varianza , ottenuti sperimentalmente tramite misurazioni dal costruttore del

sonar. In questo modo possiamo definire la probabilità come una funzione gaussiana

rappresentabile in funzione di questi due parametri appena esposti

1 1 − 0−

(|, ) = exp +

{− ( ) ( )}

2 2

2 2

→ ( )

Dove z e 0 ricoprono il ruolo di “valore medio”.

Se vogliamo invece andare ad utilizzare l’occupancy grid, possiamo usare il concetto

che sta alla base del teorema di Bayes, per poter così aggiornare il valore di probabilità

di occupazione di ogni singola cella, con l’arrivo di ogni nuova misurazione.

(|) ∙ ()

(|) = ()

Nel nostro caso, esso diventa (|) ∙ ()

( |) = ()

Ovviamente, se la cella in esame contiene un valore pari ad 1, essa non verrà

aggiornata con l’arrivo delle nuove misure.

Un altro approccio realizzabile per la creazione di occupancy map, è quello indicato con

il nome di quadtree. In sostanza si tratta di andare a creare alberi di occupazione:

partendo da una mappa con indicati i punti in cui è presente un ostacolo o meno, la si

divide in tante celle, il cui numero dipende dalla precisione che si intende ottenere

Michele Piffari – V Anno ROBOTICA – A.A. 19/20

(tenendo conto che maggiore precisione implica una maggiore profondità del grafo e

conseguente aumento della complessità computazionale).

Una volta ottenuto la divisione in cella dell’ambiente possiamo sintetizzare la mappa di

occupazione con un albero, a cui assegnamo il valore 0 alle celle free (F) mentre diamo

il valore 1 alle celle occupied (O). In questo modo la codifica dell’ambiente diventa

semplice e si può riportare la mappa come una sequenza di 0-1: si parte dal nodo root e

si scende fino alle foglie, andando da sx verso dx.

Si può semplificare la codifica, riducendo il numero di bit necessari, andando ad

utilizzare una rappresentazione a 2 bit:

▪ →

00 cella non ancora visitata (unknown)

▪ 01→cella libera

▪ 10→ cella occupata

▪ 11→combinazione non utilizzata

In questo modo possiamo codificare in maniera più efficiente lo spazio degli stati. Un

possibile ulteriore miglioramento potrebbe essere quello di inserire un quarto stato,

quello di parent corrispondente alle combinazione 11: i nodi che si trovano in questo

stato, indicano che sono presenti figli occupati, ovvero che possono essere

ulteriormente decomposti, sempre in base alla massima profondità a cui posso arrivare

all’interno del grafo.

Risulta ovvio che se:

▪ Il nodo padre è unknown (U) anche i nodi figli lo saranno, e quindi basta

codificare solamente una coppia == per il nodo padre e sapremo che tutti i figli

saranno unknown (risparmio nella codifica).

▪ Se il nodo padre è free(F) saranno free anche i nodi figli ovviamente, e quindi

posso evitare di codificare tutti i nodi figli di un nodo free, ma limitarmi a

codificare solamente il nodo padre.

o Mappe topologiche

Questa tipologia di mappatura basa le sue caratteristiche sull’utilizzo di un grafo

composta da nodi e archi: nello specifico i nodi rappresentano luoghi con

caratteristiche che permettono di distinguerli da altri luoghi, mentre gli archi indicano il

percorso di collegamento da un punto della mappa (=nodo) all’altro.

Lo si definisce mapping topologico per via del tipo di approccio che si segue: il classico

approccio nel mapping è quello di utilizzare misure sensoriali per poi costruirsi una

mappa geometrica dalla quale ricavare le caratteristiche topologiche dell’ambiente

stesso.

→ → ℎ ℎ

Con l’approccio nodi-archi invece, abbiamo che prima si ricava una struttura topologica

della mappa, data dall’andare ad individuare luoghi “chiave” e distinguibili

nell’ambiente: una volta trovati questi luoghi e uniti si crea la mappa geometrica,

grazie alle informazioni metriche ottenute dal movimento del robot, sempre in

riferimento ad un sistema di riferimento “world”.

→ →

Si tratta quindi di una continua alternanza path following e hill climb

▪ →

Path following per andare a spostarsi, in maniera rettilinea o meno, da un

luogo distintivo all’altro

Michele Piffari – V Anno ROBOTICA – A.A. 19/20

▪ →

Hill climb si definisce ogni luogo in funzione di un certo numero di features

che permettono di discriminare un luogo da un altro che è differente; un

esempio di feature utile potrebbe essere la distanza da un punto comune. In

questo modo, massimizzando questo insieme di features, saremo in grado di

differenziare i luoghi uno dall’altro, così da avere un criterio di scelta per

definire quali sono i nodi topologici. Ovviamente si tratta di una

massimizzazione locale, poiché il robot si trova a massimizzare solamente in

una zona circoscritta dalla sua visuale.

Localizzazione del robot

- Si è visto come, durante la costruzione di mappe dell’ambiente, risulti essere molto importante

localizzare il robot, per poter associare ad ogni “immagine” presa dall’ambiente, un punto nello

spazio ben preciso, sempre in riferimento ad un sistema di riferimento fisso.

Quindi è molto importante la tematica relativa alla localizzazione del robot.

- È importante anche evidenziare che nell’analisi della localizzazione del robot, è importante

andare a distinguere

o Localizzazione assoluta: espressa sempre rispetto ad un sistema di riferimento globale

o Localizzazione relativa: espressa rispetto alla posizione di partenza del robot

Ogni posizione/angolo/coordinata sarà sempre espressa rispetto ad un sistema di riferimento

definito (che sia quello globale o quello locale).

→ ↑ , →↓

- Possiamo riconoscere due filoni principali.

Localizzazione basata su mappa (Monte Carlo Localization)

- Posso avere a disposizione una mappa di qualsiasi tipo:

o Geometrica

o Topologica

o Occupancy grid

- Errore cumulativo: come si evidenzia nel dead reckoning, potremmo utilizzare il calcolo

odometrico per andare a definire la localizzazione del robot, essendo noto il punto di partenza.

Ma, come ben sappiamo, un approccio di questo tipo è soggetto ad un forte errore cumulativo,

che deve essere limitato.

- Inoltre abbiamo un modello molti a uno (sensor aliasing) dei sensori: questo significa che un

sensore può ricevere in input percezioni uguali relative però a localizzazioni differenti. Questo

ci fa capire come non sia possibile utilizzare solamente una misura per indicare e specificare la

localizzazione del robot, proprio pre la non univocità delle misure. È quindi necessaria una

sorta di sensor fusion, in cui, per ottenere la localization del robot, andiamo a fondere più

informazioni. È concettualmente uguale a quello che fa l’essere umano: potrebbe trovarsi in

due stanza bianche uguali, per esempio, ma, ricordando il percorso che ha fatto per arrivarci,

sarebbe in grado di localizzarsi diversamente, e catalogare le stanze come effettivamente

differenti.

- è proprio questo il caso in cui, unitamente al calcolo odometrico, si utilizzano le letture

sensoriali incrociate con le conoscenze a priori derivanti dal fatto che la mappa sia nota.

- Approccio probabilistico è necessario

- L’approccio MC localization può così essere schematizzato:

Michele Piffari – V Anno ROBOTICA – A.A. 19/20

- L’approccio alla localizzazione basata su mappa prevede quindi degli step sequenziali, che

sostanzialmente sono mirati all’aggiornamento delle proprie “belief”, per andare a ridurre

quello che è l’errore cumulativo. L’idea base è che la movimentazione vada ad incrementare

l’errore, mentre le letture sensoriali vadano a ridurlo: è il concetto di

o

Action model —> si aggiorna lo stato allo stato usando l’azione compiuta

+1

o

See model —> si aggiorna lo stato allo stato usando la percezione dei sensori

+1

- Ecco quelli che sono i 5 passi da portare avanti nell’approccio MC:

o Calcolo odometrico

In questo contesto andiamo ad eseguire un update discreto dell’odometria del robot

(posizione e orientamento).

Possiamo ricavare il differenziale di spostamento come

Si parte da

= , = , = à ,

= à

+ = 2 = 2

= ( + ) , = ( − ) {

− =

2 2

Dalla prima equazione ricaviamo che +

= 2

Noi cerchiamo lo spostamento infinitesimo

= ∫ = ∫ ( ) + ∫ ( )

2 2