Spazio di stato continuo.
Azioni continue.
Probabilistic Roadmaps (PRM) [Kavraki et al.]
Rapidly Exploring Random Trees (RRT) [Lavalle et al.]
Planning in due fasi
1. Fase di Learning
2. Fase 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.
RRT (Rapidly Exploring Random Trees)
Algoritmo base RRT
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
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.
Inizia con lo stato iniziale come radice dell’albero
Prendi uno stato target
Trova il nodo più vicino nell’albero
Estendi verso il target il nodo più vicino
Vai al passo 2
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:
Stato iniziale come radice dell’albero.
Prendi uno stato target:
Trova il nodo più vicino dell’albero.
Estendi il nodo più vicino al target.
Vai al passo 2.
Pianificazione con RRT
Ripianificazione con ERRT
RRT ed ERRT convergono probabilisticamente.
2. Robotica mobile - parte prima
3. Robotica mobile - parte seconda
4. Robotica Probabilistica - Filtri Bayesiani (parte prima)
5. Robotica Probabilistica - Filtri Bayesiani (parte seconda)
7. Modello Probabilistico dei Sensori
8. Robotica Probabilistica - Filtri Gaussiani
10. SLAM
11. Filtri Discreti
12. FastSLAM
13. SLAM grid-based
14. Esplorazione basata su guadagno di informazione