TY - GEN
T1 - Decentralized task allocation using magnet
T2 - Proceedings of the ninth international conference
AU - Hoogendoorn, Mark
AU - Gini, Maria L.
AU - Jonker, Catholijn M.
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
KW - Automated auctions
KW - Logistics
KW - Multi-agent contracting
UR - http://www.scopus.com/inward/record.url?scp=36849067396&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=36849067396&partnerID=8YFLogxK
U2 - 10.1145/1282100.1282161
DO - 10.1145/1282100.1282161
M3 - Conference contribution
AN - SCOPUS:36849067396
SN - 1595937005
SN - 9781595937001
T3 - ACM International Conference Proceeding Series
SP - 319
EP - 328
BT - ICEC 2007
Y2 - 19 August 2007 through 22 August 2007
ER -