The Robot Routing Problem for Collecting
Aggregate Stochastic Rewards
Rayna Dimitrova, Ivan Gavran, Rupak Majumdar,
Vinayak S. Prabhu, and Sadegh Esmaeil Zadeh Soudjani1
1

Max Planck Institute for Software Systems, Kaiserslautern, Germany
{Rayna,Gavran,Rupak,Vinayak,Sadegh}@mpi-sws.org

arXiv:1704.05303v2 [cs.SY] 17 Jul 2017

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 -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.
1998 ACM Subject Classification I.2.8 Problem Solving, Control Methods, and Search
Keywords and phrases Path Planning, Graph Games, Quantitative Objectives, Discounting
Digital Object Identifier 10.4230/LIPIcs...

1

Introduction

Reward collecting problems on metric spaces are at the core of many applications, and studied
classically in combinatorial optimization under many well-known monikers: the traveling
salesman problem, the knapsack problem, the vehicle routing problem, the orienteering
problem, and so on. Typically, these problems model the metric space as a discrete graph
whose nodes or edges constitute rewards, either deterministic or stochastic, and ask how
to traverse the graph to maximize the collected rewards. In most versions of the problem,
rewards are either fixed or cumulative. In particular, once a reward appears, it stays there
until collection. However, in many applications, existing rewards may disappear (e.g., a
customer changing her mind) or have more “value” if they are collected fast.
We introduce the Robot Routing problem, which combines the spatial aspects of traveling
salesman and other reward collecting problems on graphs with stochastic reward generation
and with the possibility that uncollected rewards may disappear at each stage. The robot
routing problem consists of a finite graph and a reward process for each node of the graph.
The reward process models dynamic requests which appear and disappear. At each (discrete)
time point, a new reward is generated for the node according to a stochastic process with
expectation λ. However, at each point, a previously generated reward disappears with a fixed
© Rayna Dimitrova, Ivan Gavran, Rupak Majumdar, Vinayak S. Prabhu, and Sadegh Soudjani;
licensed under Creative Commons License CC-BY
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

XX:2

The Robot Routing Problem for Collecting Aggregate Stochastic Rewards

probability δ. When the node is visited, the entire reward is collected. The optimization
problem for robot routing asks, given a graph and a reward process, what is the optimal (or
-optimal) path a robot should traverse in this graph to maximize the expected reward?
As an illustrating example for our setting, consider a vendor planning her path through a
city. At each street corner, and at each time step, a new customer arrives with expectation λ,
and an existing customer leaves with probability δ. When the vendor arrives at the corner,
she serves all the existing requests at once. We ignore other possible real-world features and
behaviors e.g., customers leaving queues if the queue length is long. How should the vendor
plan her path? Similar problems can be formulated for traffic pooling [25], for robot control
[13], for patrolling [15], and many other scenarios.
Despite the usefulness of robot routing in many scenarios involving dynamic appearance
and disappearance of rewards, algorithms for its solution have not, to the best of our
knowledge, been studied before. In this paper, we study two optimization problems: the
value computation problem, that asks for the maximal expected reward over a finite or
infinite horizon, and the path computation problem, that asks for a path realizing the optimal
(or -optimal) reward. The key observation to solving these problems is that the reward
collection can be formulated as discounted sum problems over an extended graph, using the
correspondence between stopping processes and discounted sum games.
For finite horizon robot routing we show that the value decision problem (deciding if the
maximal expected reward is at least a certain amount) is NP-complete when the horizon
bound is given in unary, and the value and optimal path can be computed in exponential
time using dynamic programming.
For the infinite horizon problem, where the accumulated reward is defined as the long run
average, we show that the value decision problem is NP-hard if the probability of a reward
disappearing is more than a threshold dependent on the number of nodes. We show that
computing the optimal long run average reward can be reduced to a 1-player mean-payoff
game on an infinite graph. By solving the mean payoff game on a finite truncation of this
graph, we can approximate the solution up to an arbitrary precision. This gives us an
algorithm that, for any given , computes an -optimal path in time exponential in the size of
the original graph and logarithmic in 1/. Unlike finite mean-payoff 2-player games, strategies
which generate optimal paths for robot routing even in the 1-player setting can require
memory. For the non-discounted infinite horizon problem (that is, when rewards do not
disappear) we show that the optimal path and value problems are solvable in polynomial time.
Related work The robot routing problem is similar in nature to a number of other problems
studied in robot navigation, vehicle routing, patrolling, and queueing network control, but to
the best of our knowledge has not been studied so far.
There exists a plethora of versions of the famous traveling salesman problem (TSP) which
explore the trade-off between the cost of the constructed path and its reward. Notable
examples include the orienteering problem [23], in which the number of locations visited in
a limited amount of time is to be maximized, vehicle routing with time-windows [17] and
deadlines-TSP [2], which impose restrictions or deadlines on when locations should be visited,
as well as discounted-reward-TSP [4] in which soft deadlines are implemented by means of
discounting. Unlike in our setting, in all these problems, rewards are static, and there is no
generation and accumulation of rewards, which is a key feature of our model.
In the dynamic version of vehicle routing [7] and the dynamic traveling repairman
problem [3], tasks are dynamically introduced and the objective is to minimize the expected
task waiting time. In contrast, we focus on limit-average objectives, which are a classical way
to combine rewards over infinite system runs. Patrolling [6] is another graph optimization

R. Dimitrova, I. Gavran, R. Majumdar, V. S. Prabhu, and S. E. Z. Soudjani

problem, motivated by operational security. The typical goal in patrolling is to synthesize a
strategy for a defender against a single attack at an undetermined time and location, and is
thus incomparable to ours. A single-robot multiple-intruders patrolling setting that is close to
ours is described in [15], but there again the objective is to merely detect whether there is a
visitor/intruder at a given room. Thus, the patrolling environment in [15] is described by the
probability of detecting a visitor for each location. On the contrary, our model can capture
counting patrolling problems, where the robot is required not only to detect the presence of
visitors but to register/count as many of them as possible. Another related problem is the
information gathering problem [20]. The key difference between the information gathering
setting and ours is that [20] assumes that making an observation earlier has bigger value than
if a lot of observations have already been made. This restriction on the reward function is not
present in our model, since the reward value collected when visiting node v at time t (making
observation (v, t), in their terms) only depends on the last time when v was previously visited,
and not on the rest of the path (the other observations made, in their terms).
Average-energy games [8, 5] are a class of games on finite graphs in which the limit-average
objective is defined by a double summation. The setting discussed in [8, 5] considers static
edge weights and no discounting. Moreover, the inner sum in an average-energy objective is
over the whole prefix so far, while in our setting the inner sum spans from the last to the
current visit of the current node, which is a crucial difference between these two settings.
Finally, there is a rich body of work on multi-robot routing [24, 1, 18, 10, 11] which is
closely related to our setting. However, the approaches developed there are limited to static
tasks with fixed or linearly decreasing rewards. The main focus in the multi-robot setting is
the task allocation and coordination between robots, which is a dimension orthogonal to the
aggregate reward collection problem which we study.
Markov decision processes (MDP) [19] seem superficially close to our model. In an MDP,
the rewards are determined statically as a function of the state and action. In contrast, the
dynamic generation and accumulation of rewards in our model, especially the individual
discounting of each generated reward, leads to algorithmic differences: for example, while
MDPs admit memoryless strategies for long run average objectives, strategies require memory
in our setting and there is no obvious reduction to, e.g., an exponentially larger, MDP.
We employed the reward structure of this article in [13] with the goal of synthesizing
controllers for reward collecting Markov processes in continuous space. The work [13] is
mainly focused on addressing the continuous dynamics of the underlying Markov process
where the authors use abstraction techniques [12] to provide approximately optimal controllers
with formal guarantees on the performance while maintaining the probabilistic nature of the
process. In contrast, we tackle the challenges of this problem with having a deterministic
graph as the underlying dynamical model of the robot and study the computational complexity
of the proposed algorithms thoroughly.
Contributions We define a novel optimization problem for formalizing and solving reward
collection in a metric space where stochastic rewards appear as well as disappear over time.
We consider reward-collection problems in a novel model with dynamic generation and
accumulation of rewards, where each reward can disappear with a given probability.
We study the value decision problem, the value computation problem, and the path
computation problem over a finite horizon. We show that the value decision problem is
NP-complete when the horizon is given in unary. We describe a dynamic programming
approach for computing the optimal value and an optimal path in exponential time.
We study the value decision problem, the value computation problem, and the path

XX:3

XX:4

The Robot Routing Problem for Collecting Aggregate Stochastic Rewards

computation problem over an infinite horizon. We show that for sufficiently large values of
the disappearing factor δ the value decision problem is NP-hard. We provide an algorithm
which for any given  > 0, computes an -optimal path in time exponential in the size of
the original graph and logarithmic in 1/. We demonstrate that strategies (in the 1-player
robot routing games) which generate infinite-horizon optimal paths can require memory.

2

Problem Formulation

Preliminaries and notation A finite directed graph G = (V, E) consists of a finite set of
nodes V and a set of edges E ⊆ V × V . A path π = v0 , v1 , . . . in G is a finite or infinite
sequence of nodes in G, such that (vi , vi+1 ) ∈ E for each i ≥ 0. We denote with |π| = N
the length (number of edges) of a finite path π = v0 , v1 , . . . , vN and write π[i] = vi and
π[0 . . . N ] = v0 , v1 , . . . vN . For an infinite path π, we define |π| = ∞. We also denote the
cardinality of a finite set U by |U |. We denote by N = {0, 1, ..} and Z+ = {1, 2, ..} the sets of
non-negative and positive integers respectively. We define Z[n, m] = {n, n + 1, . . . , m} for any
n, m ∈ N, n ≤ m. We denote with I(·) the indicator function which takes a Boolean-valued
expression as its argument and returns 1 if this expression evaluates to true and 0 otherwise.
Problem setting Fix a graph G = (V, E). We consider a discrete-time setting where at
each time step t ∈ N, at each node v ∈ V a reward process generates rewards according to
some probability distribution. Once generated, each reward at a node decays according to a
decaying function. A reward-collecting robot starts out at some node v0 ∈ V at time t = 0,
and traverses one edge in E at each time step. Every time the robot arrives at a node v ∈ V ,
it collects the reward accumulated at v since the last visit to v. Our goal is to compute the
maximum expected reward that the robot can possibly collect, and to construct an optimal
path for the robot in the graph, i.e., a path whose expected total reward is maximal.
To formalize reward accumulation, we define a function Lastπ which (for path π) maps an
index t ≤ |π| and a node v ∈ V to the length of the path starting at the previous occurrence
of v in π till position t; and to t + 1 if v does not occur in π before time t:
Lastπ (t, v) := min (t + 1, {t − j ∈ N | j < t, π[j] = v}) .
Reward functions Let ξ : Ω × V → R be a set of random variables defined on a sample
space Ω and indexed by the set of nodes V . Then ξ(·, v), v ∈ V, is a measurable function
from Ω to R that generates a random reward at node v at any time step. Let π be the path
in G traversed by the robot. At time t, the position of the robot is the node π[t], and the
robot collects the uncollected decayed reward generated at node π[t] (since its last visit to
π[t]) up till and including time t. Then, the robot traverses the edge (π[t], π[t + 1]), and at
time t + 1 it collects the rewards at node π[t + 1].
The uncollected reward at time t at a node v given a path π traversed by the robot is
defined by the random variable
Lastπ (t,v)−1

accπ (t, v) :=

X

γ(v)j ξ(w(t − j), v),

w(·) ∈ Ω.

j=0

The value γ(v) in the above definition is a discounting factor that models the probability
that a reward at node v survives for one more round, that is, the probability that a given
reward instance at node v disappears at any step is 1 − γ(v).
Note that the previous time a reward was collected at node v was at time t − Lastπ (v, t),
the time node v was last visited before t. Thus accπ (t, v) corresponds to the rewards

R. Dimitrova, I. Gavran, R. Majumdar, V. S. Prabhu, and S. E. Z. Soudjani

XX:5

generated at node v at times t, t − 1, . . . , t − Lastπ (t, v) + 1, which have decayed by factors of
γ(v)0 , γ(v)1 , . . . , γ(v)Lastπ (t,v)−1 , respectively. When traversing a path π, the robot collects
the accumulated reward accπ (t, π[t]) at time t at node π[t].
We define the expected finite N -horizon sum reward for a path π as:
"N
#
X
(N )
rsum (π) := E
accπ (t, π[t]) .
t=0

Let λ : V → R≥0 be a function that maps each node v ∈ V to the expected value of the
reward generated at node v for each time step, λ(v) = E [ξ(·, v)]. We assume that the rewards
generated at each node are independent of the agent’s move. Thus, the function λ will be
sufficient for our study, since we have
(N )
rsum
(π) =

N
X

Lastπ (t,v)−1

Eaccπ (t, π[t]), where Eaccπ (t, v) :=

t=0

X

γ(v)j λ(v).

(1)

j=0

For an infinite path π, the limit-average expected reward is defined as
(N )

rav (π) = lim inf
N →∞

rsum (π)
.
N +1

(2)

The finite and infinite-horizon reward values forn a node v are defined as the
o best rewards
(N )
(N )
over all paths originating in v: Rsum (v) = supπ rsum (π) | π[0] = v, |π| = N and Rav (v) =
supπ {rav (π) | π[0] = v, |π| = ∞}, respectively. The choice of limit-average in (2) is due to the
(N )
unbounded sum reward rsum (π) when N goes to infinity. For a given path π, the sequence
(N )
rsum (π) /(N +1) in (2) may not converge. Thus we opt for the worst case limiting behavior
of the sequence. Alternatively, one may select the best case limiting behavior lim supN →∞
in (2) with no substantial change in the results of this paper.
Node-invariant functions λ and γ and definition of cost functions In the case when the
functions λ and γ are constant, we write λ and γ for the respective constants. In this case, the
(N )
expressions for rsum (π) and rav (π) can be simplified using the identity 1+γ +γ 2 +· · ·+γ q−1 =
1−γ q
1−γ for γ < 1. Then we have
(N )
rsum
(π) =

N Lastπ (π[t],t)−1
X
X
t=0

=λ·

γj λ = λ ·

t=0

1 + γ + . . . + γ Lastπ (t,π[t])−1



t=0

j=0

N
X

N 
X

N
1 − γ Lastπ (t,π[t])
(N + 1)λ
λ X Lastπ (t,π[t])
=
−
γ
.
1−γ
1−γ
1 − γ t=0

(3)

The expression rav (π) can be simplified as:
N

rav (π) = lim inf
N →∞

1
λ
λ
1 X Lastπ (t,π[t])
(N )
rsum
(π) =
−
lim sup
γ
.
N +1
1−γ
1 − γ N →∞ N + 1 t=0

(4)

