POMDP-based Object Search with Growing State Space and Hybrid Action Domain

1. Problématique

La localisation efficace d'objets cibles dans des environnements intérieurs complexes et encombrés (meubles, étagères, tables) représente un défi majeur pour les robots mobiles. Les difficultés principales proviennent de :

• Erreurs de localisation et champs de vision limités.
• Occlusions visuelles fréquentes où les objets sont partiellement ou totalement cachés par d'autres éléments.
• Espaces d'états et d'actions complexes : La nécessité de gérer des espaces d'états qui évoluent (détection de nouveaux objets au fur et à mesure) et des espaces d'actions hybrides (continus pour le mouvement du robot, discrets pour les décisions logiques).
• Limites des approches existantes : Les méthodes basées sur l'apprentissage (RL) sont souvent spécifiques à un environnement, tandis que les solveurs POMDP classiques peinent à gérer les espaces continus de haute dimension et les états croissants sans reconstruire entièrement l'arbre de croyance, ce qui est coûteux en calcul.

2. Méthodologie : GNPF-kCT

Les auteurs proposent un cadre complet basé sur un Processus de Décision Markovien Partiellement Observable (POMDP) et un nouveau solveur en ligne nommé GNPF-kCT (Growing Neural Process filtered k-center clustering tree).

A. Formulation du POMDP

• Espace d'état (S) : Croissant. Il inclut la configuration du robot et les états des objets. Un "objet cible hypothétique" (guessed target object) est introduit avec un modèle de grille (grid-world) pour guider l'exploration même avant la détection physique de l'objet. De nouveaux objets détectés ajoutent des dimensions à l'espace d'état ($S_k = S_{k-1} \times \Delta S_{k-1}$).
• Espace d'actions (A) : Hybride ($A_c \times A_d$).
  • Continu ($A_c$) : Mouvements de la base, hauteur du bras, angles de la tête (pan/tilt).
  • Discret ($A_d$) : Déclarer un objet comme cible/obstacle, retirer un objet.
• Observation (O) : Basée sur les données des capteurs (nuages de points 3D, images RGB-D) et la mise à jour des probabilités (log-odds) sur les grilles des objets.
• Récompense (R) : Conçue pour encourager la déclaration correcte, le retrait d'obstacles et la localisation finale de la cible, tout en pénalisant les actions illégales ou coûteuses.

B. Le Solveur GNPF-kCT

Ce solveur combine plusieurs techniques avancées pour surmonter les limites des solveurs POMDP traditionnels :

