Dynamic Multi-Agent Task Allocation with Spatial and Temporal Constraints

Authors

  • Sofia Amador Ben-Gurion University of the Negev
  • Steven Okamoto Ben-Gurion University of the Negev
  • Roie Zivan Ben-Gurion University of the Negev

DOI:

https://doi.org/10.1609/aaai.v28i1.8889

Keywords:

Task Allocation, Market Equilibrium

Abstract

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 due to temporal and spatial constraints that require tasks to be executed sequentially by agents. We propose FMC_TA, a novel task allocation algorithm that allows tasks to be easily sequenced to yield high-quality solutions. FMC_TA first finds allocations that are fair (envy-free), balancing the load and sharing important tasks between agents, and efficient (Pareto optimal) in a simplified version of the problem. It computes such allocations in polynomial or pseudo-polynomial time (centrally or distributedly, respectively) using a Fisher market with agents as buyers and tasks as goods. It then heuristically schedules the allocations, taking into account inter-agent constraints on shared tasks. We empirically compare our algorithm to state-of-the-art incomplete methods, both centralized and distributed, on law enforcement problems inspired by real police logs. The results show a clear advantage for FMC_TA both in total utility and in other measures commonly used by law enforcement authorities.

Downloads

Published

2014-06-21

How to Cite

Amador, S., Okamoto, S., & Zivan, R. (2014). Dynamic Multi-Agent Task Allocation with Spatial and Temporal Constraints. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.8889

Issue

Section

AAAI Technical Track: Multiagent Systems