Planificación de movimiento - Motion planning
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
Un problema básico de planificación de movimiento es calcular una ruta continua que conecte una configuración inicial S y una configuración objetivo G, evitando al mismo tiempo 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 (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 2 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, θ ).
- 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 3 SO (3), y una configuración requiere 6 parámetros: (x, y, z) para traslación y ángulos de Euler (α, β, γ).
- 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 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).
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 los algoritmos de búsqueda (como A * ) se utilizan 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 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. El pavimento se descompone en dos subpavimentos X - , X + realizados con cajones tales 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.
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.
Algoritmos geométricos
Señale robots entre obstáculos poligonales.
Traducir objetos entre obstáculos
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 emite 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. Una función de navegación o una función de navegación probabilística 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 . Nuevamente, la detección de colisiones se usa 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. 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 de hitos cercanos, 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 realizando una caminata aleatoria de Monte Carlo en cadena de Markov direccional con alguna distribución de propuesta local.
- Es posible reducir sustancialmente la cantidad 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).
- 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
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 integridad 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
- Brazos manipuladores (con dinámica)
- Drones
- 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
- 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
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
- "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