Decentralized task allocation using magnet: An empirical evaluation in the logistics domain

This paper presents a decentralized task allocation method that can handle allocation of tasks with time and precedence constraints in a multi-agent setting where not all information needed for a centralized approach is shared. In our MAGNET-based approach agents distribute tasks via first-price reverse combinatorial auctions, where the auctioneer is whatever agent has tasks to be allocated. The choice of MAGNET is based on its uniqueness to handle auctions for allocation of tasks which include time windows and precedence constraints. Empirical evaluations based on real data obtained from a logistics company show that the system performs well. The costs of the allocations obtained by our approach are on average within 5% from the optimal allocation. The computation time is linear in the number of tasks, while computing the optimal allocation is an NP-hard problem.