Provably Safe Motion Planning Under Unknown Disturbances

Énoncé du Problème
Ce papier aborde le défi de la planification de trajectoire pour des systèmes robotiques soumis à des perturbations aléatoires de distributions inconnues. Les planificateurs basés sur l'échantillonnage traditionnels supposent souvent des modèles déterministes ou s'appuient sur des hypothèses distributionnelles fortes (par exemple, un bruit gaussien) et des modèles de perturbations bornées. Ces approches aboutissent fréquemment à des trajectoires excessivement conservatrices qui échouent dans des environnements encombrés ou nécessitent une connaissance irréaliste de la distribution des perturbations. Les auteurs formulent le problème comme la génération d'une trajectoire pour des systèmes linéaires (ou linéarisables par retour d'état) satisfaisant des contraintes stochastiques d'évitement d'obstacles et d'atteinte de l'objectif avec une haute confiance, malgré l'inconnue des distributions de l'état initial et du bruit de processus. Le système doit opérer dans des espaces de travail contenant des obstacles de forme arbitraire, tout en respectant les contraintes d'état et de commande.

Méthodologie
L'approche proposée, dénommée WDR-X (Wasserstein Distributionally Robust-X), est un cadre de planification de trajectoire basé sur l'échantillonnage qui intègre une quantification de l'incertitude pilotée par les données avec une recherche arborescente. La méthodologie se déroule en deux phases principales :

1. Construction du Tube d'Ambiguïté (Hors ligne) :
   Au lieu de supposer une distribution de bruit spécifique, l'algorithme apprend un tube d'ambiguïté de Wasserstein à partir d'un ensemble de $N$ échantillons de trajectoires i.i.d. Ce tube est une séquence d'ensembles d'ambiguïté (boules de Wasserstein) qui, avec un niveau de confiance défini par l'utilisateur, contient la vraie distribution d'état à chaque instant.

   • Dynamique de l'Erreur : Les auteurs découplent le problème de planification de la propagation de l'incertitude en analysant la dynamique de l'erreur par rapport à une trajectoire de référence. Ils démontrent que l'ensemble d'ambiguïté pour l'état peut être dérivé de l'ensemble d'ambiguïté de l'erreur et de l'état de référence.
   • Horizon Infini : Contrairement aux méthodes précédentes où les bornes d'ambiguïté croissent sans limite au fil du temps, cette approche construit un tube de longueur temporelle infinie avec une confiance finie. Elle y parvient en apprenant des ensembles d'ambiguïté pilotés par les données à des instants spécifiques et en dérivant les ensembles pour les instants intermédiaires en utilisant la dynamique du système, résultant en un profil de rayon en « dents de scie » qui reste borné.
   • Décomposition en Dimension Inférieure : Pour pallier le fléau de la dimensionnalité, le cadre exploite des tubes d'ambiguïté de dimension inférieure. En projetant la distribution d'état sur des sous-espaces pertinents pour des contraintes spécifiques (par exemple, la position dans l'espace de travail pour les obstacles, l'effort de commande pour les limites), la méthode réduit considérablement la complexité en échantillons et le coût computationnel tout en maintenant les garanties de sécurité.

2. Planification Probabilistement Complète (En ligne) :
   Le planificateur fait croître un arbre basé sur l'échantillonnage (par exemple, RRT) au-dessus des trajectoires de référence nominales (déterministes).

   • Vérification de Validité : À chaque nœud, l'algorithme vérifie si l'état satisfait les contraintes stochastiques. Cela se fait en évaluant la probabilité de collision au pire cas sur l'ensemble d'ambiguïté appris.
   • Vérificateurs Efficaces : Le papier introduit trois stratégies de vérification de validité :
     • Vérificateur Exact : Un algorithme sans optimisation basé sur le transport de masse de probabilité qui calcule la probabilité de collision au pire cas exacte pour des distributions discrètes.
     • Vérificateur Paresseux (Lazy) : Une méthode plus rapide et plus conservatrice utilisant des tubes de confiance (boules) pré-calculés, évitant les calculs détaillés de transport de masse.
     • Vérificateur à Base de Bandit : Une approche hybride qui sélectionne adaptativement entre les vérificateurs exact et paresseux en utilisant un cadre de bandit à plusieurs bras. Cela équilibre l'efficacité et le conservatisme, en particulier dans des environnements complexes comme les passages étroits.

