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

Resumen Técnico: Estabilidad de la Política para Medir el Desempeño Operativo en la Asignación de Tareas con Ventanas de Tiempo bajo Influencia Adversaria Interna

Planteamiento del Problema
El artículo aborda la vulnerabilidad de los sistemas autónomos de recogida y entrega ante agentes adversarios internos. En estos sistemas, un programador centralizado empareja agentes disponibles con solicitudes de servicio. Sin embargo, los agentes comprometidos o estratégicos dentro de la flota pueden falsear sus ubicaciones reportadas para capturar asignaciones de tareas e intencionalmente dejar dichas solicitudes sin atender. Este comportamiento interrumpe al programador, causando retrasos, cancelaciones de solicitudes y una utilización ineficiente de los recursos.

Un desafío central identificado es la definición de "estabilidad de la política" en tales entornos adversarios. Las definiciones de estabilidad tradicionales dependen de:

1. Cargas de trabajo de la teoría de colas: Estas requieren analizar la ejecución de rutas específicas de cada agente, lo cual es inviable cuando los agentes se desvían arbitrariamente o no prestan el servicio a las solicitudes.
2. Costos de Aprendizaje por Refuerzo (RL) con descuento: Estos dependen de un factor de descuento que puede restar importancia a la degradación en horizontes de largo plazo y enmascarar los efectos adversarios acumulativos.
3. Métricas basadas únicamente en el backlog (acumulado): Estas no logran distinguir entre las solicitudes que eventualmente se atienden tras un retraso excesivo y aquellas que nunca se atienden dentro de una ventana de tiempo operativamente aceptable.

Los autores argumentan que los criterios existentes son inadecuados para entornos adversarios donde los agentes no cooperativos se desvían arbitrariamente de las rutas asignadas.

Metodología
Los autores proponen un nuevo marco para analizar la estabilidad basado en señales observables a nivel de sistema en lugar de acciones inferidas a nivel de agente.

• Nueva Formulación de Estabilidad: El artículo introduce un criterio de estabilidad de costo promedio definido por dos cantidades observables:

  1. El número de solicitudes pendientes ($O_t$).
  2. El número acumulado de solicitudes canceladas ($C_t$).
     El costo por etapa se define como $g = O_t + C_t$. Una política es estable si el costo promedio esperado sobre un horizonte infinito es finito.

• Análisis Teórico:

  • Supuestos: El análisis asume llegadas de solicitudes acotadas y ventanas de tiempo de solicitud finitas (las solicitudes expiran si no se atienden dentro de una duración específica).
  • Teorema Clave: Bajo estos supuestos, el número de solicitudes pendientes está uniformemente acotado en el tiempo (Observación 1). En consecuencia, el artículo demuestra (Teorema 1) que la estabilidad bajo el criterio de costo promedio propuesto es equivalente a mantener el número esperado de solicitudes canceladas acumuladas uniformemente acotado en el tiempo.
  • Estabilidad Degenerada: Los autores caracterizan un régimen patológico llamado "estabilidad degenerada". Sin ventanas de tiempo finitas, un sistema podría satisfacer los criterios clásicos de estabilidad basados en el backlog mientras mantiene un backlog de solicitudes retrasadas grande y operativamente inaceptable. Las ventanas de tiempo finitas convierten el exceso de espera en cancelaciones observables, eliminando así este régimen degenerado.

• Modelos Adversarios y Políticas de Asignación:

  • Conocimiento Adversario: Se definen tres modelos basados en la disponibilidad de información: Solo-Solicitud (información limitada), Información de Equipo (coordinación entre adversarios) y Omnipotente (conciencia total del sistema y conocimiento del algoritmo del programador).
  • Políticas de Asignación: Se estudian tres políticas: Greedy (vecino más cercano local), Asignación Instantánea (IA) (emparejamiento óptimo global con compromiso) e Asignación Instantánea con Reasignación (IA-RA) (emparejamiento global que permite la reasignación antes de la recogida).
  • Asignación Consciente de la Factibilidad: Los autores introducen mecanismos de asignación que restringen los emparejamientos a pares agente-solicitud capaces de cumplir con las restricciones de la ventana de tiempo antes de su expiración.

Contribuciones Clave

1. Estabilidad de Costo Promedio Observable: Una formulación de estabilidad basada en señales a nivel de sistema (solicitudes pendientes y cancelaciones) que no requiere reconstruir la ejecución de la ruta a nivel de agente, lo que la hace aplicable tanto a entornos cooperativos como adversarios.
2. Teorema de Equivalencia: Una prueba que muestra que, bajo llegadas acotadas y ventanas de tiempo finitas, la estabilidad es equivalente a acotar el número esperado de solicitudes canceladas acumuladas en el tiempo.
3. Identificación de la Estabilidad Degenerada: Una caracterización de un régimen donde los criterios basados en el backlog falsamente certifican la estabilidad a pesar de un mal servicio, lo que motiva la necesidad de ventanas de tiempo finitas y penalizaciones por cancelación.
4. Marco Adversario: Desarrollo de procedimientos de asignación conscientes de la factibilidad y modelos de conocimiento adversario que capturan distintos niveles de conciencia estratégica y coordinación.
5. Evaluación Empírica: Un estudio de caso utilizando datos reales de movilidad de taxis de San Francisco para evaluar el marco propuesto.

Resultados
El estudio empírico, realizado en una red vial simulada de San Francisco con datos reales de demanda, arrojó los siguientes hallendazgos:

• Calibración de la Flota: Se verificó que los tamaños de flota cooperativa derivados de las líneas base existentes de la teoría de colas producen un comportamiento estable bajo ventanas de tiempo finitas.
• Validación de la Estabilidad Degenerada: En configuraciones sin expiración de solicitudes, el número de solicitudes pendientes se estancó, lo que llevó a que las métricas clásicas de backlog clasificaran el sistema como estable a pesar de los retrasos significativos. Esto confirmó la existencia de la estabilidad degenerada.
• Impacto Adversario: Bajo ventanas de tiempo finitas, la métrica de costo promedio propuesta identificó correctamente la inestabilidad mediante el crecimiento sostenido del costo de la política impulsado por las cancelaciones de solicitudes.
  • La inestabilidad aumentó con la proporción de agentes adversarios.
  • Los adversarios Omnipotentes causaron la degradación más severa, seguidos por los modelos de Información de Equipo y Solo-Solicitud.
  • Se encontró que la política IA-RA es más vulnerable que IA o Greedy porque los mecanismos de reasignación permiten a los adversarios redirigir repetidamente a los agentes cooperativos, amplificando la interrupción.
• Comparación de Métricas: La métrica propuesta (backlog + cancelaciones) identificó regímenes inestables que una métrica de solo backlog pasó por alto, demostrando que el backlog acotado por sí solo es insuficiente para evaluar la calidad del servicio en sistemas sensibles al tiempo y adversarios.

Significancia
El artículo afirma que su principal significancia radica en proporcionar una definición de estabilidad que está directamente ligada a los fallos de servicio operativo (cancelaciones) en lugar de cargas de trabajo teóricas. Al vincular la estabilidad con la limitación de las solicitudes canceladas, la formulación ofrece una métrica significativa para sistemas de enrutamiento sensibles al tiempo donde los retrasos son inaceptables.

Los autores enfatizan que las ventanas de tiempo de solicitud finitas no son simplemente un detalle de modelado, sino que son esenciales para distinguir entre una operación aceptable y un régimen de "estabilidad degenerada" donde los sistemas parecen estables pero fallan en atender las solicitudes dentro de marcos de tiempo aceptables. Este trabajo cierra la brecha entre el análisis de estabilidad de enrutamiento, la seguridad contra el engaño (spoofing) interno y las restricciones prácticas del servicio con ventanas de tiempo, ofreciendo un marco que permanece robusto incluso cuando los agentes se desvían de los comportamientos prescritos.