Allocation of Time-extended Tasks Via Auctions

We present a method based on auctions for decentralized allocation
of time-extended tasks to multiple agents. We use first-price reverse
combinatorial auctions to allocate tasks to bidders, using MAGNET's
bid clearing algorithms.  The uniqueness of MAGNET is its ability to
handle auctions for tasks that have temporal constraints.
Since combinatorial auctions can be impractical, we present two
extensions, one that enables agents to express preferences for tasks
with specific durations and time windows, the second that extends
single-item auctions to navigation tasks with temporal constraints.
We evaluate the results empirically in the transportation domain
using data from a logistics company and with robots in simulation.
[Work done with John Collins, Mark Hoogendoorn, and Maitreyi Nanjanath]