Max-sum for allocation of changing cost tasks

James Parker; Alessandro Farinelli; Maria Gini

doi:10.1007/978-3-319-48036-7_46

Max-sum for allocation of changing cost tasks

James Parker, Alessandro Farinelli, Maria Gini

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

We present a novel decentralized approach to allocate agents to tasks whose costs increase over time. Our model accounts for both the natural growth of the tasks and the effort of the agents at containing such growth. The objective is to minimize the increase in task costs. We show how a distributed coordination algorithm, which is based on max-sum, can be formulated to include costs of tasks that grow over time. Considering growing costs enables our approach to solve a wider range of problems than existing methods. We compare our approach against state-of-the-art methods in both a simple simulation and RoboCup Rescue simulation.

Original language	English (US)
Title of host publication	Intelligent Autonomous Systems 14 - Proceedings of the 14th International Conference IAS-14
Editors	Weidong Chen, Hesheng Wang, Koh Hosoda, Emanuele Menegatti, Masahiro Shimizu
Publisher	Springer Verlag
Pages	629-642
Number of pages	14
ISBN (Print)	9783319480350
DOIs	https://doi.org/10.1007/978-3-319-48036-7_46
State	Published - 2017
Event	14th International Conference on Intelligent Autonomous Systems, IAS 2016 - Shanghai, China Duration: Jul 3 2016 → Jul 7 2016

Publication series

Name	Advances in Intelligent Systems and Computing
Volume	531
ISSN (Print)	2194-5357

Other

Other	14th International Conference on Intelligent Autonomous Systems, IAS 2016
Country/Territory	China
City	Shanghai
Period	7/3/16 → 7/7/16

Bibliographical note

Funding Information:
Work supported in part by NSF-IIP-1439728 and the Graduate School of the University of Minnesota.

Publisher Copyright:
© Springer International Publishing AG 2017.

Keywords

Binary max-sum
Multi-robot systems
Task allocation

Publisher link

10.1007/978-3-319-48036-7_46

Find It

Find It at U of M Libraries

Cite this

Parker, J., Farinelli, A., & Gini, M. (2017). Max-sum for allocation of changing cost tasks. In W. Chen, H. Wang, K. Hosoda, E. Menegatti, & M. Shimizu (Eds.), Intelligent Autonomous Systems 14 - Proceedings of the 14th International Conference IAS-14 (pp. 629-642). (Advances in Intelligent Systems and Computing; Vol. 531). Springer Verlag. https://doi.org/10.1007/978-3-319-48036-7_46

Max-sum for allocation of changing cost tasks. / Parker, James; Farinelli, Alessandro; Gini, Maria.
Intelligent Autonomous Systems 14 - Proceedings of the 14th International Conference IAS-14. ed. / Weidong Chen; Hesheng Wang; Koh Hosoda; Emanuele Menegatti; Masahiro Shimizu. Springer Verlag, 2017. p. 629-642 (Advances in Intelligent Systems and Computing; Vol. 531).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Parker, J, Farinelli, A & Gini, M 2017, Max-sum for allocation of changing cost tasks. in W Chen, H Wang, K Hosoda, E Menegatti & M Shimizu (eds), Intelligent Autonomous Systems 14 - Proceedings of the 14th International Conference IAS-14. Advances in Intelligent Systems and Computing, vol. 531, Springer Verlag, pp. 629-642, 14th International Conference on Intelligent Autonomous Systems, IAS 2016, Shanghai, China, 7/3/16. https://doi.org/10.1007/978-3-319-48036-7_46

Parker, James ; Farinelli, Alessandro ; Gini, Maria. / Max-sum for allocation of changing cost tasks. Intelligent Autonomous Systems 14 - Proceedings of the 14th International Conference IAS-14. editor / Weidong Chen ; Hesheng Wang ; Koh Hosoda ; Emanuele Menegatti ; Masahiro Shimizu. Springer Verlag, 2017. pp. 629-642 (Advances in Intelligent Systems and Computing).

@inproceedings{af196e8dfb7d4d2aafa8319b9fea6fd7,

title = "Max-sum for allocation of changing cost tasks",

abstract = "We present a novel decentralized approach to allocate agents to tasks whose costs increase over time. Our model accounts for both the natural growth of the tasks and the effort of the agents at containing such growth. The objective is to minimize the increase in task costs. We show how a distributed coordination algorithm, which is based on max-sum, can be formulated to include costs of tasks that grow over time. Considering growing costs enables our approach to solve a wider range of problems than existing methods. We compare our approach against state-of-the-art methods in both a simple simulation and RoboCup Rescue simulation.",

keywords = "Binary max-sum, Multi-robot systems, Task allocation",

author = "James Parker and Alessandro Farinelli and Maria Gini",

note = "Funding Information: Work supported in part by NSF-IIP-1439728 and the Graduate School of the University of Minnesota. Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 14th International Conference on Intelligent Autonomous Systems, IAS 2016 ; Conference date: 03-07-2016 Through 07-07-2016",

year = "2017",

doi = "10.1007/978-3-319-48036-7_46",

language = "English (US)",

isbn = "9783319480350",

series = "Advances in Intelligent Systems and Computing",

publisher = "Springer Verlag",

pages = "629--642",

editor = "Weidong Chen and Hesheng Wang and Koh Hosoda and Emanuele Menegatti and Masahiro Shimizu",

booktitle = "Intelligent Autonomous Systems 14 - Proceedings of the 14th International Conference IAS-14",

}

TY - GEN

T1 - Max-sum for allocation of changing cost tasks

AU - Parker, James

AU - Farinelli, Alessandro

AU - Gini, Maria

N1 - Funding Information: Work supported in part by NSF-IIP-1439728 and the Graduate School of the University of Minnesota. Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - We present a novel decentralized approach to allocate agents to tasks whose costs increase over time. Our model accounts for both the natural growth of the tasks and the effort of the agents at containing such growth. The objective is to minimize the increase in task costs. We show how a distributed coordination algorithm, which is based on max-sum, can be formulated to include costs of tasks that grow over time. Considering growing costs enables our approach to solve a wider range of problems than existing methods. We compare our approach against state-of-the-art methods in both a simple simulation and RoboCup Rescue simulation.

AB - We present a novel decentralized approach to allocate agents to tasks whose costs increase over time. Our model accounts for both the natural growth of the tasks and the effort of the agents at containing such growth. The objective is to minimize the increase in task costs. We show how a distributed coordination algorithm, which is based on max-sum, can be formulated to include costs of tasks that grow over time. Considering growing costs enables our approach to solve a wider range of problems than existing methods. We compare our approach against state-of-the-art methods in both a simple simulation and RoboCup Rescue simulation.

KW - Binary max-sum

KW - Multi-robot systems

KW - Task allocation

UR - http://www.scopus.com/inward/record.url?scp=85013074736&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85013074736&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-48036-7_46

DO - 10.1007/978-3-319-48036-7_46

M3 - Conference contribution

AN - SCOPUS:85013074736

SN - 9783319480350

T3 - Advances in Intelligent Systems and Computing

SP - 629

EP - 642

BT - Intelligent Autonomous Systems 14 - Proceedings of the 14th International Conference IAS-14

A2 - Chen, Weidong

A2 - Wang, Hesheng

A2 - Hosoda, Koh

A2 - Menegatti, Emanuele

A2 - Shimizu, Masahiro

PB - Springer Verlag

T2 - 14th International Conference on Intelligent Autonomous Systems, IAS 2016

Y2 - 3 July 2016 through 7 July 2016

ER -

Max-sum for allocation of changing cost tasks

Abstract

Publication series

Other

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this