Learning When to Quit: Meta-Reasoning for Motion Planning

Autores: Yoonchang Sung, Leslie Pack Kaelbling, Tomás Lozano-Pérez · IROS 2021

Licencias

• Acceso abierto
• Artículo: CC BY 4.0

Todo lo que sigue se basa en el artículo completo bajo su licencia CC BY 4.0; su figura se muestra con crédito a los autores.

En resumen

Aprende a partir de ejecuciones anteriores del planificador cuándo detener un planificador de movimiento anytime (RRT, PRM, Lazy PRM*) para maximizar el compromiso entre la calidad de la trayectoria y el tiempo de planificación.

Por qué importa

Todo robot que planifica con RRT o PRM tiene que elegir un presupuesto de tiempo de planificación, y un tiempo fijo o un umbral de calidad fijo desperdicia tiempo o calidad de la trayectoria. El método envuelve un planificador anytime sin modificar, por lo que puede añadirse sobre planificadores existentes de tipo OMPL siempre que se disponga de problemas de entrenamiento de la distribución de entornos objetivo.

Problema

Los planificadores de movimiento anytime siguen acortando una trayectoria cuanto más tiempo se ejecutan, pero no existe una relación bien caracterizada entre la calidad de la solución y el tiempo de cómputo, por lo que no está claro cuándo dejar de planificar y empezar a moverse. Sus perfiles de rendimiento son muy poco suaves porque las trayectorias más cortas aparecen a saltos repentinos cuando el planificador encuentra una nueva clase de homotopía, lo que descarta una extrapolación en línea sencilla de la calidad futura.

Solución propuesta

Los autores aprenden una política de parada a partir de los perfiles de rendimiento de problemas de planificación anteriores extraídos de la misma distribución, maximizando una utilidad ponderada por el usuario U(q, t) = wq − (1 − w)t. Una variante basada en modelo aprende un proceso de decisión de Markov sobre calidad y tiempo discretizados y lo resuelve con iteración de valores; dos variantes sin modelo (un clasificador prealimentado sobre características diseñadas a mano y un modelo secuencia a secuencia RNN) imitan decisiones de parada de un oráculo calculadas a posteriori. Una CNN predice la longitud de la trayectoria óptima a partir de una imagen 2D del espacio de trabajo para que los perfiles de problemas de distinta dificultad puedan normalizarse y compararse.

Ideas clave

• Los tiempos de parada óptimos pueden calcularse a posteriori para cada ejecución de entrenamiento, lo que convierte el problema de aprendizaje de la política en aprendizaje por imitación supervisado en lugar de aprendizaje por refuerzo.
• Normalizar la calidad de la trayectoria requiere la longitud de la trayectoria óptima, que es desconocida; una CNN que la predice a partir de una imagen 2D del espacio de trabajo hace comparables los perfiles entre problemas, y un normalizador deficiente (una línea recta del inicio a la meta) reduce la utilidad de forma marcada.
• Unas características de historial más ricas (pendiente, planitud) hacen que el modelo de transición basado en modelo sea mucho más preciso, pero su coste de estimación crece de segundos a más de un día, un caso directo de la maldición de la dimensionalidad.
• La RNN aprende sus propias características temporales a partir de la secuencia de utilidad en bruto y dio los resultados buenos más fiables entre planificadores y pesos de utilidad.

Resultados principales

• Precisión del predictor CNN de la longitud de la trayectoria óptima en 200 espacios de trabajo reservados: 88,21 %, 96,23 % y 94,25 % en tres distribuciones de entornos.
• El uso del normalizador CNN dio utilidades de 0,58, 0,65 y 0,66 en esos tres entornos, frente a 0,63, 0,70 y 0,67 con las longitudes óptimas reales y 0,39, 0,40 y 0,60 con un normalizador de línea recta.
• La pérdida en datos reservados del modelo de transición bajó de 1,84 (sin características) a 0,22 con (t, q) y a 0,10 con (t, q, pendiente), mientras que el tiempo de estimación subió de 0,41 s a 10,64 s y 11 933,72 s.
• RRT* con w = 0,8: utilidad del oráculo 0,677, RNN 0,670, basado en modelo 0,663, clasificador 0,658, frente a 0,634 del método de referencia de calidad fija y 0,575 del de tiempo fijo.
• PRM* con w = 0,8: oráculo 0,718, basado en modelo 0,702, RNN 0,698, clasificador 0,697, calidad fija 0,674, tiempo fijo 0,662.
• Con w = 0,2 el método de referencia de calidad fija pasó a ser negativo (−0,283 para RRT, −0,344 para PRM, −0,367 para Lazy PRM*), mientras que los métodos aprendidos se mantuvieron positivos.

Limitaciones

• El predictor CNN de la solución óptima recibe una imagen 2D del espacio de trabajo, lo que limita los métodos a problemas con espacios de trabajo planos; se sugiere la extensión a 3D mediante rejillas de vóxeles o nubes de puntos, pero no se lleva a cabo.
• Se supone que un problema nuevo procede de la misma distribución que los problemas de entrenamiento, y el entrenamiento requiere muchas ejecuciones largas del planificador en problemas representativos.
• Añadir características de historial al método basado en modelo era computacionalmente inviable en los experimentos más grandes, por lo que solo usó (q, q_prev, t).
• Toda la evaluación se hace en simulación con un robot rígido de tres grados de libertad en espacios de trabajo 2D; no se probó ningún robot físico.
• Solo se estudió una utilidad lineal U(q, t) = wq − (1 − w)t.

Impacto en el campo

El artículo fue finalista del IROS 2021 Best Paper Award on Cognitive Robotics y tiene 14 citas. No indica que se hayan publicado código ni datos.

Resumen

Los planificadores de movimiento anytime se usan ampliamente en robótica. Sin embargo, la relación entre la calidad de su solución y el tiempo de cómputo no se comprende bien y, por tanto, no está claro cómo determinar cuándo abandonar la planificación y comenzar la ejecución. En este artículo abordamos el problema de decidir cuándo detener la deliberación con una capacidad de cómputo limitada, el llamado metarrazonamiento, para la planificación de movimiento anytime. Proponemos métodos de aprendizaje basados en datos, metarrazonamiento basado en modelo y sin modelo, que son aplicables a distintas distribuciones de entornos e independientes de la elección del planificador de movimiento anytime. Como parte del marco, diseñamos un predictor de la solución óptima basado en una red neuronal convolucional que predice la longitud de la trayectoria óptima a partir de una imagen 2D dada del espacio de trabajo. Evaluamos empíricamente el rendimiento de los métodos propuestos en simulación, en comparación con métodos de referencia.

Enlaces

• arXiv 2103.04374: https://arxiv.org/abs/2103.04374
• DOI 10.1109/IROS51168.2021.9636864: https://doi.org/10.1109/IROS51168.2021.9636864
• PDF: https://arxiv.org/pdf/2103.04374v1