Planificación cinedinámica

Muchos algoritmos heurísticos prácticos basados ​​en optimización estocástica y muestreo iterativo han sido desarrollados por una amplia gama de autores para abordar el problema de planificación cinedinámica. Los enfoques populares incluyen extensiones de algoritmos RRT como RRT* para sistemas cinedinámicos y métodos basados ​​en muestreo como el control de integral de trayectoria predictiva de modelo (MPPI). Se ha demostrado que estas técnicas estocásticas funcionan bien en la práctica y pueden manejar espacios de estados complejos y de alta dimensión de manera más eficiente que los métodos deterministas. Sin embargo, todos los métodos de planificación de movimiento están sujetos a la dureza PSPACE de la planificación de movimiento clásica incluso sin dinámica, lo que significa (suponiendo las conjeturas habituales de complejidad estructural) que todos pueden ser de tiempo exponencial en el peor de los casos en la dimensión del espacio de estados ^{[ 1 ]} (el número de grados de libertad). Por otro lado, los métodos deterministas tienen garantías demostrables ^{[ 1 ]} de completitud, precisión y complejidad ^{[ 2 ] [ 3 ]} (para una dimensión fija, son de tiempo polinomial no solo en la complejidad geométrica, sino también en${\displaystyle (1/\varepsilon )}$, la cercanía de la aproximación deseada), mientras que la mayoría de los métodos heurísticos/estocásticos recientes sacrifican al menos uno de estos criterios.

Los recientes avances en programación entera mixta han posibilitado nuevos enfoques deterministas para la planificación cinemática. Estos métodos formulan el problema de planificación como una tarea de optimización que determina simultáneamente la trayectoria espacial y la secuencia de control, respetando todas las restricciones cinemáticas. ^{[ 4 ]} Mediante el uso de técnicas como las envolventes de McCormick para manejar restricciones bilineales, estos enfoques pueden proporcionar soluciones óptimas globales con garantías matemáticas, logrando además una aceleración computacional significativa en comparación con los métodos tradicionales.

Los algoritmos genéticos también se han adaptado para la planificación cinemática, en particular para la optimización sin gradiente en terrenos difíciles. Estos métodos utilizan computación evolutiva para optimizar trayectorias en horizontes que se alejan, con operadores de mutación especializados que aseguran que los controles del vehículo se mantengan dentro de los límites operativos. ^{[ 5 ]} Este enfoque es particularmente útil cuando se trata de funciones de costo no diferenciables o cuando la información del gradiente no está disponible o no es confiable.

El trabajo teórico fundamental de la década de 1990 ^{[ 1 ]} se extendió a grados de libertad superiores, e incluso a${\displaystyle n}$-link, robots cinemáticos de cadena abierta 3D bajo dinámica lagrangiana completa . ^{[ 2 ] [ 3 ]} Sin embargo, muchas de las técnicas heurísticas subsiguientes (que suelen emplear optimización estocástica) se limitaron a entornos planos. La planificación cinedinámica más reciente se ha extendido más allá de estos entornos planos para manejar terrenos 3D complejos representados como complejos simpliciales o mallas triangulares. Este avance es particularmente importante para aplicaciones como la navegación de vehículos autónomos en entornos todoterreno, donde los cambios de elevación y la geometría del terreno impactan significativamente la dinámica del vehículo. Estos métodos deben tener en cuenta los ángulos de cabeceo, la curvatura de la superficie y el acoplamiento entre la geometría del terreno y las restricciones cinemáticas del vehículo.