Auction-based task allocation for online pickup and delivery problems with time constraints and uncertainty

Abstract

Auctions have established themselves as highly efficient mechanisms for the online allocation of time-constrained pickup and delivery tasks, which is an important problem in the domain of distributed autonomous systems. Current methods leverage simple temporal networks (STNs) to allow agents to efficiently process temporal constraints in the bidding phase of the auction. However, they suffer from two major weaknesses which limit their applicability in real-world systems. Firstly, they are relatively ineffective when tasks have non-deterministic durations, as the STN representation enforces a binary notion of plan controllability which is highly restrictive. We remedy this by introducing the probabilistic temporal sequential single item auction (pTeSSI), a novel polynomial-time auction-based task allocation mechanism in which plans are represented as simple temporal networks with uncertainty (STNUs). Using a recently proposed non-binary characterization of controllability in STNUs, agents efficiently determine the risk of unsuccessful dispatch of their temporal plans and incorporate this in their bids. We evaluate our auction mechanism in an online simulation of an on-demand UAV delivery system and demonstrate that it is more effective and efficient than the current state of the art method. In addition, we propose a dynamic re-auctioning routine to address the second main weakness of sequential auctions when applied to online problems, namely that they do not revisit existing partial allocations over time. We demonstrate that dynamic re-auctioning increases the quality of the allocation and improves system performance, but also increases the auction duration. We mitigate this downside by bundling tasks based on their spatio-temporal synergy and auctioning bundles, rather than single tasks, at once.