Home

Federica EU

1/29

Alberto Finzi » 15.Navigazione - parte prima

Navigazione

Obstacle avoidance: evitare ostacoli (fissi, mobili).

Path Planning: pianificare un cammino.

Exploration: esplorare un ambiente.

Plan Execution: eseguire un piano di navigazione.

Ostacoli: somma di Minkowski

Come rappresentare robot e ostacoli.

Forma ostacolo + forma del robot.

Robot approssimato da punto materiale.

Ostacolo aumentato (somma di minkowski).

Percorsi tra Ostacoli: Metodi Voroni

Percorsi equidistanti tra i due punti-oggetto più vicini.

Roadmap a partire dalla mappa:

raggiungere il path vicino;
path verso il goal;
raggiungere il goal.

Percorsi tra ostacoli: Metodi Bug

I metodi voroni richiedono mappa intera, percorsi equidistanti e lunghi.

Metodo Bug

vai da A a B in linea retta;
se c’e’ ostacolo circumnavigalo finchè non incontri/vedi la linea AB;
continua a seguire AB.

Non sempre si ottiene un buon piano, ma è garantito l’arrivo a B se questo è raggiungibile.

Percorsi tra Ostacoli: Metodi Potenziali

Goal basso potenziale, ostacoli alto potenziale;

Ad ogni punto potenziale:

$U_\Sigma=\sum_{t=1:k}U_{0,t}(x)+U_g(x)$

Ad ogni punto forza:

$F(x)=-\nabla U_\Sigma (x)$

$=-\sum_{t=1:k}\nabla U_{0,t}(x)-\nabla U_g(x)$

Quale potenziale?

Percorsi tra Ostacoli: Metodi Potenziali (segue)

Funzioni tipiche:

$U_{0,t}=\eta\left\{\begin{array}{ll}\frac 1 2 \left( \frac 1 {\rho(x)}-\frac 1 {\rho 0}\right)^2 ~~\forall~~\rho(x)\leq \rho_0 \\ \\ 0 ~~~~~~~~~~~~~~~~~~~~\text{otherwise}\end{array}\right$

$U_g(x)=\frac 1 2 (x-x_g)^2$

Tra voroni e bug per vicinanza ad ostacoli.

Metodo locale, quindi problema di minimi locali.

Funzioni tipiche.

Pianificazione di cammino

Path Planning: traiettorie prive di collisioni tra partenza e destinazione.

Ottimizzazione: il robot dovrebbe raggiungere la destinazione prima possibile.

Pianificazione e Ambiente Dinamico

Come reagire ad ostacoli imprevisti?

Efficacia
Affidabilità

Approcci

Dynamic Window Approach [Simmons 96, Fox et al. 97, Brock & Khatib 99]
Pianificazione basata su grid map [Konolige 00]
Nearness Diagram Navigation [Minguez et al. 01, 02]
Vector-Field-Histogram [Ulrich & Borenstein 98]
A*, D*, D* Lite, ARA*, …

Obiettivi in ambiente dinamico

Calcolo del cammino ottimo considerando incertezze potenziali nelle azioni.

Generare azioni rapidamente in caso di ostacoli imprevisti.

Dynamic Windows

Collision avoidance: trovare traiettorie senza collisione con operazioni geometriche.

Se il robot si muove su archi di circonferenza con comandi (v, w), quali (v,w) sono ammissibili?

Dynamic Windows (segue)

V_s = tutte le velocità del robot
V_a = area libera da ostacoli
V_d = velocità raggiungibili in un certo tempo date le possibili accellerazioni

Spazio di ricerca = V_s & V_a & V_d

Esempio di spazio di ricerca.

Dynamic Windows (segue)

Come scegliere (v,w)?

I comandi sono scelti da una funzione euristica.

La funzione cerca di minimizzare il tempo di navigazione con la seguente politica:

vai veloce nella direzione giusta

Dynamic Windows (segue)

Funzione di navigazione euristica.

Pianificazione ristretta allo spazio (x,y).

Non pianificazione nello spazio delle velocità.

Funzione di navigazione:

$NF=\alpha\cdot vel+\beta\cdot nf +\gamma \cdot \Alpha nf+ \delta \cdot goal$

dove:

α: max velocità;
nf: costo per raggiungere il goal;
Δnf: scostamento dal path pianificato;

goal: vicinanza al goal.

Dynamic Windows (segue)

Brevi tempi di reazione (dipendenti da parametri).

Veloce in ambienti popolati.

Dynamic Windows (segue)

Reagisce rapidamente.
Richiede bassa potenza di calcolo.
Guida il robot su percorsi liberi da ostacoli.
Utilizzato in diverse applicazioni reali.
Traiettorie risultanti a volte subottime.
Minimi locali possono impedire al robot di raggiungere la destinazione.

Problema con Dynamic Windows

Il robot è troppo veloce per entrare nel corridoio.

Problema tipico nel mondo reale: il robot non rallenta in tempo per entrare.

Path Planning

Si può utilizzare A* per pianificare il path del robot.

Richiede una struttura a grafo con un numero di archi limitato.

Di solito si usa una occupancy grid 2D.

Minimizza costo stimato

g(n), costo corrente dallo stato iniziale ad n.
h(n), costo stimato da n al prossimo goal.
f(n) = g(n)+h(n), costo stimato della soluzione più economica passante per n.
Dato h*(n) il costo della soluzione ottima per n, h è ammissibile se per ogni n: h(n) ≤ h*(n).
Si richiede che h is ammissibile (la distanza euclidea dal goal è ammissibile nello spazio euclideo).