Decentralised Dynamic Task Allocation: A Practical Game-Theoretic Approach
OA Location
Author(s)
Chapman, A
Micillo, RA
Kota, R
Jennings, N
Type
Conference Paper
Abstract
This paper reports on a novel decentralised technique for planning agent schedules in dynamic task allocation problems. Specifically, we use a Markov game formulation of these problems for tasks with varying hard deadlines and processing requirements. We then introduce a new technique for approximating this game using a series of static potential games, before detailing a decentralised solution method for the approximating games that uses the Distributed Stochastic Algorithm. Finally, we discuss an implementation of our approach to a task allocation problem in the RoboCup Rescue disaster management simulator. Our results show that our technique performs comparably to a centralised task scheduler (within 6% on average), and also, unlike its centralised counterpart, it is robust to restrictions on the agents’ communication and observation range.
Date Issued
2009-05
Date Acceptance
2009-05-01
Citation
2009, pp.915-922
Start Page
915
End Page
922
Identifier
http://eprints.soton.ac.uk/267066/
Source
The Eighth International Conference on Autonomous Agents and Multiagent Systems (AAMAS ’09)
Notes
Event Dates: 10-15 May, 2009 keywords: Multi-agent planning, Game theory
Publication Status
Unpublished