Planificación de movimiento

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 Cfree.

La planificación exacta del movimiento para sistemas de alta dimensión bajo restricciones complejas es intratable computacionalmente. Los algoritmos de campo potencial son eficientes, pero caen presa de los 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.Son incapaces de determinar que no existe un camino, 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 vanguardia 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 robots con patas).

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 cuadriceditar

Los enfoques basados en cuadricula superponen una cuadricula en el espacio de configuración, y asumen que cada configuración se identifica con un punto de cuadricula. En cada punto de cuadrícula, se permite que el robot se mueva a puntos de cuadrícula adyacentes, siempre que la línea entre ellos esté completamente contenida dentro de Cfree (esto se prueba con detección de colisiones). Esto discretiza el conjunto de acciones, y los algoritmos de búsqueda (como un*) se utilizan 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 Cfree. Además, el número de puntos en la cuadrícula crece exponencialmente en la dimensión de espacio de configuración, lo que los hace inapropiados para problemas de alta dimensión.

Los enfoques tradicionales basados en cuadrículas producen trazados cuyos cambios de rumbo se limitan a múltiplos de un ángulo de base dado, lo que a menudo resulta en trazados subóptimos. Los enfoques de planificación de rutas de 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ícula a menudo necesitan buscar repetidamente, por ejemplo, cuando cambia el conocimiento del robot sobre el espacio de configuración o el propio espacio de configuración durante el seguimiento de rutas. Los algoritmos de búsqueda heurística incrementales se vuelven a planificar rápidamente mediante el uso de la experiencia con los problemas de planificación de rutas similares anteriores para acelerar su búsqueda del actual.

Búsqueda basada en intervaleseditar

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 subpavantes X -, X + hechos con cajas tales que X-Cf Cfree X X+. Caracterizar Cfree equivale a resolver un problema de inversión de conjunto. Por lo tanto, el análisis de intervalos podría usarse cuando Cfree no se puede describir por desigualdades lineales para tener un recinto garantizado.

El robot puede moverse libremente en X-y no puede salir de X+. Para ambos subpavientos, se construye un gráfico vecino y se pueden encontrar rutas utilizando algoritmos como Dijkstra o A*. Cuando una ruta es factible en X -, también es factible en Cfree. Cuando no existe una ruta en X+ desde una configuración inicial hasta el objetivo, tenemos la garantía de que no existe una ruta factible en Cfree. En cuanto al enfoque basado en cuadrículas, el enfoque por intervalos 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 en la que un gancho con dos grados de libertad tiene que moverse de izquierda a derecha, evitando dos pequeños segmentos horizontales.

La descomposición con subpavantes utilizando análisis de intervalos también permite caracterizar la topología de Cfree, como contar su número de componentes conectados.

Algoritmos geométricoseditar

Robots de puntos entre obstáculos poligonales

• Gráfico de visibilidad
• Descomposición de celdas

Traducir objetos entre obstáculos

• Suma de Minkowski

Encontrar la salida de un edificio

• Traza de rayos más lejanos

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 salidas de emergencia de edificios.

Campos de potencial artificialeditar

Un enfoque es tratar la configuración del robot como un punto en un campo potencial que combina la atracción hacia la meta y la repulsión de los obstáculos. La trayectoria resultante se genera como la trayectoria. Este enfoque tiene ventajas en que la trayectoria se produce con poco cálculo. 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 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 muestreoseditar

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 retiene las de Cfree para usar 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 en Cfree. Una vez más, la detección de colisiones se utiliza para probar la inclusión en Cfree. Para encontrar un camino que conecte S y G, se agregan a la hoja de ruta. Si una ruta en la hoja de ruta enlaza S y G, el planificador tiene éxito y devuelve esa ruta. Si no, la razón no es definitiva: o bien no hay un camino en Cfree, 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 Cfree, se ha demostrado que a medida que el número de configuraciones N aumenta, 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 más comúnmente vistos tienen buena visibilidad.

Hay muchas variantes de este esquema básico:

• Por lo general, es mucho más rápido probar solo 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 mejoren la conectividad de la hoja de ruta.
• Las muestras cuasirandom normalmente producen 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 de muestreo.
• Emplea muestreo local realizando una caminata aleatoria de cadena de Markov direccional de Monte Carlo con alguna distribución de propuesta local.
• Es posible reducir sustancialmente el número de hitos necesarios para resolver un problema dado permitiendo la visión curva de los ojos (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 cultivo de árboles suelen ser más rápidas para este caso (planificación de una sola consulta). Las hojas de ruta siguen siendo útiles si se van a realizar muchas consultas en el mismo espacio (planificación de consultas múltiples)

Lista de algoritmos destacadoseditar

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