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

Resumo Técnico: Estabilidade de Política para Medição de Desempenho Operacional em Atribuição de Tarefas com Janelas de Tempo sob Influência Adversária Interna

Declaração do Problema
O artigo aborda a vulnerabilidade de sistemas autônomos de coleta e entrega (pickup-and-delivery) a agentes adversários internos. Nesses sistemas, um escalonador centralizado combina agentes disponíveis a solicitações de serviço. No entanto, agentes comprometidos ou estratégicos dentro da frota podem falsificar suas localizações relatadas para capturar atribuições de tarefas e, intencionalmente, deixar essas solicitações sem atendimento. Esse comportamento interrompe o escalonador, causando atrasos, cancelamentos de solicitações e utilização ineficiente de recursos.

Um desafio central identificado é a definição de "estabilidade de política" em tais ambientes adversários. As definições de estabilidade tradicionais baseiam-se em:

1. Cargas de trabalho de teoria de filas: Estas exigem a análise da execução de rotas específicas de cada agente, o que é inviável quando os agentes se desviam arbitrariamente ou falham em atender às solicitações.
2. Custos de Aprendizado por Reforço (RL) com desconto: Estes dependem de um fator de desconto que pode subestimar a degradação de longo horizonte e mascarar efeitos adversários cumulativos.
3. Métricas baseadas apenas em backlog (pendências): Estas não conseguem distinguir entre solicitações que são eventualmente atendidas após um atraso excessivo e aquelas que nunca são atendidas dentro de uma janela de tempo operacionalmente aceitável.

Os autores argumentam que os critérios existentes são inadequados para cenários adversários onde agentes não cooperativos se desviam arbitrariamente das rotas atribuídas.

Metodologia
Os autores propõem um novo arcabouço para analisar a estabilidade baseado em sinais observáveis do sistema, em vez de ações inferidas do nível do agente.

• Nova Formulação de Estabilidade: O artigo introduz um critério de estabilidade de custo médio definido por duas quantidades observáveis:

  1. O número de solicitações pendentes ($O_t$).
  2. O número cumulativo de solicitações canceladas ($C_t$).
     O custo por estágio é definido como $g = O_t + C_t$. Uma política é estável se o custo médio esperado ao longo de um horizonte infinito for finito.

• Análise Teórica:

  • Premissas: A análise assume chegadas de solicitações limitadas e janelas de tempo de solicitação finitas (as solicitações expiram se não forem atendidas dentro de uma duração específica).
  • Teorema Principal: Sob essas premissas, o número de solicitações pendentes é uniformemente limitado ao longo do tempo (Observação 1). Consequentemente, o artigo prova (Teorema 1) que a estabilidade sob o critério de custo médio proposto é equivalente a manter o número cumulativo esperado de solicitações canceladas uniformemente limitado ao longo do tempo.
  • Estabilidade Degenerada: Os autores caracterizam um regime patológico chamado "estabilidade degenerada". Sem janelas de tempo finitas, um sistema pode satisfazer critérios clássicos de estabilidade baseados em backlog enquanto mantém um backlog grande e operacionalmente inaceitável de solicitações atrasadas. Janelas de tempo finitas convertem o tempo de espera excessivo em cancelamentos observáveis, eliminando assim esse regime degenerado.

• Modelos Adversários e Políticas de Atribuição:

  • Conhecimento Adversário: Três modelos são definidos com base na disponibilidade de informação: Somente Solicitação (informação limitada), Informação de Equipe (coordenação entre adversários) e Onipotente (consciência total do sistema e conhecimento do algoritmo do escalonador).
  • Políticas de Atribuição: Três políticas são estudadas: Gananciosa (vizinho mais próximo local), Atribuição Instantânea (IA) (correspondência ótima global com compromisso) e Atribuição Instantânea com Reatribuição (IA-RA) (correspondência global permitindo reatribuição antes da coleta).
  • Alocação Consciente de Viabilidade: Os autores introduzem mecanismos de atribuição que restringem as correspondências a pares agente-solicitação capazes de cumprir as restrições de janela de tempo antes da expiração.

