Obstacle avoidance: evitare ostacoli (fissi, mobili).
Path Planning: pianificare un cammino.
Exploration: esplorare un ambiente.
Plan Execution: eseguire un piano di navigazione.
Come rappresentare robot e ostacoli.
Forma ostacolo + forma del robot.
Robot approssimato da punto materiale.
Ostacolo aumentato (somma di minkowski).
Percorsi equidistanti tra i due punti-oggetto più vicini.
Roadmap a partire dalla mappa:
I metodi voroni richiedono mappa intera, percorsi equidistanti e lunghi.
Metodo Bug
Non sempre si ottiene un buon piano, ma è garantito l’arrivo a B se questo è raggiungibile.
Goal basso potenziale, ostacoli alto potenziale;
Ad ogni punto potenziale:
Ad ogni punto forza:
Quale potenziale?
Funzioni tipiche:
Tra voroni e bug per vicinanza ad ostacoli.
Metodo locale, quindi problema di minimi locali.
Path Planning: traiettorie prive di collisioni tra partenza e destinazione.
Ottimizzazione: il robot dovrebbe raggiungere la destinazione prima possibile.
Come reagire ad ostacoli imprevisti?
Approcci
Calcolo del cammino ottimo considerando incertezze potenziali nelle azioni.
Generare azioni rapidamente in caso di ostacoli imprevisti.
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?
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
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
Funzione di navigazione euristica.
Pianificazione ristretta allo spazio (x,y).
Non pianificazione nello spazio delle velocità.
Funzione di navigazione:
dove:
α: max velocità;
nf: costo per raggiungere il goal;
Δnf: scostamento dal path pianificato;
goal: vicinanza al goal.
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.
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*.
Si assume il robot localizzato.
Il robot ha a disposizione una occupancy grid.
Spesso vengono eseguiti i comandi correttamente.
Problemi
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.
Non il path più breve, ma quello che minimizza la probabilità di perdersi.
Considerare: lunghezza path e informazione persa (es. Robot Minerva).
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.
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.
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.
Nuovi comandi ogni 0.25 secondi.
Dopo 0.25 c’e’ timeout e abort.
Che fare in questo caso?
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.
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