Effective Approximations for Planning with Spatially Distributed Tasks
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Planning in cooperative multiagent systems can be neatly formalized using Multi-Agent MDPs, but solving these models is computationally costly. This paper introduces a sub-class of problems called spatial task allocation problems (SPATAPS) that model problems in which a team of agents has to service a dynamically changing set of tasks that is spatially distributed in the environment. We propose to tackle SPATAPS using online, distributed planning by combining subjective agent approximations with restriction of attention to current tasks in the world. An empirical evaluation shows that the combination of both strategies allows to scale to very large problems, while providing near-optimal solutions.