Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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.

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)

Vs = tutte le velocità del robot
Va = area libera da ostacoli
Vd = velocità raggiungibili in un certo tempo date le possibili accellerazioni

Spazio di ricerca = Vs & Va & Vd

Esempio di spazio di ricerca.

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).

Brevi tempi di reazione (dipendenti da parametri).

Veloce in ambienti popolati.

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.

Il robot è troppo veloce per entrare nel corridoio.

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

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).

Value Iteration

Per calcolare il cammino minimo da ogni stato si può utilizzare value iteration (simile a Dijkstra).

La funzione di costo così ottenuta è un’euristica ottima per A*.

Assunzioni in A* path planning

Si assume il robot localizzato.
Il robot ha a disposizione una occupancy grid.
Spesso vengono eseguiti i comandi correttamente.

Problemi

  • Il robot può essere delocalizzato.
  • Traiettorie troppo vicine ad ostacoli.
  • Le traiettorie devono essere allineate alla struttura a grid.

Convoluzione della grid map

La convoluzione sfoca la mappa.

Gli ostacoli diventano più grandi.

Si esegue A* nella nuova mappa.

Aumenta la distanza degli ostacoli ma il cammino rimane breve.

La tecnica è veloce e affidabile.

Ambiente 1D, celle dopo due passi di convoluzione.

Ambiente 1D, celle dopo due passi di convoluzione.


Altro approccio: Costal Navigation

Non il path più breve, ma quello che minimizza la probabilità di perdersi.

Considerare: lunghezza path e informazione persa (es. Robot Minerva).

Entropy Map.

Entropy Map.


5D Path-planning

Alternativa all’approccio a due livelli.

Piani nello spazio (x,y,θ,v,w) usando A*.

Genera sequenze di comandi per raggiungere il goal.

Massimizza il trade-off tra tempo di esecuzione e distanza dagli ostacoli.

Spazio di Ricerca

Idea: cerca nello spazio discretizzato (x,y,θ,v,w).

Problema: spazio di ricerca troppo grande dati i vincoli temporali (0.25 secs per controllo on-line).

Soluzione: restringere lo spazio di ricerca.

Passi dell’algoritmo

Aggiornamento (statico) della grid map sulla base dell’input sensoriale.

Usa A* per trovare un cammino nello spazio (x,y) usando la grid map aggiornata.

Determina uno spazio ristretto 5D usano la traiettoria precedente.

Trova una traiettoria pianificando nello spazio 5D ristretto.

Passi dell’algoritmo


Timeout

Nuovi comandi ogni 0.25 secondi.

Dopo 0.25 c’e’ timeout e abort.

Che fare in questo caso?

  • Se traiettoria precedente ancora ok, allora mantieni
  • altrimenti, cerca nella 2D oppure usa DWA.

Confronto con DWA

Il 5D permette di passare meglio attraverso passaggi
stretti con maggiore velocità.

Il 5D permette di passare meglio attraverso passaggi stretti con maggiore velocità.


Riassunto

Metodi di navigazione affidabile e robusta richiedono path planning e collision avoidance integrati.

Alcuni approcci considerano vincoli cinematici e piani nello spazio delle velocità.

Approcci che combinano ricerca e tecniche reattive dimostrano prestazioni superiori alle DWA.

Con approcci 5D la qualità della traiettoria aumenta.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion