Multi-Robot Routing for Persistent Monitoring with Latency Constraints
Ahmad Bilal Asghar
Stephen L. Smith
Shreyas Sundaram
Abstract— In this paper we study a multi-robot path planning
problem for persistent monitoring of an environment. We
represent the areas to be monitored as the vertices of a weighted
graph. For each vertex, there is a constraint on the maximum
time spent by the robots between visits to that vertex, called
the latency, and the objective is to find the minimum number of
robots that can satisfy these latency constraints. The decision
version of this problem is known to be PSPACE-complete. We
present a O(log ρ) approximation algorithm for the problem
where ρ is the ratio of the maximum and the minimum latency
constraints. We also present an orienteering based heuristic
to solve the problem and show through simulations that in
most of the cases the heuristic algorithm gives better solutions
than the approximation algorithm. We evaluate our algorithms
on large problem instances in a patrolling scenario and in a
persistent scene reconstruction application. We also compare
the algorithms with an existing solver on benchmark instances.
I. INTRODUCTION
With the rapid development in field robotics, teams of
robots can now perform long term monitoring tasks. Ex-
amples of such tasks include infrastructure inspection [1]
to detect presence of anomalies or failures; patrolling for
surveillance [2], [3] to detect threats in the environment;
3D reconstruction of scenes [4], [5] in changing environ-
ments; informative path planning [6] for observing dynamic
properties of an area; and forest fire monitoring [7]. In such
persistent monitoring scenarios, locations in an environment
need to be visited repeatedly by a team of robots. Since the
duration of the events, or the rate of change of the properties
to be monitored, can be different for different locations,
each location will have a different latency constraint, which
specifies the maximum time allowed between consecutive
visits to that location. In this paper we study the problem of
finding a set of paths that continually visit a set of locations
while collectively satisfying the latency constraints on each
location.
We represent the locations of interest in the environment
as the vertices of a graph. The edge weights give the travel
time between the vertices and each vertex has a latency
constraint that defines the maximum allowed time between
two consecutive visits to that vertex. The problem is to find
walks on the graph for the minimum number of robots that
can satisfy the latency constraints.
Related Work: Persistent monitoring problems have been
extensively studied in the literature [8], [9], [10], [11].
This research is partially supported by the Natural Sciences and Engi-
neering Research Council of Canada (NSERC).
Ahmad Bilal Asghar and Stephen L. Smith are with the Department of
Electrical and Computer Engineering, University of Waterloo, Waterloo, ON
N2L 3G1 Canada. Shreyas Sundaram is with the School of Electrical and
Computer Engineering, Purdue University, West Lafayette, IN 47907 USA.
In [12], persistent coverage using multiple robots in a contin-
uous environment is considered. The problem of determining
a visit sequence for a set of locations along with the time
spent at each location to gather information is considered
in [13], [14]. For the problem with latency constraints, the
authors in [15] use incomplete greedy heuristics to find if a
single robot can satisfy the constraints on all vertices of a
graph. They show that if a solution exists, then a periodic
solution also exists. In this paper, we consider the multi-
robot problem and our objective is to minimize the number
of robots that can satisfy the latency constraints on the given
graph. This problem has been considered in [16], [17], where
it is called Cyclic Routing of Unmanned Aerial Vehicles.
The decision version of the problem for a single robot is
shown to be PSPACE-complete in [17]. The authors also
show that the length of even one period of a feasible walk can
be exponential in the size of the problem instance. In [16],
the authors propose a solver based on Satisfiability Modulo
Theories (SMT). To apply an SMT solver, they impose an
upper bound on the length of the period of the solution.
Since an upper bound is not known a priori, the solver will
not return the optimal solution if the true optimal period
exceeds the bound. The authors generate a library of test
instances, but since their algorithm scales exponentially with
the problem size, they solve instances up to only 7 vertices.
We compare our algorithms with their solver and show that
our algorithms run over 500 times faster on average and
return solutions with the same number of robots on 98% of
the benchmark instances provided by [16].
A related single robot problem is studied in [18] where
each vertex has a weight associated with it and the objective
is to minimize the maximum weighted latency (time between
consecutive visits) for an infinite walk. The authors provide
an approximation algorithm for this problem. The authors
in [2] study the single robot problem for a security applica-
tion where the length of attack on each vertex of the graph
is given. To intercept all possible attacks, they design an
algorithm to repeatedly patrol all vertices with the maximum
revisit time to each vertex less than its length of attack.
Timed automata have been used to model general multi-
robot path planning problems [19] as the clock states can
capture the concurrent time dependent motion. In [20],
temporal logic constraints are used to specify high level
mission objectives to be achieved by a set of robots. The
routing problem with latency constraints can also be modeled
as a timed automaton since multiple robots may require
synchronization to satisfy the latency constraints. A timed
automaton based solution to the problem is presented in [21],
however it is shown to perform more poorly than the SMT-
based approach in [16], which we use as a comparison for
arXiv:1903.06105v1  [cs.RO]  14 Mar 2019
our proposed algorithms.
Several vehicle routing problems are closely related to
persistent monitoring with latency constraints. In the ve-
hicle routing problem with time windows [22], customers
have to be served within their time windows by several
vehicles with limited capacity. The goal is to minimize
the number of vehicles required. Since the problem does
not require repeated visits, the length of the resulting tour
is polynomially bounded, and thus the problem is in NP.
In the deadline-TSP [23], the vertices have deadlines for
first visits. In the period vehicle routing problem [24], the
problem is to design routes for each day of a given period
where each customer may require a number of visits (in a
given number of allowable combinations) during this period.
The main difference between these problems and the cyclic
routing problem with latency constraints is that the latency
constraints need to be satisfied indefinitely which makes it
harder than these problems.
Contributions: We present a O(log ρ) approximation algo-
rithm for the problem where ρ is the ratio of the maximum
and the minimum latency constraints (Section IV). We also
provide an algorithm for the problem of minimizing the
maximum weighted latency with multiple robots and show
that an approximation algorithm for this problem yields a bi-
criterion approximation for our problem. We present an ori-
enteering based heuristic algorithm to solve the problem and
prove its completeness (Section V). We show through simu-
lations that the heuristic algorithm gives better solutions than
the approximation algorithm. We evaluate the performance
of the algorithms on large problem instances in a patrolling
scenario and in an image collection application for 3D scene
reconstruction. We also compare our algorithms against an
existing solver on benchmark instances (Section VI).
II. BACKGROUND AND NOTATION
Given a directed graph G = (V, E) with edge lengths l(e)
for each e ∈E, a simple walk in graph G is defined as a
sequence of vertices (v1, v2, . . . , vk) such that (vi, vi+1) ∈E
for each 1 ≤i < k. An infinite walk is a sequence of vertices
(v1, v2, . . .) such that (vi, vi+1) ∈E for each i ∈N. Given
walks W1 and W2, [W1, W2] represents the concatenation of
the walks. Given a finite walk W, an infinite periodic walk is
constructed by concatenating infinite copies of W together,
and is denoted by ∆(W). A cycle is a simple walk that starts
and ends at the same vertex with no other vertex appearing
more than once.
In general, a walk can stay for some time at a vertex
before traversing the edge towards the next vertex. Therefore
we define a timed walk W in graph G as a sequence
(o1, o2, . . . , ok), where oi = (vi, ti) is an ordered pair that
represents the holding time ti that the walk W spends at
vertex vi, such that (vi, vi+1) ∈E for each 1 ≤i < k.
The definitions of infinite walk and periodic walk can be
extended to infinite timed walk and periodic timed walk. A
walk with ordered pairs of the form (vi, 0) becomes a simple
walk. The vertices traversed by walk W are given by V (W)
and the length of walk W = ((v1, t1), (v2, t2), . . . , (vk, tk))
is given by l(W) = Pk−1
i=1 l(vi, vi+1) + Pk
i=1 tk. Since
we are considering a multi-robot problem, synchronization
between the walks is important. Given a set of walks W =
{W1, W2, . . . , Wk} on graph G, we assume that at time 0,
each robot i is at the first vertex vi
1 of its walk Wi, and will
spend the holding time ti
1 at that vertex before moving to vi
2.
Given a graph G and length λ, the MINIMUM CYCLE
COVER PROBLEM (MCCP) is to find minimum number of
cycles that cover the whole graph such that the length of the
longest cycle is at most λ. This problem is NP-hard and a
14/3-approximation algorithm for MCCP is given in [25].
Given a graph G = (V, E) with vertex weights ψi for
i ∈V , and length λ, the ORIENTEERING problem is to find
a path from vertex s to t of length at most λ such that the
sum of the weights on the vertices in the path is maximized.
This problem is also NP-hard and a (2 + ϵ)-approximation
is given in [26].
III. PROBLEM STATEMENT
Let G = (V, E) be a directed weighted graph with edge
lengths l(e) for each e ∈E. The edge lengths are metric and
represent the time taken by the robot to travel between the
vertices. The latency constraint for each vertex v is denoted
by r(v) and represents the maximum time allowed between
consecutive visits to v. The time taken by the robots to
inspect a vertex can be added to the length of the incoming
edges of that vertex to get an equivalent metric graph with
zero inspection times and modified latency constraints [16].
Hence, we assume that the time required by the robots to
inspect a vertex is zero. We formally define the problem
statement after the following definition.
Definition III.1 (Latency). Given a set of infinite walks
W = {W1, W2, . . . , Wk} on a graph G, let av
i represent
the ith arrival time for the walks to vertex v. Similarly, let
dv
i represent the ith departure time from vertex v. Then the
latency L(W, v) of vertex v on walks W is defined as the
maximum time spent away from vertex v by the walks, i.e.,
L(W, v) = supi (av
i+1 −dv
i ).
Problem III.2 (Minimizing Robots with Latency Con-
straints). Given the latency constraints r(v), ∀v ∈V , the
optimization problem is to find a set of walks W with
minimum cardinality such that L(W, v) ≤r(v), ∀v ∈V .
The
decision
version
of
the
problem
is
to
deter-
mine whether there exists a set of R walks W
=
{W1, W2, . . . , WR} such that L(W, v) ≤r(v) for all v ∈V .
Note that a general solution to Problem III.2 will be a set of
timed walks with possibly non-zero holding times.
In this problem definition, the graph and its edge lengths
capture the robot motion in the environment. This graph
can be generated from a probabilistic roadmap, or any other
environment decomposition method. The latency constraints
provide the maximum allowable time between visits to a
vertex. For example, in dynamic scene reconstruction, each
vertex corresponds to a viewpoint [4]. The latency constraints
may encode the maximum staleness of information that can
be tolerated for the voxels captured at that viewpoint.
Fig. 1: A graph with three vertices and the walk (a, b, a, c). The length of
shown edges is one. Equally placing two robots on this walk does not halve
the latencies.
A. Multiple Robots on the Same Walk
In multi-robot problems that involve finding cycles or tours
in a graph, equally placing n robots on a tour reduces the
cost of that tour by a factor of n [27]. That is not true for
Problem III.2: if a periodic walk W gives latency L(W, v) on
vertex v, equally spacing more robots on one period of that
walk does not necessarily reduce the latency for that vertex.
Figure 1 gives an example of such a walk. The latency of
vertices a, b and c on the walk (a, b, a, c) are 2, 4 and 4
respectively. The length of one period of the walk is 4. If
we place another robot following the first robot with a lag
of 2 units, the latency of vertex a remains the same. If we
place the second robot at a lag of 1 unit, the latency will
reduce to 1 for vertex a and 3 for vertices b and c. Hence
we need more sophisticated algorithms than finding a walk
for a single robot and adding more robots on that walk until
the constraints are satisfied, unless that walk is a cycle.
IV. APPROXIMATION ALGORITHM
Since Problem III.2 is PSPACE-complete, we resort to
finding approximate and heuristic solutions to the problem.
In this section, we present an approximation algorithm for
the problem.
A. O(log ρ) Approximation
We first mention a simple approach to the problem and
then improve it incrementally to get the approximation
algorithm. One naive solution is to find a TSP tour of the
graph and equally place robots on that tour to satisfy all
the latency constraints. However, a single vertex with a
very small r(v) can result in a solution with the number
of robots proportional to 1/r(v). To solve this issue, we can
partition the vertices of the graph such that the latencies in
one partition are close to each other, and then place robots
on the TSP tour of each partition. If more than one robot
is required for a partition V ′, then another approach is to
solve the MCCP for that partition. The benefit of using the
MCCP over placing multiple robots on a TSP is that if all
the vertices in V ′ had the same latency requirement, then we
have a guarantee on the number of cycles required for that
partition. However, a general solution to the problem might
not consist of simple cycles. Lemma IV.2 relates solutions
consisting of cycles to general solutions and shows that a
solution consisting of cycles will have latencies no more
than twice that of any general solution with same number of
robots. Therefore, if we solve the MCCP on a partition with
its latency constraints multiplied by two, we have a guarantee
on the number of cycles. We can then use the naive idea from
TSP based solutions and place multiple robots on each cycle
to satisfy the latency constraints.
Algorithm 1: APPROXIMATIONALGORITHM
Input: Graph G = (V, E), latency constraints r(v), ∀v
Output: A set of walks W, such that L(W, v) ≤r(v)
1: Let rmax = maxv r(v), rmin = minv r(v), ρ = rmax
rmin
2: if rmax/rmin is an exact power of 2 then ρ = rmax
rmin + 1
3: W = {}
4: Let Vi be the set of vertices v such that rmin2i−1 ≤
r(v) < rmin2i for 1 ≤i ≤⌈log2 ρ⌉
5: for i = 1 to ⌈log2 ρ⌉do
6:
C = MCCP(Vi, rmin2i+1)
7:
for C in C do
8:
Equally place ⌈l(C)/ minv∈V (C) r(v)⌉robots on
cycle C to get walks W′
9:
W = {W, W′}
The approximation algorithm is given in Algorithm 1.
The first four lines of the algorithm partition the vertices
according to their latency constraints. For each of those
partitions, the function MCCP(V, λ) called in line 6 uses
an approximation algorithm for the minimum cycle cover
problem from [25]. Then, the appropriate number of robots
are placed on each cycle returned by the MCCP function
to satisfy the latency constraints. We will need the fol-
lowing definition to establish the approximation ratio of
Algorithm 1. A similar relaxation technique was used in [18].
Definition IV.1. Let rmin = minv r(v). The latency con-
straints of the problem are said to be relaxed if for any
vertex v, its latency constraint is updated from r(v) to
¯r(v) = rmin2x such that x is the smallest integer for which
r(v) < rmin2x.
We will also need the following lemma that follows from
Lemma 2 in [27] and we omit the proof for brevity.
Lemma IV.2. For any set of walks W on an undirected
metric graph with vertices V , there exists a set of walks W′
on V with |W| = |W′|, such that each walk Wi ∈W′ is a
cycle of vertices Vj ⊆V , and the sets Vj partition V , and
maxv L(W′, v) ≤2 maxv L(W, v).
The following proposition gives the approximation factor
of Algorithm 1.
Proposition IV.3. Given an undirected metric graph G =
(V, E) with latency constraints r(v) for v ∈V , Algorithm 1
constructs R walks W = {W1, W2, . . . , WR} such that
L(W, v) ≤r(v) for all v ∈V and R ≤4α⌈log(ρ)⌉ROPT,
where ROPT is the minimum number of robots required to
satisfy the latency constraints and α is the approximation
factor of MCCP.
Proof. Given that ROPT robots will satisfy the latency con-
straints r(v), they will also satisfy the relaxed constraints
¯r(v) since ¯r(v) > r(v). Therefore, there exists a set of at
most ROPT walks W∗such that for v ∈Vi, L(W∗, v) ≤
rmin2i.
Using Lemma IV.2, given the set W∗, ROPT cycles can
be constructed in Vi such that the latency of each vertex in
Vi is at most rmin2i+1. Hence, running an α approximation
algorithm for Minimum Cycle Cover Problem (MCCP) on
the subgraph with vertices Vi and with maximum cycle
length rmin2i+1 will not return more than αROPT cycles.
Since MCCP returns cycles, equally placing k robots on
each cycle will reduce the latency of each vertex on that cycle
by a factor of k. As r(v) ≥rmin2i+1/4 for each v ∈Vi, we
will need to place at most 4 robots on each cycle.
Finally, since there are at most ⌈log ρ⌉partitions Vi, the
algorithm will return R ≤4α⌈log(ρ)⌉ROPT walks.
Runtime: Since we run the approximation algorithm for
MCCP on partitions of the graph, the runtime of Algorithm 1
is the same as that of the approximation algorithm of MCCP.
That is because the runtime of MCCP is superlinear, so if
P |Vi| = |V |, then P |Vi|p ≤|V |p for p ≥1.
Remark IV.4 (Heuristic Improvements). Instead of finding
cycles using MCCP for each partition Vi in line 6 of the
algorithm, we can also equally place robots on the Traveling
Salesman Tour of Vi to get a feasible solution. In practice, we
use both of these methods and pick the solution that gives the
lower number of robots for each Vi. This modification can
return better solutions to the problem but does not improve
the approximation guarantee established in Proposition IV.3.
B. Relation to Min Max Weighted Latency
The approximation algorithm and analysis presented above
helps in formulating an algorithm for the multi-robot version
of a related problem. In [18], the authors study in detail the
problem of minimizing the maximum weighted latency of a
graph given a single robot. Here we define the multiple robot
version of the problem.
Problem IV.5 (Minimizing Maximum Weighted Latency:).
Given a graph G = (V, E) with weights φ(v) for v ∈V ,
and a set of walks W, the weighted latency of v is defined
as C(W, v) = φ(v)L(W, v). Given the number of robots R,
the problem of minimizing maximum weighted latency is to
find a set of R infinite walks W = {W1, W2, . . . , WR} such
that the cost maxv C(W, v) is minimized.
Without loss of generality, φ(v) is assumed to be normal-
ized such that maxv φ(v) = 1. In this section we relate this
problem to Problem III.2.
In [18][Algorithm 2], an approximation algorithm for the
single robot version of Problem IV.5 is given. We will refer to
that approximation algorithm as MINMAXLATENCYONER-
OBOT(Gj), which returns a walk in graph Gj such that the
maximum weighted latency of that walk is not more than
(8 log ρj + 10)OPTj
1, where ρj is the ratio of maximum to
minimum vertex weights in Gj and OPTj
1 is the optimal
maximum weighted latency for one robot in Gj. We use
this approximation algorithm as a subroutine in Algorithm 2
for minimizing the maximum weighted latency with multiple
robots.
Proposition IV.6. Given an instance of Problem IV.5, Algo-
rithm 2 constructs R walks such that the maximum weighted
latency of the graph is not more than ( 8 log ρ
R
+ 10)OPT1
if R ≤log ρ and 3OPT1/⌊R/⌈log ρ⌉⌋otherwise, where
Algorithm 2: LATENCYWALKS
Input: Graph G = (V, E), vertex weights φ(v), ∀v ∈V ,
and number of robots R.
Output: A set of R walks {W1, . . . , WR} in G.
1: ρ = maxi,j φi/φj
2: if maxi,j φi/φj is an exact power of 2 then ρ =
maxi,j φi/φj + 1
3: Let Vi be the set of vertices of weight 1
2i < φ(u) ≤
1
2i−1
for 1 ≤i ≤⌈log2 ρ⌉
4: if R < log ρ then
5:
for j = 1 to R do
6:
Let Gj be a subgraph of G with vertices Vi for
⌈j−1
R log ρ⌉+ 1 ≤i ≤⌈j
R log ρ⌉
7:
Wj = MINMAXLATENCYONEROBOT(Gj)
8: if R ≥log ρ then
9:
Equally space ⌊R/⌈log ρ⌉⌋robots on TSP tour of Vi
for all i to get {W1, . . . , W⌈log ρ⌉⌊
R
⌈log ρ⌉⌋}
10:
for k = R −⌈log ρ⌉⌊
R
⌈log ρ⌉⌋+ 1 to R do
11:
Find subset Vi that has the maximum cost with
currently assigned robots
12:
Equally space all the robots on Vi along with
robot k to get Wk
ρ = max φ(vi)
φ(vj) and OPT1 is the maximum weighted latency
of the single optimal walk.
Proof. The maximum vertex weight in the subgraph Gj
constructed at line 6 of the algorithm will be at most
1/(2
j−1
R
log ρ), whereas the minimum vertex weight in Gj
will be at least 1/(2
j
R log ρ). Hence the ratio of the maximum
to minimum vertex weights in Gj will be at most ρj = 2
log ρ
R .
Therefore, the approximation algorithm for one robot will
return a walk Wj such that the maximum weighted latency
of Wj will not be more than (8 log ρj +10)OPTj
1. Moreover,
OPTj
1 ≤OPT1 and hence if R < log ρ, the maximum
weighted latency will be at most ( 8 log ρ
R
+ 10)OPT1.
The TSP tour of Vi is an optimal solution when all the ver-
tex weights in Vi are equal. Since the vertex weights within
Vi differ by a factor of 2 at most, and the approximation
factor of TSP tour in metric graphs is 3/2, the maximum
weighted latency of the TSP tour will be at most 3OPT1.
Equally placing ⌊R/⌈log ρ⌉⌋will decrease the latency of all
the vertices by a factor of ⌊R/⌈log ρ⌉⌋.
Note that Algorithm 2 bounds the cost of the solution
by a function of the optimal cost of a single robot. This
algorithm shows that R robots can asymptotically decrease
the weighted latency given by a single walk by a factor of R,
which is not straightforward for this problem as discussed in
Section III-A.
Now we show that if there is an approximation algorithm
for Problem IV.5, it can be used to solve Problem III.2 using
the optimal number of robots but with the latency constraints
relaxed by a factor α. This is referred to as a (α, 1)-bi-
criterion algorithm [28] for Problem III.2.
Proposition IV.7. If there exists an α-approximation algo-
rithm for Problem IV.5, then there exists a (α, 1)-bi-criterion
approximation algorithm for Problem III.2.
We will need the following lemma relating the two prob-
lems to prove the proposition. Given an instance of the
decision version of Problem III.2 with R robots, let us define
an instance of Problem IV.5 by assigning φ(v) = rmin
r(v), ∀v ∈
V , where rmin = minv r(v).
Lemma IV.8. An instance of the decision version of Prob-
lem III.2 is feasible if and only if the optimal maximum
weighted latency is at most rmin for the corresponding
instance of Problem IV.5.
Proof. If the optimal set of walks W has a cost more than
rmin, then L(W, v) > rmin/φ(v) = r(v) for some vertex v.
Hence the latency constraint for that vertex is not satisfied
and the set of walks W is not feasible.
If the optimal set of walks W has a cost at most rmin,
then L(W, v)φ(v) ≤rmin for all v. Hence, L(W, v) ≤
rmin/φ(v) = r(v). So, the latency constraints are satisfied
for all vertices and W is feasible.
Proof of Proposition IV.7. If a problem instance of Prob-
lem III.2 with R robots is feasible, then by Lemma IV.8
the optimal set of walks has a cost at most rmin. The α-
approximation algorithm for the corresponding Problem IV.5
will return a set of walks W with a cost no more than αrmin.
Hence, L(W, v) ≤αrmin/φ(v) = αr(v), for all v.
Hence, we can use binary search to find the minimum
number of robots for which the α-approximation algorithm
for the corresponding Problem IV.5 results in a latency at
most αr(v) for all v. This will be the minimum number of
robots for which the problem is feasible.
V. HEURISTIC ALGORITHMS
The approximation algorithm for Problem III.2 presented
in Section IV is guaranteed to provide a solution within
a fixed factor of the optimal solution. In this section, we
propose a heuristic algorithm based on the orienteering
problem, which in practice provides high-quality solutions.
A. Partitioned Solutions
In general, walks in a solution of the problem may
share some of the vertices. However, sharing the vertices
by multiple robots requires coordination and communication
among the robots. Such strategies may also require the robots
to hold at certain vertices for some time before traversing
the next edge, in order to maintain synchronization. This is
not possible for vehicles that must maintain forward motion,
such as fixed-wing aircraft. The following example illustrates
that if vertices are shared by the robots, lack of coordination
or perturbation in edge weights can lead to large errors in
latencies.
Example: Consider the problem instance shown in Fig-
ure 2. An optimal set of walks for this problem is given
by {W1, W2, W3} where W1
= ((a, 1), (b, 1)), W2
=
((b, 0), (c, 0)) and W3 = ((c, 0), (d, 1), (c, 1)). Note that
walk W1 starts by staying on vertex a, while W2 leaves
vertex b and W3 leaves vertex c. Also note that any parti-
tioned solution will need 4 robots. Moreover, if the length
of edge {b, c} changes from 3 to 3 −ϵ, (e.g., if the robot’s
speed increases slightly) the latencies of vertices b and c will
keep changing with time and will go up to 5. Hence, a small
deviation in robot speed can result in a large impact on the
monitoring objective.
Fig. 2: A problem instance with an optimal set of walks that share
vertices. The latency constraints for each vertex are written inside that
vertex. The edge lengths are labeled with the edges. The optimal walks
are {W1, W2, W3} where W1 = ((a, 1), (b, 1)), W2 = ((b, 0), (c, 0))
and W3 = ((c, 0), (d, 1), (c, 1)).
Since the above mentioned issues will not occur if the
robots do not share the vertices of the graph, and the problem
is PSPACE-complete even for a single robot, we focus on
finding partitioned walks in this section. The general greedy
approach used in this section is to find a single walk that
satisfies latency constraints on a subset of vertices V ′ ⊆V .
Note that we do not know V ′ beforehand, but a feasible walk
on a subset of vertices will determine V ′. We then repeat this
process of finding feasible walks on the remaining vertices
of the graph until the whole graph is covered.
B. Greedy Algorithm
We now consider the problem of finding a single walk on
the graph G = (V, E) that satisfies the latency constraints
on the vertices in V ′ ⊆V . Given a robot walking on a
graph, let p(k) represent the vertex occupied by the robot
after traversing k edges (after k steps) of the walk. Also,
at step k, let the maximum time left until a vertex i has
to be visited by the robot for its latency to be satisfied be
represented by si(k). If that vertex is not visited by the robot
within that time, we say that the vertex expired. Hence, the
vector s(k) = [s1(k), . . . , s|V ′|(k)]T represents the time to
expiry for each vertex. At the start of the walk, si(0) = r(i),
and si(k) evolves according to the following equation:
si(k) =
(
r(i)
if p(k) = i
si(k −1) −l(p(k −1), p(k))
otherwise.
(1)
We will use the notation si without the step k if it is
clear that we are talking about the current time to expiry.
An incomplete greedy heuristic for the decision version of
the problem with R = 1 is presented in [15]. The heuristic
is to pick the vertex with minimum value of si(k) as the
next vertex to be visited by the robot. This heuristic does
not ensure that all the vertices on the walk will have their
latency constraints satisfied since the distance to a vertex
i to be visited might get larger than si(k). To overcome
this, we propose a modification to the heuristic to apply
it to our problem. Given a walk W on graph G, the
function PERIODICFEASIBILITY(W, G) determines whether
the periodic walk ∆(W) is feasible on the vertices that
are visited by W. This can be done simply in O(|W|)
by traversing the walk [W, W] and checking if the time
to expiry for any of the visited vertices becomes negative.
Given this function, the simple greedy algorithm is to pick
the vertex i = arg min{sj} subject to the constraint that
PERIODICFEASIBILITY([W, i], G) returns true, where W is
the walk traversed so far. The algorithm terminates when all
the vertices are either expired, or covered by the walk.
C. Orienteering Based Greedy Algorithm
Algorithm 3 also finds partitioned walks by finding a
feasible walk on a subset of vertices and then considering
the remaining subgraph. The idea is to visit more vertices
on the way to the greedily picked vertex. From the current
vertex x, the target vertex y is picked greedily as described in
Section V-B. Then the time d is calculated in line 10 which is
the maximum time to go from x to y for which the periodic
walk remains feasible. In line 15, ORIENTEERING(V −
Vexp, x, y, d, ψ) finds a path in the vertices V −Vexp from x
to y of length at most d maximizing the sum of the weights
ψ on the vertices of the path. The set Vexp
represents
the expired vertices whose latencies cannot be satisfied by
the current walk, and they will be considered by the next
robot. The vertices with less time to expiry are given more
importance in the path by setting weight ψi = 1/si for
vertex i. The vertices that are already in the walk will remain
feasible, and so their weight is discounted by a small number
m to encourage the path to explore unvisited vertices.
Algorithm 3: ORIENTEERINGGREEDY
Input: Graph G = (V, E), latency constraints r(v), ∀v
Output: A set of walks W, such that L(W, v) ≤r(v)
1: j = 1, W = {}
2: while V is not empty do
3:
Vexp = {}
4:
si = r(i) for all i ∈V
5:
Wj = pick vertex a randomly from V
6:
while V −V (Wj) −Vexp is not empty do
7:
x = last vertex in Wj
8:
for y ∈V −Vexp in increasing order of s do
9:
if PERIODICFEASIBILITY([Wj, y], G) then
10:
Use binary search between l(x, y) and sy
to get d (time to go from x to y) such that
[Wj, y] remains feasible
11:
for z in V −(Vexp ∪V (Wj)) do
12:
if sz < d + l(y, a) then Vexp =
Vexp ∪z
13:
ψi = 1/si for all non expired vertices i
14:
ψi = mψi for i in V (Wj)
15:
Wj
=
[Wj,ORIENTEERING(V
−
Vexp, x, y, d, ψ)]
16:
Update s using Equation (1)
17:
else
18:
Vexp = Vexp ∪y
19:
W = {W, Wj}, j = j + 1
20:
V = V −V (Wj)
Lemma V.1. Algorithm 3 returns a feasible solution, i.e., for
the set of walks W returned by Algorithm 3, L(W, v) ≤r(v),
for all v ∈V .
Proof. The vertices covered by the walk Wj added to the
solution in line 19 are removed from the set of vertices
before finding the rest of the walks. Hence the latencies of
the vertices V (Wj) will be satisfied by only Wj. We will
show that every time Wj is appended in line 15, it remains
feasible on V (Wj).
Wj starts from a single vertex a, and hence is feasible
at the start. Let us denote W −
j
as the walk before line 15
and W +
j
as the walk after line 15. Due to line 10, if W −
j
is feasible in a particular iteration, then [W −
j , y] will remain
feasible. Hence the only vertices than can possibly have their
latency constraints violated in W +
j
are in the orienteering
path from x to y. Consider any vertex z in the path from
x to y returned by the ORIENTEERING function in line 15.
If z ∈V (W −
j ), then L(W +
j , z) ≤r(z) because of line 10.
If z /∈V (W −
j ), then r(z) = l(W −
j ) + sz and by line 12,
r(z) ≥l(W −
j )+d+l(y, a). As z is only visited once in W +
j ,
L(W +
j , z) = l(W +
j ) ≤l(W −
j ) + d + l(y, a) ≤r(z).
An approximation algorithm for ORIENTEERING can be
used in line 15 of Algorithm 3. In our implementation,
we used an ILP formulation to solve ORIENTEERING. To
improve the runtime in practice, we pre-process the graph
before calling the ORIENTEERING solver to consider only
the vertices z such that l(x, z) + l(z, y) ≤d. We show in
the next section that although the runtime of Algorithm 3 is
more than that of Algorithm 1, it can still solve instances
with up to 90 vertices in a reasonable amount of time, and
it finds better solutions.
VI. SIMULATION RESULTS
We now present the performance of the algorithms pre-
sented in the paper. For the approximation algorithm, we
used the LKH implementation [29] to find the TSP of
the graphs instead of the Christofides approximation al-
gorithm [30]. This results in the loss of approximation
guarantee but gives better results in practice. The orienteering
paths in Algorithm 3 were found using the ILP formulation
from [31] and the ILP’s were solved using the Gurobi
solver [32].
A. Patrolling an Environment
The graphs for the problem instances were generated ran-
domly in a real world environment. The scenario represents a
ground robot monitoring the University of Waterloo campus.
Vertices around the campus buildings represent the locations
to be monitored and a complete weighted graph was created
by generating a probabilistic road-map to find paths between
those vertices. Figure 3 shows the patrolling environment.
To generate random problem instances of different sizes,
n random vertices were chosen from the original graph.
The latency constraints were generated uniformly randomly
between TSP/k and kTSP where k was chosen randomly
Fig. 3: The environment used for generation of random instances. The red
dots represent the vertices to be monitored and the green dots represent the
vertices in the PRM used to find shortest paths between red vertices.
10
20
30
40
50
60
70
80
90
Number of Vertices
10 -2
10 0
10 2
Time (s)
Orienteering Based Algorithm
Approximation Algorithm
Greedy Algorithm
(a)
0
20
40
60
80
100
Number of Vertices
1
2
3
4
5
6
7
Number of Robots
Orienteering Based Algorithm
Approximation Algorithm
Greedy Algorithm
(b)
Fig. 4: Average run times of the algorithms (a), and number of robots
returned by each algorithm (b). The line plot shows the mean over 10
random instances for each graph size. The error bars in (b) show the
minimum and maximum number of robots required for a graph size.
between 4 and 8 for each instance. Here TSP represents the
TSP length of the graph found using LKH.
For each graph size, 10 random instances were created.
The average run times of the algorithms are presented in
Figure 4a. As expected, Algorithm 3 is considerably slower
than the approximation and simple greedy algorithms due
to multiple calls to the ILP solver. However, as shown in
Figure 4b, Algorithm 3 also gives the minimum number of
robots for most of these instances.
B. Persistent 3D Scene Reconstruction
Another application of our algorithms is in capturing
images for 3D reconstruction of a scene. Since existing
algorithms focus on computing robot paths to map a static
scene [5], [4], our algorithms could be applied to persistently
Fig. 5: The walks returned by Algorithm 3 to continually monitor the
mausoleum of the Taj Mahal. The cones at each viewpoint show the camera
angle. Note that the walk on the left is not a tour, as it visits the vertex with
least latency twice within a period. The walk on the right is a tour and it
visits the vertices that the first robot was unable to cover.
monitor and thus maintain an up-to-date reconstruction of
a scene that changes over time. To demonstrate this, we
create problem instances using a method similar to [4]. The
viewpoints were generated on a grid around the building
to be monitored. For each viewpoint, five camera angles
were randomly generated, and best angle was selected for
each viewpoint based on a view score that was calculated
assuming a square footprint for the camera. For each camera
angle, equally placed rays were projected onto the building
within the footprint and a score was calculated based on the
distance and incidence angle of the ray. This calculation is
similar to that in [4], although they used a more detailed
hemisphere coverage model.
After selecting the viewing angles, the final score of a
camera pose was evaluated as in [4] by greedily picking
the best viewpoint first and evaluating the marginal score of
other viewpoints. The resulting graph had 109 vertices. The
latencies were set such that the most informative viewpoint
is visited every 8 minutes and on average each viewpoint is
visited every 50 minutes. Algorithm 3 found a solution in
150 seconds using two walks, as shown in Figure 5. Note
that Algorithm 1 returned a solution with 3 robots.
C. Comparison with Existing Algorithms in Literature
In [21], [16] the authors propose an SMT (Satisfiability
Modulo Theory) based approach using Z3 solver [33] to
solve the decision version of the problem. The idea is
to fix an upper bound on the period of the solution and
model the problem as a constraint program. The authors
also provide benchmark instances for the decision version
of the problem. We tested our algorithms on the benchmark
instances provided and compare the results to the SMT based
solver provided by [16].
Out of 300 benchmark instances, given a time limit of 10
minutes, the Z3 solver returned 182 instances as satisfiable
with the given number of robots. We ran our algorithms
for each instance and checked if the number of robots
returned are less than or equal to the number of robots in the
benchmark instance. The approximation algorithm satisfied
170 instances whereas Algorithm 3 satisfied 178 instances.
The four satisfiable instances that Algorithm 3 was unable
to satisfy had optimal solutions where the walks share the
vertices, and Algorithm 3 returned one more robot than the
optimal in all those instances. The drawback of the constraint
program to solve the problem is the scalability. It spent an
average of 3.76 seconds on satisfiable instances whereas
Algorithm 3 spent 3 ms on those instances on average.
Moreover, on one such instance where Algorithm 3 returned
one more robot than the Z3 solver, Z3 solver spent 194
seconds as compared to ∼5 ms for Algorithm 3. Note that
these differences are for benchmark instances having up to 7
vertices. As shown above, Algorithm 3 takes ∼100 seconds
for 90 vertex instances whereas we were unable to solve
instances with even 15 vertices within an hour using the Z3
solver. Hence, the scalability of the Z3 based solver hinders
its use for problem instances of practical sizes.
VII. CONCLUSION AND FUTURE WORK
In this paper we presented and analyzed an approximation
and a heuristic algorithm for the problem of finding the
minimum number of robots that can satisfy the latency
constraints for the vertices in a graph. We demonstrated
the performance of the algorithms through simulations. We
also presented and analyzed an algorithm for minimizing the
maximum latency given multiple robots. Finding the relation
between the partitioned optimal solution and a general opti-
mal solution is an interesting direction for future work.
REFERENCES
[1] G. Cabrita, P. Sousa, L. Marques, and A. De Almeida, “Infrastructure
monitoring with multi-robot teams,” in Int. Conf. on Intelligent Robots
and Systems, 2010, pp. 18–22.
[2] N. Basilico, N. Gatti, and F. Amigoni, “Patrolling security games:
Definition and algorithms for solving large instances with single
patroller and single intruder,” Artificial Intelligence, vol. 184, pp. 78–
123, 2012.
[3] A. B. Asghar and S. L. Smith, “Stochastic patrolling in adversarial
settings,” in IEEE American Control Conf., 2016, pp. 6435–6440.
[4] M. Roberts, D. Dey, A. Truong, S. Sinha, S. Shah, A. Kapoor,
P. Hanrahan, and N. Joshi, “Submodular trajectory optimization for
aerial 3D scanning,” in Int. Conf. on Computer Vision, 2017, pp. 5334–
5343.
[5] A. Bircher, K. Alexis, M. Burri, P. Oettershagen, S. Omari, T. Mantel,
and R. Siegwart, “Structural inspection path planning via iterative
viewpoint resampling with application to aerial robotics,” in IEEE Int.
Conf. on Robotics and Automation, 2015, pp. 6423–6430.
[6] N. Cao, K. H. Low, and J. M. Dolan, “Multi-robot informative path
planning for active sensing of environmental phenomena: A tale of
two algorithms,” in Int. Conf. on Autonomous Agents and Multi-Agent
Systems, 2013, pp. 7–14.
[7] L. Merino, F. Caballero, J. R. Mart´ınez-De-Dios, I. Maza, and
A. Ollero, “An unmanned aircraft system for automatic forest fire mon-
itoring and measurement,” Journal of Intelligent & Robotic Systems,
vol. 65, no. 1-4, pp. 533–548, 2012.
[8] P. F. Hokayem, D. Stipanovic, and M. W. Spong, “On persistent
coverage control,” in IEEE Conf. on Decision and Control, 2007, pp.
6130–6135.
[9] N. Nigam and I. Kroo, “Persistent surveillance using multiple un-
manned air vehicles,” in IEEE Aerospace Conf., 2008, pp. 1–14.
[10] N. Nigam, S. Bieniawski, I. Kroo, and J. Vian, “Control of multiple
uavs for persistent surveillance: algorithm and flight test results,” IEEE
Transactions on Control Systems Technology, vol. 20, no. 5, pp. 1236–
1251, 2012.
[11] Y. Elmaliach, N. Agmon, and G. A. Kaminka, “Multi-robot area patrol
under frequency constraints,” Annals of Mathematics and Artificial
Intelligence, vol. 57, no. 3-4, pp. 293–320, 2009.
[12] J. M. Palacios-Gas´os, E. Montijano, C. Sagues, and S. Llorente,
“Multi-robot persistent coverage using branch and bound,” in IEEE
American Control Conf., 2016, pp. 5697–5702.
[13] X. Yu, S. B. Andersson, N. Zhou, and C. G. Cassandras, “Optimal
visiting schedule search for persistent monitoring of a finite set of
targets,” in IEEE American Control Conf., 2018, pp. 4032–4037.
[14] ——, “Optimal dwell times for persistent monitoring of a finite set of
targets,” in American Control Conf., 2017, pp. 5544–5549.
[15] J. Las Fargeas, B. Hyun, P. Kabamba, and A. Girard, “Persistent
visitation under revisit constraints,” in IEEE Int. Conf. on Unmanned
Aircraft Systems, 2013, pp. 952–957.
[16] N. Drucker, M. Penn, and O. Strichman, “Cyclic routing of unmanned
aerial vehicles,” in Int. Conf. on AI and OR Techniques in Constriant
Programming for Combinatorial Optimization Problems.
Springer,
2016, pp. 125–141.
[17] H.-M. Ho and J. Ouaknine, “The cyclic-routing uav problem is pspace-
complete,” in Int. Conf. on Foundations of Software Science and
Computation Structures.
Springer, 2015, pp. 328–342.
[18] S. Alamdari, E. Fata, and S. L. Smith, “Persistent monitoring in
discrete environments: Minimizing the maximum weighted latency be-
tween observations,” The International Journal of Robotics Research,
vol. 33, no. 1, pp. 138–154, 2014.
[19] M. M. Quottrup, T. Bak, and R. Zamanabadi, “Multi-robot planning:
A timed automata approach,” in IEEE Int. Conf. on Robotics and
Automation, vol. 5, 2004, pp. 4417–4422.
[20] A. Ulusoy, S. L. Smith, X. C. Ding, C. Belta, and D. Rus, “Optimality
and robustness in multi-robot path planning with temporal logic
constraints,” The International Journal of Robotics Research, vol. 32,
no. 8, pp. 889–911, 2013.
[21] N. Drucker, “Cyclic routing of unmanned aerial vehicles,” Master’s
thesis, Technion – Israel Institute of Technology, Israel, 2014.
[22] O. Br¨aysy and M. Gendreau, “Vehicle routing problem with time
windows, part I: Route construction and local search algorithms,”
Transportation Science, vol. 39, no. 1, pp. 104–118, 2005.
[23] J. N. Tsitsiklis, “Special cases of traveling salesman and repairman
problems with time windows,” Networks, vol. 22, no. 3, pp. 263–282,
1992.
[24] N. Christofides and J. E. Beasley, “The period routing problem,”
Networks, vol. 14, no. 2, pp. 237–256, 1984.
[25] W. Yu and Z. Liu, “Improved approximation algorithms for some
min-max and minimum cycle cover problems,” Theoretical Computer
Science, vol. 654, pp. 45–58, 2016.
[26] C. Chekuri, N. Korula, and M. P´al, “Improved algorithms for ori-
enteering and related problems,” ACM Transactions on Algorithms,
vol. 8, no. 3, p. 23, 2012.
[27] Y. Chevaleyre, “Theoretical analysis of the multi-agent patrolling
problem,” in IEEE Int. Conf. on Intelligent Agent Technology, 2004,
pp. 302–308.
[28] R. K. Iyer and J. A. Bilmes, “Submodular optimization with sub-
modular cover and submodular knapsack constraints,” in Advances in
Neural Information Processing Systems, 2013, pp. 2436–2444.
[29] K. Helsgaun, “An effective implementation of the Lin–Kernighan trav-
eling salesman heuristic,” European Journal of Operational Research,
vol. 126, no. 1, pp. 106–130, 2000.
[30] N. Christofides, “Worst-case analysis of a new heuristic for the
travelling salesman problem,” Carnegie-Mellon Univ Pittsburgh Pa
Management Sciences Research Group, Tech. Rep., 1976.
[31] A. N. Letchford, S. D. Nasiri, and D. O. Theis, “Compact formulations
of the steiner traveling salesman problem and related problems,”
European Journal of Operational Research, vol. 228, no. 1, pp. 83–92,
2013.
[32] Gurobi, “Gurobi optimizer,” 2018. [Online]. Available: http://www.
gurobi.com
[33] L. De Moura and N. Bjørner, “Z3: An efficient SMT solver,” in Int.
Conf. on Tools and Algorithms for the Construction and Analysis of
Systems.
Springer, 2008, pp. 337–340.