Anytime Motion Planning

También llamado: anytime planning, anytime planner
Categoría: Planning & manipulation › Motion planning
Etiquetas: motion-planning, sampling-based-planning, optimal-planning, real-time, bounded-computation

Planificación de movimiento que devuelve rápidamente un camino válido y luego lo sigue mejorando mientras haya tiempo, de modo que hay una respuesta utilizable siempre que se detenga el planificador.

Definición

Un planificador de movimiento anytime (anytime motion planner) produce una primera solución factible y libre de colisiones lo antes que puede y después dedica el tiempo restante a mejorarla, normalmente reduciendo la longitud del camino, el tiempo de ejecución u otro coste. En cada momento posterior a la primera solución dispone de la mejor respuesta hasta ese punto, que puede devolver si se le interrumpe. La idea procede de la noción más amplia de algoritmos anytime en inteligencia artificial, introducida por Dean y Boddy a finales de la década de 1980, en la que la calidad de la solución se intercambia por tiempo de cálculo y la relación entre ambos se describe mediante un perfil de rendimiento.

En la búsqueda en grafos, el comportamiento anytime suele obtenerse ejecutando primero una heurística ponderada e inflada y ajustando después el peso a la vez que se reaprovecha el esfuerzo de búsqueda anterior, como en Anytime Repairing A (ARA). En la planificación basada en muestreo, los planificadores asintóticamente óptimos como RRT y la variante PRM de los mapas de rutas probabilísticos son anytime por naturaleza: siguen muestreando y reconectando después de la primera solución, y el coste del mejor camino tiende al óptimo a medida que crece el número de muestras. Informed RRT y Batch Informed Trees (BIT) aceleran la fase de mejora restringiendo las muestras a la región que todavía podría contener un camino mejor. Un árbol aleatorio de exploración rápida** simple no es anytime en este sentido, porque se detiene en cuanto conecta con el objetivo, aunque se le pueden añadir reinicios o posprocesado.

La mejora con el tiempo rara vez es suave. El coste suele bajar a saltos, sobre todo cuando el planificador encuentra una ruta por un hueco distinto entre obstáculos, es decir, un camino en una nueva clase de homotopía, y puede haber tramos largos casi sin ganancia. Eso convierte la decisión de parar en un problema en sí mismo: parar demasiado pronto desperdicia calidad, parar demasiado tarde desperdicia tiempo que el robot podría dedicar a moverse. Los presupuestos de tiempo fijos son la práctica habitual, mientras que los métodos de metarrazonamiento aprenden o estiman cuándo ya no compensa seguir calculando.

Por qué importa

Los robots rara vez disponen de una cantidad de tiempo fija y conocida para planificar. Un planificador anytime ofrece casi de inmediato una alternativa segura y convierte cualquier tiempo sobrante en un movimiento mejor, lo que conviene a sistemas que deben actuar dentro de un plazo pero a los que aun así les importa la calidad del camino, la energía o el tiempo de ciclo.

Aplicaciones clave

Planificación de movimiento de brazos con presupuestos de tiempo por consulta en cadenas de manipulación
Replanificación para robots móviles y vehículos que deben actuar en un ciclo de control fijo
Planificación de rutas para robots aéreos, donde los caminos más cortos ahorran batería
Búsqueda heurística en grafos sobre cuadrículas y retículas con reducción de peso al estilo de ARA*
Investigación en metarrazonamiento sobre cuándo dejar de planificar y empezar a actuar

En la práctica

Un manipulador móvil planifica los movimientos del brazo con un planificador basado en muestreo asintóticamente óptimo de una biblioteca como OMPL. Cada consulta recibe un presupuesto de tiempo: el planificador suele encontrar un primer camino al principio de ese presupuesto y luego sigue acortándolo. El equipo registra el mejor coste frente al tiempo transcurrido en muchas consultas grabadas y ve que la mayor parte de la ganancia llega pronto, con caídas grandes ocasionales cuando se encuentra tarde una ruta más corta alrededor de un obstáculo. En lugar de gastar siempre el presupuesto completo, paran cuando el coste no ha mejorado durante un intervalo fijado, o usan una regla de parada aprendida, y después aplican atajos y parametrización temporal al resultado antes de enviarlo al controlador.

Ideas erróneas comunes

Anytime significa que la primera solución es casi óptima — la primera solución suele estar lejos del óptimo, y la calidad depende de cuánto tiempo funcione el planificador
El coste mejora de forma constante con el tiempo — normalmente baja a saltos desiguales, con largas mesetas entre ellos
La optimalidad asintótica garantiza un buen camino dentro del presupuesto de tiempo — solo describe el límite cuando el cálculo crece sin cota y no dice nada sobre un plazo finito
Usar todo el presupuesto de tiempo es siempre lo mejor — el tiempo dedicado a planificar es tiempo que no se dedica a moverse, así que parar antes suele ser el mejor compromiso

Quién debería saberlo

Ingenieros de planificación de movimiento que configuran planificadores basados en muestreo o en búsqueda
Desarrolladores de manipulación móvil y navegación que trabajan con límites de tiempo real
Investigadores en robótica que estudian la planificación con cálculo acotado
Estudiantes que aprenden planificación de movimiento óptima

Tecnologías relacionadas

ARA (Anytime Repairing A)
RRT*
Informed RRT*
BIT* (Batch Informed Trees)
OMPL

Términos relacionados

Proyectos relacionados

GENESIS: World's fastest physics engine: 43M FPS for embodied AI learning
Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
FAST-LIVO2: Fast, direct LiDAR-inertial-visual odometry from HKU-MARS, published in IEEE T-RO
Dora AI: Dataflow middleware for AI robotics applications, built in Rust
OpenMind OM1: AI-native operating system for robots with modular perception, cognition, and action
Fast DDS: eProsima's high-performance DDS middleware — the default transport under ROS 2