Navigazione

From RobotGarage
Jump to: navigation, search
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.

Navigazione


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.

Navigazione: Bug1 Algorithm
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

Navigazione: Bug1 Algorithm 


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

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.

Navigazione: Bug2 Algorithm
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

 Navigazione: Bug2 Algorithm


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

Navigazione: Bug1 Algorithm Navigazione: Bug2 Algorithm


Tangent Bug

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.

Navigazione attraverso funzioni Potenziali


Navigazione con Funzioni Potenziali : Funzione Potenziale Funzione potenziale

Navigazione con Funzioni Potenziali : Gradiente di U 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.


Navigazione con Funzioni Potenziali (1)  Navigazione con Funzioni Potenziali (3)


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. 

Navigazione con Funzioni Potenziali (2)

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).

Navigazione con Funzioni Potenziali (3)

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. 
Navigazione con Funzioni Potenziali : Potenziale Attrattivo


Potenziale repulsivo.
E’ dato dalla somma dei potenziali repulsivi per ogni
ostacolo. Ha il ruolo di allontanare il robot dagli ostacoli presenti nell’ambiente
Navigazione con Funzioni Potenziali : Potenziale Repulsivo (5)


Navigazione con Funzioni Potenziali : Potenziale Repulsivo (6)  Navigazione con Funzioni Potenziali : Potenziale Repulsivo (7)



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 è:

Navigazione con Funzioni Potenziali : Potenziale Attrattivo

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)

Navigazione con Funzioni Potenziali : Potenziale Attrattivo

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 è:


Navigazione con Funzioni Potenziali : Potenziale Repulsivo

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

Navigazione con Funzioni Potenziali : Potenziale Repulsivo (1)

Se di(q) va a zero allora il gradiente va a infinito!

Navigazione con Funzioni Potenziali : Potenziale Repulsivo

L’algoritmo di discesa del gradiente

Navigazione con Funzioni Potenziali : Discesa del Gradiente
 
Navigazione con Funzioni Potenziali : Discesa del Gradiente. Algoritmo

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

Navigazione con Funzioni Potenziali : Minimi Locali

Il potenziale attrattivo e quello repulsivo si controbilanciano!!


Esistono approcci per risolvere il problema dei minimi locali:

  1. '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
  2. Navigation Functions: Libro: Principles of Robot Motion

Altri algoritmi di navigazione

Testi sull'argomento

Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox