研究对抗性车辆干扰下的多车调度稳定性，给出舰队规模与坏车比例的稳定阈值。
Provably Stable Multi-Agent Routing with Bounded-Delay Adversaries in the Decision Loop
- 通过理论分析确定坏车占比上限，超过则原有调度策略必然失效
- 推导出在给定坏车比例下维持系统稳定的最小车队规模
- 基于旧金山出租车数据验证，适用于高干扰场景的自动驾驶接驾系统
本文研究多智能体路径规划场景中，敌对智能体参与任务分配与决策循环，通过施加有界延迟降低车队性能的问题。重点刻画车队规模与敌对智能体比例的条件，使调度策略保持稳定——即未完成请求数量随时间均匀有界。首先建立敌对智能体占比的阈值，超过该值时，原本对合作车队稳定的调度策略将被证明不稳定。随后推导出在最大敌对比例下恢复系统稳定的车队规模充分条件。最后在真实旧金山出租车数据的自动驾驶接驾案例中实证验证了理论结果。
原文摘要 · Abstract (English)
In this work, we are interested in studying multi-agent routing settings, where adversarial agents are part of the assignment and decision loop, degrading the performance of the fleet by incurring bounded delays while servicing pickup-and-delivery requests. Specifically, we are interested in characterizing conditions on the fleet size and the proportion of adversarial agents for which a routing policy remains stable, where stability for a routing policy is achieved if the number of outstanding requests is uniformly bounded over time. To obtain this characterization, we first establish a threshold on the proportion of adversarial agents above which previously stable routing policies for fully cooperative fleets are provably unstable. We then derive a sufficient condition on the fleet size to recover stability given a maximum proportion of adversarial agents. We empirically validate our theoretical results on a case study on autonomous taxi routing, where we consider transportation requests from real San Francisco taxicab data.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。