We propose a model for the allocation of agents to tasks when the tasks have a cost which grows over time. Our model accounts for both the natural growth of tasks and the effort of the agents at containing such growth. The objective is to produce solutions that minimize the growth of tasks (potentially stopping such growth) by efficiently coordinating the operations of the agents. This problem has strong spatial and temporal components, as the agents require time not only to work on the tasks but also to move between tasks and during that time the costs of completing the tasks continue to grow. We propose a novel distributed coordination algorithm, called Lazy max-sum, which works well even when the model of the environment has errors. The algorithm handles homogeneous as well as heterogeneous agents, which can do different amounts of work per time unit and have different travel speeds. We show experimentally that the algorithm outperforms other methods in both a simple simulation and the RoboCup Rescue agent simulation.
Bibliographical noteFunding Information:
Work supported in part by National Science Foundation, United States (NSF-IIP-1439728) and the Graduate School of the University of Minnesota, United States.
Work supported in part by National Science Foundation, United States ( NSF-IIP-1439728 ) and the Graduate School of the University of Minnesota, United States .
© 2018 Elsevier B.V.
Copyright 2018 Elsevier B.V., All rights reserved.
- Decentralized methods
- Task allocation