Contributions Clés
Le papier apporte les contributions spécifiques suivantes :

• Algorithme : Un algorithme de planification de trajectoire basé sur l'échantillonnage pour des systèmes linéaires avec des perturbations additives inconnues, utilisant des données d'observation de trajectoires.
• Garanties Théoriques : Des preuves de justesse et de complétude probabiliste pour le planificateur sous des hypothèses assouplies concernant les distributions de perturbations.
• Propagation de l'Ambiguïté : De nouveaux résultats théoriques sur la propagation de l'ambiguïté distributionnelle, montrant spécifiquement que la propagation de l'ambiguïté se découple de la planification pour les systèmes linéaires, permettant un tube unique appris hors ligne.
• Bornes Plus Étroites : Une caractérisation plus stricte de la taille des ensembles d'ambiguïté pilotés par les données définis par la distance de Wasserstein 1 par rapport à la littérature existante, utilisant des inégalités de McDiarmid unilatérales et des informations sur les moments.
• Vérification de Validité : Trois méthodes de vérification de validité qui échangent efficacité et conservatisme, toutes moins conservatrices que les travaux existants, unifiées par un schéma de bandit à plusieurs bras qui sélectionne adaptativement le vérificateur approprié.
• Réduction de Dimensionnalité : Une formalisation de l'utilisation de multiples tubes d'ambiguïté de dimension inférieure pour réduire les exigences en données et computationnelles sans sacrifier la sécurité.

Résultats Expérimentaux
Les auteurs ont évalué l'approche sur deux systèmes : un système linéaire de dimension 4 et un système de drone de dimension 8 naviguant dans des espaces de travail 2D.

• Lignes de Base : La méthode a été comparée à des approches robustes distributionnelles basées sur les moments (TS et Risk-Assigned) et à d'autres variantes basées sur Wasserstein (Particle, Confidence, Hybrid).
• Performance :
  • Dans des environnements encombrés et à passages étroits, le Bandit-WDR-RRT proposé a nettement surpassé les lignes de base basées sur les moments, qui ont échoué à trouver des trajectoires en raison d'un conservatisme excessif. Par exemple, dans un passage étroit avec un bruit non gaussien, les lignes de base ont obtenu des taux de succès de 0 à 9 %, tandis que Bandit-WDR-RRT a atteint jusqu'à 100 %.
  • Le vérificateur à base de bandit a démontré le meilleur équilibre, égalant ou dépassant les taux de succès des autres variantes tout en étant 1,5 à 3 fois plus rapide que l'approche hybride.
  • L'approche de dimension inférieure a permis avec succès la planification pour le système de drone de dimension 8 en apprenant des tubes séparés pour les contraintes de position et de commande, démontrant ainsi son évolutivité.
• Sécurité : Des simulations de Monte Carlo ont confirmé que les trajectoires générées ont atteint des taux de succès de 99 à 100 % dans l'évitement des collisions, validant la justesse des contraintes du tube d'ambiguïté.

Signification
Le papier affirme que sa signification principale réside dans la fourniture d'un cadre de planification de trajectoire prouvé sûr et évolutif pour des systèmes avec des distributions de perturbations inconnues. En exploitant les ensembles d'ambiguïté de Wasserstein et l'apprentissage piloté par les données, l'approche évite les sur-approximations géométriques inhérentes aux méthodes basées sur les moments et les hypothèses distributionnelles des méthodes basées sur le gaussien. La capacité à gérer des obstacles de forme arbitraire et des contraintes non convexes sans sacrifier la complétude probabiliste rend la méthode adaptée à des applications robotiques réelles complexes où la sécurité est critique et où les modèles de perturbations sont incertains. L'introduction du vérificateur de validité à base de bandit améliore encore l'utilité pratique en gérant dynamiquement le compromis entre la vitesse computationnelle et le conservatisme de la solution.