Résumé technique : Anticipation courtoise dans les environnements partagés persistants

Énoncé du problème

L'article traite du défi de la planification de tâches à long terme pour plusieurs robots opérant dans un environnement partagé et persistant. Dans ce cadre, les robots se voient assigner des tâches séquentiellement à partir d'une séquence réservée, l'état terminal d'une tâche devenant l'état initial de la suivante.

Les planificateurs de tâches standards sont « myopes », se concentrant uniquement sur la minimisation du coût immédiat pour accomplir la tâche actuelle sans vision à long terme. Cela conduit à un comportement « égoïste » où un robot laisse l'environnement dans un état terminal qui augmente le coût d'exécution des tâches futures assignées à lui-même ou à d'autres robots. Les auteurs identifient que dans les environnements où les robots possèdent des capacités distinctes (par exemple, la taille, la résistance à la chaleur, des outils spécialisés) et des responsabilités distinctes, ces effets secondaires négatifs s'accumulent au fil du temps. Un robot pourrait placer un objet dans un endroit inaccessible à un pair ou dans un état qu'un pair ne peut résoudre, forçant des interventions coûteuses (telles que des actions d'« aide ») ou des détours plus tard dans la séquence.

Les méthodes de planification anticipative existantes [11]–[13] améliorent la planification myope en considérant les propres tâches futures d'un robot, mais restent « égoïstes » dans les contextes multi-robots, car elles ne tiennent pas compte de la manière dont les actions actuelles impactent les contraintes et les capacités des autres agents.

Méthodologie : Planification anticipative courtoise

Les auteurs proposent une Planification anticipative courtoise, une approche basée sur des modèles qui sélectionne les plans en minimisant conjointement le coût immédiat de la tâche actuelle et le coût futur agrégé pour tous les robots partageant l'environnement.

1. Fonction d'objectif

