Kinodynamic Planning

También llamado: kinodynamic motion planning
Categoría: Planning & manipulation › Motion planning
Etiquetas: motion-planning, dynamics, sampling-based-planning, trajectory-optimization, state-space

Planificación de movimiento que respeta tanto las restricciones geométricas, como las colisiones, como la dinámica del sistema, y encuentra entradas de control a lo largo del tiempo en lugar de solo un camino libre de colisiones.

Definición

Planificación cinodinámica (kinodynamic planning) es la planificación de movimiento en la que la solución debe cumplir a la vez restricciones cinemáticas, como evitar obstáculos y respetar los límites de las articulaciones, y restricciones dinámicas, como aceleraciones, fuerzas o pares acotados. El término lo introdujeron Donald, Xavier, Canny y Reif en 1993. En lugar de buscar un camino geométrico en el espacio de configuraciones y asignarle los tiempos después, un planificador cinodinámico busca una duración y una función de control cuya trayectoria resultante, obtenida integrando la dinámica del sistema, empiece en el estado inicial, se mantenga en el espacio libre y termine en una región objetivo.

Por tanto, la búsqueda se realiza en el espacio de estados, que incluye velocidades además de posiciones y a menudo tiene el doble de dimensión que el espacio de configuraciones. La principal dificultad es que, en general, dos estados cercanos no pueden unirse con una línea recta: conectarlos requiere resolver un problema de valores en la frontera de dos puntos bajo la dinámica, que es fácil para sistemas sencillos como los dobles integradores o los coches de Dubins, pero difícil en general. Los planificadores basados en muestreo, como el RRT cinodinámico introducido por LaValle y Kuffner, evitan esto haciendo crecer un árbol hacia delante: eligen un nodo, aplican controles muestreados o elegidos durante un tiempo corto y conservan los estados resultantes. Métodos posteriores como SST añaden la casi optimalidad asintótica sin necesitar una función de guiado (steering function).

Otras familias abordan el mismo problema de forma distinta. Los planificadores basados en búsqueda usan una retícula de primitivas de movimiento precalculadas, cada una de ellas dinámicamente factible. Los métodos de optimización de trayectorias, incluidos la colocación directa y el disparo (shooting), tratan los controles y los estados como variables de decisión y resuelven un programa no lineal con restricciones, que converge rápido localmente pero puede quedar atrapado en mínimos locales. Los sistemas prácticos suelen combinar ambos: una etapa de muestreo o de búsqueda encuentra una trayectoria factible y la optimización la refina después. Cuando la dinámica es incierta, como al empujar objetos, los planificadores pueden usar modelos aprendidos o residuales del sistema y planificar con controles en lazo abierto que luego corrige la realimentación.

Por qué importa

Los robots rápidos o pesados, los coches, los drones y los objetos empujados no pueden seguir caminos geométricos arbitrarios: un camino que ignora la cantidad de movimiento o los límites de los actuadores puede ser imposible de ejecutar. La planificación cinodinámica produce trayectorias que el sistema realmente puede seguir, lo que importa sobre todo cuando el robot se mueve rápido o tiene una autoridad de control limitada.

Aplicaciones clave

Planificación de trayectorias para coches y otros vehículos no holonómicos
Planificación de vuelo agresivo para drones y aeronaves de ala fija
Manipulación no prensil, como la planificación de secuencias de empujes
Movimientos rápidos de brazos cerca de los límites de par y velocidad
Planificación de movimiento de robots con patas y humanoides con dinámica de contacto
Maniobras de naves espaciales y vehículos submarinos

En la práctica

Un brazo robótico debe empujar una caja sobre una mesa hasta una región objetivo, evitando un obstáculo, sin agarrarla. El equipo modela el movimiento de la caja en función de parámetros del empuje como el punto de contacto, la dirección y la duración, usando un modelo analítico de empuje corregido por un residual aprendido. Un RRT cinodinámico muestrea acciones de empuje desde el estado actual de la caja, propaga cada una a través del modelo y añade al árbol las poses de la caja resultantes, descartando los empujes que colisionarían con el obstáculo. Cuando una rama alcanza la región objetivo, se ejecuta la secuencia de empujes, y la pose de la caja se vuelve a observar después de cada empuje para que el planificador pueda replanificar desde el estado real si el modelo se equivocó.

Ideas erróneas comunes

La planificación cinodinámica es planificación geométrica seguida de parametrización temporal — los pipelines desacoplados pueden producir caminos que ninguna trayectoria dinámicamente factible puede seguir, mientras que los planificadores cinodinámicos tienen en cuenta la dinámica durante la búsqueda
Cualquier planificador basado en muestreo puede hacerse cinodinámico cambiando la métrica de distancia — conectar dos estados requiere en general resolver un problema de valores en la frontera o propagar controles hacia delante, no trazar una línea recta
Un plan cinodinámico puede ejecutarse en lazo abierto — los errores del modelo y las perturbaciones se acumulan, así que el plan normalmente se sigue con un controlador por realimentación o se replanifica

Quién debería saberlo

Ingenieros de planificación de movimiento para vehículos, drones y brazos
Investigadores de manipulación que trabajan en empujes y otras tareas dinámicas
Ingenieros de planificación para conducción autónoma
Estudiantes de robótica que estudian la planificación más allá del espacio de configuraciones

Tecnologías relacionadas

RRT cinodinámico (Kinodynamic RRT)
Stable Sparse RRT (SST)
Planificadores de retícula de estados (State Lattice Planners)
Open Motion Planning Library (OMPL)
Optimización de trayectorias (Trajectory Optimization)

Términos relacionados

Proyectos relacionados

Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms
Ruckig: Real-time jerk-constrained time-optimal trajectory generation for robots and machines

Vídeos

6.8210 Spring 2024 Lecture 18: Sampling-based (kinodynamic) motion planning: underactuated