For the special case γ = 1 (i.e., when the rewards are not discounted), the expression for the
PN
(N )
finite-horizon reward is rsum (π) = λ t=0 Lastπ (t, π[t]).
We define cost functions that map a path π to a real valued finite- or infinite-horizon cost:
)
c(N
sum (π)

:=

N
X
t=0

(N )

γ Lastπ (π[t],t)

and

cav (π) := lim sup
N →∞

csum (π)
.
N +1

(5)

XX:6

The Robot Routing Problem for Collecting Aggregate Stochastic Rewards

(N )

From Equations (3) and (4), the computation of optimal paths for the reward functions rsum
(N )
and rav corresponds to computing paths that minimize the cost functions csum (π) and cav (π),
(N )
respectively. Analogously to Rsum (v) and Rav (v), the infimums of the cost functions in (5)
(N )
over paths are denoted by Csum (v) and Cav (v) respectively.
I Example 1. Consider the graph Ge = (Ve , Ee ) in Figure 1 with Ve = {a, b, c, d}, which we
will use as a running example throughout the paper. The functions λ and γ are constant.
Consider the finite path π1 = adabcad. For the
occurrences of node a in π1 we have Lastπ1 (0, a) = 1,
b
Lastπ1 (2, a) = 2, Lastπ1 (5, a) = 3, and similarly for
a
d
the other nodes in π1 . The reward for π1 as a function
7λ
λ
6
of λ and γ is rsum
(π1 ) = 1−γ
− 1−γ
(γ + γ 2 + γ 2 +
c
6
γ 4 + γ 5 + γ 3 + γ 5 ) for γ < 1 and rsum
(π1 ) = 22λ
ω
Figure 1 A graph Ge = (Ve , Ee ) with for γ = 1. For the infinite path π2 = (abc) we have
two simple cycles sharing a single node. Lastπ2 (0, a) = 1, Lastπ2 (1, b) = 2, Lastπ2 (2, c) = 3 and
the value of Last is 3 in all other cases. Thus we have
λ
λ
rav (π2 ) = 1−γ
− 1−γ
γ 3 for γ < 1 and rav (π2 ) = 3λ for γ = 1. Similarly, for π3 = (abcad)ω
we have rav (π3 ) =

λ
1−γ

−

λ
1−γ

·

(γ 2 +γ 3 +3γ 5 )
5

for γ < 1 and rav (π3 ) = 4λ for γ = 1.

Problem statements We investigate optimization and decision problems for finite and
infinite-horizon robot routing. The value computation problems ask for the computation of
(N )
Rsum (v) and Rav (v). The corresponding decision problems asks to check if the respective
one of these two quantities is greater than or equal to a given threshold R ∈ R.
I Definition 2 (Value Decision Problems). Given a finite directed graph G = (V, E), an
expected reward function λ : V → R≥0 , a discounting function γ : V → (0, 1], an initial node
v0 ∈ V and a threshold value R ∈ R,
(N )
The finite horizon value decision problem is to decide, given N , if Rsum (v0 ) ≥ R.
The infinite horizon value decision problem is to decide if Rav (v0 ) ≥ R.
For a finite directed graph G = (V, E), expected reward and discounting functions
λ : V → R≥0 and γ : V → (0, 1] and v0 ∈ V , a finite path π is said to be an optimal path for
time-horizon N if (a) π[0] = v0 and |π| = N , and (b) for every path π 0 in G with π 0 [0] = v0
(N )
(N )
and |π 0 | = N it holds that rsum (π) ≥ rsum (π 0 ). Similarly, an infinite path π is said to be
optimal for the infinite horizon if π[0] = v0 and for every infinite path π 0 with π 0 [0] = v0 in
G it holds that rav (π) ≥ rav (π 0 ). We can also define corresponding threshold paths: given a
(N )
value R a path π is said to be threshold R-optimal if rsum (π) ≥ R or rav (π) ≥ R, respectively.
(N )
An -optimal path is one which is Rsum (v0 ) −  or Rav (v0 ) −  threshold optimal (for finite or
infinite horizon respectively).
I Example 3. Consider again the graph Ge shown in Figure 1. Examining the expressions
computed in Example 1, we have that rav (π2 ) > rav (π3 ) for γ = 0.1 and rav (π3 ) > rav (π2 ) for
γ = 0.9. Thus, in general, the optimal value depends on γ. Due to the structure of the set of
infinite paths in Ge we can analytically compute the optimal value Rav (v) for each v ∈ Ve as
a function of γ and a corresponding optimal path (the proof is in the appendix):
λ
λ
3
ω
1−γ − 1−γ γ and the path (abc) is optimal;
2
3
5
8
+γ )
λ
λ
[a1 , a2 ], then Rav (v) = 1−γ
− 1−γ
· (γ +4γ +2γ
and (abcabcad)ω is optimal;
8
2
3
5
λ
λ
[a2 , 1], then Rav (v) = 1−γ
− 1−γ
· (γ +γ5 +3γ ) and the path (abcad)ω is optimal.

if γ ∈ [0, a1 ], then Rav (v) =
if γ ∈
if γ ∈

R. Dimitrova, I. Gavran, R. Majumdar, V. S. Prabhu, and S. E. Z. Soudjani

The constants a1 ≈ 0.2587 and a2 ≈ 0.2738 are respectively the unique real roots of polynomials γ 6 +2γ 3 −4γ +1 and 5γ 6 −14γ 3 +12γ −3 in the interval (0, 1). Note that for γ = 1 we have
Rav (v) = 4λ which is achieved by (abcad)ω . The path (abc)(ad)(abc)2 (ad)2. . . (abc)n (ad)n. . .,
which is not ultimately periodic, also achieves the optimal reward.
Paths as strategies We often refer to infinite paths as resulting from strategies (of the
collecting agent). A strategy σ in G is a function that maps finite paths π[0 . . . m] to nodes
such that if σ(π) is defined then (π[m], σ(π)) ∈ E. Given an initial node v0 , the strategy
σ generates a unique infinite path π, denoted as outcome(v0 , σ). Thus, every infinite path
π = v0 , v1 , . . . defines a unique strategy σπ where σπ (π[0 . . . i]) = vi+1 , and σπ () = v0 , and
σπ is undefined otherwise. Clearly, outcome(v0 , σπ ) = π. We say a strategy σ is optimal for
a path problem if the path outcome(v0 , σ) is optimal. A strategy σ is memoryless if for every
two paths π 0 [0 . . . m0 ], π 00 [0 . . . m00 ] for which π 0 [m0 ] = π 00 [m00 ], it holds that σ(π 0 ) = σ(π 00 ).
We say that memoryless strategies suffice for the optimal path problem if there always exists
a memoryless strategy σ such that outcome(v0 , σ) is an optimal path.

3

(N )
Finite Horizon Rewards: Computing Rsum
(v)

In this section we consider the finite-horizon problems associated with our model. The
following theorem summarizes the main results.
I Theorem 4. Given G = (V,E), expected reward and discounting functions, node v ∈ V ,
and horizon N ∈ N:
1. The finite-horizon value decision problem is NP-complete if N is in unary.
(N )
2. The value Rsum (v) for v ∈ V is computable in exponential time even if N is in binary.
Analogous results hold for the related reward problem where in addition to the initial
node v, we are also given a destination node vf , and the objective is to go from v to vf in at
most N steps while maximizing the reward.
The finite-horizon value problem is NP-hard by reduction from the Hamiltonian path
problem (the proof is in the appendix), even in the case of node-invariant λ and γ. Membership
in NP in case N is in unary follows from the fact that we can guess a path of length N and
check that the reward for that path is at least the desired threshold value.
To prove the second part of the theorem, we construct a finite augmented weighted graph.
For simplicity, we give the proof for node-invariant λ and γ, working with the cost
functions csum and cav . The augmented graph construction in the general case is a trivial
generalization by changing the weights of the nodes, and the dynamic programming algorithm
used for computing the optimal cost values is easily modified to compute the corresponding
PN
(N )
reward values instead. For γ < 1 the objective is to minimize csum (π) = t=0 γ Lastπ (t,π[t])
PN
(N )
and for γ = 1 the objective is to maximize rsum (π) = λ t=0 Lastπ (t, π[t]) over paths π.
Augmented weighted graph Given a finite directed graph G = (V, E) we define the
e = (Ve , E)
e which “encodes” the values Lastπ (t, v) for the paths in
augmented weighted graph G
G explicitly in the augmented graph node. We can assume w.l.o.g. that V = {1, 2, . . . , |V |}.
|V |
The set of nodes Ve is V × Z+ (the set Ve is infinite). A node (v, b1 , b2 , . . . , b|V | ) ∈ Ve
represents the fact that the current node is v, and that for each node u ∈ V the last visit
to u (before the current time) was bu time units before the current time.
The weight of a node (v, b1 , b2 , . . . , b|V | ) ∈ Ve is γ bv .
e consists of edges (v, b1 , b2 , . . . , b|V | ) → (v 0 , b0 , b0 , . . . , b0 ) such that
The set of edges E
1 2
|V |
(v, v 0 ) ∈ E; and b0v = 1, and b0u = bu + 1 for all u 6= v.

XX:7

XX:8

The Robot Routing Problem for Collecting Aggregate Stochastic Rewards

e there exists a unique path π
Let π be a path in G. In the graph G
e that corresponds to π:
π
e = (π[0], 1, 1, . . . , 1) , (π[1], b11 , b12 , . . . , b1|V | ) , (π[2], b21 , b22 , . . . , b2|V | ) , . . .

(6)

starting from the node (π[0], 1, 1, . . . , 1) such that for all t and for all v ∈ V , we have
e starting from (v0 , 1, 1, . . . , 1), there exists a
Lastπ (t, v) = btv . Dually, for each path π
e in G
unique path π in G from the node v0 such that Lastπ (t, v) = btv for all t and v.
For a path π
e in the form of (6) let
)
e
c(N
π ) :=
sum (e

N
X
t=0

N

t

γ bvt

and

e
cav (e
π ) := lim sup
N →∞

1 X btv
γ t . Observe that:
N + 1 t=0

(N )

e
csum (e
π ) is the sum of weights associated with the first N + 1 nodes of π
e.
e
cav (e
π ) is the limit-average of the weights associated with the nodes of π
e.
(N )
Thus, e
csum and e
cav define the classical total finite sum (shortest paths) and limit average
(N )
(N )
objectives on weighted (infinite) graphs [26]. Additionally, e
csum (e
π ) = csum (π), and e
cav (e
π) =
cav (π) where π is the path in G corresponding to the path π
e.
(N )
(N )
esum
Now, define C
((v0 , 1, 1, . . . , 1)) as the infimum of e
csum (e
π ) over all paths π
e with π
e[0] =
(N )
eav ((v0 , 1, 1, . . . , 1)). Then it is easy to see that Csum
(v0 , 1, 1, . . . , 1), and similarly for C
(v0 ) =
(N )
esum
eav ((v0 , 1, 1, . . . , 1)). Thus, we can reduce the optimal
((v0 , 1, 1, . . . , 1)) and Cav (v0 ) = C
C
e The major difficulty is that G
e is
path and value problems for G to standard objectives in G.
infinite. However, note that only the first N + 1 nodes of π
e are relevant for the computation
(N )
(N )
esum
of e
csum (e
π ). Thus, the value of C
((v0 , 1, . . . , 1)) can be computed on a finite subgraph of
e obtained by considering only the finite subset of nodes V ×Z[1, N + 1]|V | ⊆ Ve .
G,
(N )
esum
For γ < 1, we obtain the value C
(e
π ) by a standard dynamic programming algorithm
which computes the shortest path of length N on this finite subgraph starting from the node
(v0 , 1, 1, . . . , 1) (and keeping track of the number of steps). For γ = 1, where the objective
PN
(N )
is to maximize rsum (π) = λ t=0 Lastπ (t, π[t]) over paths π, we proceed analogously. Note
that the subgraph used for the dynamic programming computations is of exponential size in
terms of the size of G and the description of N . This gives the desired result in Theorem 4.

4

Infinite Horizon Rewards: Computing Rav (v)

Since we consider finite graphs, every infinite path eventually stays in some strongly connected
component (SCC). Furthermore, the value of the reward function rav (π) does not change if
we alter/remove a finite prefix of the path π. Thus, it suffices to restrict our attention to
the SCCs of the graph: the problem of finding an optimal path from a node v ∈ V reduces
to finding the SCC that gives the highest reward among the SCCs reachable from node v.
Therefore, we assume that the graph is strongly connected.

4.1

Hardness of Exact Rav (v) Value Computation

Since it is sufficient for the hardness results, we consider node-invariant λ and γ.
Insufficiency of memoryless strategies. Before we turn to the computational hardness of
the value decision problem, we look at the strategy complexity of the optimal path problem
and show that optimal strategies need memory.
I Proposition 5. Memoryless strategies do not suffice for the infinite horizon problem.

R. Dimitrova, I. Gavran, R. Majumdar, V. S. Prabhu, and S. E. Z. Soudjani

XX:9

Proof. Consider Example 3. A memoryless strategy results in paths which cycle exclusively
either in the left cycle, or the right cycle (as from node a, it prescribes a move to either only
b or only d). As shown in Example 3, the optimal path for γ ≥ a1 needs to visit both cycles.
Thus, memoryless strategies do not suffice for this example.
J
For ω-regular objectives, strategies based on latest visitation records [14, 22], which
depend only on the order of the last node visits (i.e., for all node pairs v1 6= v2 ∈ V , whether
the last visit of v1 was before that of v2 or vice versa) are sufficient. However, we can show
that such strategies do not suffice either. To see this, recall the graph in Figure 1 for which
the optimal path for γ = 0.26 is (abcabcad)ω . Upon visiting node a this strategy chooses one
of the nodes b or d depending on the number of visits to b since the last occurrence of d. On
the other hand, every strategy based only on the order of last visits is not able to count the
number of visits to b and thus, results in a path that ends up in one of (abc)ω , or (ad)ω , or
(abcad)ω , which are not optimal for this γ. The proof is given in the appendix. It is open if
finite memory strategies are sufficient for the infinite-horizon optimal path problem.
NP-Hardness of the value decision problem To show NP-hardness of the infinite-horizon
value decision problem, we first give bounds on Rav (v0 ). The following Lemma proven in the
appendix, establishes these bounds.
I Lemma 6. For any graph G = (V, E) and any node v0 ∈ V , Rav (v0 ) is bounded as
λ

1 − γ nv
1 − γp
≤ Rav (v0 ) ≤ λ
,
1−γ
1−γ

(7)

where nv = |V | and p is the length of the longest simple cycle in G.
I Corollary 7. If the graph G = (V, E) contains a Hamiltonian cycle, any path π =
(v1 v2 . . . v|V | )ω , with v1 v2 . . . v|V | v1 being a Hamiltonian cycle, is optimal and the optimal
value of Rav (v0 ) is exactly the upper bound in (7).
The following lemma establishes a relationship between the value of optimal paths and
the existence of a Hamiltonian cycle in the graph, and is useful for providing a lower bound
on the computational complexity of the value decision problem.
I Lemma 8. If the upper bound in (7) is achieved with a path π for some γ < 1/|V |, then
the graph contains a Hamiltonian cycle ρ that occurs in π infinitely often.
Proof. The proof is by contradiction. Suppose π does not visit any Hamiltonian cycle
infinitely often. Then it visits each such cycle at most a finite number of times. Without
loss of generality we can assume that the path doesn’t visit any such cycles, since the total
number of Hamiltonian cycles is finite. We have for nv = |V |
)
c(N
sum (π) ≥

N
X
t=0

γ Lastπ (t,π[t]) I(Lastπ (t, π[t]) < nv ) ≥ γ nv −1

N
X

I(Lastπ (t, π[t]) < nv ).

t=0

Now let’s look at πn,nv = π[n(n + 1) . . . (n + nv )] a finite sub-path of length nv . There is
at least one node repeated in πn,nv since the graph has nv distinct nodes. Note that if
π[n] = π[n + nv ], there must be another repetition due to the lack of Hamiltonian cycles in
the path. In either case, there is an in ∈ Z[n, n + nv ] such that Lastπ (in , π[in ]) < nv .
 
N
X
)
nv −1
nv −1 N
c(N
(π)
≥
γ
I(Last
(t,
π[t])
<
n
)
≥
γ
π
v
sum
nv
t=0
 

1
N
1
⇒ cav (π) ≥ γ nv −1 lim sup
= γ nv −1
⇒ γ nv ≥ γ nv −1 /nv ⇒ γ ≥ 1/nv ,
nv
N →∞ N + 1 nv

XX:10

The Robot Routing Problem for Collecting Aggregate Stochastic Rewards

which is a contradiction with the assumption that γ < 1/nv . Then a necessary condition for
cav (π) = γ nv with some γ < 1/nv is the existence of a Hamiltonian cycle.
J
Remark. Following the same reasoning of the above proof it is possible to improve the upper
bound in (7) as Rav (v0 ) ≤ λ (1 − γ p /nv ) /(1 − γ) for small values of γ, where p is the length
of the longest simple cycle of the graph.
I Theorem 9. The infinite horizon value decision problem is NP-hard for γ < 1/|V |.
Proof. We reduce the Hamiltonian cycle problem to the infinite horizon optimal path problem.
Given a graph G = (V,
 E), we fix some λ and γ < 1/|V |. We show that G is Hamiltonian iff
Rav (v0 ) ≥ λ 1 − γ |V | /(1 − γ). If G has a Hamiltonian cycle
 v1 v2 . . . v|V | v1 , then the infinite
path π = (v1 v2 . . . v|V | )ω has reward rav (π) = λ 1 − γ |V | /(1 − γ), for any choice of γ. For
the other direction, applying Lemma 8 with γ < 1/|V | implies that G is Hamiltonian.
J
Non-discounted rewards (γ = 1) and node-invariant function λ Contrary to the finitehorizon non-discounted case, the infinite-horizon optimal path and value problems for γ = 1
(N )
can be solved in polynomial time. To see this, note that the reward expression rsum (π)
P
(N )
can be written as rsum (π) = λ v∈V y(v, π, N ), where y(v, π, N ) is defined as y(v, π, N ) =
1 + max U, for U = {j ∈ N|j ≤ N, π[j] = v} ∪ {−1}. Then, we can bound the reward by
rav (π) ≤ lim

N →∞

λ

P|V (π)|
i=1

(N + 1 − i + 1)
λ|V (π)|(2N − |V (π)| + 3)
= lim
= λ|Inf(π)|,
N →∞
N +1
2(N + 1)

where Inf(π) is the set of nodes visited in the path π infinitely often. This indicates that
the maximum reward is bounded by λ times the maximal size of a reachable SCC in the
graph G. This upper bound is also achievable: we can construct an optimal path by finding a
maximal SCC reachable from the initial node and a (not necessarily simple) cycle v1 . . . vn v1
that visits all the nodes in this SCC. Then, a subset of optimal paths contains paths of the
form π0 · (v1 . . . vn )ω , where π0 is any finite path that reaches v1 . This procedure can be
done with a computational time polynomial in the size of G.
I Example 10. Consider the graph in Figure 1. The optimal reward for the infinite-horizon
non-discounted case is 4λ, achievable by the path π = (abcad)ω . Another path which is not ultimately periodic but achieves the same reward π 0 = (abc)(ad)(abc)2 (ad)2 . . . (abc)n (ad)n . . ..
Note that for the case γ = 1 there always exists an ultimately periodic optimal path,
such a path is generated by a finite-memory strategy.

4.2

Approximate Computation of Rav (v)

In the previous section we discussed how to solve the infinite-horizon value and path
computation problems for the non-discounted case. Now we show how the infinite-horizon path
and value computation problems for γ < 1 can be effectively approximated. We first define
functions that over and underapproximate Cav (v) (thus also Rav (v)) and establish bounds on
the error of these approximations. Given an integer K ∈ N, approximately optimal paths and
an associated interval approximating Cav (v) can be computed using a finite augmented graph
e K based on the augmented graph G
e of Section 3. Intuitively, G
e K is obtained from G
e by
G
pruning nodes that have a component greater than K in their augmentation. By increasing
the value of K, the approximation error can be made arbitrarily small.
We describe the approximation algorithm for node-invariant λ and γ. The results
generalize trivially to the case when λ and γ are not node-invariant by choosing K large
enough to satisfy the condition that bounds the approximation error for each λ(v) and γ(v).

R. Dimitrova, I. Gavran, R. Majumdar, V. S. Prabhu, and S. E. Z. Soudjani

Consider the following functions from V ∗×N to R≥0 :

Approximate cost functions
)
c̄(N
sum (π, K)

:=

N
X

γ min{K,Lastπ (t,π[t])}

and

t=0
)
c(N
sum (π, K) :=

N
X

γ Lastπ (t,π[t]) I(Lastπ (t, π[t]) ≤ K).

t=0
(N )

Informally, for c̄sum (π, K), if the last visit to node π[t] occurred more than K time units before
(N )
time t, the cost is γ K , rather than the original smaller amount γ Lastπ (t,π[t]) . For c sum (π, K),
if the last visit to π[t] occurred more than K time steps before time t, then the cost is 0. For
both, if the last visit to the node π[t] occurred less than or equal to K steps before, we pay the
(N )
(N )
(N )
actual cost γ Lastπ (t,π[t]) . The above definition implies that c sum (π, K) ≤ csum (π) ≤ c̄sum (π, K)
for every π. Then we have C(v0 , K) ≤ Cav (v0 ) ≤ C(v0 , K), where we define
(N )

C(v0 , K) :=

inf

lim sup

π,π[0]=v0 N →∞

c sum (π, K)
N +1

and

(N )

C(v0 , K) :=

inf

lim sup

π,π[0]=v0 N →∞

c̄sum (π, K)
.
N +1

The difference between the upper and lower bounds can be tuned by selecting K:
(N )
)
c̄(N
sum (π, K) − c sum (π, K) =

N
X

γ K I(Lastπ (t, π[t]) ≥ K + 1)

t=0
)
(N )
K
=⇒ 0 ≤ c̄(N
sum (π, K) − c sum (π, K) ≤ (N + 1)γ
)
(N )
(N )
K
=⇒ c(N
sum (π, K) ≤ c̄sum (π, K) ≤ c sum (π, K) + (N + 1)γ

=⇒ C(v0 , K) ≤ C(v0 , K) ≤ C(v0 , K) + γ K .
Therefore Cav (v0 ) belongs to the interval [C(v0 , K), C(v0 , K)] ⊂ [0, γ K ] and the length of
the interval is at most γ K . In order to guarantee the total error of  > 0 hfor theiactual
λ
/ ln γ.
reward Rav (v0 )1 , we can select K ∈ N according to 1−γ
γ K ≤  =⇒ K ≥ ln (1−γ)
λ
The value Cav (v0 ) can be computed up to the desired degree of accuracy by computing either
C(v0 , K) or C(v0 , K). Next, we give the procedure for computing C(v0 , K) (the procedure
eK .
for C(v0 , K) is similar). It utilizes a finite augmented weighted graph G
e K Recall the infinite augmented weighted graph
Truncated augmented weighted graph G
e from Section 3. We define a truncated version G
e K = (VeK , E
eK ) of G
e where we only keep
G
e
track of Lastπ (t, v) values less than or equal to K. For GK we define two weight functions w
(N )

(N )

and w, for c̄sum and c sum respectively.
The set of nodes VeK is V × Z[0, K]|V | .
For a node ve = (v, b1 , b2 , . . . , b|V | ) ∈ Ve ,
the weight ω(e
v ) is γ bv if bv > 0 and γ K otherwise.
the weight ω(e
v ) is γ bv if bv > 0 and 0 otherwise.
eK consists of edges (v, b1 , b2 , . . . , b|V | ) → (v 0 , b0 , b0 , . . . , b0 ) such that
The set of edges E
1 2
|V |
0
0
(v → v ) ∈ E, bv = 1, and for u 6= v:
1

Since Rav (v0 ) is upper bounded by λ/(1 − γ), we assume that the required accuracy  is less than this
upper bound.

XX:11

XX:12

The Robot Routing Problem for Collecting Aggregate Stochastic Rewards

b0u = bu + 1 if bu > 0 and bu + 1 ≤ K,
b0u = 0 if bu = 0 or bu + 1 > K.
e K we specify two different weights for path π at time step t in the case when
Thus, in G
the previous visit to π[t] in π was more than K time steps ago.
Similarly to the infinite augmented graph we have
(N )
c̄sum (π, K) is the sum of weights assigned by w to the first (N + 1) nodes of π
e.
(N )
c sum (π, K) is the sum of weights assigned by w to the first (N + 1) nodes of π
e.
It is easy to see that C(v0 , K) is the least possible limit-average cost with respect to w in
e K starting from the node ve0 = (v0 , 1, 1, . . . , 1). The same holds for C(v0 , K) with w. Below
G
we show how to compute C(v0 , K). The case C(v0 , K) is analogous, and thus omitted.
Algorithm for computing C(v0 , K) We now describe a method to compute C(v0 , K) as
e K with respect to w. It is well-known that this can
the least possible limit-average cost in G
be reduced to the computation of the minimum cycle mean in the weighted graph [26], which
in turn can be done using the algorithm from [16] that we now describe.
e K is strongly connected. For every ve ∈ VeK , and every
As before, first we assume that G
n ∈ Z+ , we define Wn (e
v ) as the minimum weight of a path of length n from ve0 to ve; if no
such path exists, then Wn (e
v ) = ∞. The values Wn (e
v ) can be computed by the recurrence
Wn (e
v) =

min {Wn−1 (e
u) + w(e
v )},

n = 1, 2, . . . , |VeK |,

eK
(e
u,e
v )∈E
with the initial conditions W0 (e
v0 ) = 0 and W0 (e
v ) = ∞ for any ve =
6 ve0 . Then, we can compute
#
"
W|Ve | (e
v ) − Wn (e
v)
K
.
C(v0 , K) = min
max
|VeK | − n
eK n∈Z[0,|VeK |−1]
e
v ∈V
A cycle ρe with the computed minimum mean can be extracted by fixing the node ve which
achieves the minimum in the above value and the respective path length n and finding a
minimum-weight path from ve0 to ve and a cycle of length |VeK | − n within this path. Thus,
e K obtained by repeating ρe infinitely often realizes this value. A path π from
the path π
e in G
v0 in G with cav (π) = C(v0 , K) is obtained from π
e by projection on V .
e K is not strongly connected we have to consider each of its
In the general case, when G
SCCs reachable from ve0 , and determine the one with the least minimum cycle mean.
For each SCC with m edges and n nodes the computation of the quantities W requires
O(n · m) operations. The computation of the minimum cycle mean for this component
requires O(n2 ) further operations. Since n ≤ m because of the strong connectivity, the
e K can be computed
overall computation time for the SCC is O(n · m). Finally, the SCCs of G
eK |) [21]. This gives us the following result.
in time O(|VeK | + |E
I Lemma 11. The value C(v0 , K) and a path π with limit average cost cav (π) = C(v0 , K)
eK .
can be computed in time polynomial in the size of G
The same result can be established for the under approximation C(v0 , K).
e K is |VeK | = |V | × (K + 1)|V | . For the approximation
Remark. The number of nodes of G
procedure described above it suffices to augment the graph with the information about which
nodes were visited in the last K steps and in what order. Thus, we can alternatively consider
K
a graph with |V | × |V | nodes in the case when the computed K is smaller than |V |.
e K reachable from initial
I Example 12. Figure 2 shows the SCC of the augmented graph G
node (a, 1, 1, 1, 1) for the graph given in Figure 1 and K = 5. The nodes in the SCC are
denoted by shorthands in the picture, e.g., a1 = (a, 3, 2, 1, 4). The labels on the nodes

R. Dimitrova, I. Gavran, R. Majumdar, V. S. Prabhu, and S. E. Z. Soudjani

b2 , γ 3
b

a1 , γ

3

b1 , γ

b

c3 , (γ 5 , 0)
b

3

c1 , γ

b

b

3

c2 , γ 5
b

a2 , γ 3

b

b

d1 , γ 5
b

a5 , γ 2
b

5

b4 , (γ , 0)
b3 , γ 5
b

b

b

d4 , γ 2

a4 , γ 2

b

d3 , γ 2

b

d2 ,
(γ 5 , 0)

a1 = (a, 3, 2, 1, 4)
a3 = (a, 2, 4, 3, 1)
a5 = (a, 2, 0, 0, 1)

a2 = (a, 3, 2, 1, 0)
a4 = (a, 2, 0, 5, 1)

b1 = (b, 1, 3, 2, 5)
b3 = (b, 1, 5, 4, 2)

b2 = (b, 1, 3, 2, 0)
b4 = (b, 1, 0, 0, 2)

c1 = (c, 2, 1, 3, 0)
c3 = (c, 2, 1, 0, 3)

c2 = (c, 2, 1, 5, 3)

d1 = (d, 1, 3, 2, 5)
d3 = (d, 1, 5, 4, 2)

d2 = (d, 1, 3, 2, 0)
d4 = (d, 1, 0, 0, 2)

b

a3 , γ 2

e5 for the graph in Figure 1. The node labels
Figure 2 The SCC of the finite augmented graph G
are the values of the functions w and w (in black if w = w, otherwise respectively in blue and red).
e 5 already
correspond to the values of the weight functions w and w. As we can see, G
contains simple cycles (a2 b2 c2 a2 ), (a3 b3 c2 a1 b1 c1 a2 d2 a3 ), (a3 b3 c2 a1 d1 a3 ), which correspond to
the optimal paths presented in Example 3. The outcome of the minimum cycle mean for
e 5 will be the same with the two sets of weights only for the first and third interval for γ
G
determined in Example 3, but will be different for the second case in which the term γ 8 is
replaced respectively by γ 5 and 0 for the upper and lower bounds.
Theorem 13, a consequence of Lemma 11, states the approximate computation result.
I Theorem 13. Given a graph G = (V, E), node v0 ∈ V , rational values λ and 0 < γ < 1,
|V |
and
for K =
h errori bound  > 0, we can compute in time polynomial in |V |(K + 1)
ln

(1−γ)
λ

/ ln γ (i.e., exponential in |V |), infinite paths πunder and π over and values rav (πunder )

and rav (πover ) such that rav (πunder ) ≤ Rav (v0 ) ≤ rav (πover ) and rav (πover ) − rav (πunder ) ≤ .

4.3

Approximation via Bounded Memory

The algorithm presented earlier is based on an augmentation of the graph with a specific
structure updated deterministically and whose size depends on the desired quality of approximation. Furthermore, in this graph there exists a memoryless strategy with approximately
optimal reward. We show that this allows us to quantify how far from the optimal reward
value is a strategy that is optimal among the ones with bounded memory of fixed size.
First, we give the definition of memory structures. A memory structure M = (M, m0 , δ)
for a graph G = (V, E) consists of a set M , initial memory m0 ∈ M and a memory update
function δ : M × V → M . The memory update function can be extended to δ ∗ : V ∗ → M
by defining δ ∗ () = m0 and δ ∗ (π · v) = δ(δ ∗ (π), v). A memory structure M together with a
function τ : V × M → V such that (v, τ (v, m)) ∈ E for all v ∈ V and m ∈ M , and an initial
node v0 ∈ V define a strategy σ : V ∗ → V where σ() = v0 and σ(π · v) = τ (v, δ ∗ (π)). In
this case we say that the strategy σ has memory M. Given a bound B ∈ N on memory
size we define the finite graph G × B = (V G×B , E G×B ), where V G×B = V × Z[1, B]; and
E G×B = {((v, i), (v 0 , j)) ∈ (V ×Z[1, B]) × (V ×Z[1, B]) | (v, v 0 ) ∈ E}).
Memoryless strategies in this graph precisely correspond to strategies that have memory
of size B. More precisely, for each strategy σ in G = (V, E) that has memory M =
(M, m0 , δ) there exists a memoryless strategy σM in G × |M | such that the projection of

