Résumé technique : Résolution efficace des jeux à hiérarchie mixte par approximations quasi-stratégiques

Énoncé du problème

La coordination multi-robots implique souvent des structures d'information complexes où la prise de décision n'est ni purement simultanée (Nash) ni purement séquentielle (Stackelberg), mais un mélange des deux. Les solveurs de théorie des jeux existants peinent à gérer ces jeux à hiérarchie mixte, en particulier lorsqu'ils impliquent :

1. Des contraintes non linéaires (par exemple, découlant de dynamiques de mouvement non linéaires).
2. Des objectifs non quadratiques (codant des tâches complexes au-delà de simples coûts quadratiques).
3. Des modèles d'information en structure de forêt, où les robots forment des chaînes leader-suiveur (arbres) interagissant via des équilibres de Nash entre différentes branches.

Une barrière théorique et computationnelle majeure réside dans le fait que la dérivation des conditions d'optimalité du premier ordre (conditions de Karush–Kuhn–Tucker ou KKT) pour de tels jeux nécessite le calcul de dérivées d'ordre de plus en plus élevé des politiques de meilleure réponse des suiveurs à mesure que la profondeur de la hiérarchie augmente. Cela rend les méthodes de résolution directe intraitables pour des hiérarchies profondes ou des dynamiques complexes.

Méthodologie

Les auteurs proposent un cadre pour résoudre des jeux à hiérarchie mixte en structure de forêt à $N$ robots en approximatant les conditions d'optimalité afin d'éviter le calcul de dérivées d'ordre élevé.

1. Formulation du problème

Le jeu est modélisé comme un graphe acyclique orienté $G$ où les nœuds représentent les robots et les arêtes représentent les relations leader-suiveur. Les auteurs supposent que $G$ est une forêt (une union d'arbres déconnectés), garantissant que chaque robot a au plus un leader direct.

• Stratégies : Chaque robot $i$ minimise un objectif $J_i(z)$ soumis à des contraintes d'égalité $g_i(z_i)=0$ (par exemple, les dynamiques).
• Définition de l'équilibre : Un équilibre à hiérarchie mixte exige que chaque robot satisfasse :
  • Conditions de Stackelberg : Optimiser sa stratégie et les stratégies de son sous-arbre étant donné les stratégies de ses leaders.
  • Conditions de Nash : Optimiser sa stratégie étant donné les stratégies des robots dans d'autres branches (parents Nash) qu'il ne peut influencer.

2. Approximation quasi-stratégique

Pour contourner l'intraitabilité des dérivées d'ordre élevé dans les conditions KKT exactes, les auteurs introduisent une approximation quasi-stratégique :

• Mécanisme : Lors de la dérivation des conditions KKT pour un leader, la méthode intègre les politiques de meilleure réponse des suiveurs. Cependant, au lieu de calculer la dépendance récursive complète de ces politiques par rapport à la stratégie du leader (ce qui génère des dérivées d'ordre supérieur), la méthode ignore les dérivées d'ordre supérieur des politiques des suiveurs.
• Effet : Cela réduit la complexité récursive, permettant la construction du système KKT en utilisant uniquement les gradients de politique du premier ordre. Cela étend les travaux récents sur les jeux de feedback Nash et Stackelberg au contexte à hiérarchie mixte.

3. Solveur de Newton inexact

Les auteurs développent une méthode de Newton inexacte pour résoudre le système KKT approximatif résultant :

• Algorithme : Le solveur itère dans l'ordre topologique inverse pour construire les conditions KKT approximatives pour chaque robot. Il résout ensuite un système linéaire en utilisant une Jacobienne approximative (où les termes d'ordre supérieur sont mis à zéro) pour déterminer une direction de recherche.
• Convergence : L'article fournit une preuve théorique de convergence exponentielle locale pour les jeux avec objectifs non quadratiques et contraintes non linéaires, à condition que les sensibilités de politique d'ordre supérieur soient faibles par rapport aux gradients du premier ordre (une condition souvent remplie dans les problèmes de contrôle avec une régularisation forte).

Contributions clés

1. Approximation raisonnée : Une méthode novatrice pour construire des conditions d'optimalité approximatives pour des jeux à hiérarchie mixte non linéaires et contraints par égalité, en intégrant les meilleures réponses des suiveurs sous forme d'approximations de politique localement du premier ordre (quasi-stratégies).
2. Algorithme évolutif : Un solveur efficace et flexible pour des jeux à hiérarchie mixte en structure de forêt arbitraire avec coûts et contraintes non linéaires. Les auteurs prouvent et démontrent empiriquement une convergence exponentielle locale.
3. Implémentation open-source : La publication de MixedHierarchyGames.jl, une bibliothèque Julia hautement optimisée. La bibliothèque prend en charge des scénarios complexes, y compris des expériences matérielles et des simulations avec des centaines de variables.

Résultats expérimentaux

L'approche a été évaluée à la fois sur du matériel et en simulation :

• Matériel (Garde de cible) : Une expérience à trois robots impliquant un poursuivant, un gardien et une cible. Le gardien mène la cible, tandis que tous deux ont une relation de Nash avec le poursuivant. Le solveur s'est exécuté en temps réel (moyenne de 13,6 ms par appel) sur un CPU standard, coordonnant avec succès les robots de manière à horizon glissant pour atteindre l'objectif de garde de cible.
• Simulation (Fusion de convoi) : Un scénario de fusion à quatre véhicules a été testé sous quatre structures de hiérarchie différentes : Nash pur, deux hiérarchies mixtes et une chaîne Stackelberg pure.
  • Le solveur a démontré que le changement de structure hiérarchique conduit à des comportements distincts et interprétables (par exemple, un véhicule leader accélérant pour maintenir sa position par rapport à céder).
  • Tous les équilibres résultants ont assuré des interactions sûres.
  • Les résultats empiriques ont confirmé la décroissance monotone de la fonction de mérite et la convergence exponentielle locale près de l'équilibre, validant le théorème 1.

Importance et affirmations

L'article prétend combler un vide critique dans la planification multi-robots en permettant la résolution efficace de jeux à hiérarchie mixte avec dynamiques non linéaires et objectifs non quadratiques, qui étaient auparavant limités à des contextes linéaires/quadratiques ou à des structures simples.

• Faisabilité en temps réel : L'approximation quasi-stratégique supprime avec succès le goulot d'étranglement computationnel des dérivées d'ordre élevé, permettant une convergence en temps réel pour des structures d'information complexes.
• Généralité : Le cadre unifie les jeux de Nash et de Stackelberg comme cas particuliers et gère des topologies de forêt arbitraires.
• Impact pratique : La méthode est démontrée comme viable pour un déploiement réel, comme en témoigne l'expérience matérielle où les robots ont exécuté avec succès des plans générés par le solveur dans un environnement dynamique.

Les auteurs concluent que, bien que l'hypothèse de structure de forêt (Hypothèse 2) limite actuellement la portée aux arbres à leader unique, l'approche quasi-stratégique proposée fournit une base robuste pour résoudre des jeux à information complexe et asymétrique en robotique. Les travaux futurs visent à assouplir cette hypothèse pour permettre des structures à plusieurs leaders et à intégrer des contraintes d'inégalité.