⚡ electrical engineering

Conformal Constraint Tightening for Chance-Constrained Motion Planning with Unknown Dynamics

Cet article propose une méthode agnostique au planificateur qui exploite la prédiction conforme pour resserrer les contraintes de planification basées sur les écarts entre les trajectoires nominales et réelles, fournissant ainsi des garanties probabilistes d'achèvement de tâche pour les robots autonomes opérant sous des dynamiques inconnues.

Auteurs originaux : Shubham Natraj, Bruno Sinopoli, Yiannis Kantaros

Publié 2026-07-27

📖 9 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Shubham Natraj, Bruno Sinopoli, Yiannis Kantaros

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous apprenez à un robot à naviguer dans un labyrinthe. Pour ce faire, vous lui donnez une carte et un ensemble de règles. Mais voici le piège : la carte que vous possédez n'est qu'une supposition. C'est un modèle « nominal », un croquis de l'effort maximal pour décrire comment le robot se déplace. Dans le monde réel, le robot peut être plus lourd que vous ne le pensiez, ou le sol peut être glissant, ou ses roues peuvent patiner. Cet écart entre votre carte sommaire et la réalité désordonnée est appelé « décalage de modèle » (model mismatch). Si vous faites trop confiance à votre carte, le robot pourrait s'écraser contre un mur qu'il pensait éloigné, ou rater complètement la ligne d'arrivée. C'est un problème majeur en robotique car nous ne pouvons pas toujours connaître la physique exacte d'une nouvelle machine ou d'un environnement avant de l'envoyer sur le terrain. Nous avons besoin d'un moyen de planifier un trajet qui soit sûr même lorsque notre carte est imparfaite. C'est là qu'intervient le concept de « planification avec contraintes de probabilité » (chance-constrained planning) : au lieu d'exiger un trajet qui soit toujours parfait (ce qui est souvent impossible), nous visons un trajet qui fonctionne la plupart du temps, disons 95 % du temps, nous offrant ainsi un filet de sécurité contre notre propre ignorance.

Le document que vous allez lire traite exactement de ce problème : comment rendre le plan d'un robot sûr lorsque le comportement réel du robot est inconnu, mais que nous disposons d'un modèle approximatif et grossier pour travailler. Les auteurs, Shubham Natraj, Bruno Sinopoli et Yiannis Kantaros, proposent une astuce ingénieuse utilisant un outil statistique appelé « prédiction conforme » (Conformal Prediction). Considérez la prédiction conforme comme un « inspecteur de sécurité » qui examine un ensemble de tests passés pour déterminer à quel point le vrai robot pourrait dévier de la carte. Ils ne cherchent pas à corriger la carte ; au contraire, ils réduisent l'espace de jeu. Ils prennent les zones sûres sur la carte et les rendent plus petites, et la zone d'arrivée plus petite également, par un montant spécifique. Ce montant est calculé de telle sorte que si le robot reste à l'intérieur de ces zones rétrécies, il est mathématiquement garanti de rester en sécurité dans le monde réel avec une probabilité élevée.

Voici l'histoire de la manière dont ils ont procédé et de ce qu'ils ont découvert.

Le Problème : La Carte vs Le Territoire

Les robots doivent se déplacer d'un point de départ à un objectif tout en évitant les obstacles. Généralement, les ingénieurs utilisent un modèle informatique pour simuler le mouvement du robot. Ils exécutent un algorithme de planification (comme un GPS intelligent) pour trouver une séquence de mouvements qui semble parfaite sur l'ordinateur. Mais lorsqu'ils exécutent cette même séquence sur le vrai robot, les choses tournent mal. Peut-être que le moteur du robot est légèrement plus faible, ou que le vent le pousse différemment. Le chemin « réel » emprunté par le robot dévie du chemin « nominal » que l'ordinateur avait planifié. Si cette dérive est trop importante, le robot heurte un obstacle ou manque l'objectif.

