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

Technische Samenvatting: Beleidsstabiliteit voor het Meten van Operationele Prestaties bij Taaktoewijzing met Tijdvensters onder Interne Adversariële Invloed

Probleemstelling
Het artikel behandelt de kwetsbaarheid van autonome pick-up-en-delivery-systemen voor interne adversariële agenten. In dergelijke systemen koppelt een centrale scheduler beschikbare agenten aan serviceverzoeken. Echter, gecompromitteerde of strategische agenten binnen het wagenpark kunnen echter hun gerapporteerde locaties vervalsen om taaktoewijzingen te kapen en deze verzoeken vervolgens opzettelijk onbeantwoord te laten. Dit gedrag verstoort de scheduler, wat leidt tot vertragingen, annuleringen van verzoeken en inefficiënt gebruik van middelen.

Een centrale uitdaging die wordt geïdentificeerd, is het definiëren van "beleidsstabiliteit" in dergelijke adversariële omgevingen. Traditionele definities van stabiliteit vertrouwen op:

1. Wachtrijtheoretische werklasten: Deze vereisen het analyseren van agent-specifieke route-uitvoering, wat onhaalbaar is wanneer agenten willekeurig afwijken of verzoeken niet uitvoeren.
2. Discounted Reinforcement Learning (RL) kosten: Deze zijn afhankelijk van een kortingsfactor die langetermijnverslechtering kan onderwaarderen en cumulatieve adversariële effecten kan maskeren.
3. Alleen-backlog metrieken: Deze slagen er niet in om onderscheid te maken tussen verzoeken die uiteindelijk na excessieve vertraging worden afgehandeld en verzoeken die nooit worden afgehandeld binnen een operationeel acceptabel tijdvenster.

De auteurs stellen dat bestaande criteria slecht geschikt zijn voor adversariële settings waar niet-coöperatieve agenten willekeurig afwijken van hun toegewezen routes.

Methodologie
De auteurs stellen een nieuw kader voor met de analyse van stabiliteit gebaseerd op observeerbare systeem-signalen in plaats van geïnfereerde agent-niveau acties.

• Nieuwe Stabiliteitsformulering: Het artikel introduceert een gemiddelde-kosten stabiliteitscriterium gedefinieerd door twee observeerbare grootheden:

  1. Het aantal openstaande verzoeken ($O_t$).
  2. Het cumulatieve aantal geannuleerde verzoeken ($C_t$).
     De fasekost wordt gedefinieerd als $g = O_t + C_t$. Een beleid is stabiel als de verwachte gemiddelde kosten over een oneindige horizon eindig zijn.

• Theoretische Analyse:

  • Aannames: De analyse gaat uit van begrensde aankomsten van verzoeken en eindige verzoek-tijdvensters (verzoeken verlopen als ze niet binnen een specifieke duur worden afgehandeld).
  • Kernstelling: Onder deze aannames is het aantal openstaande verzoeken uniform begrensd over de tijd (Opmerking 1). Bijgevolg bewijzen de auteurs (Theorem 1) dat stabiliteit onder het voorgestelde gemiddelde-kosten criterium equivalent is aan het uniform begrensd houden van het verwachte cumulatieve aantal geannuleerde verzoeken over de tijd.
  • Degeneratieve Stabiliteit: De auteurs karakteriseren een pathologische regime genaamd "degeneratieve stabiliteit". Zonder eindige tijdvensters kan een systeem voldoen aan klassieke backlog-gebaseerde stabiliteitscriteria terwijl het een grote, operationeel onacceptabele backlog van vertraagde verzoeken behoudt. Eindige tijdvensters zetten excessief wachten om in observeerbare annuleringen, waardoor dit degeneratieve regime wordt uitgesloten.

• Adversariële Modellen en Toewijzingsbeleid:

  • Adversariële Kennis: Drie modellen worden gedefinieerd op basis van informatiebeschikbaarheid: Request-Only (beperkte info), Team-Information (coördinatie tussen adversariële agenten) en Omnipotent (volledig systeembewustzijn en kennis van het algoritme van de scheduler).
  • Toewijzingsbeleid: Drie beleidsregels worden bestudeerd: Greedy (lokale dichtstbijzijnde buur), Instantaneous Assignment (IA) (globale optimale matching met commitment) en Instantaneous Assignment with Reassignment (IA-RA) (globale matching die hertoewijzing toestaat vóór de pick-up).
  • Haalbaarheidsbewuste Allocatie: De auteurs introduceren toewijzingsmechanismen die matches beperken tot agent-verzoek paren die in staat zijn om aan de tijdvenster-beperkingen te voldoen voordat de expiratie optreedt.

