University of Leicester
Browse
LIPIcs-CONCUR-2017-13.pdf (630.75 kB)

The robot routing problem for collecting aggregate stochastic rewards

Download (630.75 kB)
conference contribution
posted on 2018-04-27, 11:19 authored by Rayna Dimitrova, Ivan Gavran, Rupak Majumdar, Vinayak S. Prabhu, Sadegh Esmaeil Zadeh Soudjani
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 -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 NPlower bounds and show that optimal strategies require memory in general. We also provide an algorithm for computing ∼-optimal infinite paths for arbitrary ∼ > 0.

History

Citation

Leibniz International Proceedings in Informatics, LIPIcs, 2017, 85, pp. 13:1-13:1

Author affiliation

/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Informatics

Source

28th International Conference on Concurrency Theory (CONCUR 2017)

Version

  • VoR (Version of Record)

Published in

Leibniz International Proceedings in Informatics

Publisher

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

issn

1868-8969

isbn

9783959770484

Copyright date

2017

Available date

2018-04-27

Publisher version

http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7792

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC