Planificación de movimiento

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

• Si el robot es un punto único (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 usando dos parámetros (x, y).
• Si el robot es una figura 2D que puede trasladarse y rotar, el espacio de trabajo sigue siendo bidimensional. Sin embargo, C es el grupo euclidiano especial SE (2) = R ²${\displaystyle \times }$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 es una figura sólida 3D que puede trasladarse y rotar, el espacio de trabajo es tridimensional, pero C es el grupo euclidiano especial SE(3) = R ³${\displaystyle \times }$SO (3), entonces la configuración requiere 6 parámetros: (x, y, z) para la traslación y los ángulos de Euler (α, β, γ).
• Si el robot es un manipulador de base fija con N articulaciones de revolución (y sin bucles cerrados), C es N-dimensional.
• Si el bloqueo de cardán no es aceptable (por ejemplo, en R ^N donde N ≥ 3 ), entonces puede ser necesario el uso de cuaterniones u otras soluciones alternativas, lo que aumenta las dimensiones de rotación o la complejidad de la solución.

El conjunto de configuraciones que evitan la colisión con obstáculos se denomina espacio libre C _{_free} . El complemento de C _{_free} en C se denomina región de obstáculos o región prohibida.

A menudo, resulta prohibitivamente difícil calcular explícitamente la forma de C _libre . Sin embargo, comprobar si una configuración dada está en C _libre es eficiente. En primer lugar, la cinemática directa determina la posición de la geometría del robot, y la detección de colisiones comprueba si la geometría del robot colisiona 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 de movimiento global, el espacio objetivo es observable por los sensores del robot. Sin embargo, en la planificación de movimiento local, el robot no puede observar el espacio objetivo en algunos estados. Para solucionar este problema, el robot recorre varios espacios objetivo virtuales, cada uno ubicado dentro del área observable (alrededor del robot). Un espacio objetivo virtual se denomina subobjetivo.

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

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

Estos métodos 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 dimensionalidad.

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

Los enfoques basados ​​en cuadrículas a menudo requieren búsquedas repetidas, por ejemplo, cuando cambia el conocimiento del robot sobre el espacio de configuración o cuando el propio espacio de configuración cambia durante el seguimiento de la trayectoria. Los algoritmos de búsqueda heurística incremental replanifican rápidamente utilizando la experiencia con problemas de planificación de trayectorias similares anteriores para acelerar la búsqueda del problema 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 ⁺ hechos con cajas tales que X ⁻ ⊂ C _free ⊂ X ⁺ . Caracterizar C _free equivale a resolver un problema de inversión de conjuntos . Por lo tanto, el análisis de intervalos podría usarse cuando C _free no puede describirse mediante desigualdades lineales para tener un cerco garantizado.

El robot puede moverse libremente en X ⁻ , pero no puede salir de X ⁺ . Para ambos subpavimentos, se construye un grafo de vecindad y se pueden encontrar caminos usando algoritmos como Dijkstra o A* . Cuando un camino es factible en X ⁻ , también lo es en C _free . 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 _free . En cuanto al enfoque basado en cuadrícula, el enfoque de intervalos es inapropiado para problemas de alta dimensión, debido a 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 ilustran este ejemplo: un gancho con dos grados de libertad debe moverse de izquierda a derecha, evitando dos pequeños segmentos horizontales.

Nicolas Delanoue ha demostrado que la descomposición con subpavimentos utilizando análisis de intervalos también permite caracterizar la topología de C _libre , como por ejemplo contar su número de componentes conexas. ^{[ 2 ]}

Robots apuntando entre obstáculos poligonales

• Gráfico de visibilidad
• Descomposición celular
• Diagrama de Voronoi

Trasladar objetos entre obstáculos

• suma de Minkowski

Cómo encontrar la salida de un edificio

• trazado del rayo más lejano

Dado un conjunto de rayos alrededor de la posición actual, cuya longitud coincide con la de un rayo que impacta contra 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 evacuación de emergencia de edificios.

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 obtiene como el camino. Este enfoque tiene ventajas, ya que la trayectoria se genera con poco cálculo. Sin embargo, puede quedar atrapado en mínimos locales del campo potencial y no encontrar un camino, o bien 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 bien 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 un mapa de ruta de configuraciones muestreadas. Un algoritmo básico muestrea N configuraciones en C y conserva aquellas en C _libres para usarlas como hitos . Luego se construye un mapa de ruta que conecta dos hitos P y Q si el segmento de línea PQ está completamente en C _libre . Nuevamente, se usa la detección de colisiones para probar la inclusión en C _libre . Para encontrar una ruta que conecte S y G, se agregan al mapa de ruta. Si una ruta en el mapa de ruta une S y G, el planificador tiene éxito y devuelve esa ruta. Si no, la razón no es definitiva: o no hay ninguna ruta en C _libre , o el planificador no muestreó suficientes hitos.

Estos algoritmos funcionan bien para espacios de configuración de alta dimensión, ya que, a diferencia de los algoritmos combinatorios, su tiempo de ejecución no depende (explícitamente) de forma exponencial de la dimensión de C. Además, suelen ser mucho más fáciles de implementar. Son probabilísticamente completos, lo que significa que la probabilidad de que produzcan una solución se aproxima a 1 a medida que se invierte más tiempo. Sin embargo, no pueden determinar si no existe ninguna 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 aproxima exponencialmente a 1. ^{[ 6 ]} 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 la mayoría de los espacios que se ven con frecuencia tienen buena visibilidad.

Existen 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 ubicar 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 del muestreo.
• Emplea muestreo local ^{[ 7 ]} realizando una caminata aleatoria de Monte Carlo de 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 al permitir visiones curvas (por ejemplo, gateando sobre los obstáculos que bloquean el camino entre dos hitos ^{[ 8 ]} ).
• Si solo se necesitan una o unas pocas consultas de planificación, no siempre es necesario construir un mapa de ruta de todo el espacio. Las variantes de crecimiento de árbol suelen ser más rápidas en este caso (planificación de una sola consulta). Los mapas de ruta siguen siendo útiles si se van a realizar muchas consultas en el mismo espacio (planificación de múltiples consultas).

• A*
• Algoritmo de errores
• D*
• El algoritmo de Dijkstra
• Enfoque de ventana dinámica
• Hoja de ruta probabilística
• Árbol aleatorio de exploración rápida
• Theta*
• Histograma de campo vectorial

Holonómico

• Brazos manipuladores (con dinámica)

No holónomo

• Drones
• coches
• monociclos
• Aviones
• Sistemas con aceleración limitada
• Obstáculos en movimiento (el tiempo no puede retroceder)
• Aguja orientable con punta biselada
• Robots de accionamiento diferencial

Los sistemas híbridos son aquellos que combinan comportamientos discretos y continuos. Algunos ejemplos de estos sistemas son:

• Manipulación robótica
• Ensamblaje mecánico
• Locomoción de robots con patas
• Robots reconfigurables

• incertidumbre del movimiento
• Información faltante
• Detección activa
• Planificación sin sensores
• Sistemas de control en red ^{[ 9 ]}

• Mapas de dinámica ^{[ 10 ]}