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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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