Résumé technique : PRISM - Planification probabiliste efficace et localement optimale avec garanties de joignabilité

Énoncé du problème

Le document traite du défi fondamental de la planification dans l'espace de croyance (belief-space planning) pour les systèmes robotiques opérant sous incertitude de mouvement, contraintes d'état et contraintes de commande. Plus précisément, le problème consiste à diriger un système d'une distribution gaussienne initiale $I = \mathcal{N}(\mu_I, \Sigma_I)$ vers une distribution gaussienne cible $G = \mathcal{N}(\mu_G, \Sigma_G)$ tout en respectant des contraintes probabilistes (de chance) sur les états et les commandes.

Les approches existantes font face à des limitations significatives :

• Les méthodes basées sur l'échantillonnage (ex. : FIRM, CS-BRM, RRT*) peinent souvent à obtenir une couverture élevée dans des espaces de croyance de grande dimension sans nécessiter un nombre impraticable de nœuds. Elles manquent fréquemment de garanties de complétude en temps fini et peuvent produire des trajectoires qui violent les contraintes ou sont sous-optimales en raison de leur dépendance aux techniques de contrôle robuste qui gonflent les coûts.
• Les méthodes basées sur les ensembles (ex. : Graphes d'ensembles convexes) offrent des garanties de complétude pour la planification déterministe mais éprouvent des difficultés à établir la joignabilité au sein des ensembles convexes de l'espace de croyance.
• Les méthodes de pilotage de covariance (covariance steering) optimisent généralement conjointement les trajectoires de moyenne et de covariance, ce qui rend difficile l'analyse séparée de la joignabilité et entraîne souvent des coûts de calcul élevés pour la planification multi-requêtes.

La difficulté centrale réside dans l'établissement de garanties de joignabilité dans des espaces de croyance contraints, particulièrement pour déterminer si une covariance d'état peut être réduite ou dirigée vers une cible tout en respectant les limites des actionneurs et l'évitement d'obstacles.

Méthodologie : Algorithme PRISM

Les auteurs proposent PRISM (Precomputed Regions for Inflation-based Stochastic Motion planning), un algorithme de planification multi-requêtes qui décompose le problème de planification dans l'espace de croyance en deux phases distinctes : la réduction de la covariance (covariance shrinking) et le pilotage déterministe de la moyenne.

1. Fondement théorique : Joignabilité de la covariance d'état

Une contribution théorique clé est la dérivation de nouvelles conditions suffisantes pour la joignabilité de la covariance d'état sous des contraintes d'obstacles et d'actionneurs.

• Réductibilité : Le document introduit le concept de covariance « $\delta$-strictement réductible ». Il prouve que si une covariance initiale $\Sigma_1$ se situe dans des limites spécifiques définies par un paramètre $\delta$ et un horizon temporel $N$, elle peut être réduite à une covariance isotrope plus petite $cI$ en un temps fini tout en respectant toutes les contraintes.
• Découplage : Ces conditions permettent à PRISM de séparer le problème de planification. L'algorithme réduit d'abord l'incertitude du système à une covariance isotrope constante et précalculée ($c^{(N)}_{1,\delta}I$). Une fois la covariance réduite à ce niveau de « sécurité », le problème se transforme en un problème de pilotage de moyenne déterministe avec des contraintes resserrées et des obstacles gonflés.

2. Construction de graphe hors ligne

PRISM construit une carte routière (roadmap) hors ligne dans l'espace déterministe :

• Resserrement des contraintes : En utilisant la trajectoire de covariance précalculée, l'algorithme resserre les contraintes d'état et de commande et gonfle les obstacles pour garantir que toute trajectoire satisfaisant les contraintes déterministes satisfera les contraintes de chance probabilistes originales.
• Décomposition de l'espace : L'espace d'état sûr (avec des contraintes resserrées) est décomposé en une union de polytopes convexes chevauchants.
• Génération de graphe : Les nœuds sont placés aux centroïdes de ces polytopes. Les arêtes sont calculées entre les polytopes intersectants en résolvant un problème de pilotage de moyenne déterministe (Problème V.3) pour trouver des chemins réalisables entre les centroïdes.
• Élévation (Lifting) : Ces arêtes déterministes sont « élevées » dans l'espace de croyance en combinant la trajectoire de la moyenne avec la trajectoire de covariance précalculée.

3. Planification en ligne et optimisation locale

• Phase en ligne : Étant donné une distribution de départ et une de but spécifiques, PRISM tente d'abord de diriger le système vers une moyenne stationnaire au sein d'un polytope sûr où la covariance peut être réduite (si l'état initial ne satisfait pas déjà les conditions de réductibilité). Il connecte ensuite les distributions de départ et de but au graphe précalculé et effectue une recherche de graphe pour trouver un chemin réalisable.
• Optimisation locale : Une fois un chemin réalisable trouvé, PRISM emploie un nouveau module d'optimisation locale en ligne. Ce module alterne entre :
  1. Raccourcissement d'arête : Réduction de l'allocation de temps pour les arêtes individuelles.
  2. Raccourcissement de chemin (Shortcutting) : Recherche de connexions directes entre des nœuds non adjacents pour éliminer les arêtes inutiles.
  3. Optimisation convexe : Résolution d'un programme semi-défini convexe (SDP) pour optimiser les trajectoires de moyenne et de covariance pour des allocations de temps et des séquences d'arêtes fixes.
     Ce processus est garanti d'être « anytime » (renvoie toujours une solution réalisable) et améliore considérablement le coût.

Contributions clés

1. Nouvelles conditions de joignabilité : Le document établit de nouvelles conditions suffisantes pour la joignabilité de la covariance d'état sous des contraintes d'obstacles et d'actionneurs, permettant la séparation de la planification de la moyenne et de la covariance.
2. Algorithme PRISM : Un planificateur multi-requêtes qui exploite ces conditions pour atteindre une couverture élevée sans échantillonner directement l'espace de croyance, évitant ainsi l'inefficacité de l'échantillonnage de haute dimension.
3. Sous-module d'optimisation locale : Une méthode en ligne qui co-optimise les trajectoires de moyenne et de covariance, démontrant des améliorations de performance de plus de $2,5\times$ par rapport aux méthodes de l'état de l'art.
4. Garanties théoriques : Preuves de correction (soundness — toutes les trajectoires respectent les contraintes de chance) et de complétude (garantie de trouver un chemin en temps fini) sous des hypothèses modérées sur les distributions de départ et de but (ex. : moyennes stationnaires, covariances bornées).
5. Validation empirique : Simulations étendues démontrant une couverture supérieure et un coût inférieur par rapport à FIRM, CS-BRM, MAX-COVAR, MAX-COV-BALL et les variantes de RRT*.

Résultats expérimentaux

Les auteurs ont évalué PRISM sur un quadrotor à 6 degrés de liberté dans des environnements 2D avec des largeurs de couloirs variables et des champs d'obstacles encombrés.

• Couverture :
  • Dans des environnements de bureaux confinés avec des passages étroits, PRISM a atteint une couverture de 100 % sur toutes les largeurs de couloir, tandis que les méthodes basées sur l'échantillonnage (RRT, RRT*, MAX-COV-BALL) ont vu leur couverture chuter significativement à mesure que les passages se rétrécissaient.
  • Dans des environnements encombrés avec des bruits d'actionneurs variables, PRISM a maintenu une couverture de 97 à 100 % même dans des scénarios « difficiles » (moyennes non stationnaires, grande covariance initiale) où toutes les autres méthodes atteignaient moins de 45 % de couverture.
• Coût :
  • Après optimisation locale, PRISM produit des trajectoires avec un coût moyen et une variance de coût nettement inférieurs.
  • Dans l'environnement encombré, le coût médian du chemin de PRISM était de 97,9, contre 110,8 pour CS-BRM et 114,5 pour RRT* (après leur propre optimisation locale).
  • L'optimisation locale de PRISM convergeait plus rapidement (médiane de 5,93s) que les autres méthodes, principalement parce que son planificateur global produit des chemins avec moins d'arêtes.
• Temps de calcul :
  • La construction du graphe hors ligne de PRISM était très efficace (< 1 minute pour les environnements de bureaux, ~4-5 minutes pour les environnements encombrés), surpassant nettement CS-BRM qui nécessitait des heures en raison de la vérification de collision de milliers d'arêtes.
  • Les temps de recherche de chemin en ligne étaient comparables aux bases les plus rapides (~0,65s en moyenne).

Signification et affirmations

Le document affirme que PRISM représente une avancée significative dans la planification contrainte dans l'espace de croyance en abordant le compromis entre couverture et coût qui affecte les méthodes existantes. En découplant la réduction de la covariance du pilotage de la moyenne, PRISM évite la « malédiction de l'histoire » et l'inefficacité de l'échantillonnage de haute dimension.

Les auteurs soulignent que PRISM offre des garanties de complétude en temps fini pour un large sous-ensemble de l'espace de croyance, une propriété souvent absente des approches basées sur l'échantillonnage. De plus, l'inclusion d'un module d'optimisation locale efficace garantit que les trajectoires résultantes ne sont pas seulement réalisables, mais aussi localement optimales en termes de coût de commande. Les résultats suggèrent que PRISM est particulièrement adapté aux environnements complexes et contraints où les méthodes de planification traditionnelles échouent à trouver des chemins réalisables ou produisent des trajectoires excessivement coûteuses.