Principais Contribuições

1. Estabilidade de Custo Médio Observável: Uma formulação de estabilidade baseada em sinais do sistema (pendências e cancelamentos) que não requer a reconstrução da execução de rotas do nível do agente, tornando-a aplicável tanto a ambientes cooperativos quanto adversários.
2. Teorema de Equivalência: Uma prova mostrando que, sob chegadas limitadas e janelas de tempo finitas, a estabilidade é equivalente a limitar o número esperado de solicitações canceladas ao longo do tempo.
3. Identificação de Estabilidade Degenerada: Uma caracterização de um regime onde critérios baseados em backlog certificam falsamente a estabilidade, apesar da má qualidade de serviço, motivando a necessidade de janelas de tempo finitas e penalidades de cancelamento.
4. Arcabouço Adversário: Desenvolvimento de procedimentos de atribuição conscientes de viabilidade e modelos de conhecimento adversário que capturam diferentes níveis de consciência estratégica e coordenação.
5. Avaliação Empírica: Um estudo de caso utilizando dados reais de mobilidade sob demanda de táxis de San Francisco para avaliar o arcabouço proposto.

Resultados
O estudo empírico, conduzido em uma rede rodoviária simulada de San Francisco com dados reais de demanda, apresentou as seguintes conclusões:

• Calibração da Frota: Os tamanhos de frota cooperativa derivados de bases de referência de teoria de filas existentes foram verificados como produtores de comportamento estável sob janelas de tempo finitas.
• Validação da Estabilidade Degenerada: Em configurações sem expiração de solicitação, o número de solicitações pendentes estabilizou, levando métricas clássicas de backlog a classificar o sistema como estável, apesar dos atrasos significativos. Isso confirmou a existência de estabilidade degenerada.
• Impacto Adversário: Sob janelas de tempo finitas, a métrica de custo médio proposta identificou corretamente a instabilidade através do crescimento sustentado do custo da política impulsionado por cancelamentos de solicitações.
  • A instabilidade aumentou com a proporção de agentes adversários.
  • Adversários Onipotentes causaram a degradação mais severa, seguidos pelos modelos de Informação de Equipe e Somente Solicitação.
  • A política IA-RA mostrou-se mais vulnerável que a IA ou a Gananciosa, pois os mecanismos de reatribuição permitem que adversários redirecionem repetidamente agentes cooperativos, amplificando a interrupção.
• Comparação de Métricas: A métrica proposta (pendências + cancelamentos) identificou regimes instáveis que uma métrica de apenas backlog não detectou, demonstrando que o backlog limitado sozinho é insuficiente para avaliar a qualidade do serviço em sistemas sensíveis ao tempo e adversários.

Significância
O artigo afirma que sua principal significância reside em fornecer uma definição de estabilidade que está diretamente ligada a falhas operacionais de serviço (cancelamentos) em vez de cargas de trabalho teóricas. Ao vincular a estabilidade à limitação de solicitações canceladas, a formulação oferece uma métrica significativa para sistemas de roteamento sensíveis ao tempo onde atrasos são inaceitáveis.

Os autores enfatizam que as janelas de tempo de solicitação finitas não são meramente um detalhe de modelagem, mas essenciais para distinguir entre uma operação aceitável e um regime de "estabilidade degenerada", onde os sistemas parecem estáveis, mas falham em atender às solicitações dentro de prazos aceitáveis. Este trabalho preenche a lacuna entre a análise de estabilidade de roteamento, segurança contra falsificação (spoofing) interna e as restrições práticas de serviço com janelas de tempo, oferecendo um arcabouço que permanece robusto mesmo quando os agentes se desviam dos comportamentos prescritos.