La planificación del movimiento , también planificación de la ruta (también conocida como problema de navegación o problema del movimiento del piano ), es un problema computacional para encontrar una secuencia de configuraciones válidas que mueva el objeto desde el origen hasta el destino. El término se utiliza en geometría computacional , animación por computadora , robótica y juegos de computadora .
Por ejemplo, considere conducir un robot móvil dentro de un edificio hasta un punto de ruta distante. Debe ejecutar esta tarea evitando las paredes y no cayendo 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 del movimiento podrían abordar robots con un mayor número de articulaciones (por ejemplo, manipuladores industriales), tareas más complejas (por ejemplo, manipulación de objetos), diferentes restricciones (por ejemplo, un automóvil que sólo puede avanzar) e incertidumbre (por ejemplo, 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 , los videojuegos , el diseño arquitectónico , la cirugía robótica y el estudio de moléculas biológicas .
Un problema básico de planificación del movimiento es calcular una trayectoria 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 los obstáculos se describe en un espacio de trabajo 2D o 3D, mientras que el movimiento se representa como una ruta en un espacio de configuración (posiblemente de dimensiones superiores) .
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:
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 llama obstáculo o región prohibida.
A menudo, resulta prohibitivamente difícil calcular explícitamente la forma de C libre . Sin embargo, probar si una configuración determinada está libre de C es eficiente. Primero, la cinemática directa determina la posición de la geometría del robot y la detección de colisiones prueba si la geometría del robot choca con la geometría del entorno.
El espacio objetivo es un subespacio del espacio libre que indica hacia dónde queremos que se mueva el robot. En la planificación global del movimiento, el espacio objetivo es observable mediante los sensores del robot. 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 pasa por varios espacios de destino virtuales, cada uno de los cuales está ubicado dentro del área observable (alrededor del robot). Un espacio objetivo virtual se denomina submeta.
El espacio de obstáculos es un espacio al que el robot no puede moverse. El espacio con obstáculos no es lo opuesto al espacio libre.
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 libre .
La planificación exacta del movimiento para sistemas de alta dimensión bajo restricciones complejas es computacionalmente intratable . Los algoritmos de campo potencial son eficientes, pero son víctimas de mínimos locales (una excepción son los campos potenciales armónicos). 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 ningún camino, pero tienen una probabilidad de falla que disminuye a cero a medida que se pasa 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 ).
Los enfoques basados en cuadrículas superponen una cuadrícula en el espacio de configuración y asumen que cada configuración está identificada 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 colisiones). Esto discretiza el conjunto de acciones y se utilizan algoritmos de búsqueda (como A* ) para encontrar un camino desde el principio hasta el objetivo.
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 inadecuados 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 base determinado, lo que a menudo resulta en rutas subóptimas. Los enfoques de planificación de rutas en cualquier ángulo encuentran rutas más cortas propagando 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 replanifican rápidamente utilizando la experiencia con problemas de planificación de rutas similares anteriores para acelerar la búsqueda del actual.
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. [1] El pavimento se descompone en dos subpavimentos X − ,X + realizados con cajones tales que X − ⊂ C libre ⊂ X + . Caracterización de cantidades libres de C para resolver un problema de inversión de conjuntos . Por lo tanto, el análisis de intervalos podría usarse cuando el C libre no puede describirse mediante desigualdades lineales para tener un recinto garantizado.
Por tanto, al robot se le permite moverse libremente en X − y no puede salir de X + . Para ambos subpavimentos, se construye un gráfico vecino y se pueden encontrar caminos usando algoritmos como Dijkstra o A* . Cuando un camino es factible en X − , también lo es en C libre . Cuando no existe ningún camino en X + desde una configuración inicial hasta el objetivo, tenemos la garantía de que no existe ningún camino factible en C libre . En cuanto al enfoque basado en cuadrícula, 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.
Una ilustración la proporcionan las tres figuras de la derecha, donde un gancho con dos grados de libertad tiene que moverse de izquierda a derecha, evitando dos pequeños segmentos horizontales.
Nicolas Delanoue ha demostrado que 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. [2]
Robots puntuales entre obstáculos poligonales.
Traducir objetos entre obstáculos.
Encontrar la salida de un edificio
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 las salidas de emergencia de los edificios.
Un enfoque es tratar la configuración del robot como un punto en un campo potencial que combina atracción hacia la meta y repulsión hacia los obstáculos. La trayectoria resultante se genera como ruta. Este enfoque tiene la ventaja 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 un camino, o pueden encontrar un camino no óptimo. Los campos potenciales artificiales pueden tratarse como ecuaciones continuas similares a los campos potenciales electrostáticos (tratando al robot como una carga puntual), o el movimiento a través del campo puede discretizarse utilizando un conjunto de reglas lingüísticas. [3] Una función de navegación [4] o una función de navegación probabilística [5] son tipos de funciones potenciales artificiales que tienen la cualidad de no tener puntos mínimos excepto el punto objetivo.
Los algoritmos basados en muestreo representan el espacio de configuración con una hoja de ruta de configuraciones muestreadas. Un algoritmo básico muestra N configuraciones en C y conserva aquellas en C de forma gratuita para usarlas como hitos . Luego se construye una hoja de ruta que conecta dos hitos P y Q si el segmento de línea PQ está completamente libre en C. Nuevamente, la detección de colisiones se utiliza para probar la inclusión en C free . Para encontrar un camino 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. De lo contrario, el motivo no es definitivo: o no hay una ruta libre en C o el planificador no tomó muestras de 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 dedica más tiempo. Sin embargo, no pueden determinar si no existe una solución.
Dadas las condiciones básicas de visibilidad en C free , 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. [6] La visibilidad no depende explícitamente de la dimensión de C; es posible tener un espacio de altas dimensiones con "buena" visibilidad o un espacio de bajas dimensiones con "mala" visibilidad. El éxito experimental de los métodos basados en muestras sugiere que los espacios más comúnmente vistos tienen buena visibilidad.
Hay muchas variantes de este esquema básico:
Se dice que un planificador de movimiento está completo si en un tiempo finito produce una solución o informa correctamente que no hay ninguna. La mayoría de los algoritmos completos se basan en la geometría. El rendimiento de un planificador completo se evalúa por su complejidad computacional . Al demostrar matemáticamente esta propiedad, hay que asegurarse de que ocurra en un tiempo finito y no sólo en el límite asintótico. Esto es especialmente problemático si ocurren secuencias infinitas (que convergen sólo en el caso límite) durante una técnica de demostración 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 hacen sólo 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 sirve en la mayoría de los casos como fundamento/guía teórica. Los planificadores basados en un enfoque de fuerza bruta siempre son completos, pero sólo 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 permite sólo un número máximo de iteraciones y luego siempre se detiene con o sin solución. Para sistemas en tiempo real, esto normalmente se logra mediante el uso de un temporizador de vigilancia , que simplemente detendrá el proceso. El mecanismo de vigilancia debe ser independiente de todos los procesos (normalmente realizado mediante rutinas de interrupción de bajo nivel). Sin embargo, de esta forma no se llegará al caso asintótico descrito en el párrafo anterior. Informará cuál es el mejor que ha encontrado hasta el momento (que es mejor que nada) o ninguno, pero no puede informar correctamente que no hay ninguno. Todas las realizaciones, incluido un perro guardián, son siempre incompletas (excepto que todos los casos pueden evaluarse en un tiempo finito).
La integridad solo se puede lograr 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 integridad es fácil, ya que sólo se necesita encontrar un bucle infinito o un resultado incorrecto. 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 integridad de la resolución es la propiedad que garantiza que el planificador encontrará una ruta si la resolución de una cuadrícula subyacente es lo suficientemente buena. La mayoría de los planificadores completos de resolución se basan en cuadrículas o intervalos. La complejidad computacional de los planificadores de resolución completa 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 la cuadrícula) y d es la configuración. dimensión espacial.
La completitud 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 se suele utilizar esta propiedad, ya que permite configurar el tiempo de espera del watchdog en función de un tiempo medio de convergencia.
Los planificadores incompletos no siempre producen un camino factible cuando existe (ver 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 tomen el control.
Se han desarrollado muchos algoritmos para manejar variantes de este problema básico.
Los sistemas híbridos son aquellos que mezclan comportamiento discreto y continuo. Ejemplos de tales sistemas son:
{{cite book}}: |journal=ignorado ( ayuda )