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. (C) 2018 Elsevier B.V. All rights reserved.

Lazy max-sum for allocation of tasks with growing costs

Farinelli, Alessandro;
2018-01-01

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. (C) 2018 Elsevier B.V. All rights reserved.
2018
Multi-agent; Task allocation; Decentralized methods
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/988598
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 4
social impact