hide
Free keywords:
cs.SY,Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computer Science and Game Theory, cs.GT,Mathematics, Optimization and Control, math.OC
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.
