Forecast-Aware Cooperative Planning on Temporal Graphs under Stochastic Adversarial Risk

1. Problématique

L'article aborde le défi de la navigation coopérative de plusieurs robots dans des environnements dynamiques où les conditions de traversée évoluent en raison de la présence d'adversaires (patrouilles) ou de dangers mobiles. Contrairement aux approches classiques qui supposent des risques statiques, ce travail considère un risque stochastique temporel.

• Contexte : Les robots doivent atteindre leurs objectifs tout en évitant des arêtes (liens du graphe) occupées par des adversaires.
• Dynamique : Les adversaires se déplacent selon un processus de Markov d'ordre un (modèle "stay-move" : rester sur l'arête ou passer à une arête adjacente). Cela crée une incertitude sur la localisation future des menaces.
• Mécanisme de soutien (Support) : Les robots peuvent coopérer en occupant des nœuds de soutien spécifiques pour couvrir les arêtes à risque, réduisant ainsi le coût de traversée pour leurs coéquipiers.
• Défi principal : Les planificateurs myopes (qui ne regardent que le risque actuel) échouent car ils ne peuvent pas anticiper l'évolution du risque. Cela conduit à des actions de soutien mal placées (trop tôt, trop tard ou au mauvais endroit), augmentant les coûts totaux de la mission.

2. Méthodologie

Les auteurs proposent un cadre de planification en trois étapes intégré sur des graphes temporels :

A. Modélisation et Prévision du Risque

• Dynamique des adversaires : Le mouvement des $M$ adversaires est modélisé comme une chaîne de Markov sur l'ensemble des arêtes du graphe.
• Propagation temporelle : En utilisant une matrice de transition d'arête à arête ($\Theta$), le système propage les distributions de probabilité initiales vers l'avant dans le temps.
• Prévision : Cela génère des prévisions de risque d'arête ($\rho_{uv}(t)$), représentant la probabilité qu'au moins un adversaire occupe l'arête $(u, v)$ à un instant $t$ futur.

B. Allocation de Soutien Consciente des Prévisions (Forecast-Aware Support Allocation)

Au lieu de fixer les positions de soutien uniquement sur le risque initial, l'algorithme identifie dynamiquement les nœuds de soutien optimaux pour les arêtes qui deviendront risquées.

• Sélection des candidats : Pour chaque arête à risque futur, seuls les nœuds de soutien à proximité (dans un rayon $k$-sauts) sont considérés.
• Fonction de notation (Scoring) : Chaque nœud candidat reçoit un score basé sur deux facteurs :
  1. Recouvrement de trajectoire ($\hat{P}$) : Combien de robots passent par ce nœud sur leurs chemins optimaux (trafic robotique).
  2. Potentiel de risque ($\hat{R}$) : L'intensité du risque cumulé prévu sur l'arête à couvrir, pondérée par la distance.
• Allocation : Les nœuds avec les scores les plus élevés sont sélectionnés pour couvrir les arêtes à risque, créant une carte de correspondance $\Gamma$ entre nœuds de soutien et arêtes.

C. Planification Jointe sur Graphe Temporel

• Objectif : Minimiser le coût attendu de l'équipe (somme des coûts de déplacement, d'attente et de soutien).
• Approximation : Puisque les réalisations exactes des adversaires sont inconnues, le planificateur utilise les valeurs attendues des risques ($\rho_{uv}(t)$) pour calculer les coûts d'arête.
• Algorithme : Une variante de Lazy A* (A* paresseux) est utilisée sur le graphe temporel. Elle diffère l'évaluation des risques jusqu'à l'exploration de l'arête, ce qui permet une recherche efficace tout en maintenant l'optimalité de l'heuristique.

3. Contributions Clés

1. Formulation nouvelle : Définition du problème de traversée coopérative sur des graphes temporels sous risque adversaire stochastique, où les coûts évoluent dynamiquement.
2. Mécanisme d'allocation prédictif : Introduction d'une méthode d'allocation de soutien qui anticipe l'évolution du risque et l'aligne avec le trafic robotique prévu, plutôt que de réagir au risque actuel.
3. Validation empirique : Démonstration que cette approche réduit systématiquement le coût attendu de l'équipe par rapport aux méthodes non anticipatrices (baselines) et s'approche des performances d'un planificateur "oracle" (qui connaîtrait l'avenir).

4. Résultats Expérimentaux

Les expériences ont été menées sur des graphes aléatoires de différentes tailles (5 à 20 nœuds) avec des configurations variées de robots (2 à 4) et d'adversaires (4), avec des probabilités de "rester" (stay) variant de 0,2 à 1,0.

• Réduction des coûts : La méthode "Forecast-aware" obtient systématiquement le coût d'équipe le plus bas parmi toutes les stratégies de soutien (y compris Random et TCGRE - une méthode statique).
• Performance par rapport aux baselines :
  • Elle surpasse largement l'approche "No Support" (pas de soutien).
  • Elle bat l'approche "TCGRE" (soutien statique) car elle place le soutien sur les arêtes qui deviendront risquées plus tard, pas seulement sur celles qui le sont immédiatement.
  • Elle se rapproche de la borne inférieure "No Risk" (oracle idéal).
• Efficacité computationnelle : La méthode termine toujours dans les délais (90s), même pour les scénarios les plus complexes, tandis que d'autres méthodes échouent souvent (dépassement de temps) en raison de l'incapacité à trouver des trajectoires viables sans soutien bien placé.
• Calibration : Les simulations de Monte Carlo montrent que le coût réel réalisé ($J_{real}$) correspond très étroitement au coût attendu prévu ($J_{exp}$), validant la précision du modèle de prévision.
• Analyse qualitative : Sur un exemple visuel, la méthode permet de réduire le coût de l'équipe de ~42% et de gagner un pas de temps en évitant les attentes prolongées grâce à un soutien coordonné et anticipé.

5. Signification et Impact

Ce travail représente une avancée significative dans la planification multi-robots en environnement hostile :

• Passage du statique au dynamique : Il comble le fossé entre les modèles de risque statiques (courants dans la littérature MAPF) et la réalité des environnements dynamiques où les menaces se déplacent.
• Anticipation vs Réaction : Il démontre que l'anticipation (forecasting) est cruciale pour l'efficacité de la coopération. Réagir au risque présent est insuffisant ; il faut se préparer au risque futur.
• Synergie Trafic-Risque : L'intégration de la prévision de risque avec la connaissance des trajectoires des robots (trafic) permet d'optimiser l'allocation des ressources de soutien, évitant le gaspillage de capacités de soutien sur des zones peu fréquentées.
• Limites et Perspectives : L'approche repose actuellement sur une connaissance parfaite des dynamiques adverses et une planification centralisée. Les travaux futurs visent à intégrer l'estimation en ligne des dynamiques adverses et à passer à une coordination décentralisée.

En résumé, cet article propose un cadre robuste permettant aux équipes de robots de naviguer efficacement dans des environnements à risque évolutif en transformant l'incertitude stochastique en une stratégie de soutien proactive et optimisée.