Lazy max-sum for allocation of tasks with growing costs

James Parker, Alessandro Farinelli, Maria L Gini

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)44-56
Number of pages13
JournalRobotics and Autonomous Systems
Volume110
DOIs
StatePublished - Dec 2018

Bibliographical note

Funding 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.

Funding 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 .

Publisher Copyright:
© 2018 Elsevier B.V.

Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

Keywords

  • Decentralized methods
  • Multi-agent
  • Task allocation

Fingerprint

Dive into the research topics of 'Lazy max-sum for allocation of tasks with growing costs'. Together they form a unique fingerprint.

Cite this