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 » 16.Navigazione - parte seconda


Path Planning Probabilistico

Spazio di stato continuo.
Azioni continue.

Probabilistic Roadmaps (PRM) [Kavraki et al.]
Rapidly Exploring Random Trees (RRT) [Lavalle et al.]

Probabilistic Roadmap

Planning in due fasi

1. Fase di Learning

  • Campionamento delle configurazioni libere
  • Connessione di coppie di nodi con archi nello spazio libero

2. Fase di Query

  • Trova il percorso sul grafo che connette la posizione iniziale con il goal

Fasi di Learning e di Query

Fase di learning

Configurazione random nello spazio libero, poi connessa da archi collegando tutti i k vicini a distanza minore di n.

Fase di query
Connette goal e pos. iniziale e cerca lo shortest path (A*, Dijkstra).

Probabilisticamente completo: all’aumentare dei punti, la probabilità di non trovare il percorso va a zero.


Rapidly Exploring Random Trees

RRT (Rapidly Exploring Random Trees)

  • Esplora lo spazio continuo (non c’è bisogno di una grid map).
  • Usa ricerca random e l’approssimazione per velocizzare.
  • Permette la definizione di un planner probabilisticamente completo.

RRT: Algoritmo

Algoritmo base RRT

 

  1. La configurazione iniziale è la radice dell’albero
  2. Prendi uno stato a caso nello spazio delle configurazioni
  3. Trova il nodo più vicino nell’albero
  4. Estendi quel nodo verso lo stato se possibile
  5. Vai al passo 2
Passi dell’algoritmo.

Passi dell'algoritmo.


RRT: Algoritmo (segue)

Algoritmo BuildRRT
Input: conf. iniziale qinit, num. nodi RRT K, dist. incrementale Δq)
Output: grafo RRT G

G.init(qinit)

 

for k = 1 to K

qrand ← RAND_CONF()

qnear ← NEAREST_VERTEX(qrand, G)

qnew ← NEW_CONF(qnear, Δq)

G.add_vertex(qnew)

G.add_edge(qnear, qnew)

return G

RRT: Ostacoli e Pianificazione

Ignora le estensioni dell’albero che incontrano gli ostacoli.

L’albero risultante contiene solo cammini validi.

Quando il nodo goal è stato incluso nell’albero, il percorso dalla posa iniziale al goal è ottenuto considerando il cammino inverso dal nodo goal alla radice.

RRT Orientato al Goal

Inizia con lo stato iniziale come radice dell’albero
Prendi uno stato target

  • Con Prob. p lo stato goal
  • Con Prob. 1-p uno stato random

Trova il nodo più vicino nell’albero
Estendi verso il target il nodo più vicino
Vai al passo 2


RRT: Algoritmo


RRT: Pianificazione e Ripianificazione

Se l’ambiente è dinamico ci sono fallimenti frequenti.

Che fare in caso di fallimento?

Si può ripianificare dallo stato attuale (RRT è veloce).

Piani precedenti possono guidare la ricerca (waypoints).

Waypoint cache:

  • Quando si trova un piano, memorizza i waypoints con rimpiazzamento random.
  • Durante la selezione del target cerca un target dalla waypont cache con probabilità q.

ERRT: RRT esteso

Stato iniziale come radice dell’albero.
Prendi uno stato target:

  • Goal con prob. p
  • Elemento random dalla waypoint cache con prob. q
  • Elemento random con prob. 1-q-p

Trova il nodo più vicino dell’albero.
Estendi il nodo più vicino al target.
Vai al passo 2.

Pianificazione RRT

Pianificazione con RRT

  • Alto p – pochi ostacoli noti
  • Basso p – molti ostacoli noti

Ripianificazione con ERRT

  • Alto q – poca dinamica
  • Basso q – molta dinamica
  • ERRT – tende ad usare vecchi piani

RRT ed ERRT convergono probabilisticamente.

  • 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