Contrairement à la planification anticipative standard pour un robot unique qui minimise $V_{sg}(s_0) + \sum P(\tau')V_{\tau'}(s_g)$ (Éq. 2), l'objectif proposé (Éq. 3) agrège les coûts anticipatifs de tous les robots $R$ :
$$s^*_g = \arg\min_{s'_g \in G_\tau} \left[ V^*_{s'_g}(s_0) + \sum_{r \in R} V^r_{A.P.}(s'_g) \right]$$
Ici, $V^r_{A.P.}(s'_g)$ représente le coût attendu pour le robot $r$ pour accomplir une tâche ultérieure tirée de ses responsabilités spécifiques, en partant de l'état terminal $s'_g$ du plan actuel.

2. Formulation factorisée et estimateurs

Le calcul direct du coût futur attendu conjoint nécessite d'énumérer toutes les séquences de tâches futures possibles pour tous les robots, un espace combinatoire qui est informatiquement intraitable. Pour résoudre cela, les auteurs décomposent le problème en estimateurs indépendants par robot :

• Estimation augmentée par l'apprentissage : Pour chaque robot $r$, un réseau de neurones sur graphe (GNN) est entraîné indépendamment pour estimer $V^r_{A.P.}(s'_g)$.
• Données d'entraînement : Les GNN sont entraînés hors ligne en utilisant des données générées en résolvant des tâches issues de la distribution de responsabilité d'un robot à l'aide d'un planificateur standard (FastDownward avec FF-A*). L'entrée est un graphe de scène parcimonieux représentant l'état de l'environnement.
• Modularité : Comme les estimateurs sont entraînés indépendamment sur les contraintes structurelles et les responsabilités d'un seul robot, l'ajout d'un nouveau robot au système nécessite seulement l'entraînement de l'estimateur spécifique à ce robot. Aucun réentraînement des estimateurs existants ou de rollouts conjoints n'est nécessaire.

3. Algorithme de planification

Le planificateur (Algorithme 1) fonctionne comme suit :

1. Génération de candidats : En utilisant une procédure d'« échantillonnage ciblé », le planificateur génère un ensemble diversifié de plans candidats qui satisfont la tâche actuelle. Cela implique d'augmenter les tâches avec des prédicats de placement pour créer des plans structurellement distincts (par exemple, placer un bol sale sur un comptoir plutôt que dans un évier).
2. Évaluation du coût : Pour chaque plan candidat, le planificateur interroge tous les estimateurs GNN par robot pour obtenir les coûts futurs attendus.
3. Sélection : Le plan ayant la somme minimale du coût immédiat et des coûts futurs agrégés est sélectionné.

Principales contributions

1. Identification d'un obstacle à la planification : L'article souligne que l'absence de « courtoisie » dans la planification de tâches standard crée des effets secondaires négatifs qui augmentent les coûts cumulés dans les environnements partagés persistants, un problème exacerbé par l'hétérogénéité des capacités des robots.
2. Cadre d'anticipation courtoise : L'introduction d'un objectif de planification qui minimise le coût immédiat plus le coût futur attendu agrégé pour tous les agents. Ceci est réalisé via une formulation factorisée utilisant des estimateurs indépendants par robot, évitant ainsi les rollouts conjoints combinatoires.
3. Déploiement modulaire : L'approche permet un déploiement modulaire où l'ajout ou le retrait de robots nécessite uniquement l'entraînement de l'estimateur spécifique à ce robot, sans réentraîner le système.
4. Évaluation dans des domaines complexes : Les auteurs évaluent la méthode dans deux domaines basés sur PDDL :
   • Environnement domestique : Deux robots ayant des capacités similaires mais des responsabilités distinctes.
   • Environnement de restaurant : Trois robots ayant des capacités physiques distinctes (par exemple, un cuisinier grand et résistant à la chaleur, un serveur et un nettoyeur) et des responsabilités distinctes.

Résultats expérimentaux

La méthode a été évaluée sur de longues séquences de tâches (20 tâches dans le cadre domestique ; 10 tâches par robot dans le cadre du restaurant) contre deux lignes de base :

• Myope : Planification classique (FastDownward) minimisant uniquement le coût immédiat.
• Anticipation égoïste : Planification qui considère uniquement les tâches futures du robot en action.

Améliorations quantitatives :

• Environnement domestique (2 robots) : La planification courtoise a réduit le coût total de 10,43 % par rapport à la méthode Myope et de 4,03 % par rapport à l'Anticipation égoïste.
• Environnement de restaurant (3 robots) : La planification courtoise a réduit le coût total de 17,41 % par rapport à la méthode Myope et de 13,24 % par rapport à l'Anticipation égoïste.
• Validation de la modularité : Des estimateurs entraînés dans des contextes à 2 robots ont été utilisés avec succès dans des contextes à 3 robots sans réentraînement, confirmant la nature « plug-and-play » de l'approche.
• Proactivité : Dans un scénario où un robot « Nettoyeur » recevait un budget de temps pour agir pendant ses temps morts (sans tâche explicite), l'approche courtoise a permis au robot de nettoyer proactivement la vaisselle, réduisant le coût total du système de 31,4 % par rapport à une ligne de base où le robot inactif ne prenait aucune action.

Signification et affirmations

L'article affirme que l'anticipation courtoise est essentielle pour une planification de tâches séquentielle efficace dans les environnements partagés. Les auteurs soutiennent que la planification standard échoue dans ces contextes car elle ignore les « contraintes physiques » et les « responsabilités » des autres agents.

La portée des travaux réside dans la démonstration que :

1. L'hétérogénéité amplifie la valeur : Les bénéfices de la planification courtoise sont considérablement amplifiés lorsque les robots possèdent des capacités distinctes (par exemple, le cadre du restaurant), car les actions d'un robot peuvent directement permettre ou bloquer la capacité de fonctionnement d'un autre.
2. Évolutivité via la factorisation : En factorisant l'estimation du coût conjoint en modèles indépendants par robot, l'approche reste informatiquement traitable et évolutive, évitant l'intraitabilité de l'apprentissage de politique conjointe ou des rollouts exhaustifs.
3. Changement de comportement : L'approche induit des comportements où les robots considèrent activement l'impact en aval de leurs actions sur leurs pairs (par exemple, placer une poêle sale sur un chariot accessible à un nettoyeur plutôt que sur une cuisinière inaccessible pour lui), réduisant ainsi le besoin d'interventions d'« aide » coûteuses.

Les auteurs reconnaissent les limites, notant que le cadre actuel suppose l'arrivée séquentielle des tâches et ne gère pas encore l'exécution concurrente ou les changements environnementaux en temps réel causés par d'autres agents. Des travaux futurs sont proposés pour étendre cela aux contextes concurrents.