License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2017.13
URN: urn:nbn:de:0030-drops-77920
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7792/
Go to the corresponding LIPIcs Volume Portal

Dimitrova, Rayna ; Gavran, Ivan ; Majumdar, Rupak ; Prabhu, Vinayak S. ; Soudjani, Sadegh Esmaeil Zadeh

The Robot Routing Problem for Collecting Aggregate Stochastic Rewards

pdf-format:
LIPIcs-CONCUR-2017-13.pdf (0.6 MB)

Abstract

We propose a new model for formalizing reward collection problems on graphs with dynamically generated rewards which may appear and disappear based on a stochastic model. The robot routing problem is modeled as a graph whose nodes are stochastic processes generating potential rewards over discrete time. The rewards are generated according to the stochastic process, but at each step, an existing reward disappears with a given probability. The edges in the graph encode the (unit-distance) paths between the rewards' locations. On visiting a node, the robot collects the accumulated reward at the node at that time, but traveling between the nodes takes time. The optimization question asks to compute an optimal (or epsilon-optimal) path that maximizes the expected collected rewards.

We consider the finite and infinite-horizon robot routing problems. For finite-horizon, the goal is to maximize the total expected reward, while for infinite horizon we consider limit-average objectives. We study the computational and strategy complexity of these problems, establish NP-lower bounds and show that optimal strategies require memory in general. We also provide an algorithm for computing epsilon-optimal infinite paths for arbitrary epsilon > 0.

BibTeX - Entry

@InProceedings{dimitrova_et_al:LIPIcs:2017:7792,
  author =	{Rayna Dimitrova and Ivan Gavran and Rupak Majumdar and Vinayak S. Prabhu and Sadegh Esmaeil Zadeh Soudjani},
  title =	{{The Robot Routing Problem for Collecting Aggregate Stochastic Rewards}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Roland Meyer and Uwe Nestmann},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7792},
  URN =		{urn:nbn:de:0030-drops-77920},
  doi =		{10.4230/LIPIcs.CONCUR.2017.13},
  annote =	{Keywords: Path Planning, Graph Games, Quantitative Objectives, Discounting}
}

Keywords: Path Planning, Graph Games, Quantitative Objectives, Discounting
Collection: 28th International Conference on Concurrency Theory (CONCUR 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI