Heuristics on the data-collecting robot problem with immediate rewards

Zhi Xing, Jae C Oh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We propose the Data-collecting Robot Problem, where robots collect data as they visit nodes in a graph, and algorithms to solve it. There are two variations of the problem: the delayed-reward problem, in which robots must travel back to the base station to deliver the data collected and to receive rewards; and the immediate-reward problem, in which the reward is immediately given to the robots as they visit each node. The delayed-reward problem is discussed in one of the authors’ work. This paper focuses on the immediate-reward problem. The solution structure has a clustering step and a tour-building step. We propose Progressive Gain-aware Clustering that finds good quality solutions with efficient time complexity. Among the six proposed tourbuilding heuristics, Greedy Insertion and Total-Loss algorithms perform best when data rewards are different.

Original languageEnglish (US)
Title of host publicationPrinciles and Practice of Multi-Agent Systems - 19th International Conference, PRIMA 2016, Proceedings
PublisherSpringer Verlag
Pages131-148
Number of pages18
Volume9862
ISBN (Print)9783319448312
DOIs
StatePublished - 2016
Event19th International Conference on Princiles and Practice of Multi-Agent Systems, PRIMA 2016 - Phuket, Thailand
Duration: Aug 22 2016Aug 26 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9862
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other19th International Conference on Princiles and Practice of Multi-Agent Systems, PRIMA 2016
CountryThailand
CityPhuket
Period8/22/168/26/16

    Fingerprint

Keywords

  • Adversary route planning
  • Autonomous systems
  • Multi-robot systems

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Xing, Z., & Oh, J. C. (2016). Heuristics on the data-collecting robot problem with immediate rewards. In Princiles and Practice of Multi-Agent Systems - 19th International Conference, PRIMA 2016, Proceedings (Vol. 9862, pp. 131-148). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9862). Springer Verlag. https://doi.org/10.1007/978-3-319-44832-9_8