Provably Stable Multi-Agent Routing with Bounded-Delay Adversaries in the Decision Loop

-- 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. T o 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. In this paper we focus on a routing setting where a fleet of agents must pick up and deliver stochastically appearing requests. This stochastic setup is common in mobility-on-demand [1], [2], [3] and warehouse logistics [4], [5], where the location and quantity of future requests are unknown in advance. We assume that each agent handles one request at a time. In our setup, a subset of agents in the fleet may act adversarially by deviating from the prescribed plan set by the centralized control system, resulting in longer than expected service times for their assigned requests. This service delay model is inspired by operations research studies [6], particularly in transportation and delivery systems [7], [8], where drivers, after accepting a request, may pause for personal breaks or take longer routes to increase earnings when compensated per mile. We assume that if the agents take too long to service a request, then the system will remove them, hence agents can only incur a bounded delay. Hereafter we refer to this as the bounded-delay model for adversaries. Our objective in this paper is then to characterize conditions on the fleet size and the proportion of adversarial agents in the system for which a routing policy is provably stable in the presence of bounded delay adversarial agents, where a stable routing policy is one that guarantees that the number of outstanding requests is uniformly bounded over time.