Time Optimal Ergodic Search

Autores: Dayi Dong, Henry Berger, Ian Abraham · RSS 2023

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

Minimiza el tiempo de búsqueda sujeto a una cota superior γ sobre la métrica ergódica: un único parámetro fija lo exhaustiva que es la cobertura, y el optimizador elige la duración de la trayectoria.

Por qué importa

En vuelos de búsqueda y rescate o de inspección, el operador puede especificar lo exhaustivo que debe ser un barrido y obtener la trayectoria más rápida que lo cumpla, en lugar de adivinar una duración. Restricciones como los límites de velocidad y las barreras frente a obstáculos forman parte de la misma optimización, y los tiempos planificados se trasladaron a un cuadricóptero real con una diferencia de menos de 1,5 s.

Problema

La búsqueda ergódica planifica trayectorias continuas que pasan en cada región un tiempo proporcional a su información, pero los métodos existentes fijan de antemano el horizonte de planificación, por lo que el usuario no puede equilibrar la exhaustividad de la búsqueda frente al tiempo. Minimizar el tiempo y a la vez minimizar la métrica ergódica es un problema mal planteado, porque una trayectoria solo se vuelve completamente ergódica cuando el tiempo tiende a infinito.

Solución propuesta

La métrica ergódica pasa a ser una restricción de desigualdad E ≤ γ dentro de un problema de tiempo mínimo, de modo que γ fija lo gruesa o fina que debe ser la cobertura y el tiempo final tf es una variable de decisión. Los autores demuestran condiciones de optimalidad local con el principio del máximo de Pontryagin usando un 'estado ergódico extendido', y en la práctica resuelven el problema por transcripción directa sobre N puntos de nodo (Δt = tf/N) con un solver propio de lagrangiano aumentado. Los obstáculos se tratan con restricciones de funciones barrera de control discretas.

Ideas clave

• Tratar la ergodicidad como una cota y no como un objetivo hace que la búsqueda de tiempo mínimo esté bien planteada; cuando γ → 0, el tiempo óptimo crece sin límite, en consonancia con la teoría ergódica
• Reducir γ en dos órdenes de magnitud (de 0,1 a 0,001) en un mapa de información de cuatro picos aproximadamente duplicó el tiempo óptimo (de 9,86 s a 19,59 s), y aun así el plan grueso visitó todos los picos
• El esfuerzo de control normalizado por el tiempo es mayor en la parte media del rango de γ, donde la trayectoria debe equilibrar cobertura frente a tiempo, que en cualquiera de los extremos
• Las estimaciones iniciales suaves (interpolación lineal) dan soluciones consistentes; las trayectorias iniciales ruidosas o aleatorias caen en mínimos locales igual de ergódicos con tiempos más largos

Resultados principales

• Cobertura uniforme con una masa puntual en 2D: variar γ da trayectorias de 5 a 10 s con una cobertura equivalente a una trayectoria ergódica de horizonte fijo de 10 s (E = 0,007)
• Mapa de información no uniforme: tiempos óptimos de 9,86 s con γ = 0,1 y de 19,59 s con γ = 0,001
• Sensibilidad con γ = 0,05: variar el tf inicial de 4 a 8 s da un tiempo óptimo de 4,97 ± 0,23 s; variar el número de puntos de nodo N de 50 a 600 da 5,45 ± 0,39 s
• Entorno 2D con obstáculos y funciones barrera de control: tiempos óptimos de 7,79 s con γ = 0,2 a 11,85 s con γ = 0,002, y las restricciones de barrera mantienen las trayectorias alejadas de todos los obstáculos
• Experimentos con dron con γ = 0,1, 0,05 y 0,01: los tiempos de vuelo ejecutados quedaron a menos de 1,5 s de los tiempos optimizados; la trayectoria de la Fig. 1 cubre el área con obstáculos en 13,5 s
• El solver también produjo trayectorias de cobertura uniforme para un modelo no lineal de avión en 3D entre obstáculos elipsoidales aleatorios

Limitaciones

• Los autores afirman que las soluciones solo son localmente óptimas, porque la métrica ergódica es muy no lineal y no convexa
• Los autores observaron que las condiciones de optimalidad de Pontryagin son numéricamente inestables para horizontes largos, por lo que el solver práctico es un método de transcripción directa
• La planificación es fuera de línea y con obstáculos conocidos; los autores citan como trabajo futuro la planificación en tiempo real con obstáculos desconocidos e incertidumbre del entorno
• Los resultados dependen de la trayectoria inicial y de N; el solver deja de devolver soluciones para γ muy pequeños, donde el tiempo necesario se vuelve muy grande
• Los autores señalan que el coste computacional crece con la dimensión del espacio de exploración

Impacto en el campo

Ganador del RSS 2023 Best Paper Award. Los autores publican el código en github.com/ialab-yale/time_optimal_ergodic_search y una página de demostración multimedia.

Resumen

Los robots capaces de equilibrar el tiempo frente a la exhaustividad de la búsqueda pueden prestar asistencia en situaciones en las que el tiempo es crítico, como la búsqueda y rescate. Los avances recientes en los métodos de búsqueda basados en cobertura ergódica han permitido a los robots explorar y registrar por completo un área en un tiempo fijo. Sin embargo, aún no se ha demostrado la optimización del tiempo frente a la calidad de la búsqueda ergódica autónoma. En este artículo investigamos soluciones al problema de búsqueda ergódica de tiempo óptimo para la búsqueda y exploración robótica rápida y adaptativa. Planteamos el problema como un problema de tiempo mínimo con una restricción de desigualdad ergódica cuya cota superior regula y equilibra la granularidad de la búsqueda frente al tiempo. Las soluciones del problema se presentan analíticamente mediante las condiciones de optimalidad de Pontryagin y se demuestran numéricamente mediante un enfoque de optimización por transcripción directa. Mostramos la eficacia del enfoque para generar trayectorias de búsqueda ergódica de tiempo óptimo en simulación y en experimentos con drones en un entorno con obstáculos. Se muestra que la evitación de obstáculos se integra fácilmente en nuestra formulación, y realizamos estudios de ablación que investigan la dependencia de los parámetros en el tiempo optimizado y la sensibilidad de la trayectoria para la búsqueda.

Enlaces

• arXiv 2305.11643: https://arxiv.org/abs/2305.11643
• PDF: https://arxiv.org/pdf/2305.11643v1
• Código: https://github.com/ialab-yale/time_optimal_ergodic_search
• Página del proyecto: https://sites.google.com/view/time-optimal-ergodic-search