Dynamic Multi-Agent Task Allocation with Spatial and Temporal Constraints

Realistic multi-agent team applications often feature dynamic environments with soft deadlines that penalize late execution of tasks. This puts a premium on quickly allocating tasks to agents, but finding the optimal allocation is NP-hard because tasks must be executed sequentially by agents. We propose a novel task allocation algorithm that finds allocations that are fair (envy-free), balancing the load and sharing important tasks between agents, and efficient (Pareto optimal) by using a Fisher market based on a simplified problem model. Such allocations can be easily sequenced to yield high quality solutions, as shown empirically on problems inspired by real police logs.