Download - Robot Planning
![Page 1: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/1.jpg)
Robot Planning
Esplorazione di ambienti sconosciuti
Alessandro Santuari
![Page 2: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/2.jpg)
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…
![Page 3: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/3.jpg)
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…
![Page 4: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/4.jpg)
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.
![Page 5: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/5.jpg)
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.
![Page 6: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/6.jpg)
Esempio di ambiente
![Page 7: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/7.jpg)
Modellato con forme geometriche
![Page 8: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/8.jpg)
Modellato come un grafo
![Page 9: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/9.jpg)
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.
![Page 10: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/10.jpg)
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
![Page 11: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/11.jpg)
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.
![Page 12: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/12.jpg)
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.
![Page 13: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/13.jpg)
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.
![Page 14: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/14.jpg)
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
![Page 15: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/15.jpg)
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.
![Page 16: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/16.jpg)
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
![Page 17: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/17.jpg)
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.
![Page 18: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/18.jpg)
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.
![Page 19: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/19.jpg)
Esempio DFS
1 2
3
7
5 4
6
![Page 20: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/20.jpg)
Esempio DFS
1 2
3
7
5 4
6
![Page 21: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/21.jpg)
Esempio DFS
1 2
3
7
5 4
6
![Page 22: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/22.jpg)
Esempio DFS
1 2
3
7
5 4
6
![Page 23: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/23.jpg)
Esempio DFS
1 2
3
7
5 4
6
![Page 24: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/24.jpg)
Esempio DFS
1 2
3
7
5 4
6
Il robot è bloccato!
Questo è il nodo libero visitato più recentemente
![Page 25: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/25.jpg)
Esempio DFS
1 2
3
7
5 4
6
Penalità!
![Page 26: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/26.jpg)
Esempio DFS
1 2
3
7
5 4
6
Penalità!
![Page 27: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/27.jpg)
Esempio DFS
1 2
3
7
5 4
6
![Page 28: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/28.jpg)
Esempio DFS
1 2
3
7
5 4
6
![Page 29: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/29.jpg)
Esempio DFS
1 2
3
7
5 4
6
![Page 30: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/30.jpg)
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.
![Page 31: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/31.jpg)
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…
![Page 32: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/32.jpg)
Grafo “cattivo” per DFS
s
a b
c d
…,…,…,…
![Page 33: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/33.jpg)
Grafo “cattivo” per DFS
s
a b
c d
A ,…,…,…
![Page 34: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/34.jpg)
Grafo “cattivo” per DFS
s
a b
c d
A, C,…,…
![Page 35: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/35.jpg)
Grafo “cattivo” per DFS
s
a b
c d
A, C, B, …
![Page 36: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/36.jpg)
Grafo “cattivo” per DFS
s
a b
c d
A, C, B, D
![Page 37: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/37.jpg)
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!
![Page 38: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/38.jpg)
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.
![Page 39: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/39.jpg)
Esempio Greedy
1 2
3
7
5 4
6
![Page 40: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/40.jpg)
Esempio Greedy
1 2
3
7
5 4
6
![Page 41: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/41.jpg)
Esempio Greedy
1 2
3
7
5 4
6
![Page 42: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/42.jpg)
Esempio Greedy
1 2
3
7
5 4
6
![Page 43: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/43.jpg)
Esempio Greedy
1 2
3
7
5 4
6
![Page 44: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/44.jpg)
Esempio Greedy
1 2
3
7
5 4
6
Il robot è bloccato!
Questo è il nodo libero più vicino
![Page 45: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/45.jpg)
Esempio Greedy
1 2
3
7
5 4
6
Penalità!
![Page 46: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/46.jpg)
Esempio Greedy
1 2
3
7
5 4
6
![Page 47: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/47.jpg)
Esempio Greedy
1 2
3
7
5 4
6
Penalità!
![Page 48: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/48.jpg)
Esempio Greedy
1 2
3
7
5 4
6
![Page 49: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/49.jpg)
Esempio Greedy
1 2
3
7
5 4
6
![Page 50: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/50.jpg)
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.
![Page 51: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/51.jpg)
Grafo “cattivo” per Greedy
1 2 4 8 7
a b
Il robot percorre un particolare cammino iniziale…
![Page 52: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/52.jpg)
Grafo “cattivo” per Greedy
1 2 4 8 7
a b
![Page 53: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/53.jpg)
Grafo “cattivo” per Greedy
1 2 4 8 7
a b
![Page 54: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/54.jpg)
Grafo “cattivo” per Greedy
1 2 4 8 7
a b
Bloccato!Il più vicino nodo libero
![Page 55: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/55.jpg)
Grafo “cattivo” per Greedy
1 2 4 8 7
a b
Il più vicino nodo libero
![Page 56: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/56.jpg)
Grafo “cattivo” per Greedy
1 2 4 8 7
a b
![Page 57: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/57.jpg)
Grafo “cattivo” per Greedy
1 2 4 8 7
a b
![Page 58: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/58.jpg)
Grafo “cattivo” per Greedy
1 2 4 8 7
a b
![Page 59: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/59.jpg)
Grafo “cattivo” per Greedy
1 2 4 8 7
a b
![Page 60: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/60.jpg)
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!
![Page 61: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/61.jpg)
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
![Page 62: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/62.jpg)
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}
![Page 63: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/63.jpg)
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
![Page 64: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/64.jpg)
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
![Page 65: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/65.jpg)
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.
![Page 66: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/66.jpg)
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;
![Page 67: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/67.jpg)
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).
![Page 68: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/68.jpg)
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)|.
![Page 69: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/69.jpg)
Algoritmo Panaite e Pelc
Le penalità generate da questo algoritmo sono lineari nel numero di nodi del grafo poiché:
PPANAITE(G) 3|V(G)|
![Page 70: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/70.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6Satura(1
)
![Page 71: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/71.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 72: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/72.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 73: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/73.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 74: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/74.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 75: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/75.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 76: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/76.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 77: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/77.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6Fine
Satura(1)
![Page 78: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/78.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
Tutti i nodi blu tornano bianchi
![Page 79: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/79.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 80: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/80.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6Satura(5)
![Page 81: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/81.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 82: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/82.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 83: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/83.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 84: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/84.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 85: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/85.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 86: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/86.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 87: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/87.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
Esplora deve risalire l’albero e continuare
dal nodo 1
![Page 88: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/88.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 89: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/89.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 90: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/90.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 91: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/91.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 92: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/92.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 93: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/93.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
![Page 94: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/94.jpg)
Esempio Panaite e Pelc
1 2
3
7
5 4
6
Penalità esterne : 12Penalità interne : 3
… ho finito!
![Page 95: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/95.jpg)
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|.
![Page 96: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/96.jpg)
Verifica con |V|=100
Panaite e Pelc con
miglioramenti
![Page 97: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/97.jpg)
Grafi sfavorevoli per Greedy
![Page 98: Robot Planning](https://reader036.vdocumenti.com/reader036/viewer/2022081506/568146b7550346895db3df13/html5/thumbnails/98.jpg)
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.