Robot Planning
Esplorazione di ambienti sconosciuti
Alessandro Santuari
Il problema
Esplorare e mappare un ambiente
sconosciuto utilizzando un robot.
Utilizzare un algoritmo efficiente
tenendo conto delle limitazioni del
robot: sensori, memoria, capacità di
movimento…
Applicazioni
Oggi vengono utilizzati per esplorare
reti informatiche o per costruire una
mappa di un sito web.
In futuro potremo utilizzare questi robot
per ottenere mappe di sistemi idraulici,
caverne inesplorate…
L’ambiente
Il robot non può utilizzare direttamente
le informazioni provenienti dai sensori
(es. telecamere, sensori di distanza…)
Occorre un metodo per astrarre ed
evidenziare le informazioni importanti.
Bisogna creare un modello semplificato
dell’ambiente.
Il modello dell’ambiente
A seconda delle applicazioni vengono utilizzate strategie
differenti per creare un modello dell’ambiente.
Il nostro approccio consiste nel modellare l’ambiente
come un grafo dove il robot può muoversi solo lungo
gli archi.
Altri modelli si basano su forme geometriche, ad
esempio l’ambiente può essere visto come un
“terreno” con ostacoli poligonali.
Esempio di ambiente
Modellato con forme geometriche
Modellato come un grafo
Il modello dell’ambiente (2)
Nel nostro caso l’ambiente è visto come
un grafo non orientato e connesso.
Il robot dovrà esplorare tutti i nodi e
tutti gli archi per fornire una mappa
completa.
Struttura del robot
Algoritmo d’esplorazione
Mappa parziale
Funzioni primitive del robot
Passaggio dal mondo reale al modello di riferimento
(e viceversa)
Raccolta informazioni
(telecamere, sensori)
“Azioni”
(marcare zone e percorsi, muoversi)
Ambiente
Il robot, limitazioni
Non ha nessuna conoscenza del grafo a
priori.
Attivato su un nodo arbitrario.
Può muoversi solo lungo gli archi, un
passo alla volta.
Vede gli archi inesplorati che partono da
un nodo ma non può sapere dove
portano.
Il robot, assunzioni
Durante l’esplorazione il robot prepara
una mappa parziale che consiste in tutti
i nodi e archi già esplorati.
Può marcare i nodi e gli archi visitati e li
riconosce quando sono incontrati
ancora.
Terminologia
Un nodo è saturo se tutti gli archi che
partono da quel nodo sono visitati, altrimenti
è detto libero.
Il robot situato in v è bloccato se v è saturo.
Una mossa-penalità è una qualsiasi mossa
lungo un arco già esplorato.
La penalità di un algoritmo A che esegue su
un grafo G, indicato con PA(G), è data dal
numero totale di mosse penalità nel caso
pessimo.
Struttura del robot
Algoritmo d’esplorazione
Mappa parziale
Funzioni primitive del robot
Passaggio dal mondo reale al modello di riferimento
(e viceversa)
Raccolta informazioni
(telecamere, sensori)
“Azioni”
(marcare zone e percorsi, muoversi)
Ambiente
Primitive del robot
Nodo Posizione()
Restituisce il nodo sul quale si trova il robot, cioè il nodo corrente.
int QuantiInesplorati()
Deve esistere un arco inesplorato da
percorrere!
Il numero di archi inesplorati incidenti al nodo corrente.
QuantiInesplorati() > 0
Lista<Nodo> Esplorati()
I nodi adiacenti alla posizione del robot che possono essere raggiunti
passando per un arco esplorato. V deve essere adiacente al nodo
corrente attraverso un arco esplorato.
MuoviSuInesplorato()
Muove il robot lungo un arco inesplorato arbitrario che parte dal nodo
corrente.
MuoviSuEsplorato(Nodo v)
Muove il robot verso il nodo v seguendo un arco esplorato.
Struttura del robot
Algoritmo d’esplorazione
Mappa parziale
Funzioni primitive del robot
Passaggio dal mondo reale al modello di riferimento
(e viceversa)
Raccolta informazioni
(telecamere, sensori)
“Azioni”
(marcare zone e percorsi, muoversi)
Ambiente
Algoritmi d’esplorazione
Sia G=(V,E) un grafo non orientato e
connesso. n=|V(G)| e m=|E(G)|.
Ci interesserà capire l’ordine di grandezza
delle penalità generate da un algoritmo.
Le penalità prodotte da un algoritmo A sono
lineari nel numero di nodi di un grafo se
esiste una costante c tale che per ogni grafo
G, PA(G)  c |V(G)|
Se un algoritmo è lineare nel numero di nodi,
allora le penalità non dipendono dal numero
di archi.
Algoritmo Depth First Search
Un semplice metodo per esplorare un grafo ci
viene dato dalla strategia DFS.
Finché il nodo corrente è libero, il robot
percorre un arco incidente inesplorato.
Quando rimane bloccato su un nodo, si
sposta verso il nodo libero visitato più
recentemente, utilizzando un cammino
minimo nel rispetto della parte già esplorata
del grafo.
Esempio DFS
6
5
1
4
3
7
2
Esempio DFS
6
5
1
4
3
7
2
Esempio DFS
6
5
1
4
3
7
2
Esempio DFS
6
5
1
4
3
7
2
Esempio DFS
6
5
1
4
3
7
2
Esempio DFS
Questo è il nodo
6 libero visitato
più recentemente
5
1
4
2
3
7
Il robot è bloccato!
Esempio DFS
6
5
1
4
Penalità!
3
7
2
Esempio DFS
6
5
Penalità!
1
4
3
7
2
Esempio DFS
6
5
1
4
3
7
2
Esempio DFS
6
5
1
4
3
7
2
Esempio DFS
6
5
1
4
3
7
2
Algoritmo DFS
L’algoritmo DFS non utilizza abbastanza
informazioni sulla parte già esplorata
del grafo.
Esso guida il robot scegliendo sempre il
nodo libero visitato più recentemente,
anche quando si trova molto lontano.
… questo algoritmo non produce
penalità lineari nel numero di nodi.
Algoritmo DFS
Panaite e Pelc hanno fornito una classe
di grafi per i quali l’algoritmo non
funziona bene.
L’idea è quella di creare dei nodi liberi il
più lontano possibile uno dall’altro.
Vediamo un esempio di questi grafi…
Grafo “cattivo” per DFS
…,…,…,…
c
s
a
b
d
Grafo “cattivo” per DFS
A ,…,…,…
c
s
a
b
d
Grafo “cattivo” per DFS
A, C,…,…
c
s
a
b
d
Grafo “cattivo” per DFS
A, C, B, …
c
s
a
b
d
Grafo “cattivo” per DFS
A, C, B, D
c
s
a
b
d
Grafo “cattivo” per DFS
A, C, B, D
c
d
s
a
b
Il robot è bloccato e si sposterà
secondo l’ordine DFS su D, B, C, A
attraversando il grafo quattro volte!
Algoritmo Greedy
Finché il nodo corrente è libero, il robot
percorre un arco incidente inesplorato.
Quando rimane bloccato, il robot si
muove verso il più vicino nodo libero,
utilizzando un cammino minimo in
accordo alla parte già esplorata del
grafo.
Esempio Greedy
6
5
1
4
3
7
2
Esempio Greedy
6
5
1
4
3
7
2
Esempio Greedy
6
5
1
4
3
7
2
Esempio Greedy
6
5
1
4
3
7
2
Esempio Greedy
6
5
1
4
3
7
2
Esempio Greedy
Questo è il nodo libero
più vicino
6
5
1
4
2
3
7
Il robot è bloccato!
Esempio Greedy
6
5
1
4
Penalità!
3
7
2
Esempio Greedy
6
5
1
4
3
7
2
Esempio Greedy
6
Penalità!
5
1
4
3
7
2
Esempio Greedy
6
5
1
4
3
7
2
Esempio Greedy
6
5
1
4
3
7
2
Algoritmo Greedy
Il robot si muove sempre cercando il più
vicino nodo libero, senza preoccuparsi se
questi spostamenti causeranno molte penalità
in futuro.
E’ dimostrato che l’algoritmo Greedy non è
lineare nel numero di nodi. La dimostrazione
utilizza un’altra classe di grafi di controesempio.
L’idea è quella di creare dei nodi liberi
sufficientemente vicini al robot per attrarlo
lontano da parti inesplorate del grafo.
Grafo “cattivo” per Greedy
Il robot percorre un particolare cammino iniziale…
1
a
2
4
8
7
b
Grafo “cattivo” per Greedy
1
a
2
4
8
7
b
Grafo “cattivo” per Greedy
1
a
2
4
8
7
b
Grafo “cattivo” per Greedy
Il più vicino
Bloccato!
nodo libero
1
a
2
4
8
7
b
Grafo “cattivo” per Greedy
1
a
2
Il più vicino
nodo libero
4
8
7
b
Grafo “cattivo” per Greedy
1
a
2
4
8
7
b
Grafo “cattivo” per Greedy
1
a
2
4
8
7
b
Grafo “cattivo” per Greedy
1
a
2
4
8
7
b
Grafo “cattivo” per Greedy
1
a
2
4
8
7
b
Grafo “cattivo” per Greedy
Il robot ha commesso molte penalità
ed è stato attratto lontano dall’unico nodo
inesplorato!
1
a
Inesplorato!
2
4
8
7
b
Il robot deve ancora attraversare tutto il grafo
per completare l’esplorazione!
L’algoritmo di Panaite e Pelc
E’ lineare nel numero di nodi del grafo.
Commette al massimo 3|V(G)| penalità
per ogni grafo connesso G.
L’idea è quella di generare la maggior
parte delle penalità su di un albero di
copertura generato dinamicamente.
L’algoritmo si basa su due funzioni
principali: ESPLORA e SATURA
Funzione Esplora
Questa funzione guida il robot lungo
l’albero di copertura a partire dal nodo r
Al termine della funzione tutto il grafo
è esplorato.
Utilizza due array:


