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

Ambiente

“Azioni” (marcare zone e percorsi, muoversi)

Raccolta informazioni(telecamere, sensori)

Passaggio dal mondo reale al modello di riferimento(e viceversa)

Mappa parziale Funzioni primitive del robot

Algoritmo d’esplorazione

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

Ambiente

“Azioni” (marcare zone e percorsi, muoversi)

Raccolta informazioni(telecamere, sensori)

Passaggio dal mondo reale al modello di riferimento(e viceversa)

Mappa parziale

Algoritmo d’esplorazione

Funzioni primitive del robot

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.

Nodo Posizione()Restituisce il nodo sul quale si trova il robot, cioè il nodo corrente.

int QuantiInesplorati()Il numero di archi inesplorati incidenti al nodo corrente.

Lista<Nodo> Esplorati()I nodi adiacenti alla posizione del robot che possono essere

raggiunti passando per un arco esplorato.

Primitive del robot

Deve esistere un arco inesplorato da percorrere!

QuantiInesplorati() > 0

V deve essere adiacente al nodo corrente attraverso un arco

esplorato.

Struttura del robot

Ambiente

“Azioni” (marcare zone e percorsi, muoversi)

Raccolta informazioni(telecamere, sensori)

Passaggio dal mondo reale al modello di riferimento(e viceversa)

Mappa parziale Funzioni primitive del robot

Algoritmo d’esplorazione

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

1 2

3

7

5 4

6

Esempio DFS

1 2

3

7

5 4

6

Esempio DFS

1 2

3

7

5 4

6

Esempio DFS

1 2

3

7

5 4

6

Esempio DFS

1 2

3

7

5 4

6

Esempio DFS

1 2

3

7

5 4

6

Il robot è bloccato!

Questo è il nodo libero visitato più recentemente

Esempio DFS

1 2

3

7

5 4

6

Penalità!

Esempio DFS

1 2

3

7

5 4

6

Penalità!

Esempio DFS

1 2

3

7

5 4

6

Esempio DFS

1 2

3

7

5 4

6

Esempio DFS

1 2

3

7

5 4

6

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

s

a b

c d

…,…,…,…

Grafo “cattivo” per DFS

s

a b

c d

A ,…,…,…

Grafo “cattivo” per DFS

s

a b

c d

A, C,…,…

Grafo “cattivo” per DFS

s

a b

c d

A, C, B, …

Grafo “cattivo” per DFS

s

a b

c d

A, C, B, D

Grafo “cattivo” per DFS

s

a b

c d

A, C, B, D

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

1 2

3

7

5 4

6

Esempio Greedy

1 2

3

7

5 4

6

Esempio Greedy

1 2

3

7

5 4

6

Esempio Greedy

1 2

3

7

5 4

6

Esempio Greedy

1 2

3

7

5 4

6

Esempio Greedy

1 2

3

7

5 4

6

Il robot è bloccato!

Questo è il nodo libero più vicino

Esempio Greedy

1 2

3

7

5 4

6

Penalità!

Esempio Greedy

1 2

3

7

5 4

6

Esempio Greedy

1 2

3

7

5 4

6

Penalità!

Esempio Greedy

1 2

3

7

5 4

6

Esempio Greedy

1 2

3

7

5 4

6

Algoritmo GreedyIl 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 contro-esempio.L’idea è quella di creare dei nodi liberi sufficientemente vicini al robot per attrarlo lontano da parti inesplorate del grafo.

Grafo “cattivo” per Greedy

1 2 4 8 7

a b

Il robot percorre un particolare cammino iniziale…

Grafo “cattivo” per Greedy

1 2 4 8 7

a b

Grafo “cattivo” per Greedy

1 2 4 8 7

a b

Grafo “cattivo” per Greedy

1 2 4 8 7

a b

Bloccato!Il più vicino nodo libero

Grafo “cattivo” per Greedy

1 2 4 8 7

a b

Il più vicino nodo libero

Grafo “cattivo” per Greedy

1 2 4 8 7

a b

Grafo “cattivo” per Greedy

1 2 4 8 7

a b

Grafo “cattivo” per Greedy

1 2 4 8 7

a b

Grafo “cattivo” per Greedy

1 2 4 8 7

a b

Grafo “cattivo” per Greedy

1 2 4 8 7

a b

Il robot ha commesso molte penalitàed è stato attratto lontano dall’unico nodo inesplorato!

Inesplorato! 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)

Parent[r] := null;

Parent[u] := unassigned u V(G)\{r};Color[u] := bianco u V(G);v := r;

while v null doSatura(v);

if v ha un vicino u tale che parent[u] = unassigned

parent[u] := v;

v := u;

else

v := parent[v];

MuoviSuEsplorato(v);

v

Esplora(Nodo r)

Parent[r] := null;

Parent[u] := unassigned u V(G)\{r};Color[u] := bianco u V(G);v := r;

while v null doSatura(v);

if v ha un vicino u tale che parent[u] = unassigned

parent[u] := v;

v := u;

else

v := parent[v];

MuoviSuEsplorato(v);

v

EsploraAl 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 eu := 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

1 2

3

7

5 4

6Satura(1

)

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6Fine

Satura(1)

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Tutti i nodi blu tornano bianchi

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6Satura(5)

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esplora deve risalire l’albero e continuare

dal nodo 1

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Esempio Panaite e Pelc

1 2

3

7

5 4

6

Penalità esterne : 12Penalità interne : 3

… ho finito!

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.