Multi-Resolution POMDP Planning for Multi-Object Search in 3D

Auteurs: Kaiyu Zheng, Yoonchang Sung, George Konidaris, Stefanie Tellex · IROS 2021

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

La recherche de plusieurs objets en 3D formulée comme un POMDP, résolue en ligne par une planification parallèle à plusieurs résolutions d'octree ; elle bat des références sans hiérarchie dans de grands espaces simulés et fonctionne sur un Kinova MOVO.

Pourquoi c'est important

Elle fait passer la recherche d'objets par POMDP des cartes 2D à des régions de recherche 3D tout en maintenant la planification en ligne dans un temps fixe par pas. La croyance en octree n'a pas besoin d'être construite en entier, et l'occultation est traitée par une étiquette de voxel UNKNOWN, sans modèles géométriques des objets encombrants.

Problème

Les robots domestiques doivent trouver plusieurs objets sur des étagères, sous des tables et dans des placards avec un champ de vision de caméra limité, en forme de tronc de pyramide, et en présence d'occultations. La recherche d'objets fondée sur les POMDP repose sur des principes solides, mais les travaux antérieurs réduisaient l'espace de recherche ou la mobilité du robot à la 2D, car une croyance exacte sur de grands espaces d'états 3D est intraitable et de grands espaces d'observation imposent aux planificateurs un facteur de branchement élevé.

Solution proposée

Les auteurs définissent 3D-MOS, un POMDP orienté objet avec des poses de caméra 6D, les actions MOVE, LOOK et FIND, et des observations constituées de voxels étiquetés dans le tronc de pyramide de vision, factorisées par objet. Un modèle d'observation par voxel et une croyance en octree donnent des mises à jour de croyance exactes en O(|V| log |G|) et un échantillonnage à n'importe quelle résolution en O(log |G|) ; des POMDP abstraits à des résolutions plus grossières sont chacun résolus par POUCT en parallèle, et l'action de plus grande valeur est exécutée (MR-POUCT).

Idées clés

• Factoriser l'état et l'observation par objet fait croître l'espace des croyances linéairement, et non exponentiellement, avec le nombre d'objets.
• Modéliser l'étiquette de chaque voxel séparément, les voxels occultés ou hors champ étant non informatifs, réduit l'espace d'observation pour la planification et limite les mises à jour de croyance aux voxels visibles.
• Stocker les croyances dans un octree, où chaque nœud contient la somme des valeurs de ses enfants, donne des croyances exactes à chaque résolution et un échantillonnage en temps logarithmique.
• Planifier en parallèle à plusieurs résolutions et exécuter la meilleure action permet de faire face à des tailles et distances d'objets inconnues auxquelles une résolution unique ne conviendrait pas.
• Les croyances particulaires (POMCP) souffrent d'un appauvrissement des particules avec de grands espaces d'observation et se dégradent jusqu'à un comportement aléatoire dans ce domaine.

Principaux résultats

• En simulation sur 12 configurations (côté de l'espace de recherche m ∈ {4, 8, 16, 32}, n ∈ {2, 4, 6} objets, 40 essais chacune), MR-POUCT a surpassé la recherche Exhaustive dans tous les cas de test à m = 16 et m = 32 en récompense cumulée actualisée.
• La recherche Exhaustive a fait mieux dans les petits espaces (m = 4 et 8), où une vue couvre jusqu'à 17,2 % et 8,8 % de la grille ; à m = 32, une vue couvre au plus 2,6 %.
• Chaque méthode disposait d'au plus 3,0 s de planification par pas et de 120 s à 480 s au total selon m ; POMCP a donné de mauvais résultats à cause de l'appauvrissement des particules.
• Avec du bruit de capteur sur l'instance (16, 2, 10), MR-POUCT a été systématiquement le meilleur pour tous les réglages essayés, et β n'a eu presque aucun effet tant que β < 1. Le texte parle de 5 réglages de α mais énumère six valeurs (10, 100, 500, 10³, 10⁴, 10⁵).
• Sur un Kinova MOVO, le robot a trouvé 3 des 6 objets placés à différentes hauteurs dans deux régions d'environ 10 m² × 2 m en environ 15 minutes, en abaissant son torse si nécessaire pour voir une cible.
• Utiliser k = 10 ou k = 40 échantillons de Monte-Carlo pour le modèle d'observation abstrait a donné des performances de recherche similaires ; k = 10 a été retenu.

Limites

• Supposer les objets indépendants économise du calcul mais peut écarter des dépendances utiles entre objets ; la recherche d'objets corrélés reste ouverte (selon les auteurs).
• Le modèle d'observation ne raisonne pas sur la géométrie des objets, et chaque objet est supposé tenir dans un seul voxel à la résolution de planification (selon les auteurs).
• Une politique de rollout aléatoire uniforme a été utilisée ; les auteurs suggèrent un rollout heuristique pour des problèmes plus réalistes, au prix de l'optimalité.
• Sur le robot réel, les objets couverts par aucun point de vue de la carte topologique ont été manqués ; les auteurs proposent une carte plus dense ou des destinations MOVE échantillonnées.
• Les objets et obstacles sont supposés statiques, l'état du robot est supposé observable, et dans les petits espaces de recherche la simple recherche exhaustive a fait mieux.

Impact sur le domaine

L'article a remporté le IROS 2021 Best RoboCup Paper Award et compte 33 citations. Il renvoie à une page de projet avec une vidéo des observations volumétriques et des mises à jour de la croyance en octree ; il ne mentionne pas de publication du code.

Résumé

Les robots opérant dans les foyers doivent trouver des objets sur des étagères, sous des tables et dans des placards. Dans de tels environnements, il est crucial de rechercher efficacement à l'échelle 3D tout en composant avec un champ de vision limité et la complexité de la recherche de plusieurs objets. Les approches de recherche d'objets fondées sur des principes utilisent fréquemment le processus de décision markovien partiellement observable (POMDP) comme cadre sous-jacent pour calculer des stratégies de recherche, mais restreignent l'espace de recherche à la 2D. Dans cet article, nous présentons une formulation POMDP pour la recherche de plusieurs objets dans une région 3D avec un champ de vision en forme de tronc de pyramide. Pour résoudre efficacement ce POMDP, nous proposons un algorithme de planification multirésolution fondé sur la recherche arborescente Monte-Carlo en ligne. Dans cette approche, nous concevons une nouvelle représentation de croyance fondée sur un octree pour capturer l'incertitude sur les objets cibles à différents niveaux de résolution, puis nous dérivons des POMDP abstraits à des résolutions plus faibles avec des espaces d'états et d'observations considérablement plus petits. L'évaluation dans un domaine 3D simulé montre que notre approche trouve les objets plus efficacement et avec plus de succès qu'un ensemble de références sans hiérarchie de résolution, sur des instances plus grandes et pour la même exigence de calcul. Nous démontrons notre approche sur un robot mobile qui trouve des objets placés à différentes hauteurs dans deux régions de 10m² × 2m en déplaçant sa base et en actionnant son torse.

Liens

• arXiv 2005.02878: https://arxiv.org/abs/2005.02878
• DOI 10.1109/IROS51168.2021.9636737: https://doi.org/10.1109/IROS51168.2021.9636737
• PDF: https://arxiv.org/pdf/2005.02878v4
• Page du projet: https://zkytony.github.io/3D-MOS/