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 Citation (Scopus)

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

Reward
Robot
Heuristics
Robots
Base stations
Clustering
Greedy Heuristics
Vertex of a graph
Time Complexity
Insertion
Immediately
Graph in graph theory

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

Heuristics on the data-collecting robot problem with immediate rewards. / Xing, Zhi; Oh, Jae C.

Princiles and Practice of Multi-Agent Systems - 19th International Conference, PRIMA 2016, Proceedings. Vol. 9862 Springer Verlag, 2016. p. 131-148 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9862).

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

Xing, Z & Oh, JC 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, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9862, Springer Verlag, pp. 131-148, 19th International Conference on Princiles and Practice of Multi-Agent Systems, PRIMA 2016, Phuket, Thailand, 8/22/16. https://doi.org/10.1007/978-3-319-44832-9_8
Xing Z, Oh JC. 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. Springer Verlag. 2016. p. 131-148. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-44832-9_8
Xing, Zhi ; Oh, Jae C. / Heuristics on the data-collecting robot problem with immediate rewards. Princiles and Practice of Multi-Agent Systems - 19th International Conference, PRIMA 2016, Proceedings. Vol. 9862 Springer Verlag, 2016. pp. 131-148 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{f0839cb1667741c9a336df4261152fce,
title = "Heuristics on the data-collecting robot problem with immediate rewards",
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.",
keywords = "Adversary route planning, Autonomous systems, Multi-robot systems",
author = "Zhi Xing and Oh, {Jae C}",
year = "2016",
doi = "10.1007/978-3-319-44832-9_8",
language = "English (US)",
isbn = "9783319448312",
volume = "9862",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "131--148",
booktitle = "Princiles and Practice of Multi-Agent Systems - 19th International Conference, PRIMA 2016, Proceedings",

}

TY - GEN

T1 - Heuristics on the data-collecting robot problem with immediate rewards

AU - Xing, Zhi

AU - Oh, Jae C

PY - 2016

Y1 - 2016

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

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

KW - Adversary route planning

KW - Autonomous systems

KW - Multi-robot systems

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

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

U2 - 10.1007/978-3-319-44832-9_8

DO - 10.1007/978-3-319-44832-9_8

M3 - Conference contribution

SN - 9783319448312

VL - 9862

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 131

EP - 148

BT - Princiles and Practice of Multi-Agent Systems - 19th International Conference, PRIMA 2016, Proceedings

PB - Springer Verlag

ER -