Obstáculo de velocidad

Término en robótica y planificación del movimiento.

El obstáculo de velocidad VO _AB para un robot A , con posición x _A , inducido por otro robot B , con posición x _B y velocidad v _B .

En robótica y planificación de movimiento , un obstáculo de velocidad , comúnmente abreviado VO , es el conjunto de todas las velocidades de un robot que resultarán en una colisión con otro robot en algún momento en el tiempo, asumiendo que el otro robot mantiene su velocidad actual. ^[1] Si el robot elige una velocidad dentro del obstáculo de velocidad, entonces los dos robots eventualmente chocarán, si elige una velocidad fuera del obstáculo de velocidad, se garantiza que dicha colisión no ocurrirá. ^[1]

Este algoritmo para evitar colisiones de robots ha sido redescubierto y publicado repetidamente bajo diferentes nombres: en 1989 como una aproximación de tablero de maniobras , ^[2] en 1993 se introdujo por primera vez como el "obstáculo de velocidad", ^[3] en 1998 como conos de colisión, ^[4] y en 2009 como mapas de velocidad prohibida. ^[5] El mismo algoritmo se ha utilizado en la navegación portuaria marítima desde al menos 1903. ^[6]

El obstáculo de velocidad para un robot inducido por un robot puede escribirse formalmente como ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle VO_{A|B}=\{\mathbf {v} \,|\,\exists t>0:(\mathbf {v} -\mathbf {v} _{B})t\in D(\mathbf {x} _{B}-\mathbf {x} _{A},r_{A}+r_{B})\}}$

donde tiene posición y radio , y tiene posición , radio y velocidad . La notación representa un disco con centro y radio . ${\displaystyle A}$ ${\displaystyle \mathbf {x} _{A}}$ ${\displaystyle r_{A}}$ ${\displaystyle B}$ ${\displaystyle \mathbf {x} _{B}}$ ${\displaystyle r_{B}}$ ${\displaystyle \mathbf {v} _{B}}$ ${\displaystyle D(\mathbf {x} ,r)}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle r}$

Las variaciones incluyen obstáculos de velocidad comunes (CVO), ^[7] obstáculos de velocidad de intervalo de tiempo finito (FVO), ^{[8] obstáculos de velocidad} generalizados (GVO), ^{[9] obstáculos de velocidad recíprocos} híbridos (HRVO), ^{[10] obstáculos de velocidad} no lineales (NLVO), ^[11] obstáculos de velocidad recíprocos (RVO), ^[12] y obstáculos de velocidad probabilísticos recursivos (PVO). ^[13]

Referencias

1. Fiorini, P.; Shiller, Z. (julio de 1998). "Planificación del movimiento en entornos dinámicos utilizando obstáculos de velocidad". Revista internacional de investigación en robótica . 17 (7): 760–772. CiteSeerX  10.1.1.56.6352 . doi :10.1177/027836499801700706. ISSN  0278-3649. S2CID  9073894.
2. Tychonievich, LP; Zaret, D.; Mantegna, R.; Evans, R.; Muehle, E.; Martin, S. (1989). Un enfoque de tablero de maniobras para la planificación de rutas con obstáculos en movimiento . Conferencia conjunta internacional sobre inteligencia artificial (IJCAI). págs. 1017–1021.
3. Fiorini, P.; Shiller, Z. (1993). Planificación del movimiento en entornos dinámicos utilizando el paradigma de velocidad relativa . Conferencia IEEE sobre Robótica y Automatización. págs. 560–565.
4. Chakravarthy, A.; Ghose, D. (septiembre de 1998). "Evitación de obstáculos en un entorno dinámico: un enfoque de cono de colisión". IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans . 28 (5): 562–574. CiteSeerX 10.1.1.101.2050 . doi :10.1109/3468.709600. 
5. Damas, B.; Santos-Victor, J. (2009). Evitar obstáculos en movimiento: el mapa de velocidad prohibida . IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 4393–4398.
6. Miller, FS; Everett, AF (1903). Instrucciones para el uso del tablero de amarre de Martin y el indicador de rumbo de Battenberg . Autoridad de los Lores Comisionados del Almirantazgo.
7. Abe, Y.; Yoshiki, M. (noviembre de 2001). Método de prevención de colisiones para múltiples agentes móviles autónomos mediante cooperación implícita . IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 01). Nueva York, NY : IEEE . págs. 1207–1212. doi :10.1109/IROS.2001.977147.
8. Guy, SJ; Chhugani, J.; Kim, C.; Satish, N.; Lin, M.; Manocha, D.; Dubey, P. (agosto de 2009). ClearPath: prevención de colisiones altamente paralelas para simulación de múltiples agentes . Simposio ACM SIGGRAPH/Eurographics sobre animación por computadora (SCA 09). Nueva York, NY : ACM . págs. 177–187. doi :10.1145/1599470.1599494.
9. Wilkie, D.; vd Berg, J.; Manocha, D. (octubre de 2009). Obstáculos de velocidad generalizados . IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 09). Nueva York, NY : IEEE . doi :10.1109/IROS.2009.5354175.
10. Snape, J.; vd Berg, J.; Guy, SJ; Manocha, D. (octubre de 2009). Navegación independiente de múltiples robots móviles con obstáculos híbridos de velocidad recíproca. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 09). Nueva York, NY : IEEE .
11. Large, F.; Sekhavat, S.; Shiller, Z.; Laugier, C. (diciembre de 2002). Uso de obstáculos de velocidad no lineal para planificar movimientos en un entorno dinámico . IEEE International Conference on Control, Automation, Robotics and Vision (ICARCV 02). Nueva York, NY : IEEE . págs. 734–739. doi :10.1109/ICARCV.2002.1238513.
12. vd Berg, J. ; Lin, M.; Manocha, D. (mayo de 2008). Obstáculos de velocidad recíproca para navegación multiagente en tiempo real . IEEE International Conference on Robotics and Automation (ICRA 08). Nueva York, NY : IEEE . págs. 1928–1935. CiteSeerX 10.1.1.127.6140 . doi :10.1109/ROBOT.2008.4543489. 
13. Fulgenzi, C.; Spalanzani, A.; Laugier, C. (abril de 2007). Evitación dinámica de obstáculos en un entorno incierto combinando PVO y cuadrícula de ocupación . IEEE International Conference on Robotics and Automation (ICRA 07). Nueva York, NY : IEEE . págs. 1610–1616. CiteSeerX 10.1.1.696.8423 . doi :10.1109/ROBOT.2007.363554.