Les auteurs soutiennent que nous ne pouvons pas toujours connaître la physique exacte du robot à l'avance. Nous pouvons avoir un modèle appris (une supposition basée sur des données) ou un modèle de physique simplifié, mais cela ne sera jamais 100 % précis. Le défi est de calculer une séquence de contrôle (une liste de mouvements) qui fonctionne sur le vrai robot, même si nous n'avons que le modèle approximatif pour planifier.

La Solution : L'astuce de la « Bulle de Sécurité »

La solution des auteurs est un processus en deux étapes qui transforme un problème incertain et risqué en un problème déterministe et sûr.

Étape 1 : Le Calibrage (L'essai routier)
D'abord, ils doivent savoir à quel point le décalage peut être important. Ils prennent leur modèle approximatif et le testent sur un ensemble de problèmes de test. Pour chaque problème, ils trouvent un chemin qui fonctionne sur l'ordinateur. Ensuite, ils exécutent réellement ce même chemin sur le vrai robot et observent ce qu'il se passe. Ils mesurent la distance entre l'endroit où l'ordinateur pensait que le robot se trouverait et l'endroit où il se trouvait réellement. Ils font cela pour 100 scénarios de test différents.

En utilisant une méthode statistique appelée prédiction conforme, ils examinent ces 100 mesures et se demandent : « Quelle est la distance maximale dont le vrai robot a dévié de la prédiction de l'ordinateur dans 95 % (ou 99 %, etc.) de ces cas ? » Cela leur donne un « rayon de sécurité », appelons-le $\hat{q}_\alpha$ . Ce nombre représente une bulle de « pire cas ». Ils savent qu'avec une probabilité élevée, le vrai robot ne sera jamais à plus de cette distance du chemin prédit par l'ordinateur.

Étape 2 : Le Resserrement (Réduire la pièce)
C'est alors que la magie opère. Au lieu de planifier sur la carte originale, ils créent une nouvelle carte « resserrée ».

Ils prennent les obstacles sur la carte et les agrandissent (inflation) par le rayon de sécurité $\hat{q}_\alpha$ .
Ils prennent l'espace libre et la zone d'arrivée et les réduisent (érosion) par ce même montant.

Imaginez que vous marchez dans un couloir avec un sac à dos large et encombrant. Si vous planifiez votre trajectoire en collant aux murs, vous pourriez heurter les murs avec votre sac à dos. Alors, vous faites comme si les murs étaient plus loin et le couloir plus étroit. Vous marchez au milieu de ce couloir imaginaire plus étroit. Si vous restez au milieu de ce couloir étroit, votre sac à dos ne heurtera jamais les vrais murs.

Les auteurs prouvent que si un robot parvient à trouver un chemin à travers cette version resserrée et « durcie » de la carte en utilisant le modèle approximatif, alors ce même chemin est garanti d'être sûr sur le vrai robot avec la probabilité prescrite. Le robot n'a pas besoin de connaître la vraie dynamique ; il a juste besoin de résoudre le problème plus difficile de la version resserrée de la carte.

Les Expériences : Est-ce que ça marche ?

Pour tester cela, les auteurs ont testé deux scénarios différents.

Scénario 1 : La voiture qui ralentit (Véhicule Dubins)
Ils ont utilisé un modèle de voiture simple qui tourne mais ne peut pas se déplacer latéralement. La « vraie » voiture présentait un défaut caché : elle était plus lente que ce que le modèle prédisait à cause de la friction (simulée par un paramètre $\beta_v$ ). Ils ont testé des niveaux de décalage de 0,05, 0,10, 0,15 et 0,20.

Le Résultat : Lorsqu'ils ont utilisé leur méthode de « resserrement », le robot a atteint l'objectif et évité les collisions à un taux qui correspondait ou dépassait leur garantie de sécurité. Par exemple, s'ils demandaient un taux de réussite de 90 %, le robot réussissait en réalité plus de 90 % du temps.
Le Compromis : À mesure qu'ils demandaient une sécurité plus élevée (par exemple, 99 % au lieu de 90 %), la « bulle de sécurité » devenait plus grande, le couloir devenait plus étroit, et il devenait plus difficile pour le planificateur de trouver un chemin. Le taux de réussite de la recherche d'un chemin chutait, mais les chemins qu'il trouvait étaient beaucoup plus fiables.
Comparaison : Ils ont comparé cela à un planificateur standard qui ignorait le décalage. Le planificateur standard trouvait des chemins plus souvent, mais ces chemins échouaient sur le vrai robot beaucoup plus fréquemment. La méthode des auteurs était bien plus efficace pour réellement accomplir la tâche en toute sécurité.

Scénario 2 : Le drone instable (Quadrotor planaire)
Ils ont testé un drone plus complexe, à 6 dimensions, qui présente un bruit aléatoire (rafales de vent) et utilise un modèle de réseau neuronal appris (qui est souvent imparfait).

Le Résultat : Même avec le chaos ajouté du bruit aléatoire et d'un modèle appris, la méthode a tenu bon. La « couverture empirique » (la fréquence à laquelle le robot restait à l'intérieur de la bulle de sécurité) était systématiquement supérieure à la cible.
Performance : Avec un niveau de sécurité cible de 90 %, leur méthode a atteint un taux de réussite de la tâche de 100 % sur le vrai drone, alors que le planificateur « nominal » standard n'a réussi qu'environ 55 %. Cela montre qu'en étant un peu plus prudent lors de la phase de planification, on obtient un bien meilleur résultat dans le monde réel.

Ce qu'ils ont trouvé et ce que cela signifie

L'article démontre qu'il n'est pas nécessaire de connaître la physique exacte d'un robot pour planifier un chemin sûr. Il suffit d'avoir un modèle grossier et quelques données pour mesurer à quel point ce modèle peut être erroné. En utilisant la prédiction conforme pour créer une « bulle de sécurité » et en rétrécissant l'espace de planification en conséquence, on peut transformer un problème risqué et incertain en un problème sûr et soluble.

Les auteurs montrent que cette approche est « indépendante du planificateur » (planner-agnostic), ce qui signifie qu'elle fonctionne avec n'importe quel algorithme de planification (comme l'algorithme RRT qu'ils ont utilisé). Peu importe la façon dont le planificateur trouve le chemin ; tant que le chemin reste à l'intérieur des zones resserrées, la garantie est respectée.

Cependant, il y a un coût. Plus vous exigez de sécurité (plus la probabilité souhaitée est élevée), plus le plan devient conservateur. Le « couloir » devient plus étroit, et parfois le planificateur ne trouve aucun chemin. Les auteurs ont constaté que si le taux de succès du planificateur (trouver un chemin) diminue à mesure que les exigences de sécurité augmentent, la fiabilité des chemins qu'il trouve grimpe en flèche. Dans leurs expériences, la méthode a systématiquement surpassé la planification standard qui ignorait les erreurs de modèle, prouvant qu'un peu de prudence mathématique va très loin pour assurer la sécurité des robots.

En résumé, l'article fournit un moyen robuste et mathématiquement fondé de dire : « Je ne sais pas exactement comment ce robot se déplace, mais je sais de combien mon estimation pourrait être erronée, donc je vais planifier comme si le monde était un peu plus dangereux qu'il n'en a l'air. » Et les expériences montrent que cette stratégie fonctionne, transformant un pari potentiellement dangereux en une mission fiable.

Résumé Technique : Resserrement de Contraintes Conformes pour la Planification de Mouvement à Contraintes de Chance avec une Dynamique Inconnue

1. Formulation du Problème

