Planificación de movimiento

Problema computacional

Este artículo necesita citas adicionales para su verificación . Por favor, ayuda a mejorar este artículo mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado. Encuentre fuentes:  "Planificación de movimiento"  -  noticias  · periódicos  · libros  · académico  · JSTOR ( junio de 2013 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

La planificación del movimiento , también la planificación de la ruta (también conocida como el problema de navegación o el problema del movimiento del piano ) es un problema computacional para encontrar una secuencia de configuraciones válidas que mueva el objeto desde el origen al destino. El término se utiliza en geometría computacional , animación por computadora , robótica y juegos de computadora .

Por ejemplo, considere la posibilidad de llevar un robot móvil dentro de un edificio a un punto de ruta distante. Debe ejecutar esta tarea evitando las paredes y sin caerse por las escaleras. Un algoritmo de planificación de movimiento tomaría una descripción de estas tareas como entrada y produciría los comandos de velocidad y giro enviados a las ruedas del robot. Los algoritmos de planificación de movimiento pueden abordar robots con un mayor número de articulaciones (p. Ej., Manipuladores industriales), tareas más complejas (p. Ej., Manipulación de objetos), diferentes restricciones (p. Ej., Un automóvil que solo puede avanzar) e incertidumbre (p. Ej., Modelos imperfectos de el entorno o el robot).

La planificación del movimiento tiene varias aplicaciones robóticas, como la autonomía , la automatización y el diseño de robots en software CAD , así como aplicaciones en otros campos, como la animación de personajes digitales , videojuegos , diseño arquitectónico , cirugía robótica y el estudio de moléculas biológicas .

Conceptos

Ejemplo de un espacio de trabajo.

Espacio de configuración de un robot del tamaño de un punto. Blanco = C _libre , gris = C _obs .

Espacio de configuración para un robot traductor rectangular (en la imagen en rojo). Blanco = C _libre , gris = C _obs , donde gris oscuro = los objetos, gris claro = configuraciones donde el robot tocaría un objeto o dejaría el espacio de trabajo.

Ejemplo de ruta válida.

Ejemplo de una ruta no válida.

Ejemplo de hoja de ruta.

Un problema básico de planificación de movimiento es calcular una ruta continua que conecta una configuración inicial S y una configuración objetivo G, evitando la colisión con obstáculos conocidos. La geometría del robot y el obstáculo se describe en un espacio de trabajo 2D o 3D , mientras que el movimiento se representa como una trayectoria en un espacio de configuración (posiblemente de mayor dimensión) .

Espacio de configuración

Una configuración describe la pose del robot y el espacio de configuración C es el conjunto de todas las configuraciones posibles. Por ejemplo:

• Si el robot es un solo punto (de tamaño cero) que se traslada en un plano bidimensional (el espacio de trabajo), C es un plano y una configuración se puede representar mediante dos parámetros (x, y).
• Si el robot tiene una forma bidimensional que se puede trasladar y rotar, el espacio de trabajo sigue siendo bidimensional. Sin embargo, C es el grupo euclidiano especial SE (2) = R ² SO (2) (donde SO (2) es el grupo ortogonal especial de rotaciones 2D), y una configuración se puede representar usando 3 parámetros (x, y, θ ).${\displaystyle \times }$
• Si el robot tiene una forma sólida en 3D que se puede trasladar y rotar, el espacio de trabajo es tridimensional, pero C es el grupo euclidiano especial SE (3) = R ³ SO (3), y una configuración requiere 6 parámetros: (x, y, z) para traslación y ángulos de Euler (α, β, γ).${\displaystyle \times }$
• Si el robot es un manipulador de base fija con N articulaciones giratorias (y sin bucles cerrados), C es N-dimensional.

Espacio libre

El conjunto de configuraciones que evita la colisión con obstáculos se denomina espacio _libre C _libre . El complemento de C _libre en C se denomina obstáculo o región prohibida.

A menudo, es prohibitivamente difícil calcular explícitamente la forma de C _libre . Sin embargo, probar si una configuración dada está en C _libre es eficiente. Primero, la cinemática de avance determina la posición de la geometría del robot y las pruebas de detección de colisiones si la geometría del robot choca con la geometría del entorno.

Espacio objetivo

El espacio objetivo es un subespacio de espacio libre que indica hacia dónde queremos que se mueva el robot. En la planificación del movimiento global, los sensores del robot pueden observar el espacio objetivo. Sin embargo, en la planificación del movimiento local, el robot no puede observar el espacio objetivo en algunos estados. Para resolver este problema, el robot atraviesa varios espacios de destino virtuales, cada uno de los cuales se encuentra dentro del área observable (alrededor del robot). Un espacio objetivo virtual se denomina subobjetivo.

Espacio de obstáculos

El espacio de obstáculos es un espacio al que el robot no puede moverse. El espacio de obstáculos no es opuesto al espacio libre.

Algoritmos

Los problemas de baja dimensión se pueden resolver con algoritmos basados ​​en cuadrículas que superponen una cuadrícula sobre el espacio de configuración, o algoritmos geométricos que calculan la forma y la conectividad de C _free .

La planificación de movimiento exacta para sistemas de alta dimensión bajo restricciones complejas es computacionalmente intratable . Los algoritmos de campo potencial son eficientes, pero caen presa de mínimos locales (una excepción son los campos de potencial armónico). Los algoritmos basados ​​en muestreo evitan el problema de los mínimos locales y resuelven muchos problemas con bastante rapidez. No pueden determinar que no existe una ruta, pero tienen una probabilidad de falla que disminuye a cero a medida que se gasta más tiempo.

Los algoritmos basados ​​en muestreo se consideran actualmente de última generación para la planificación del movimiento en espacios de alta dimensión y se han aplicado a problemas que tienen docenas o incluso cientos de dimensiones (manipuladores robóticos, moléculas biológicas, personajes digitales animados y patas robots ).

Existe el algoritmo paralelo de planificación de movimiento (A1-A2) para la manipulación de objetos (para atrapar el objeto volador). ^[1]

Búsqueda basada en cuadrículas

Los enfoques basados ​​en cuadrículas superponen una cuadrícula en el espacio de configuración y asumen que cada configuración se identifica con un punto de cuadrícula. En cada punto de la cuadrícula, el robot puede moverse a puntos de la cuadrícula adyacentes siempre que la línea entre ellos esté completamente contenida dentro de C _libre (esto se prueba con detección de colisión). Esto discretiza el conjunto de acciones y se utilizan algoritmos de búsqueda (como A * ) para encontrar un camino desde el principio hasta la meta.

Estos enfoques requieren establecer una resolución de cuadrícula. La búsqueda es más rápida con cuadrículas más gruesas, pero el algoritmo no podrá encontrar rutas a través de porciones estrechas de C _libre . Además, el número de puntos en la cuadrícula crece exponencialmente en la dimensión del espacio de configuración, lo que los hace inapropiados para problemas de alta dimensión.

Los enfoques tradicionales basados ​​en cuadrículas producen rutas cuyos cambios de rumbo están restringidos a múltiplos de un ángulo de base dado, lo que a menudo resulta en rutas subóptimas. Los enfoques de planificación de rutas en cualquier ángulo encuentran rutas más cortas al propagar información a lo largo de los bordes de la cuadrícula (para buscar rápidamente) sin restringir sus rutas a los bordes de la cuadrícula (para encontrar rutas cortas).

Los enfoques basados ​​en cuadrículas a menudo necesitan buscar repetidamente, por ejemplo, cuando el conocimiento del robot sobre el espacio de configuración cambia o el propio espacio de configuración cambia durante el seguimiento de la ruta. Los algoritmos de búsqueda heurística incremental se replanifican rápidamente utilizando la experiencia con los problemas de planificación de rutas similares anteriores para acelerar la búsqueda del actual.

Búsqueda basada en intervalos

Estos enfoques son similares a los enfoques de búsqueda basados ​​en cuadrículas, excepto que generan un pavimento que cubre completamente el espacio de configuración en lugar de una cuadrícula. ^[2] El pavimento se descompone en dos subpavimentos X ^- , X ⁺ realizados con cajas de manera que X ^- ⊂ C _libre ⊂ X ⁺ . Caracterizar C _libre equivale a resolver un problema de inversión de conjuntos . Por lo tanto, el análisis de intervalos podría usarse cuando C _libre no puede describirse mediante desigualdades lineales para tener un encerramiento garantizado.

Por tanto, el robot puede moverse libremente en X ^- y no puede salir de X ⁺ . Para ambos subpavimentos, se construye un gráfico vecino y las rutas se pueden encontrar utilizando algoritmos como Dijkstra o A * . Cuando un camino es factible en X ^- , también lo es en C _libre . Cuando no existe una ruta en X ⁺ desde una configuración inicial hasta la meta, tenemos la garantía de que no existe una ruta factible en C _libre . En cuanto al enfoque basado en cuadrículas, el enfoque de intervalo es inapropiado para problemas de alta dimensión, debido al hecho de que el número de cajas a generar crece exponencialmente con respecto a la dimensión del espacio de configuración.

Las tres figuras de la derecha proporcionan una ilustración donde un gancho con dos grados de libertad debe moverse de izquierda a derecha, evitando dos pequeños segmentos horizontales.

Movimiento desde la configuración inicial (azul) hasta la configuración final del gancho, evitando los dos obstáculos (segmentos rojos). La esquina inferior izquierda del anzuelo debe permanecer en la línea horizontal, lo que hace que el anzuelo tenga dos grados de libertad.

Descomposición con cajas que cubren el espacio de configuración: La subpavimentación X ^- es la unión de todas las cajas rojas y la subpavimentación X ⁺ es la unión de las cajas rojas y verdes. El camino corresponde al movimiento representado arriba.

Esta cifra corresponde a la misma ruta que la anterior pero obtenida con muchas menos cajas. El algoritmo evita bisecar cuadros en partes del espacio de configuración que no influyen en el resultado final.

La descomposición con subpavimentos mediante análisis de intervalos también permite caracterizar la topología de C _libre , como contar su número de componentes conectados. ^[3]

Algoritmos geométricos

Señale robots entre obstáculos poligonales.

• Gráfico de visibilidad
• Descomposición celular

Traducir objetos entre obstáculos

• Suma de Minkowski

Encontrar la salida de un edificio

• rastro de rayo más lejano

Dado un haz de rayos alrededor de la posición actual atribuida con su longitud golpeando una pared, el robot se mueve en la dirección del rayo más largo a menos que se identifique una puerta. Este algoritmo se utilizó para modelar la salida de emergencia de los edificios.

Campos de potencial artificial

Un enfoque consiste en tratar la configuración del robot como un punto en un campo potencial que combina la atracción hacia el objetivo y la repulsión de los obstáculos. La trayectoria resultante se genera como ruta. Este enfoque tiene las ventajas de que la trayectoria se produce con pocos cálculos. Sin embargo, pueden quedar atrapados en mínimos locales del campo potencial y no encontrar una ruta, o pueden encontrar una ruta no óptima. Los campos de potencial artificial se pueden tratar como ecuaciones continuas similares a los campos de potencial electrostático (tratando al robot como una carga puntual), o el movimiento a través del campo se puede discretizar utilizando un conjunto de reglas lingüísticas. ^[4] Una función de navegación ^[5] o una función de navegación probabilística ^[6] son tipos de funciones potenciales artificiales que tienen la cualidad de no tener puntos mínimos excepto el punto objetivo.

Algoritmos basados ​​en muestreo

Los algoritmos basados ​​en muestreo representan el espacio de configuración con una hoja de ruta de configuraciones muestreadas. Un algoritmo básico toma muestras de N configuraciones en C y conserva las de C _libres para usarlas como hitos . Una hoja de ruta se construye a continuación, que conecta dos hitos P y Q si el PQ segmento de línea está completamente en C _libre . Una vez más, la detección de colisiones se utiliza para probar la inclusión en C _libre . Para encontrar una ruta que conecte S y G, se agregan a la hoja de ruta. Si una ruta en la hoja de ruta vincula S y G, el planificador tiene éxito y devuelve esa ruta. Si no es así, el motivo no es definitivo: o no hay una ruta en C _gratis o el planificador no muestreó suficientes hitos.

Estos algoritmos funcionan bien para espacios de configuración de alta dimensión, porque a diferencia de los algoritmos combinatorios, su tiempo de ejecución no depende (explícitamente) exponencialmente de la dimensión de C. También son (generalmente) sustancialmente más fáciles de implementar. Son probabilísticamente completos, lo que significa que la probabilidad de que produzcan una solución se acerca a 1 a medida que se gasta más tiempo. Sin embargo, no pueden determinar si no existe una solución.

Dadas las condiciones básicas de visibilidad en C _libre , se ha demostrado que a medida que aumenta el número de configuraciones N, la probabilidad de que el algoritmo anterior encuentre una solución se acerca a 1 exponencialmente. ^{[7] La} visibilidad no depende explícitamente de la dimensión de C; es posible tener un espacio de alta dimensión con "buena" visibilidad o un espacio de baja dimensión con "mala" visibilidad. El éxito experimental de los métodos basados ​​en muestras sugiere que los espacios que se ven con mayor frecuencia tienen buena visibilidad.

Hay muchas variantes de este esquema básico:

• Por lo general, es mucho más rápido probar solo los segmentos entre pares cercanos de hitos, en lugar de todos los pares.
• Las distribuciones de muestreo no uniformes intentan colocar más hitos en áreas que mejoran la conectividad de la hoja de ruta.
• Las muestras cuasialeatorias suelen producir una mejor cobertura del espacio de configuración que las pseudoaleatorias , aunque algunos trabajos recientes argumentan que el efecto de la fuente de aleatoriedad es mínimo en comparación con el efecto de la distribución muestral.
• Emplea muestreo local ^[8] realizando una caminata aleatoria de Monte Carlo en cadena de Markov direccional con alguna distribución de propuesta local.
• Es posible reducir sustancialmente el número de hitos necesarios para resolver un problema dado permitiendo miras con ojos curvados (por ejemplo, arrastrándose sobre los obstáculos que bloquean el camino entre dos hitos ^[9] ).
• Si solo se necesitan una o unas pocas consultas de planificación, no siempre es necesario construir una hoja de ruta de todo el espacio. Las variantes de crecimiento de árboles suelen ser más rápidas en este caso (planificación de consulta única). Las hojas de ruta siguen siendo útiles si se van a realizar muchas consultas en el mismo espacio (planificación de múltiples consultas)

Lista de algoritmos notables

• A*
• D*
• Árbol aleatorio de exploración rápida
• Hoja de ruta probabilística

Integridad y rendimiento

Se dice que un planificador de movimiento está completo si el planificador en un tiempo finito produce una solución o informa correctamente que no la hay. La mayoría de los algoritmos completos están basados ​​en geometría. El desempeño de un planificador completo se evalúa por su complejidad computacional. Al probar matemáticamente esta propiedad, hay que asegurarse de que ocurre en un tiempo finito y no solo en el límite asintótico. Esto es especialmente problemático, si ocurren secuencias infinitas (que convergen solo en el caso límite) durante una técnica de prueba específica, ya que entonces, teóricamente, el algoritmo nunca se detendrá. Por lo general, se piensa erróneamente que los "trucos" intuitivos (a menudo basados ​​en la inducción) convergen, lo que solo hacen para el límite infinito. En otras palabras, la solución existe, pero el planificador nunca la informará. Por lo tanto, esta propiedad está relacionada con la completitud de Turing y, en la mayoría de los casos, sirve como base / guía teórica. Los planificadores basados ​​en un enfoque de fuerza bruta siempre están completos, pero solo son realizables para configuraciones finitas y discretas.

En la práctica, la terminación del algoritmo siempre se puede garantizar mediante el uso de un contador, que solo permite un número máximo de iteraciones y luego siempre se detiene con o sin solución. Para los sistemas en tiempo real, esto generalmente se logra mediante el uso de un temporizador de vigilancia , que simplemente terminará el proceso. El perro guardián tiene que ser independiente de todos los procesos (normalmente realizado por rutinas de interrupción de bajo nivel). El caso asintótico descrito en el párrafo anterior, sin embargo, no se alcanzará de esta forma. Informará el mejor que haya encontrado hasta ahora (que es mejor que nada) o ninguno, pero no puede informar correctamente que no hay ninguno. Todas las realizaciones, incluido un perro guardián, siempre están incompletas (excepto que todos los casos pueden evaluarse en un tiempo finito).

La integridad solo puede proporcionarse mediante una prueba de corrección matemática muy rigurosa (a menudo con la ayuda de herramientas y métodos basados ​​en gráficos) y solo debe ser realizada por expertos especializados si la aplicación incluye contenido de seguridad. Por otro lado, refutar la completitud es fácil, ya que uno solo necesita encontrar un bucle infinito o un resultado incorrecto devuelto. La verificación formal / corrección de los algoritmos es un campo de investigación en sí mismo. La configuración correcta de estos casos de prueba es una tarea muy sofisticada.

La completitud de la resolución es la propiedad de que el planificador está garantizado para encontrar una ruta si la resolución de una cuadrícula subyacente es lo suficientemente fina. La mayoría de los planificadores completos de resolución se basan en cuadrículas o intervalos. La complejidad computacional de los planificadores completos de resolución depende del número de puntos en la cuadrícula subyacente, que es O (1 / h ^d ), donde h es la resolución (la longitud de un lado de una celda de cuadrícula) yd es la configuración dimensión espacial.

La integridad probabilística es la propiedad de que a medida que se realiza más "trabajo", la probabilidad de que el planificador no encuentre un camino, si existe, se acerca asintóticamente a cero. Varios métodos basados ​​en muestras son probabilísticamente completos. El desempeño de un planificador probabilísticamente completo se mide por la tasa de convergencia. Para aplicaciones prácticas, generalmente se usa esta propiedad, ya que permite configurar el tiempo de espera para el perro guardián basado en un tiempo de convergencia promedio.

Los planificadores incompletos no siempre producen un camino factible cuando existe uno (vea el primer párrafo). A veces, los planificadores incompletos funcionan bien en la práctica, ya que siempre se detienen después de un tiempo garantizado y permiten que otras rutinas se hagan cargo.

Variantes de problemas

Se han desarrollado muchos algoritmos para manejar variantes de este problema básico.

Restricciones diferenciales

Holonómico

• Brazos manipuladores (con dinámica)

No holonómico

• Drones ^[10]
• Carros
• Monociclos
• Aviones
• Sistemas delimitados por aceleración
• Obstáculos en movimiento (el tiempo no puede retroceder)
• Aguja orientable con punta biselada
• Robots de accionamiento diferencial

Restricciones de optimalidad

Sistemas híbridos

Los sistemas híbridos son aquellos que mezclan un comportamiento discreto y continuo. Ejemplos de tales sistemas son:

• Manipulación robótica
• Ensamble mecanico
• Locomoción de robot con patas
• Robots reconfigurables

Incertidumbre

• Incertidumbre de movimiento
• Falta información
• Detección activa
• Planificación sin sensores

Aplicaciones

• Navegación del robot
• Automatización
• El coche sin conductor
• Cirugía robótica
• Animación digital de personajes
• Plegado de proteínas ^[11]
• Seguridad y accesibilidad en el diseño arquitectónico asistido por computadora

Ver también

• Bloqueo de cardán : problema tradicional similar en ingeniería mecánica
• Planificación cinodinámica
• Problema de montañismo
• OMPL : la biblioteca de planificación de movimiento abierto
• Pathfinding
• Problemas de movimiento de guijarros : planificación de movimiento de varios robots
• Problema del camino más corto
• Obstáculo de velocidad

Referencias

1. Bodrenko, AI (2019). "Nuevo método de uso de robots móviles para mover carga en almacén" . Boletín de ciencia y práctica . 5 (6): 192–211. doi : 10.33619 / 2414-2948 / 43/26 .
2. Jaulin, L. (2001). "Planificación de rutas mediante intervalos y gráficos" (PDF) . Computación confiable . 7 (1).
3. Delanoue, N .; Jaulin, L .; Cottenceau, B. (2006). Contar el número de componentes conectados de un conjunto y su aplicación a la robótica (PDF) . Computación Paralela Aplicada, Notas de Conferencia en Ciencias de la Computación . Apuntes de conferencias en Ciencias de la Computación. 3732 . págs. 93-101. CiteSeerX 10.1.1.123.6764 . doi : 10.1007 / 11558958_11 . ISBN   978-3-540-29067-4.
4. Wolf, Joerg Christian; Robinson, Paul; Davies, Mansel (2004). "Planificación y control de trayectorias de campo vectorial de un robot autónomo en un entorno dinámico". Proc. Congreso Mundial de Robots FIRA 2004 . Busan, Corea del Sur: Documento 151.
5. Lavalle, Steven, Algoritmos de planificación Capítulo 8
6. Hacohen, Shlomi; Shoval, Shraga; Shvalb, Nir (2019). "Función de navegación de probabilidad para entornos estocásticos estáticos" . Revista Internacional de Control, Automatización y Sistemas . 17 (8): 2097–2113. doi : 10.1007 / s12555-018-0563-2 . S2CID 164509949 . 
7. Hsu, D .; JC Latombe, JC ; Motwani, R. (1997). "Planificación de rutas en espacios de configuración expansivos". Actas de la Conferencia Internacional sobre Robótica y Automatización . 3 . págs. 2719–2726. doi : 10.1109 / ROBOT.1997.619371 . ISBN 978-0-7803-3612-4. S2CID  11070889 .
8. Lai, Tin; Morere, Philippe; Ramos, Fabio; Francis, Gilad (2020). "Planificación basada en el muestreo local bayesiano" . IEEE Robotics and Automation Letters . 5 (2): 1954-1961. arXiv : 1909.03452 . doi : 10.1109 / LRA.2020.2969145 . ISSN 2377-3766 . S2CID 210838739 .  
9. Shvalb, N .; Ben Moshe, B .; Medina, O. (2013). "Un algoritmo de planificación de movimiento en tiempo real para un conjunto de mecanismos hiper-redundante". Robotica . 31 (8): 1327-1335. CiteSeerX 10.1.1.473.7966 . doi : 10.1017 / S0263574713000489 . 
10. Sharma, Abhishek; Basnayaka, Chathuranga M.Wijerathna; Jayakody, Dushantha Nalin K. (mayo de 2020). "Tecnologías de comunicación y redes para vehículos aéreos no tripulados: una encuesta" . Revista de aplicaciones informáticas y de red . 168 . arXiv : 2009.02280 . doi : 10.1016 / j.jnca.2020.102739 .
11. Steven M. LaValle (29 de mayo de 2006). Algoritmos de planificación . Prensa de la Universidad de Cambridge. ISBN 978-1-139-45517-6.

Otras lecturas

• Latombe, Jean-Claude (2012). Planificación del movimiento del robot . Springer Science & Business Media. ISBN 978-1-4615-4022-9.
• Algoritmos de planificación , Steven M. LaValle, 2006, Cambridge University Press, ISBN 0-521-86205-1 . 
• Principios del movimiento del robot: teoría, algoritmos e implementación , H. Choset, W. Burgard, S. Hutchinson, G. Kantor, LE Kavraki , K. Lynch y S. Thrun, MIT Press, abril de 2005.
• Mark de Berg; Marc van Kreveld; Mark Overmars y Otfried Schwarzkopf (2000). Geometría computacional (2ª ed. Revisada). Springer-Verlag . ISBN 978-3-540-65620-3. Capítulo 13: Planificación del movimiento del robot: págs. 267–290.

enlaces externos

Wikimedia Commons tiene medios relacionados con la planificación de movimiento .

• "Entorno virtual de automatización de robótica abierta", http://openrave.org/
• Jean-Claude Latombe habla sobre su trabajo con robots y planificación de movimiento, 5 de abril de 2000
• "Biblioteca de planificación de movimiento abierto ( OMPL )", http://ompl.kavrakilab.org
• "Biblioteca de estrategias de movimiento", http://msl.cs.uiuc.edu/msl/
• "Kit de planificación de movimiento", https://ai.stanford.edu/~mitul/mpk
• "Simox", http://simox.sourceforge.net
• "Planificación y control del movimiento del robot", http://www.laas.fr/%7Ejpl/book.html