Navigazione
Questo documento contiene materiale proveniente da fonti esterne: 1 [ Documento Originale - Autore: Cristian Secchi - Sito Riferimento ]
Data una configurazione di partenza e una di arrivo note, la navigazione è il problema di trovare una percorso libero da collisioni che porti il robot dalla configurazione di partenza a quella di arrivo.
Contents |
Bug Algorithms
Gli algoritmi bug si basano sulla possibilità del robot di percepire, tramite opportuni sensori eterocettivi (bumpers, range finders), la presenza di un ostacolo quando vi sono molto vicini o addirittura quando lo stanno toccando.
Idea di base: Muovere il robot in linea retta verso l’obiettivo. Quando si incontra un ostacolo, lo si circumnaviga fino a quando non è possibile muoversi in linea retta verso l’obiettivo.
Si assume che il robot sia un punto (es.: no controllo sull’orientamento per
uniciclo) dotato di un sensore di contatto.
Si assume inoltre che il robot sia in grado di conoscere la sua posizione, oltre a quella della configurazione di partenza e di quella obiettivo.
Bug1
Si definisca come m-line il segmento che collega un punto a qgoal
Il robot ha due tipi di comportamento tra i quali commuta:
motion to goal: A partire da un leave point, il robot si muove lungo la mline che connette il leave point al goal finchè non raggiunge il goal o incontra un ostacolo.
Se il robot incontra un ostacolo, il punto di contatto viene detto hit point e il comportamento del robot commuta al boundary following.
boundary following: a partire da un hit point, il robot circumnaviga l’ostacolo finchè non ritorna all’hit point.
Poi determina il punto più vicino al goal lungo il perimetro dell’ostacolo e si sposta lungo il perimetro fino a raggiungere quel punto, detto leave point e il comportamento del robot commuta al motion to goal.
Se la linea che collega il leave point i-esimo con il goal intereseca
l’ostacolo i-esimo, allora non esiste nessun percorso che consenta di
raggiungere il goal. In tal caso l’algoritmo lo segnala
Bug1 Algorithm
Input: Un robot con un sensore di contatto Output: Un percorso fino a qgoal o una conclusione che tale percorso non esiste 0: i=1; qL_0 = q_start; 1: while Forever do 2: repeat 3: Da qL_i-1, muoviti verso q_goal. 4: until q_goal è raggiunto or si tocca un ostacolo a qH_i 5: if Il goal è raggiunto then 6: Exit. 7: end if 8: repeat 9: Segui il bordo dell’ostacolo. 10: until qgoal è raggiunto or ci si ritrova a qH_i 11: Determina il punto qLi sul perimetro che è alla minima distanza dal goal. 12: vai a qL_i. 13: if la m-line che passa da qLi interseca l’ostacolo su cui si trova qL_i then 14: Concludi che qgoal non è raggiungibile e exit. 15: end if 16: i=i+1 17: end while
Bug2
- Come per il Bug1 anche il Bug2 commuta tra due comportamenti: il motion to goal e il boundary following
- Per il Bug2, la m-line è fissa ed è il segmento di linea che connette qstart a qgoal
motion to goal: A partire da un leave point, il robot si muove lungo la mline che connette qstart a qgoal finchè non raggiunge il goal o incontra un ostacolo. Se il robot incontra un ostacolo, il punto di contatto viene detto hit point e il comportamento del robot commuta al boundary following.
boundary following: a partire da un hit point, il robot circumnaviga l’ostacolo finchè non raggiunge un punto sulla m-line, detto leave point e il comportamento del robot commuta al motion to goal.
Se durante il boundary following il robot incontra di nuovo il punto da cui
è partito sulla m-line allora non esiste nessun percorso che consenta di
raggiungere il goal. In tal caso l’algoritmo lo segnala
Bug2 Algorithm
Input: Un robot con sensore di contatto Output: Un percorso fino a qgoal o una conclusione che tale percorso non esiste 0: i=1; qL_0 = q_start; 1: while True do 2: repeat 3: Da qL_i-1, muoviti verso qgoal lungo la m-line. 4: until q_goal è stato raggunto or si tocca un ostacolo all’hit point qH_i. 5: Gira a sinistra (o a destra). 6: repeat 7: Segui il bordo dell’ostacolo 8: until 9: q_goal è raggiunto or 10: qHi è raggiunto di nuovo or 11: la m-line è raggiunta di nuovo a un punto m tale che m 12: m ≠ qH_i (il robot non ha raggiunto l’ hit point), 13: d(m, q_goal) < d(m, qH_i (il robot è più vicino), e 14: Se il robot si muove verso il goal, non entra in contatto con l’ostacolo. 15: Si pongta qL_i+1 = m 16: i=i+1 17: end while
Confronto tra Bug1 e Bug2
A prima vista sembra che Bug2 sia meglio di Bug1 in quanto esso non comporta una circumnavigazione completa degli ostacoli. Tuttavia, questo non è sempre vero e dipende dal tipo di ostacoli
Bug2 è meglio di Bug1 Bug1 è meglio di Bug2
- Bug1 fa una ricerca esaustiva e trova il leave point migliore. Questo richiede che il robot percorra tutto il perimetro dell’ostacolo
- Bug2 usa un approccio opportunistico. Quando trova un leave point che è migliore di quelli che ha visto prima , lo sceglie (approccio greedy)
- Quando gli ostacoli sono “semplici”, tipicamente Bug2 è migliore di Bug1
- Nel caso in cui gli ostacoli siano “complessi”, Bug1 è migliore di Bug2
Tangent Bug
- E’ un miglioramento del Bug2.
- Proposto in:
Kamon I., Rivlin E., Rimon, E., A new range-sensor based globally convergent navigation algorithm for mobile robots, IEEE International Conference on Robotics and Automation, 1996 disponibile all’indirizzo: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=503814&isnumber=10815 accessibile solo dagli indirizzi IP UNIMORE.
- Gli algoritmi bug sono indicati solamente per robot mobili che si muovono sul piano e non si considera l’intera variabile delle configurazioni
- Attraverso la pianificazione basata su campi potenziali è possibile pianificare il moto anche per sistemi con variabili di configurazione di dimensione elevata.
- Come gli algoritmi bug, consentono di generare il percorso incrementalmente, cambiandolo man mano che un ostacolo è percepito
Funzione potenziale
Gradiente di U La funzione potenziale può essere interpretata come una funzione energia sullo spazio delle configurazioni e il gradiente di U rappresenta la forza indotta dalla presenza del potenziale. Il gradiente in una punto q punta verso la direzione in cui U cresce.
L’approccio delle funzioni potenziali guida il robot come se fosse una
particella immersa in un campo potenziale dato dai gradienti di svariate
funzioni potenziali. Alla configurazione obiettivo è associata una funzione
potenziale che genera un gradiente che attira la particella mentre ad
ogni ostacolo è associato una funzione potenziale che genera un
gradiente che respinge le particelle. La combinazione dei due gradienti
produce un percorso libero da collisioni verso la configurazione obiettivo.
Le funzioni potenziali possono essere viste come dei paesaggi in cui il
robot è immerso e lungo i quali si muove spostandosi da un punto “in
alto” a un punto più “in basso”. Il robot segue un percorso in discesa,
seguendo il gradiente negato della funzione potenziale. Questa tecnica di
movimento si chiama discesa del gradiente (gradient descent).
Il robot termina quando raggiunge una configurazione q* nella quale il
gradiente si annulla. Questo punto può essere un minimo, un massimo o un
punto di sella. Per come verranno disegnati i potenziali, q* sarà un minimo (locale)
Come si costruisce la funzione potenziale che genera il cammino da qstart a qgoal evitando gli ostacoli? Potenziale attrattivo. Ha il minimo in corrispondenza di q_goal. Il suo ruolo attirare il robot verso l’obiettivo.Potenziale repulsivo. E’ dato dalla somma dei potenziali repulsivi per ogni ostacolo. Ha il ruolo di allontanare il robot dagli ostacoli presenti nell’ambiente
Il potenziale attrattivo
Il potenziale U_att deve essere monotonicamente crescente al crescere della distanza da q_goal. In tal modo il robot, tramite gradient descent, viene attirato alla configurazione obiettivo q_goal. Ciò equivale a dire che q_goal è una configurazione di minimo isolata e che il sistema non ha punti critici. Indicando con d(q,q_goal) la distanza tra q e q_goal, una possibile scelta è:
Quando il robot è lontano dall’obiettivo, vi si avvicina velocemente (la forza che lo attrae è grande) mentre quando il robot è vicino all’ obiettivo, vi si avvicina dolcemente (la forza che lo attrae è piccola)
Il potenziale repulsivo
E’ composto da una somma di potenziali repulsivi, ciascuno associato a un ostacolo. Il termine i-esimo deve essere tale da generare una forza repulsiva tanto più grande quanto più il robot è vicino all’ostacolo iesimo. Inoltre, esso non deve generare nessuna forza se il robot è sufficientemente lontano dall’ostacolo ostacolo i-esimo. Una possibile scelta è:
Q*=distanza oltre la quale il robot ignora l’ostacolo di(q)=distanza tra il robot e l’ostacolo i esimo. nobs=numero di ostacoli
Se di(q) va a zero allora il gradiente va a infinito!
L’algoritmo di discesa del gradiente
Il valore a(i) determina la lunghezza del passo con cui robot scende lungo il gradiente di U. Se a(i) è piccolo, l’algoritmo è accurato ma computazionalmente pesante mentre se a(i) è grande l’algoritmo è più veloce ma meno accurato. La scelta di a(i) dipende dal tipo di applicazione.
Minimi Locali
E’ possibile che l’algoritmo di discesa del gradiente si fermi in un minimo
locale
Il potenziale attrattivo e quello repulsivo si controbilanciano!!
Esistono approcci per risolvere il problema dei minimi locali:
- 'Wave front planners: Numerical potential field techniques for robot path planning (J. Barraquand, B. Langlois, J.C. Latombe, , IEEE Transactions on Man and Cybernetics 22(2),1992) disponibile a http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=148426&i snumber=3929 da un indirizzo IP UNIMORE
- Navigation Functions: Libro: Principles of Robot Motion
- Esistono altre tecniche di navigazione per certi versi più complete ed efficienti di quelle illustrate sinora:
- Roadmaps
- Cell Decomposition
- Sampling based algorithms
- …
Testi sull'argomento
- Principle of Robot Motion - Theory, algorithms and Implementations. (Choset, Lynch, Hutchinson, Kantor, Burgard, Kavraki, Thrun, MIT Press 2005) - (trattazione esaustiva)
