Policy Stability for Measuring Operational Performance in Task Assignment with Time-Windows Under Internal Adversarial Influence

Résumé technique : Stabilité des politiques pour la mesure de la performance opérationnelle dans l'assignation de tâches avec fenêtres temporelles sous influence adversaire interne

Énoncé du problème
L'article traite de la vulnérabilité des systèmes autonomes de ramassage et de livraison face à des agents adversaires internes. Dans ces systèmes, un ordonnanceur centralisé fait correspondre les agents disponibles aux demandes de service. Cependant, des agents compromis ou stratégiques au sein de la flotte peuvent usurper leurs positions signalées pour capturer des assignations de tâches et intentionnellement laisser ces demandes non servies. Ce comportement perturbe l'ordonnanceur, provoquant des retards, des annulations de demandes et une utilisation inefficace des ressources.

Un défi central identifié est la définition de la « stabilité de la politique » dans de tels environnements adverses. Les définitions de stabilité traditionnelles reposent sur :

1. Les charges de travail de la théorie des files d'attente : celles-ci nécessitent l'analyse de l'exécution des itinéraires spécifiques aux agents, ce qui est irréalisable lorsque les agents dévient arbitrairement ou ne parviennent pas à servir les demandes.
2. Les coûts de l'apprentissage par renforcement (RL) avec escompte : ceux-ci dépendent d'un facteur d'escompte qui peut sous-estimer la dégradation à long terme et masquer les effets cumulés de l'adversité.
3. Les métriques basées uniquement sur le carnet de commandes (backlog) : elles ne parviennent pas à distinguer les demandes qui sont finalement servies après un délai excessif de celles qui ne sont jamais servies dans une fenêtre de temps opérationnellement acceptable.

Les auteurs soutiennent que les critères existants sont mal adaptés aux contextes adverses où des agents non coopératifs dévient arbitrairement des itinéraires assignés.

Méthodologie
Les auteurs proposent un nouveau cadre d'analyse de la stabilité basé sur des signaux observables au niveau du système plutôt que sur des actions inférées au niveau de l'agent.

• Nouvelle formulation de la stabilité : L'article introduit un critère de stabilité de coût moyen défini par deux quantités observables :

  1. Le nombre de demandes en attente ($O_t$).
  2. Le nombre cumulé de demandes annulées ($C_t$).
     Le coût par étape est défini par $g = O_t + C_t$. Une politique est stable si l'espérance du coût moyen sur un horizon infini est finie.

• Analyse théorique :

  • Hypothèses : L'analyse suppose des arrivées de demandes bornées et des fenêtres de temps de demande finies (les demandes expirent si elles ne sont pas servies dans une durée spécifique).
  • Théorème clé : Sous ces hypothèses, le nombre de demandes en attente est uniformément borné dans le temps (Remarque 1). Par conséquent, l'article prouve (Théorème 1) que la stabilité sous le critère de coût moyen proposé est équivalente au maintien d'un nombre cumulé attendu de demandes annulées uniformément borné dans le temps.
  • Stabilité dégénérée : Les auteurs caractérisent un régime pathologique appelé « stabilité dégénérée ». Sans fenêtres de temps finies, un système pourrait satisfaire les critères classiques de stabilité basés sur le carnet de commandes tout en maintenant un carnet de commandes important et opérationnellement inacceptable. Les fenêtres de temps finies convertissent l'attente excessive en annulations observables, écartant ainsi ce régime dégénéré.

• Modèles adverses et politiques d'assignation :

  • Connaissance de l'adversaire : Trois modèles sont définis selon la disponibilité de l'information : Request-Only (information limitée), Team-Information (coordination entre adversaires) et Omnipotent (pleine connaissance du système et de l'algorithme de l'ordonnanceur).
  • Politiques d'assignation : Trois politiques sont étudiées : Greedy (plus proche voisin local), Instantaneous Assignment (IA) (appariement optimal global avec engagement) et Instantaneous Assignment with Reassignment (IA-RA) (appariement global permettant la réassignation avant le ramassage).
  • Allocation sensible à la faisabilité : Les auteurs introduisent des mécanismes d'assignation qui restreignent les correspondances aux paires agent-demande capables de respecter les contraintes de la fenêtre temporelle avant expiration.