Belangrijkste Bijdragen

1. Observeerbare Gemiddelde-Kosten Stabiliteit: Een stabiliteitsformulering gebaseerd op systeem-signalen (openstaande en geannuleerde verzoeken) die geen reconstructie van agent-niveau route-uitvoering vereist, wat het toepasbaar maakt voor zowel coöperatieve als adversariële settings.
2. Equivalentiestelling: Een bewijs dat onder begrensde aankomsten en eindige tijdvensters, stabiliteit equivalent is aan het begrenzen van het verwachte cumulatieve aantal geannuleerde verzoeken.
3. Identificatie van Degeneratieve Stabiliteit: Een karakterisering van een regime waar backlog-gebaseerde criteria ten onrechte stabiliteit certificeren ondanks een slechte servicekwaliteit, wat de noodzaak van eindige tijdvensters en annuleringen-strafpunten motiveert.
4. Adversarieel Kader: Ontwikkeling van haalbaarheidsbewuste toewijzingsprocedures en adversariële kennismodellen die variërende niveaus van strategisch bewustzijn en coördinatie vastleggen.
5. Empirische Evaluatie: Een casestudy met reële San Francisco mobility-on-demand taxi data om het voorgestelde kader te evalueren.

Resultaten
De empirische studie, uitgevoerd op een gesimuleerd San Francisco wegennetwerk met echte vraagdata, leverde de volgende bevindingen op:

• Vlootkalibratie: De coöperatieve vlootgroottes afgeleid van bestaande wachtrijtheoretische baselines werden geverifieerd als zij een stabiel gedrag produceren onder eindige tijdvensters.
• Validatie van Degeneratieve Stabiliteit: In settings zonder verzoek-expiratie bleef het aantal openstaande verzoeken stagneren, wat leidde tot het classificeren van het systeem als stabiel door klassieke backlog-metrieken, ondanks aanzienlijke vertragingen. Dit bevestigde het bestaan van degeneratieve stabiliteit.
• Adversariële Impact: Onder eindige tijdvensters identificeerde de voorgestelde gemiddelde-kosten metriek instabiliteit correct door een aanhoudende groei in beleidskosten gedreven door verzoek-annuleringen.
  • Instabiliteit nam toe met de proportie adversariële agenten.
  • Omnipotent adversariële agenten veroorzaakten de meest ernstige degradatie, gevolgd door de Team-Information en Request-Only modellen.
  • Het IA-RA beleid bleek kwetsbaarder dan IA of Greedy, omdat hertoewijzingsmechanismen het mogelijk maken voor adversariële agenten om coöperatieve agenten herhaaldelijk om te leiden, wat de verstoring versterkt.
• Metriek Vergelijking: De voorgestelde metriek (backlog + annuleringen) identificeerde onstabiele regimes die een alleen-backlog metriek miste, wat aantoont dat een begrensde backlog alleen onvoldoende is voor het beoordelen van de servicekwaliteit in tijdgevoelige adversariële systemen.

Betekenis
Het artikel claimt dat de primaire betekenis ligt in het bieden van een stabiliteitsdefinitie die direct verbonden is aan operationele service-fouten (annuleringen) in plaats van theoretische werklasten. Door stabiliteit te koppelen aan het begrenzen van geannuleerde verzoeken, biedt de formulering een betekenisvolle metriek voor tijdgevoelige routing-systemen waar vertragingen onacceptabel zijn.

De auteurs benadrukken dat eindige verzoek-tijdvensters niet louter een modelleringsdetail zijn, maar essentieel zijn om onderscheid te maken tussen acceptabele operatie en een regime van "degeneratieve stabiliteit" waarbij systemen stabiel lijken maar verzoeken niet binnen acceptabele tijdframes bedienen. Dit werk overbrugt de kloof tussen routing-stabiliteitsanalyse, beveiliging tegen interne spoofing, en de praktische beperkingen van tijdvenster-gestuurde service, en biedt een kader dat robuust blijft zelfs wanneer agenten afwijken van voorgeschreven gedragingen.