Time Optimal Ergodic Search

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

Licences

• Accès libre
• Article: CC BY 4.0

Tout ce qui suit s'appuie sur l'article complet sous sa licence CC BY 4.0 ; sa figure est montrée en citant les auteurs.

En bref

Minimise le temps de recherche sous une borne supérieure γ sur la métrique ergodique : un seul paramètre fixe l'exhaustivité de la couverture, et l'optimiseur choisit la durée de la trajectoire.

Pourquoi c'est important

Pour des vols de recherche et sauvetage ou de relevé, l'opérateur peut spécifier le degré d'exhaustivité d'un balayage et obtenir la trajectoire la plus rapide qui le respecte, au lieu de deviner une durée. Des contraintes comme les limites de vitesse et les barrières d'obstacles s'insèrent dans la même optimisation, et les temps planifiés se sont reportés sur un quadrirotor réel à 1,5 s près.

Problème

La recherche ergodique planifie des trajectoires continues qui passent dans chaque région un temps proportionnel à son information, mais les méthodes existantes fixent à l'avance l'horizon de planification, si bien que l'utilisateur ne peut pas arbitrer entre exhaustivité de la recherche et temps. Minimiser le temps tout en minimisant la métrique ergodique est un problème mal posé, car une trajectoire ne devient pleinement ergodique que lorsque le temps tend vers l'infini.

Solution proposée

La métrique ergodique devient une contrainte d'inégalité E ≤ γ dans un problème de temps minimal, de sorte que γ fixe le degré de finesse de la couverture et que le temps final tf est une variable de décision. Les auteurs prouvent des conditions d'optimalité locale avec le principe du maximum de Pontryagin à l'aide d'un 'état ergodique étendu', puis résolvent le problème en pratique par transcription directe sur N points de collocation (Δt = tf/N) avec un solveur de lagrangien augmenté développé sur mesure. Les obstacles sont traités par des contraintes de fonctions barrières de commande discrètes.

Idées clés

• Traiter l'ergodicité comme une borne plutôt que comme un objectif rend la recherche en temps minimal bien posée ; quand γ → 0, le temps optimal croît sans limite, conformément à la théorie ergodique
• Abaisser γ de deux ordres de grandeur (de 0,1 à 0,001) sur une carte d'information à quatre pics a environ doublé le temps optimal (de 9,86 s à 19,59 s), et même le plan grossier visitait chaque pic
• L'effort de commande normalisé par le temps est plus élevé au milieu de la plage de γ, où la trajectoire doit arbitrer entre couverture et temps, qu'aux deux extrêmes
• Des estimations initiales lisses (interpolation linéaire) donnent des solutions cohérentes ; des trajectoires initiales bruitées ou aléatoires tombent dans des minima locaux tout aussi ergodiques mais avec des temps plus longs

Principaux résultats

• Couverture uniforme avec une masse ponctuelle 2-D : faire varier γ donne des trajectoires de 5–10 s dont la couverture équivaut à celle d'une trajectoire ergodique à horizon fixe de 10 s (E = 0,007)
• Carte d'information non uniforme : temps optimaux de 9,86 s à γ = 0,1 et de 19,59 s à γ = 0,001
• Sensibilité à γ = 0,05 : faire varier tf initial de 4 à 8 s donne un temps optimal de 4,97 ± 0,23 s ; faire varier le nombre de points N de 50 à 600 donne 5,45 ± 0,39 s
• Environnement 2-D encombré avec fonctions barrières de commande : temps optimaux de 7,79 s à γ = 0,2 jusqu'à 11,85 s à γ = 0,002, les contraintes barrières maintenant les trajectoires à l'écart de chaque obstacle
• Expériences avec drone à γ = 0,1, 0,05 et 0,01 : les temps de vol réels étaient à 1,5 s près des temps optimisés ; la trajectoire de la Fig. 1 couvre la zone encombrée en 13,5 s
• Le solveur a aussi produit des trajectoires de couverture uniforme pour un modèle d'aéronef 3-D non linéaire parmi des obstacles ellipsoïdaux aléatoires

Limites

• Les auteurs indiquent que les solutions ne sont que localement optimales, car la métrique ergodique est fortement non linéaire et non convexe
• Les auteurs ont constaté que les conditions d'optimalité de Pontryagin sont numériquement instables pour de longs horizons, d'où le choix d'une méthode de transcription directe comme solveur pratique
• La planification se fait hors ligne avec des obstacles connus ; les auteurs citent comme travaux futurs la planification en temps réel avec obstacles inconnus et incertitude environnementale
• Les résultats dépendent de la trajectoire initiale et de N ; le solveur ne renvoie plus de solution pour des γ très petits, où le temps requis devient très grand
• Les auteurs notent que le coût de calcul croît avec la dimension de l'espace d'exploration

Impact sur le domaine

Lauréat du RSS 2023 Best Paper Award. Les auteurs publient le code sur github.com/ialab-yale/time_optimal_ergodic_search ainsi qu'une page de démonstration multimédia.

Résumé

Les robots capables d'arbitrer entre le temps et l'exhaustivité d'une recherche peuvent apporter une assistance urgente dans des applications telles que la recherche et le sauvetage. Les progrès récents des méthodes de recherche fondées sur la couverture ergodique ont permis aux robots d'explorer et de fouiller complètement une zone en un temps fixé. Cependant, l'optimisation du temps face à la qualité d'une recherche ergodique autonome n'a pas encore été démontrée. Dans cet article, nous étudions des solutions au problème de recherche ergodique en temps optimal pour une recherche et une exploration robotiques rapides et adaptatives. Nous posons le problème comme un problème de temps minimal avec une contrainte d'inégalité ergodique dont la borne supérieure régule et équilibre la granularité de la recherche par rapport au temps. Les solutions du problème sont présentées analytiquement à l'aide des conditions d'optimalité de Pontryagin et démontrées numériquement par une approche d'optimisation par transcription directe. Nous montrons l'efficacité de l'approche pour générer des trajectoires de recherche ergodique en temps optimal en simulation et lors d'expériences avec un drone dans un environnement encombré. Nous montrons que l'évitement d'obstacles s'intègre facilement à notre formulation, et nous réalisons des études d'ablation sur la dépendance du temps optimisé aux paramètres et sur la sensibilité de la trajectoire pour la recherche.

Liens

• arXiv 2305.11643: https://arxiv.org/abs/2305.11643
• PDF: https://arxiv.org/pdf/2305.11643v1
• Code: https://github.com/ialab-yale/time_optimal_ergodic_search
• Page du projet: https://sites.google.com/view/time-optimal-ergodic-search