Contributions clés

1. Stabilité de coût moyen observable : Une formulation de la stabilité basée sur des signaux au niveau du système (demandes en attente et annulations) qui ne nécessite pas la reconstruction de l'exécution des itinéraires au niveau de l'agent, la rendant applicable tant aux contextes coopératifs qu'adverses.
2. Théorème d'équivalence : Une preuve montrant que, sous des arrivées bornées et des fenêtres de temps finies, la stabilité est équivalente au maintien d'un nombre cumulé attendu de demandes annulées uniformément borné.
3. Identification de la stabilité dégénérée : Une caractérisation d'un régime où les critères basés sur le carnet de commandes certifient faussement la stabilité malgré une faible qualité de service, motivant la nécessité des fenêtres de temps finies et des pénalités d'annulation.
4. Cadre de l'adversaire : Développement de procédures d'assignation sensibles à la faisabilité et de modèles de connaissance adversaire capturant différents niveaux de conscience stratégique et de coordination.
5. Évaluation empirique : Une étude de cas utilisant des données réelles de mobilité à la demande de taxis de San Francisco pour évaluer le cadre proposé.

Résultats
L'étude empirique, menée sur un réseau routier simulé de San Francisco avec des données de demande réelles, a produit les conclusions suivantes :

• Calibrage de la flotte : Les tailles de flotte coopératives dérivées des bases existantes de la théorie des files d'attente ont été vérifiées comme produisant un comportement stable sous des fenêtres de temps finies.
• Validation de la stabilité dégénérée : Dans les configurations sans expiration de demande, le nombre de demandes en attente a plafonné, conduisant les métriques classiques de carnet de commandes à classer le système comme stable malgré des délais importants. Cela a confirmé l'existence de la stabilité dégénérée.
• Impact de l'adversaire : Sous des fenêtres de temps finies, la métrique de coût moyen proposée a correctement identifié l'instabilité par une croissance soutenue du coût de la politique, pilotée par les annulations de demandes.
  • L'instabilité augmentait avec la proportion d'agents adverses.
  • Les adversaires Omnipotent ont causé la dégradation la plus sévère, suivis par les modèles Team-Information et Request-Only.
  • La politique IA-RA s'est révélée plus vulnérable que IA ou Greedy, car les mécanismes de réassignation permettent aux adversaires de rediriger de manière répétée les agents coopératifs, amplifiant la perturbation.
• Comparaison des métriques : La métrique proposée (carnet de commandes + annulations) a identifié des régimes instables que la métrique basée uniquement sur le carnet de commandes a manqués, démontant que le carnet de commandes borné seul est insuffisant pour évaluer la qualité de service dans les systèmes sensibles au temps et sujets à l'adversité.

Signification
L'article affirme que sa principale signification réside dans l'apport d'une définition de la stabilité directement liée aux échecs de service opérationnels (annulations) plutôt qu'aux charges de travail théoriques. En liant la stabilité au caractère borné des demandes annulées, la formulation offre une métrique significative pour les systèmes de routage sensibles au temps où les retards sont inacceptables.

Les auteurs soulignent que les fenêtres de temps de demande finies ne sont pas simplement un détail de modélisation, mais sont essentielles pour distinguer un fonctionnement acceptable d'un régime de « stabilité dégénérée » où les systèmes semblent stables mais échouent à servir les demandes dans des délais acceptables. Ce travail comble le fossé entre l'analyse de la stabilité du routage, la sécurité contre l'usurpation interne et les contraintes pratiques du service avec fenêtres temporelles, offrant un cadre qui reste robuste même lorsque les agents dévient des comportements prescrits.