Parent : V(G)  V(G) U {null, unassigned}
Color : V(G)  {bianco, blu, rosso}
Esplora(Nodo r)
v
Parent[r] := null;
Parent[u] := unassigned u  V(G)\{r};
Color[u] := bianco u  V(G);
v := r;
while v  null do
Satura(v);
if v ha un vicino u tale che parent[u] = unassigned
parent[u] := v;
v := u;
else
v := parent[v];
MuoviSuEsplorato(v);
Esplora(Nodo r)
v
Parent[r] := null;
Parent[u] := unassigned u  V(G)\{r};
Color[u] := bianco u  V(G);
v := r;
while v  null do
Satura(v);
if v ha un vicino u tale che parent[u] = unassigned
parent[u] := v;
v := u;
else
v := parent[v];
MuoviSuEsplorato(v);
Esplora
Al termine della funzione abbiamo eseguito
Satura su ogni nodo, pertanto il grafo è
esplorato.
Dividiamo le penalità in due tipi:


Esterne : quelle commesse dalla Esplora
Interne : quelle necessarie alla funzione Satura.
Le penalità esterne sono sempre 2(|V|-1).
Le penalità totali saranno 2(|V|-1) + p, dove
p è il numero complessivo di penalità
commesse da tutte le esecuzioni di Satura.
Satura(Nodo v)
if v è saturo then return;
color[v] := blu;
u := v;
while NOT (u = v AND v è saturo) do
if esiste un arco inesplorato incidente e
u := l’altro capo di e;
color[u] := blu;
else
Sia [u = u0,u1,…,uk = v] un cammino da u a v
dove tutti i nodi sono blu e tutti
gli archi esplorati.
color[u] := rosso;
u := u1;
MuoviSuEsplorato(u);
Tutti i nodi blu tornano bianchi;
Satura
E’ dimostrato che la procedura Satura(v)
termina quando il nodo v è saturo e il robot è
in v.
L’unica mossa penalità è commessa quando il
robot si muove da u a u1. Questa condizione
si verifica nel ramo else, dove si colora u di
rosso.
Un nodo diviene rosso solo quando è saturo
(altrimenti non sarebbe seguito il ramo else).
Satura
Una volta che un nodo è diventato rosso, non
può più cambiare colore perché la Satura non
muoverà mai più il robot su questo nodo.
Conclusione: il numero totale di penalità
interne corrisponde al numero di nodi colorati
di rosso. Le penalità generate da TUTTE le
esecuzioni di Satura non possono superare
|V(G)|.
Algoritmo Panaite e Pelc
Le penalità generate da questo
algoritmo sono lineari nel numero di
nodi del grafo poiché:
PPANAITE(G)  3|V(G)|
Esempio Panaite e Pelc
6
5
Satura(1)
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
Fine
Satura(1)
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
2
3
7
Tutti i nodi blu
tornano bianchi
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
Satura(5)
5
6
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
2
3
7
Esplora deve risalire
l’albero e continuare dal
nodo 1
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
6
5
1
4
3
7
2
Esempio Panaite e Pelc
… ho finito!
6
5
1
4
3
7
2
Penalità esterne : 12
Penalità interne :
3
Panaite e Pelc
Le penalità sono necessariamente
comprese tra 2|V| e 3|V|.
Possiamo migliorare l’algoritmo per
eliminare la limitazione inferiore dei
2|V|.
Verifica con |V|=100
Panaite e Pelc con
miglioramenti
Grafi sfavorevoli per Greedy
Conclusioni
L’algoritmo DFS non è efficiente in
quanto le penalità crescono sempre
come |E|.
Utilizzando l’algoritmo di Panaite e Pelc
abbiamo una limitazione superiore
lineare nel numero di nodi.
In pratica però il miglior algoritmo
d’esplorazione rimane il Greedy.