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

Ejemplo de 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 ruta no válida.
Ejemplo de hoja de ruta.

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.

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.

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

Holonómico

  • Brazos manipuladores (con dinámica)

No holonómico

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

Incertidumbre

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

Aplicaciones

Ver también

Referencias

Otras lecturas

enlaces externos