XX:13

XX:14

The Robot Routing Problem for Collecting Aggregate Stochastic Rewards

outcome((v0 , m0 ), σM ) on V is outcome(v0 , σ). Conversely, for each memoryless strategy σM
in G×B there exist a memory structure M = (M, m0 , δ) with |M | = B and a strategy σ with
memory M in G such that the projection of outcome((v0 , m0 ), σM ) on V is outcome(v0 , σ).
I Example 14. Recall that in Example 3 we established that an optimal path for γ = 0.26
is the path (abcabcad)ω . In the graph G × 3 there exists a simple cycle corresponding to
this path, namely (a, 1)(b, 1)(c, 2)(a, 2)(b, 2)(c, 3)(a, 3)(d, 1)(a, 1). Thus, the optimal path
(abcabcad)ω corresponds to a strategy with memory size of 3.
An optimal strategy among those with memory of a given size B can be computed by
inspecting the memoryless strategies in G × B and selecting the one with maximal reward
(these strategies are finitely but exponentially many).
A strategy returned by the approximation algorithm presented earlier uses a memory
structure of size (K + 1)|V | . If (K + 1)|V | ≤ B, then this strategy is isomorphic to some
memoryless strategy σ in G × B. Since the reward achieved by the optimal memoryless
λ
strategy in G × B is at least that of σ, its value is at most 1−γ
γ K away from Rav (v0 ). Now,
k
j
ln B
(K + 1)|V | ≤ B iff K ≤ ln|V
| − 1. Thus, under a memory size B, we are guaranteed to
 ln B 
