Heuristics on the data-collecting robot problem with immediate rewards

Zhi Xing, Jae C. Oh

Research output: Chapter in Book/Entry/PoemConference contribution

1 Scopus citations


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
EditorsMatteo Baldoni, Katsutoshi Hirayama, Paolo Torroni, Tran Cao Son, Amit K. Chopra
PublisherSpringer Verlag
Number of pages18
ISBN (Print)9783319448312
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 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other19th International Conference on Princiles and Practice of Multi-Agent Systems, PRIMA 2016


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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Heuristics on the data-collecting robot problem with immediate rewards'. Together they form a unique fingerprint.

Cite this