Dynamic Adversarial Resource Allocation: the dDAB Game

1. Problématique

L'article introduit le jeu dDAB (Dynamic Defender-Attacker Blotto), une extension dynamique du jeu classique de Colonel Blotto appliqué à la répartition de ressources sur des graphes.

• Contexte : Le problème concerne l'allocation de ressources (robots, capteurs) dans un environnement dynamique représenté par un graphe orienté $G=(V, E)$. Contrairement aux modèles statiques où l'allocation est instantanée, ici les ressources doivent se déplacer physiquement à travers le graphe (un saut par pas de temps).
• Acteurs :
  • Le Défenseur (Bleu) : Doit maintenir une supériorité numérique sur un ensemble de nœuds clés ($V_{key}$) face à un attaquant.
  • L'Attaquant (Rouge) : Tente de surclasser le défenseur sur au moins un nœud clé pour gagner.
• Dynamique du jeu : C'est un jeu séquentiel en temps discret. Le défenseur agit d'abord, puis l'attaquant observe et réagit. Les ressources peuvent se déplacer d'au plus un saut par pas de temps.
• Objectif : Déterminer la quantité nécessaire et suffisante de ressources pour le défenseur ($X$) par rapport à l'attaquant ($Y$) pour garantir une défense indéfinie ou sur un horizon fini $T$, ainsi que les stratégies de rétroaction (feedback) optimales.

2. Méthodologie

Les auteurs développent une approche basée sur l'analyse de l'accessibilité (reachability) et la programmation dynamique ensembliste.

A. Ensembles Accessibles et Requiers

• Ensemble Accessible $R(x_t)$ : L'ensemble de tous les états futurs possibles que le défenseur peut atteindre depuis l'état actuel $x_t$ en un pas de temps, compte tenu des contraintes du graphe. Cet ensemble est un polytope.
• Ensemble Requis $P_{req}(y_t)$ : Pour garantir la défense à l'instant $t+1$ contre une allocation $y_t$ de l'attaquant, le défenseur doit pouvoir atteindre un état $x_{t+1}$ tel que $x_{t+1} \ge y_{t+1}$ pour tout $y_{t+1}$ accessible à l'attaquant. Cela définit un seuil minimal de ressources par nœud.

B. Ensembles de Sécurité $k$-étapes (Q-sets)

Pour gérer l'horizon temporel et les stratégies futures, les auteurs définissent récursivement les Q-sets ($Q_k^{(i)}$) :

• $Q_k^{(i)}$ est l'ensemble des allocations du défenseur qui garantissent une défense de $k$ pas de temps, sachant que l'attaquant est concentré sur le nœud $i$ (stratégie "non-division").
• Récurrence : Un état appartient à $Q_k^{(i)}$ s'il est dans l'ensemble requis immédiat $P_{req}(y^{(i)})$ ET si, pour chaque voisin possible $j$ de l'attaquant, l'ensemble accessible du défenseur intersecte l'ensemble de sécurité $Q_{k-1}^{(j)}$.
• Convergence : L'algorithme itère jusqu'à convergence vers des ensembles de sécurité indéfinis ($Q_\infty^{(i)}$), représentant la capacité de défense perpétuelle.

C. Généralisation aux Attaquants Divisés

Une contribution majeure est la démonstration que si le défenseur possède assez de ressources pour contrer un attaquant qui ne divise jamais ses troupes (stratégie "blob"), alors il peut également contrer n'importe quelle stratégie de division.

• Superposition : La stratégie du défenseur est construite comme une superposition de sous-équipes, chacune dédiée à contrer une sous-équipe de l'attaquant.
• Théorème clé : L'attaquant n'a aucun intérêt stratégique à diviser ses ressources. Si une victoire est possible avec division, elle est aussi possible sans division.

D. Algorithme de Calcul

Un algorithme de programmation dynamique (Q-Prop) est proposé pour :

1. Construire les Q-sets en utilisant des graphes inversés pour calculer efficacement les ensembles accessibles inverses.
2. Déterminer le Ratio de Ressources Critique (CRR, $\alpha_T$) : Le rapport minimal $X/Y$ nécessaire pour gagner.
3. Générer des stratégies de rétroaction : À chaque pas de temps, le défenseur choisit une nouvelle allocation dans l'intersection de son ensemble accessible et du Q-set correspondant à la nouvelle position de l'attaquant.

3. Contributions Clés

1. Formulation du jeu dDAB : Extension du Blotto statique à un cadre dynamique avec contraintes de mobilité sur graphe.
2. Caractérisation complète : Identification des conditions nécessaires et suffisantes (via les Q-sets) pour la victoire du défenseur ou de l'attaquant.
3. Preuve de non-bénéfice de la division : Démonstration formelle que la division des ressources de l'attaquant n'augmente pas ses chances de victoire, simplifiant ainsi l'analyse de l'adversaire.
4. Algorithmes de stratégie : Développement d'algorithmes pour calculer le CRR et synthétiser des stratégies de défense optimales et réactives (feedback).
5. Validation expérimentale : Implémentation réussie sur la plateforme robotique Robotarium (Georgia Tech), validant la théorie avec des robots physiques et des ressources discrètes.

4. Résultats Principaux

• Ratio de Ressources Critique (CRR) : Les auteurs montrent que le CRR dépend fortement de la topologie du graphe (degré de sortie, boucles, connexivité).
  • Pour certains graphes (ex: anneau), un seul robot défenseur suffit contre un attaquant.
  • L'ajout d'arêtes peut paradoxalement augmenter ou diminuer le CRR (ex: rendre une arête bidirectionnelle peut augmenter le CRR de 1 à 5 dans un exemple donné).
  • Le CRR peut être un nombre non entier (ex: 3.5) pour des horizons finis, bien qu'il tende souvent vers des entiers pour des défenses indéfinies sur des graphes non orientés.
• Stratégies de Défense : Les stratégies dérivées sont des politiques de rétroaction qui réallouent les ressources en anticipant les mouvements optimaux de l'attaquant.
• Robustesse : Les simulations et expériences montrent que le défenseur peut maintenir la sécurité indéfiniment tant que $X \ge \alpha_\infty Y$, même face à des attaques adaptatives.

5. Signification et Impact

Ce travail est significatif pour plusieurs domaines :

• Sécurité des systèmes multi-agents : Il fournit des garanties formelles pour la protection d'infrastructures critiques (réseaux électriques, surveillance de périmètre) contre des menaces dynamiques et intelligentes.
• Théorie des jeux : Il comble le fossé entre les jeux statiques (Blotto) et les dynamiques de population, en intégrant les contraintes physiques de déplacement.
• Robotique : La validation sur Robotarium prouve la faisabilité de l'application de ces algorithmes complexes sur des systèmes physiques réels avec des contraintes de temps réel.
• Optimisation : L'approche par ensembles (polytopes) et programmation dynamique offre un cadre efficace pour résoudre des problèmes d'allocation de ressources sous contraintes de mobilité et d'incertitude.

En résumé, l'article propose un cadre théorique rigoureux et des outils pratiques pour concevoir des systèmes de défense robotisés capables de résister à des adversaires intelligents dans des environnements dynamiques et contraints.