−1
λ
away from the optimal.
find a strategy which has reward that at most 1−γ γ ln|V |
Next we sketch an algorithm for computing optimal B-memory bounded strategies. As
mentioned previously, we can restrict our attention to memoryless strategies in G × B.
Memoryless strategies in this graph lead to lasso shaped infinite paths, with an initial
non-cyclic path followed by a simple cycle which is repeated infinitely often. This means
that we can restrict our attention to paths of length |V | · B which complete the lasso. Now,
we apply this length bound to restrict our attention to the finite portion of the augmented
e from Section 3 that corresponds to path lengths at most |V |·B. This finite subgraph
graph G
contains nodes V × N[1, |V |·B]|V | . The dynamic programming algorithm is polynomial time
|V |
on this graph, hence we get a running time which is polynomial in |V | · (|V | · B) .
I Theorem 15. Given a graph G = (V, E), a node v0 ∈ V , rational values λ and 0 < γ < 1,
and a memory bound
 B > 1, we can compute a B-memory optimal strategy σ with reward rav
at most

5

λ
1−γ γ

ln B
ln|V |

−1

away from the optimal Rav (v0 ) in time polynomial in |V |

(|V |+1)

· B |V | .

Generalizations of the Model

General Decay Profiles. In this section we assume the expected value of the generated
reward for nodes to be time independent. Given a node v ∈ V , the associated decay profile
Γv for the node is defined to be be a strictly monotonically decreasing sequence 1, a1 , a2 , . . .
(starting from 1) converging to 0. We denote the i-th element of the sequence as Γv (i),
and the sequence portion Γv (i), Γv (i + 1), . . . Γv (j) as Γv [i..j]. If the original generated
reward at a node v was λ, after ∆ time units only λ · Γv (∆) of that reward remains after
decay if uncollected. Denote the sum of the elements of Γv [i..j] as Sum (Γv [i..j]), that is
Pj
Sum (Γv [i..j]) =
k=i Γv (k).
For a path π = v0 , v1 , . . . , (and under fixed decay profiles Γv for the nodes in V ) we define
the finite horizon cumulative (expected) reward as
(N )
rsum
(π)