Le document traite du défi de la planification de mouvement pour des robots autonomes dont la dynamique réelle est inconnue, bien qu'un modèle déterministe nominal approximatif soit disponible. L'objectif est de calculer une séquence de contrôle qui conduit le robot d'un état initial vers une région cible tout en évitant les états dangereux (obstacles) avec une probabilité de succès prescrite ( $1-\alpha$ ).

Crucialement, l'article définit cela comme un problème de planification à contraintes de chance sur une distribution de problèmes de planification ( $D_M$ ). Contrairement aux approches traditionnelles qui supposent un modèle stochastique connu ou des hypothèses structurelles sur l'incertitude (par exemple, un bruit gaussien), ce travail suppose que :

Les dynamiques réelles $f$ sont inconnues.
Seul un modèle nominal $\hat{f}$ est accessible.
Le système nominal et le système réel partagent les mêmes espaces d'état et de commande.
Les problèmes de planification (configurations d'obstacles, états initiaux, buts) sont tirés de manière i.i.d. d'une distribution inconnue.

La difficulté centrale réside dans le fait que les effets non modélisés, l'incertitude des paramètres ou les erreurs d'approximation dans les modèles appris peuvent provoquer des trajectoires qui sont sûres sous le modèle nominal mais échouent sur le système réel.

2. Méthodologie

Le cadre proposé est indépendant du planificateur (planner-agnostic), ce qui signifie qu'il peut être intégré à n'importe quel algorithme de planification de mouvement existant (par exemple, RRT, MPC, apprentissage par renforcement profond). La méthodologie se compose de trois étapes principales :

A. Prédiction Conforme (CP) pour la Quantification de l'Incertitude

Les auteurs exploitent la Prédiction Conforme pour quantifier l'écart entre les trajectoires nominales et réelles sans supposer de distribution spécifique pour l'erreur de modèle.

Jeu de données de calibration : Un jeu de données est construit en exécutant des séquences de contrôle nominalement réalisables sur le système réel afin de collecter les trajectoires réelles correspondantes.
Score de non-conformité (NCS) : Pour chaque problème de planification dans le jeu de données de calibration, un score est calculé représentant la déviation euclidienne maximale (pire cas) entre la trajectoire nominale et la trajectoire réelle sur l'horizon de planification :
$R(M) := \sup_{u} \max_{t} \|x_t - \hat{x}_t\|_2$
Note : En pratique, cela est approximé en utilisant un sous-ensemble fini de séquences de contrôle réalisables.
Calcul du seuil : Étant donné une probabilité de défaillance cible $\alpha$ , la CP calcule un seuil $\hat{q}_\alpha$ comme étant le $\alpha$ -ième quantile empirique des scores de calibration. Ce seuil fournit une borne probabiliste sur la déviation entre le nominal et le réel pour des problèmes de planification inédits tirés de la même distribution.

B. Resserrement des Contraintes

En utilisant le seuil conforme $\hat{q}_\alpha$ , les auteurs définissent un problème de planification resserré ( $M_\alpha$ ) sous le modèle nominal :

Espace Libre Resserré ( $X^{\hat{q}_\alpha}_{free}$ ) : L'espace libre original est réduit en "érodant" ses frontières. Un état $x$ n'est inclus que si une boule de rayon $\hat{q}_\alpha$ centrée en $x$ est entièrement contenue dans l'espace libre original.
Région Cible Resserrée ( $X^{\hat{q}_\alpha}_{goal}$ ) : De même, la région cible est contractée de telle sorte qu'une boule de rayon $\hat{q}_\alpha$ centrée en n'importe quel point de la nouvelle région cible soit contenue dans la région cible originale.

Géométriquement, cela équivaut à gonfler les obstacles et à contracter la région cible par le rayon $\hat{q}_\alpha$ .

C. Garantie Théorique

L'article prouve que si une séquence de contrôle résout le problème resserré $M_\alpha$ en utilisant le modèle nominal, elle satisfait le problème original à contraintes de chance sur le système réel avec une probabilité d'au moins $1-\alpha$ . Cela est dû au fait que la borne conforme garantit que la trajectoire réelle reste dans la boule de rayon $\hat{q}_\alpha$ de la trajectoire nominale ; si la trajectoire nominale reste dans l'espace libre érodé, la trajectoire réelle est garantie de rester dans l'espace libre original.

3. Contributions Clés

Quantification de l'Incertitude basée sur la CP : Développement d'un cadre qui utilise uniquement un modèle nominal et des données de calibration pour fournir une borne probabiliste sur l'écart de modèle au niveau de la trajectoire sur une distribution de problèmes de planification, sans nécessiter de modèles d'incertitude paramétriques.
Resserrement de Contrainte Indépendant du Planificateur : Une méthode pour convertir le problème à contraintes de chance en un problème de planification déterministe avec des contraintes resserrées. L'article prouve que la résolution de ce problème déterministe est une condition suffisante pour satisfaire l'exigence probabiliste originale.
Validation Empirique : Démonstration de l'efficacité du cadre dans des contextes tant déterministes (écart de paramètres) que stochastiques (modèle appris + bruit de processus).

4. Résultats Expérimentaux

Le cadre a été évalué sur deux scénarios :

Véhicule Dubins : Un système déterministe avec des paramètres de translation incorrects (simulant une résistance de surface).
Quadrotor Planaire : Un système de dimension supérieure, sous-actionné, avec une dynamique stochastique et un modèle de réseau neuronal appris.

Principales conclusions :

Couverture Empirique : Dans toutes les expériences, la couverture empirique (la fraction de trajectoires réelles satisfaisant les contraintes de sécurité/but) a systématiquement dépassé le niveau cible prescrit ( $1-\alpha$ ), validant ainsi les garanties théoriques.
Compromis (Trade-off) : À mesure que la probabilité prescrite ( $1-\alpha$ ) augmentait, le seuil conforme $\hat{q}_\alpha$ augmentait, entraînant un resserrement plus conservateur des contraintes. Cela entraînait une diminution du taux de succès du planificateur (la capacité à trouver une solution dans l'espace resserré) mais une augmentation significative du taux d'achèvement de la tâche (la capacité à exécuter avec succès la tâche sur le système réel).
Performance vs Baseline : La méthode proposée a systématiquement surpassé un planificateur RRT de référence qui utilisait le modèle nominal sans resserrement de contrainte. Pour le quadrotor, avec une couverture cible de 90 %, la méthode proposée a atteint un taux d'achèvement de tâche de 100 % contre environ 55 % pour la base de référence nominale.

5. Signification et Revendications

L'article affirme traiter une limitation critique de la littérature existante sur la planification de mouvement : la dépendance à des modèles ou simulateurs précis pour les garanties de sécurité. En découplant l'algorithme de planification de la quantification de l'incertitude, le cadre proposé permet aux planificateurs existants d'opérer en toute sécurité sur des systèmes aux dynamiques inconnues.

Les auteurs soulignent que leur approche fournit une garantie probabiliste marginale sur une distribution de problèmes de planification, plutôt qu'une garantie par tâche. Cela est particulièrement pertinent pour les applications robotiques où les planificateurs sont invoqués de manière répétée dans des environnements et des spécifications de mission variables. Le travail démontre qu'il est possible d'atteindre une grande fiabilité dans l'achèvement des tâches pour des systèmes inconnus en acceptant un certain compromis sur le taux de succès du planificateur (conservatisme) via le resserrement de contraintes conforme.

L'article reconnaît des limites, notant que l'approche peut être conservatrice, particulièrement lorsque l'ensemble des perturbations est important ou que l'écart de modèle est significatif. Des travaux futurs sont suggérés pour réduire ce conservatisme et développer des stratégies de risque adaptatives lorsqu'aucune solution ne peut être trouvée pour le problème resserré.