Dimitrova, Rayna ;
Gavran, Ivan ;
Majumdar, Rupak ;
Prabhu, Vinayak S. ;
Soudjani, Sadegh Esmaeil Zadeh
The Robot Routing Problem for Collecting Aggregate Stochastic Rewards
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 (unitdistance) 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 epsilonoptimal) path that maximizes the expected collected rewards.
We consider the finite and infinitehorizon robot routing problems. For finitehorizon, the goal is to maximize the total expected reward, while for infinite horizon we consider limitaverage objectives. We study the computational and strategy complexity of these problems, establish NPlower bounds and show that optimal strategies require memory in general. We also provide an algorithm for computing epsilonoptimal 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:113:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770484},
ISSN = {18688969},
year = {2017},
volume = {85},
editor = {Roland Meyer and Uwe Nestmann},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7792},
URN = {urn:nbn:de:0030drops77920},
doi = {10.4230/LIPIcs.CONCUR.2017.13},
annote = {Keywords: Path Planning, Graph Games, Quantitative Objectives, Discounting}
}
2017
Keywords: 

Path Planning, Graph Games, Quantitative Objectives, Discounting 
Seminar: 

28th International Conference on Concurrency Theory (CONCUR 2017)

Issue date: 

2017 
Date of publication: 

2017 