=

N
X
t=0

λ(vt ) · Sum (Γvt [0 .. t−Lastπ (t, vt )−1]) .

R. Dimitrova, I. Gavran, R. Majumdar, V. S. Prabhu, and S. E. Z. Soudjani

Note that the quantities λ(vt ) · Γvt (0), λ(vt ) · Γvt (1), . . . , λ(vt ) · Γvt (t − Lastπ (t, vt ) − 1) are
the expectations of the uncollected rewards at node vt for times t, t − 1, . . . , t − Lastπ (t, vt ) − 1
respectively.
We define the infinite horizon limit-average (expected) reward as for the multiplicative
discounting in (2). Value decision problems are defined analogously to Definition 2.
The following theorem shows that the rsum -value decision problem remains NP-hard
under any decay profile (the proof is given in the appendix); and that the rsum -values can be
computed in EXPTIME (a version of the augmented weighted graph can be defined similar
(N )
to the multiplicative discounting case to compute the finite horizon reward value Rsum (v)).
I Theorem 16. Let G = (V, E) be a finite directed graph, and let the expected rewards and
reward decay profiles be node independent (and non-zero).
1. The finite horizon rsum -value decision problem is NP-complete in case N is given in unary,
and NP-hard otherwise.
(N )
2. The value Rsum (v) for v ∈ V (given N in binary) is computable in EXPTIME.
PN
Proof. Consider N = |V |−1. Let β = λ· i=0 Sum (Γ[0 .. i]). We reduce deciding existence of
the Hamiltonian path to the rsum -value decision problem. Clearly if there exists a Hamiltonian
path in G, then the answer to the rsum -value decision problem is affirmative. Suppose the
answer to the rsum -value decision problem is affirmative. We show in this case that G must
have a Hamiltonian path. Consider any non-Hamiltonian path π = v0 , . . . , vN of length N .
We show rsum (π) < β. We have
N

(N )

β − rsum (π) X
=
ai ,
λ
i=0
where
(
ai =

0

if vi does not appear in v0 , v1 , . . . , vi−1

Sum (Γ[0 .. i]) − Sum (Γ[0 .. Lastπ (i, vi ) − 1])

otherwise.

Observe that
Sum (Γ[0 .. i]) − Sum (Γ[0 .. Lastπ (i, vi ) − 1]) > 0
in case Lastπ (i, vi ) < i + 1, i.e., if vi has appeared in the path prefix v0 , v1 , . . . , vi−1 . Since
we must have at least one node which appears twice in π, we have that at least one ai in
PN
J
i=0 ai must be strictly positive. This concludes the proof.
In the infinite horizon case, a truncated weighted graph can be defined along the lines of
P∞
(N )
e K to compute -approximate bounds on Rsum
G
(v) (even if
i=0 Γv (i) = ∞). In this case,
given  > 0, the constant K depends on the rate of decay of the sequences Γv .
Two-Player Turn-Based Game Setting. In this setting, the nodes of the graph are
partitioned into player-1 and player-2 nodes, with the outgoing edges from a node being
controlled by the respective player. The objective of player 1 (the collecting agent) is to
N
maximise its reward (rsum
(π) or rav (π)) when facing an adversarial player 2 (as earlier, in
this setting the collecting agent does not receive information about the actual generated
reward instances). Plays and strategies are defined in the standard way (see e.g., [26]). It
can be checked that the augmented weighted graphs of Sections 3 and 4 also work in this
(N )
game-based setting, and thus we obtain algorithms for computing Rsum (v) and -optimal
Rav (v) values applying algorithms for shortest path and mean-payoff games [9, 26].

XX:15

XX:16

The Robot Routing Problem for Collecting Aggregate Stochastic Rewards

6

Conclusion and Open Problems

We have introduced the robot routing problem, which is a reward collection problem on
graphs in which the reward structure combines spatial aspects with dynamic and stochastic
reward generation. We have studied the computational complexity of the finite and infinitehorizon versions of the problem, as well as the strategy complexity of the infinite-horizon case.
We have shown that optimal strategies need memory in general, and that strategies based
on last visitation records do not suffice. However, the important question about whether
finite-memory suffices for the infinite-horizon optimal path problem or infinite memory is
needed remains open. In case finite-memory suffices, it will be desirable to provide an
algorithm for precisely solving the infinite-horizon value problem. So far we have only given
methods for approximating the optimal solution.
Another interesting line of future work is the generalization of the model to incorporate
timing constraints. More specifically, in this work we have assumed that all the rewards
accumulated at a node are instantaneously collected. This assumption is justified by the
fact that in many request-serving scenarios the time taken to serve the requests at a given
location is negligible compared to the time necessary to travel between the locations. A more
precise model, however, would have to incorporate the serving time per node, which would
depend on the amount of collected reward. This would imply that the elapsed time becomes
a random variable, while in our current model it is deterministic.
Other extensions include the setting where the robot can react to the environment by
observing the collected rewards, or observing the accumulated rewards at nodes of the graph,
or where there is probabilistic uncertainty in the transitions of the robot in the graph. Finally,
the robot routing problem presents new challenges for development of efficient approximation
algorithms, which is a major research direction concerning path optimization problems.

References
1

Sofia Amador, Steven Okamoto, and Roie Zivan. Dynamic multi-agent task allocation with
spatial and temporal constraints. In Proceedings of the Twenty-Eighth AAAI Conference
on Artificial Intelligence, pages 1384–1390. AAAI Press, 2014. URL: http://dl.acm.org/
citation.cfm?id=2615731.2616029.

2

Nikhil Bansal, Avrim Blum, Shuchi Chawla, and Adam Meyerson. Approximation algorithms for deadline-TSP and vehicle routing with time-windows. In Proceedings of the
36th Annual ACM Symposium on Theory of Computing 2004, pages 166–174. ACM, 2004.
doi:10.1145/1007352.1007385.

3

Dimitris J. Bertsimas and Garrett J. van Ryzin. A stochastic and dynamic vehicle routing
problem in the Euclidean plane. Operations Research, 39(4):601–615, 1991. doi:10.1287/
opre.39.4.601.

4

Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, and Maria
Minkoff. Approximation algorithms for orienteering and discounted-reward TSP. SIAM J.
Comput., 37(2):653–670, 2007. doi:10.1137/050645464.

5

Patricia Bouyer, Piotr Hofman, Nicolas Markey, Mickael Randour, and Martin Zimmermann. Bounding average-energy games. In Foundations of Software Science and Computation Structures: 20th International Conference, FOSSACS 2017, pages 179–195. Springer
Berlin Heidelberg, 2017. doi:10.1007/978-3-662-54458-7_11.

6

Tomás Brázdil, Petr Hlinený, Antonín Kucera, Vojtech Rehák, and Matús Abaffy. Strategy
synthesis in adversarial patrolling games. CoRR, abs/1507.03407, 2015.

R. Dimitrova, I. Gavran, R. Majumdar, V. S. Prabhu, and S. E. Z. Soudjani

7

8

9
10

11

12

13

14
15

16
17

18

19

20

21
22

23

Francesco Bullo, Emilio Frazzoli, Marco Pavone, Ketan Savla, and Stephen L. Smith. Dynamic vehicle routing for robotic systems. Proceedings of the IEEE, 99(9):1482–1504, 2011.
doi:10.1109/JPROC.2011.2158181.
Krishnendu Chatterjee and Vinayak S. Prabhu. Quantitative temporal simulation and
refinement distances for timed systems. IEEE Trans. Automat. Contr., 60(9):2291–2306,
2015. doi:10.1109/TAC.2015.2404612.
Andreas Darmann, Ulrich Pferschy, and Joachim Schauer. On the shortest path game.
Discrete Applied Mathematics, 217(P1):3–18, 2017. doi:10.1016/j.dam.2015.08.003.
Ali Ekici, Pinar Keskinocak, and Sven Koenig. Multi-robot routing with linear decreasing
rewards over time. In 2009 IEEE International Conference on Robotics and Automation,
ICRA 2009, pages 958–963. IEEE, 2009. doi:10.1109/ROBOT.2009.5152803.
Ali Ekici and Anand Retharekar. Multiple agents maximum collection problem with time
dependent rewards. Computers & Industrial Engineering, 64(4):1009–1018, 2013. doi:
10.1016/j.cie.2013.01.010.
Sadegh Esmaeil Zadeh Soudjani and Alessandro Abate. Adaptive and sequential gridding
procedures for the abstraction and verification of stochastic processes. SIAM Journal on
Applied Dynamical Systems, 12(2):921–956, 2013. doi:10.1137/120871456.
Sadegh Esmaeil Zadeh Soudjani and Rupak Majumdar. Controller synthesis for reward
collecting Markov processes in continuous space. In Proceedings of the 20th International
Conference on Hybrid Systems: Computation and Control, HSCC ’17, pages 45–54, New
York, NY, USA, 2017. ACM. doi:10.1145/3049797.3049827.
Yuri Gurevich and Leo Harrington. Trees, automata, and games. In Proc. Symposium on
Theory of Computing, pages 60–65. ACM Press, 1982. doi:10.1145/800070.802177.
Satoshi Hoshino and Shingo Ugajin. Adaptive patrolling by mobile robot for changing
visitor trends. In 2016 IEEE/RSJ International Conference on Intelligent Robots and
Systems (IROS), pages 104–110, 2016. doi:10.1109/IROS.2016.7759041.
Richard M. Karp. A characterization of the minimum cycle mean in a digraph. Discrete
Mathematics, 23(3):309–311, September 1978. doi:10.1016/0012-365X(78)90011-0.
Anthonius W. J. Kolen, Alexander H. G. Rinnooy Kan, and Henricus W. J. M. Trienekens.
Vehicle routing with time windows. Oper. Res., 35(2):266–273, April 1987. doi:10.1287/
opre.35.2.266.
Justin Melvin, Pinar Keskinocak, Sven Koenig, Craig A. Tovey, and Banu Yuksel Ozkaya.
Multi-robot routing with rewards and disjoint time windows. In 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2332–2337. IEEE, 2007.
doi:10.1109/IROS.2007.4399625.
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, USA, 1st edition, 1994. doi:
10.1002/9780470316887.
Ruben Stranders, Enrique Munoz de Cote, Alex Rogers, and Nicholas R. Jennings. Nearoptimal continuous patrolling with teams of mobile information gathering agents. Artificial
Intelligence, 195:63 – 105, 2013. doi:10.1016/j.artint.2012.10.006.
Robert Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146–160, 1972. doi:10.1137/0201010.
Wolfgang Thomas. On the synthesis of strategies in infinite games. In STACS 95: Theoretical Aspects of Computer Science, volume 900 of Lecture Notes in Computer Science, pages
1–13. Springer-Verlag, 1995. doi:10.1007/3-540-59042-0_57.
Pieter Vansteenwegen, Wouter Souffriau, and Dirk Van Oudheusden. The orienteering
problem: A survey. European Journal of Operational Research, 209(1):1–10, 2011. doi:
10.1016/j.ejor.2010.03.045.

XX:17

XX:18

The Robot Routing Problem for Collecting Aggregate Stochastic Rewards

24

25

26

Changyun Wei, Koen V. Hindriks, and Catholijn M. Jonker. Dynamic task allocation for
multi-robot search and retrieval tasks. Appl. Intell., 45(2):383–401, 2016. doi:10.1007/
s10489-016-0771-5.
Tichakorn Wongpiromsarn, Alphan Ulusoy, Calin Belta, Emilio Frazzoli, and Daniela Rus.
Incremental synthesis of control policies for heterogeneous multi-agent systems with linear
temporal logic specifications. In 2013 IEEE International Conference on Robotics and
Automation, pages 5011–5018, 2013. doi:10.1109/ICRA.2013.6631293.
Uri Zwick and Mike Paterson. The complexity of mean payoff games on graphs. Theor.
Comput. Sci., 158(1&2):343–359, 1996. doi:10.1016/0304-3975(95)00188-3.

Appendix
A

Optimal Path for Example 3

Since the graph Ge is strongly connected, the optimal path is independent of the initial
state. We can also neglect a finite prefix of any path with respect to the computation of the
optimal limit-average collected rewards. Any path in the graph Ge can be (after neglecting
a finite prefix) (abc)w or (ad)w or can be presented as π = (abc)n0 (ad)m0 (abc)n1 (ad)m1 . . .
for unique sequences {nk }k and {mk }k where nk , mk ∈ Z+ . In the following we focus on
the limit-average cost function cav (π) and provide a path-independent lower bound which
is also achievable by some paths in the graph. To study the cav (π), we need to compute
(N )
lim supN →∞ of the fraction csum (π)/(N + 1). Since we intend to provide a lower bound for
this quantity, we focus on the limiting behavior of the fraction only for the subsequence
Pna
{ k=0
(3nk + 2mk ) − 1 | na = 1, 2, . . .}. The finite-horizon cost associated to π for the
Pna
horizon N = k=0
(3nk + 2mk ) − 1 is the following
)
c(N
sum (π) = g0 (γ, n0 , m0 ) +

+

na
X
 2

γ + 2γ 2mk−1 +3 + (3nk − 3)γ 3
k=1
na
X

 3

γ + γ 3nk +2 + (2mk − 2)γ 2 ,

k=1

where g0 (γ, n0 , m0 ) is the polynomial that includes the terms generated by the prefix
(abc)n0 (ad)m0 . Then
Pna
(N )
f (γ, nk , mk ) g0 (γ, n0 , m0 ) + 2γ 2m0 +3 − 2γ 2mn +3
csum (π)
Pna
= Pk=1
+
na
N +1
k=0 (3nk + 2mk )
k=0 (3nk + 2mk )
where f (γ, nk , mk ) := (2mk − 1)γ 2 + (3nk − 2)γ 3 + 2γ 2mk +3 + γ 3nk +2 . The second fraction
in the right-hand side goes to zero for na → ∞ thus the limit of the fraction is the same as
the following
P
Pna
(na )
(n )
X
aij a (3i + 2j)
f (γ, nk , mk )
f (γ, i, j)
i,j=1 aij f (γ, i, j)
k=1
Pna
=
,
=P
P
(n
)
(n
)
a
a
3i + 2j
k=1 (3nk + 2mk )
i,j=1
i,j=1 aij (3i + 2j)
i1 ,j1 =1 ai1 j1 (3i1 + 2j1 )
(8)
(n )

where aij a is the number of pairs (i, j) that appear in the finite sequence {(nk , mk ) | k =
1, 2, . . . , na }. This equality indicates that (8) is a convex combination of fractions f (γ, i, j)/(3i+
2j) thus cav (π) is lower bounded by


f (γ, i, j)
cav (π) ≥ inf
i, j ∈ Z+ .
(9)
3i + 2j

R. Dimitrova, I. Gavran, R. Majumdar, V. S. Prabhu, and S. E. Z. Soudjani

XX:19

Note that f (γ, i, j)/(3i + 2j) is exactly the cost of path π with the constant sequences nk = i
and mk = j for all k. Therefore, inequality (9) states that for the graph of Example 3, the
cost of non-periodic paths can not be less that the minimum cost of periodic paths. Then
we need to compare a countable number of polynomials and find their minimum over the
interval γ ∈ (0, 1). Such a comparison reveals that there are two support polynomials with
(i, j) equal to (1, 1), (2, 1). There is also one limit polynomial in which j is fixed and i goes
to infinity. This polynomial γ 3 is not present in (9) explicitly but is generated by the path
(abc)w which we left a side from the beginning. This completes the proof of computation in
Example 3.

B

Missing Proofs from Section 3

The NP-hardness result (Theorem 4) for γ < 1 is based on the following lemma.
I Lemma 17. For any finite graph G = (V, E) with |V | = nv , v ∈ V and γ ∈ (0, 1), we have
that

λ nv − (nv + 1)γ + γ nv +1
nv −1
Rsum (v) ≤
.
(10)
(1 − γ)2
The equality holds if and only if the graph has a Hamiltonian path starting from v.
Proof. The definition of Lastπ (t, v) implies that Lastπ (t, v) ≤ t + 1. Then for any path π
with |π| = nv − 1 and π[0] = v,
v −1
cnsum
(π) =

nX
v −1
t=0

γ Lastπ (t,π[t]) ≥

nX
v −1

γ t+1 =

t=0

γ(1 − γ nv )
1−γ

λ γ(1 − γ nv )
nv λ
nv −1
−
,
⇒rsum
(π) ≤
1−γ
1−γ 1−γ
which proves (10). If the path π is Hamiltonian, then the path does not contain any repeated
node and Lastπ (t, π[t]) = t + 1 thus π is optimal and achieves the upper bound in (10). For
the other direction, we show that a path π that satisfies the condition of the claim is a
Hamiltonian path. Suppose that this is not the case. Since the length of π is nv −1, π contains
at least one repeated node. Thus for at least one index t we have Lastπ (t, π[t]) < t + 1,
Pnv −1 Lastπ (t,π[t])
Pnv −1 t+1
nv −1
and then t=0
γ
> t=0
γ . Therefore, rsum
(π) is strictly less than the
right-hand side of (10), which contradicts the choice of the path π.
J
Theorem 4. The case for γ ∈ (0, 1) can be proved as follows. We reduce the Hamiltonian
path problem to the finite horizon value decision problem as follows. Given a graph G =
(V, E) with |V | = nv , we fix some constants λ and γ. By the inequality we showed in
nv −1
(10),
path if and only if for some v ∈ V we have Rsum
(v) ≥
 G contains a Hamiltonian

nv +1
2
λ nv − (nv + 1)γ + γ
/(1 − γ) . This completes the reduction.
The proof for γ = 1 is similar to the proof of Theorem 16.
J

C

Missing Proofs from Section 4

Lemma 6 For any graph G = (V, E) and any node v0 ∈ V , Rav (v0 ) is bounded as
λ

1 − γp
1 − γ nv
≤ Rav (v0 ) ≤ λ
,
1−γ
1−γ

where nv = |V | and p is the length of the longest simple cycle in G.

(11)

XX:20

The Robot Routing Problem for Collecting Aggregate Stochastic Rewards

Proof. Let π be an infinite path and denote with πN = π[0 . . . N ] the prefix of π of length
N . We apply the inequality of arithmetic and geometric means for n ∈ N
√
a1 +a2 +. . .+an
≥ n a1 a2 . . . an , a1 , a2 , .., an ≥ 0,
n
where the equality holds if and only if all ai ’s are equal. Then we have
PN
P
1
Lastπ (t,π[t])
yv /(N+1)
)
N +1
t=0
v
c(N
(π)
≥
(N
+1)γ
=
(N
+1)γ
,
sum
where yv = 1 + max{j ∈ N | j ≤ N, π[j] = v} if v is visited by πN , otherwise yv = 0. This
(N )
implies that yv ≤ N + 1 and csum (π) ≥ (N + 1)γ nv (N +1)/(N +1) = (N + 1)γ nv . Dividing both
sides by (N + 1) and taking lim supN →∞ gives a general path-independent lower bound
γ nv for cav (π), which also implies Cav (v0 ) = inf π {cav (π) | π[0] = v0 } ≥ γ nv . This proves the
upper bound in (11). The particular path πp = (v1 v2 . . . vp )ω , with v1 v2 . . . vp v1 being the
longest simple cycle, gives the bound Rav (v0 ) ≥ rav (πp ) which is the lower bound in (11). J
I Proposition 18. Strategies based only on last visitation records not suffice for the infinitehorizon optimal path problem.
Proof. Recall that for the graph Ge = (Ve , Ee ) in Figure 1 and γ = 0.26 the path (abcabcad)ω
is optimal. Upon visiting node a the corresponding strategy chooses one of the nodes b or d
depending on the number of visits to b since the last occurrence of d. We will now show that
every strategy based only on the order of last visits results in an ultimately periodic path the
loop of which is one of the cycles (abc)ω , or (ad)ω , or (abcad)ω , and is hence not optimal.
b e = (Vbe , E
be ) with set of states Vbe = Ve × O, where the
To this end, consider the graph G
set O consists of the vectors of elements of V , of length less than or equal to 4, that represent
the order of last occurrences of the nodes V in the traversed path. For example, ha, c, bi
denotes the fact that the last occurrence of a was after the last occurrence of c, which was
after the last occurrence of b, and node d has not occurred yet in the path. The edge relation
be ⊆ Vbe × Vbe , where (v, o) → (v 0 , o0 ) implies (v, v 0 ) ∈ Ee , updates the last occurrence order
E
in the expected way, depending on the taken edge (v, v 0 ).
b e that corresponds to (abcabcad)ω is
For example, the unique path in G
π
b = (a, hi)(b, o1 )(c, o2 )(a, o3 )(b, o4 )(c, o5 )(a, o3 )(d, o4 ) · ρbω ,
where
ρb = (a, o6 )(b, o7 )(c, o8 )(a, o9 )(b, o10 )(c, o11 )(a, o9 )(d, o10 )
and
o1 = hai, o2 = hb, ai, o3 = hc, b, ai, o4 = ha, c, bi, o5 = hb, a, ci, o6 = hd, a, c, bi, o7 = ha, d, c, bi,
o8 = hb, a, d, ci, o9 = hc, b, a, di, o10 = ha, c, b, di, o11 = hb, a, c, di.
Since there are occurrences of node (a, o3 ) in the path followed by different nodes, (b, o4 )
and (d, o4 ) respectively, and similarly for node (a, o9 ), followed by either (b, o10 ) or (d, o10 ),
b
the path π
b cannot be generated by a memoryless strategy in G.
b
In general, in G there are 5 possible reachable states of the form (a, o), namely, (a, hi),
b (that
(a, hc, b, ai), (a, hd, ai), (a, hd, a, c, bi) and (a, hc, b, a, di). A memoryless strategy in G
is, a strategy that only records the order of last visits) must map each of these nodes to a
unique successor node. Thus, such a strategy results in one of the paths (abc)ω , abc(ad)ω ,
(abcad)ω , (ad)ω , ad(abc)ω , or (adabc)ω .
For γ = 0.26 each of these paths has reward strictly smaller than (abcabcad)ω and is
hence not optimal.This concludes the proof.
J

