Belief-Space Planning
- Aussi appelé: planning in belief space
- Catégorie: Planning & manipulation › Motion planning
- Mots-clés: planning-under-uncertainty, pomdp, state-estimation, active-sensing, probabilistic-robotics
Planification sur des distributions de probabilité de l'état du robot plutôt que sur une estimation unique, afin de pouvoir choisir des actions qui réduisent l'incertitude tout en atteignant le but.
Définition
Un robot connaît rarement son état exactement : sa pose, la position des objets et le résultat des contacts ne sont connus qu'à travers des capteurs bruités. Une croyance (belief) est une distribution de probabilité sur les états possibles étant donné l'historique des actions et des observations, et l'espace des croyances est l'espace de toutes ces distributions. La planification dans l'espace des croyances (belief-space planning) choisit des actions en prédisant comment elles modifieront la croyance, et pas seulement l'état nominal. Le planificateur peut ainsi arbitrer entre la progression vers le but et la réduction de l'incertitude, par exemple en passant près d'un amer pour se localiser avant d'entrer dans une embrasure de porte étroite, ou en touchant un objet pour trouver sa position avant de le saisir.
Formellement, la planification dans l'espace des croyances est une façon de résoudre des processus de décision markoviens partiellement observables (POMDP). Le POMDP est la formulation du problème ; le reformuler sur les croyances le transforme en un problème de décision entièrement observable dans lequel la croyance joue le rôle de l'état. Les espaces de croyances sont de grande dimension, et de dimension infinie pour des états continus, si bien que les solutions exactes sont rarement praticables pour des robots et que les méthodes procèdent par approximation. Les planificateurs gaussiens dans l'espace des croyances représentent la croyance par une moyenne et une covariance, la propagent avec un filtre de Kalman étendu, puis recherchent ou optimisent sur ces croyances compactes, comme dans les belief roadmaps et la planification de mouvement fondée sur LQG. Les méthodes particulaires représentent les croyances par des échantillons pondérés, et les solveurs de POMDP en ligne explorent un arbre de séquences d'actions et d'observations à partir de la croyance courante. Beaucoup de systèmes simplifient encore en supposant l'observation la plus probable pendant la planification et en replanifiant lorsque les observations réelles arrivent.
La planification dans l'espace des croyances diffère de la planification sur l'état moyen avec des marges de sécurité, qui traite l'incertitude comme fixe. Dans l'espace des croyances, les actions peuvent délibérément réduire l'incertitude, de sorte que les plans peuvent inclure des mouvements de collecte d'information qu'un planificateur déterministe ne choisirait jamais. Le prix à payer est le calcul, et la qualité du plan dépend de la précision avec laquelle les modèles de capteur et de mouvement prédisent les croyances futures. Dans certaines tâches, des contrôleurs réactifs qui répondent à l'estimation courante sans anticipation obtiennent des performances comparables pour un coût bien moindre, ce qui explique que les planificateurs dans l'espace des croyances servent souvent de références de comparaison pour de telles méthodes.
Pourquoi c'est important
Les robots qui ne planifient que sur leur meilleure estimation de l'état peuvent s'engager dans des actions qui échouent quand cette estimation est fausse, comme saisir là où l'on croit qu'un objet se trouve. La planification dans l'espace des croyances fait de l'incertitude une partie de la décision : elle produit des plans qui localisent, mesurent ou sondent quand cela coûte moins cher qu'un échec, et offre une manière rigoureuse de décider quand davantage de perception vaut le temps qu'elle prend.
Applications principales
- Navigation avec localisation active là où les amers sont rares
- Manipulation sous incertitude sur la pose des objets, y compris la localisation par le toucher
- Insertion et autres tâches de contact où l'erreur de position dépasse le jeu
- Recherche et exploration qui arbitrent entre gain d'information et coût de déplacement
- Prise de décision pour des véhicules incertains des intentions des autres agents
- Saisie dans l'encombrement avec occultation partielle
En pratique
Un robot doit insérer une clé dans une serrure dont la position n'est connue par une caméra qu'à quelques millimètres près, soit davantage que le jeu d'insertion. Un planificateur travaillant sur l'estimation moyenne irait directement à la position supposée et la manquerait souvent. Un planificateur dans l'espace des croyances représente la position de la serrure par une gaussienne, prédit dans quelle mesure chaque mouvement et chaque contact candidats réduiraient la covariance, et trouve que faire glisser la clé le long de la face de la serrure jusqu'à ce qu'elle rencontre le bord élimine à peu de frais l'incertitude selon un axe. Le plan comprend donc un mouvement de palpage gardé avant l'insertion. Pendant l'exécution, un filtre de Kalman étendu met à jour la croyance avec les mesures d'effort, et le planificateur replanifie à partir de la nouvelle croyance chaque fois que les observations diffèrent de ses prédictions.
Idées reçues
- La planification dans l'espace des croyances n'est qu'une planification avec des marges d'erreur — les marges traitent l'incertitude comme fixe, alors que les planificateurs dans l'espace des croyances peuvent choisir des actions qui la réduisent
- Une croyance est la même chose qu'une estimation de l'état — une estimation de l'état est généralement un point unique comme la moyenne, alors que la croyance est la distribution entière, y compris sa dispersion et sa forme
- La planification dans l'espace des croyances exige de résoudre exactement le POMDP complet — les méthodes pratiques reposent sur des approximations comme les croyances gaussiennes, les particules ou l'hypothèse de l'observation la plus probable
Qui devrait le savoir
- Chercheurs en planification de mouvement et de tâches travaillant sous incertitude
- Ingénieurs en manipulation confrontés à l'incertitude sur la pose des objets
- Ingénieurs en navigation autonome
- Étudiants en robotique probabiliste
Technologies associées
- Filtre de Kalman étendu (Extended Kalman Filter)
- Filtre particulaire (Particle Filter)
- Solveurs de POMDP en ligne (Online POMDP Solvers)
- Belief Roadmap
- Planification de mouvement LQG (LQG Motion Planning)
- Métriques de gain d'information (Information Gain Metrics)
Termes associés
- Partially Observable Markov Decision Process (POMDP)
- Extended Kalman Filter
- Particle Filter
- Interactive Perception
- Robotic information gathering
- Task and Motion Planning