1. Filtrage par Processus Neuronal (Neural Process - NP) :

   • Un réseau de processus neuronal pré-entraîné prédit la faisabilité et l'efficacité des actions primitives continues.
   • Il filtre les actions inutiles (qui ne réduiraient pas l'incertitude) en utilisant une fonction de score avec une estimation d'incertitude, réduisant ainsi la dimension de l'espace d'actions à explorer.
   • La théorie garantit que si le score moyen dépasse un seuil lié à l'écart-type, l'action a une forte probabilité d'être efficace.

2. Discrétisation par Clustering k-Center (k-center clustering) :

   • Les actions continues filtrées sont regroupées en "hypersphères" via un algorithme de clustering k-center.
   • Cela permet une discrétisation adaptative : l'espace d'action est raffiné dynamiquement (divisé en sous-sphères) lorsque l'arbre de croyance est exploré suffisamment, assurant une convergence vers l'action optimale sans explosion combinatoire.

3. Réutilisation de l'Arbre de Croyance (Belief Tree Reuse) :

   • Contrairement aux méthodes classiques qui reconstruisent l'arbre entier lors de la détection d'un nouvel objet (changement d'espace d'état), GNPF-kCT réutilise l'arbre existant.
   • Il met à jour les historiques de particules et les observations pour intégrer les nouveaux objets, ne gardant que les branches pertinentes. Cela économise considérablement le temps de calcul.

4. Stratégie d'Exploration (UCB Modifié) :

   • Une borne supérieure de confiance (UCB) révisée guide la recherche Monte Carlo (MCTS). Elle intègre le rayon de l'hypersphère (pour tenir compte de la continuité) et une mesure de distance de croyance (Belief Distance) pour gérer les changements d'état.

5. Stratégie d'Exploration "Objet Hypothétique" :

   • L'introduction d'un objet cible hypothétique avec des probabilités mises à jour sur une grille permet au robot d'explorer activement des zones où la cible pourrait se trouver, même en l'absence de détection directe, améliorant l'efficacité de la recherche.

3. Contributions Clés

• Formulation Réaliste : Un modèle POMDP complet intégrant un espace d'état croissant, un domaine d'actions hybride et un processus de perception réaliste (sans marqueurs artificiels comme les QR codes).
• Nouveau Solveur Efficace : GNPF-kCT, qui combine le filtrage neuronal, le clustering hiérarchique et la réutilisation d'arbres pour résoudre des problèmes POMDP complexes en temps réel.
• Amélioration de l'Exploration : L'utilisation d'un objet cible hypothétique et de grilles de probabilité pour guider la recherche dans des environnements partiellement observables.
• Validation Expérimentale : Démonstrations réussies sur des robots réels (Fetch et Stretch) et en simulation (Gazebo), surpassant les méthodes de l'état de l'art.

4. Résultats Expérimentaux

Les expériences ont été menées dans des environnements simulés (Gazebo) et réels (bureaux) avec des robots Fetch et Stretch.

• Comparaison avec les bases POMDP : GNPF-kCT surpasse significativement les solveurs classiques (POMCP, GPOMCP) et les méthodes à domaine continu (POMCPOW, VOMCPOW) en termes de récompense cumulative, de nombre d'étapes et de taux de réussite.
• Comparaison avec les méthodes non-POMDP (LLM) : L'article compare sa méthode avec des approches basées sur les Grands Modèles de Langage (LLM) comme SayPlan et MoMa-LLM.
  • Les méthodes LLM ont échoué ou ont eu des performances médiocres dans des scénarios complexes avec occlusions, car elles peinent à modéliser les incertitudes physiques et les contraintes géométriques fines sans modèles explicites.
  • GNPF-kCT a atteint un taux de réussite de 100% dans la plupart des scénarios (y compris les plus complexes comme "Covered1" et "Complex1"), tandis que les méthodes LLM ont souvent échoué (0% de réussite dans les scénarios les plus denses).
• Robustesse : La méthode fonctionne bien avec différents paramètres et s'adapte à différents robots (Fetch et Stretch) sans réentraînement majeur du réseau neuronal.

5. Signification et Impact

Cet article est significatif car il démontre que pour des tâches de manipulation et de recherche d'objets dans des environnements réels et encombrés, les approches basées sur des modèles probabilistes rigoureux (POMDP) surpassent les approches purement basées sur le langage (LLM) lorsqu'il s'agit de gérer l'incertitude, les occlusions et les contraintes physiques.

• Praticité : Le système ne nécessite que des cartes de l'environnement, des photos de l'objet cible et des capteurs embarqués, sans besoin de modèles géométriques pré-définis pour chaque objet.
• Efficacité Computationnelle : Grâce à la réutilisation de l'arbre de croyance et au filtrage neuronal, le solveur est capable de prendre des décisions optimales en temps réel malgré la complexité croissante de l'environnement.
• Futur : Les auteurs suggèrent que l'avenir réside dans l'intégration de ces méthodes de raisonnement basées sur des modèles avec des capacités d'apprentissage (comme les VLA - Vision-Language-Action) pour améliorer la réussite des actions primitives complexes.

En résumé, GNPF-kCT représente une avancée majeure vers des robots autonomes capables de chercher et de récupérer des objets dans des maisons ou des entrepôts réels, en surmontant les défis de l'occlusion et de l'incertitude perceptionnelle.