On Endogenous Reconfiguration in Mobile
Robotic Networks
Ketan Savla1
Emilio Frazzoli1
Laboratory for Information and Decision Systems, Massachusetts Institute of
Technology {ksavla,frazzoli}@mit.edu
Abstract: In this paper, our focus is on certain applications for mobile robotic
networks, where reconfiguration is driven by factors intrinsic to the network rather
than changes in the external environment. In particular, we study a version of the
coverage problem useful for surveillance applications, where the objective is to po-
sition the robots in order to minimize the average distance from a random point in
a given environment to the closest robot. This problem has been well-studied for
omni-directional robots and it is shown that optimal configuration for the network is
a centroidal Voronoi configuration and that the coverage cost belongs to Θ(m−1/2),
where m is the number of robots in the network. In this paper, we study this problem
for more realistic models of robots, namely the double integrator (DI) model and
the differential drive (DD) model. We observe that the introduction of these motion
constraints in the algorithm design problem gives rise to an interesting behavior.
For a sparser network, the optimal algorithm for these models of robots mimics
that for omni-directional robots. We propose novel algorithms whose performances
are within a constant factor of the optimal asymptotically (i.e., as m →+∞). In
particular, we prove that the coverage cost for the DI and DD models of robots is
of order m−1/3. Additionally, we show that, as the network grows, these novel algo-
rithms outperform the conventional algorithm; hence necessitating a reconfiguration
in the network in order to maintain optimal quality of service.
1 Introduction
The advent of large scale sensor and robotic networks has led to a surge of
interest in reconfigurable networks. These systems are usually designed to
reconfigure in a reactive way, i.e., as a response to changes in external condi-
tions. Due to their importance in sensor network applications, reconfiguration
algorithms have attracted a lot of attention, e.g., see [9]. However, there are
very few instances in engineering systems, if any, that demonstrate an inter-
nal reconfiguration in order to maintain a certain level of performance when
certain intrinsic properties of the system are changed. However, examples
of endogenous reconfiguration or phase transitions are abound in nature, e.g.,
arXiv:0807.2648v2  [cs.RO]  18 Jul 2008
2
Ketan Savla
Emilio Frazzoli
desert locusts [4] who switch between gregarious and social behavior abruptly,
etc. An understanding of the phase transitions can not only provide insight
into the reasons for transitions in naturally occurring systems but also iden-
tify some design principles involving phase transition to maintain efficiency in
engineered systems.
In this paper, we observe such a phenomenon under a well-studied setting
that is relevant for various surveillance applications. We consider a version
of the so-called Dynamic Traveling Repairperson Problem, first proposed by
[12] and later developed in [2]. In this problem, service requests are generated
dynamically. In order to fulfill a request, one of the vehicles needs to travel
to its location. The objective is to design strategies for task assignment and
motion planning of the robots that minimizes the average waiting time of a
service request. In this paper, we consider a special case of this problem when
service requests are generated sparingly. This problem, also known as coverage
problem, has been well-studied in the robotics and operations research com-
munity. However, we consider the problem in the context of realistic models
of robots: double integrator models and differential drive robots. Some pre-
liminary work on coverage for curvature-constrained vehicles was reported in
our earlier work [7]. In this paper, we observe that when one takes into con-
sideration the motion constraints of the robots, the optimal solution exhibits
a phase transition that depends on the size of the network.
The contributions of this paper are threefold. First, we identify an interest-
ing characteristic of the solution to the coverage problem for double integrator
and differential drive robots, where reconfiguration is necessitated intrinsically
by the growth of the network, in order to maintain optimality. Second, we pro-
pose novel approximation algorithms for double integrator robots as well as
differential drive robots and prove that they are within a constant factor of
the optimal in the asymptotic (m →+∞) case. Moreover, we prove that,
asymptotically, these novel algorithms will outperform the conventional al-
gorithms for omni-directional robots. Lastly, we show that the coverage for
both, double integrator as well as differential drive robots scales as 1/m1/3
asymptotically.
2 Problem Formulation and Preliminary Concepts
In this section, we formulate the problem and present preliminary concepts.
Problem Formulation
The problem that we consider falls into the general category of the so called
Dynamic Traveling Repairperson Problem, originally proposed in [12]. Let Q ⊂
R2 be a convex, compact domain on the plane, with non-empty interior; we will
refer to Q as the environment. For simplicity in presentation, we assume that
Q is a square, although all the analysis presented in this paper carries through
On Endogenous Reconfiguration in Mobile Robotic Networks
3
for any convex and compact Q with non-empty interior in R2. Let A be the
area of Q. A spatio-temporal Poisson process generates service requests with
finite time intensity λ > 0 and uniform spatial density inside the environment.
In this paper, we focus our attention on the case when λ →0+, i.e., when the
service requests are generated very rarely. These service requests are identical
and are to be fulfilled by a team of m robots. A service request is fulfilled
when one of m robots moves to the target point associated with it.
We will consider two robot models: the double integrator model and the
differential drive model. The double integrator (DI) model describes the dy-
namics of a robot with significant inertia. The configuration of the robot is
g = (x, y, vx, vy) ⊂R4 where (x, y) is the position of the robot in Cartesian
coordinates, and (vx, vy) is its velocity. The dynamics of the DI robot are
given by
˙x(t) = vx(t),
˙y(t) = vy(t),
vx(t)2 + vy(t)2 ≤v2
max
∀t
˙vx(t) = ux(t),
˙vy(t) = uy(t),
ux(t)2 + uy(t)2 ≤u2
max
∀t,
where vmax and umax are the bounds on the speed and the acceleration of the
robots.
The differential drive model describes the kinematics of a robot with two
independently actuated wheels, each a distance ρ from the center of the robot.
The configuration of the robot is a directed point in the plane, g = (x, y, θ) ⊂
SE(2) where (x, y) is the position of the robot in Cartesian coordinates, and
θ is the heading angle with respect to the x axis. The dynamics of the DD
robot are given by
˙x(t) = 1
2(wl(t) + wr(t)) cos θ(t),
˙y(t) = 1
2(wl(t) + wr(t)) sin θ(t),
˙θ(t) = 1
2ρ(wr(t) −wl(t)),
|wl(t)| ≤wmax∀t, |wr(t)| ≤wmax∀t,
where the inputs wl and wr are the angular velocities of the left and the right
wheels, which we assume to be bounded by wmax. Here, we have also assumed
that the robot wheels have unit radius.
The robots are assumed to be identical. The strategies of the robots in
the presence and absence of service requests are governed by their motion
coordination algorithm. A motion coordination algorithm is a function that
determines the actions of each robot over time. For the time being, we will
denote these functions as π = (π1, π2, . . . , πm), but do not explicitly state their
domain; the output of these functions is a steering command for each vehicle.
The objective is the design of motion coordination algorithms that allow the
4
Ketan Savla
Emilio Frazzoli
robots to fulfill service requests efficiently. To formalize the notion of efficiency,
let Tj be the time elapsed between the generation of the j-th service request,
and the time it is fulfilled and let Tπ := limj→+∞limλ→0+ E[Tj] be defined
as the system time under policy π, i.e., the expected time a service request
must wait before being fulfilled, given that the robots follow the algorithm
defined by π. We shall also refer to the average system time as the coverage
cost. Note that the system time Tπ can be thought of as a measure of the
quality of service collectively provided by the robots.
In this paper, we wish to devise motion coordination algorithms that yield
a quality of service (i.e., system time) achieving, or approximating, the the-
oretical optimal performance given by Topt = infπ Tπ. Since finding the opti-
mal algorithm maybe computationally intractable, we are also interested in
designing computationally efficient algorithms that are within a constant fac-
tor of the optimal, i.e., policies π such that Tπ ≤κTopt for some constant
κ. Moreover, we are interested in studying the scaling of the performance of
the algorithms with m, i.e., size of the network, other parameters remaining
constant. Since, we keep A fixed, this is also equivalent to study the scaling
of the performance with respect to the density m/A of the network.
We now describe how a solution to this problem gives rise to an endogenous
reconfiguration in the robotic network.
Endogenous Reconfiguration
The focus of this paper is on endogenous reconfiguration, that is a reconfig-
uration necessitated by the growth of the network (as the term ‘endogenous’
implies in biology), as opposed to any external stimulus. We formally describe
its meaning in the context of this paper. In the course of the paper, we shall
propose and analyze various algorithms for the coverage problem. In particu-
lar, for each model of the robot, we will propose two algorithms, π1 and π2.
The policy π1 closely resembles the omni-directional based policy, whereas the
novel π2 policy optimizes the performance when the motion constraints of the
robots start playing a significant role. We shall show that
lim
m/A→0+
Tπ1
Topt
= 1,
lim
m→+∞
Tπ2
Tπ1
= 0,
lim sup
m→+∞
Tπ2
Topt
≤c for some constant c > 1.
This shows that, for sparse networks, the omni-directional model based al-
gorithm π1 is indeed a reasonable algorithm. However, as the network size
increases, there is a phase transition, during which the motion constraints
start becoming important and the π2 algorithm starts outperforming the π1
algorithm. Moreover, the π2 algorithm performs with a constant factor of the
optimal in the asymptotic (m →+∞) case. Hence, in order to maintain ef-
ficiency, one needs to switch away from the π1 policy as the network grows.
It is in this sense that we shall use the term endogenous reconfiguration to
denote a switch in the optimal policy with the growth of the network.
On Endogenous Reconfiguration in Mobile Robotic Networks
5
3 Lower Bounds
In this section, we derive lower bounds on the coverage cost for the robotic
network that are independent of any motion coordination algorithm adopted
by the robots. Our first lower bound is obtained by modeling the robots as
equivalent omni-directional robots. Before stating the lower bounds formally,
we need to briefly review a related problem from computational geometry
which has direct consequences for the case omni-directional robots.
The Continuous m-median Problem
Given a convex, compact set Q ⊂R2 and a set of points p = {p1, p2, . . . , pm} ∈
Qm, the expected distance between a random point q, sampled from a uniform
distribution over Q, and the closest point in p is given by
Hm(p, Q) :=
Z
Q
1
A
min
i∈{1,...,m} ∥pi −q∥dq =
m
X
i=1
Z
Vi(p)
1
A∥pi −q∥dq,
where V(p) = (V1(p), V2(p), . . . , Vm(p)) is the Voronoi (Dirichlet) parti-
tion [10] of Q generated by the points in p, i.e.,
Vi(p) = {q ∈Q : ∥q −pi∥≤∥q −pj∥, ∀j ∈{1, . . . , m}},
i ∈{1, . . . , m}.
The problem of choosing p to minimize Hm is known in geometric optimiza-
tion [1] and facility location [6] literature as the (continuous) m-median prob-
lem. The m-median of the set Q is the global minimizer
p∗
m(Q) = argminp∈Qm Hm(p, Q).
We let H∗
m(Q) = Hm(p∗
m(Q), Q) be the global minimum of Hm. The solution
of the continuous m-median problem is hard in the general case because the
function p 7→Hm(p, Q) is not convex for m > 1. However, gradient algorithms
for the continuous multi-median problem can be designed [5]. We would not
go further into the details of computing these m-median locations and assume
that these locations are given or that a computationally efficient algorithm
for obtaining them is available.
This particular problem formulation, with demand generated indepen-
dently and uniformly from a continuous set, is studied thoroughly in [11] for
square regions and [13] for more general compact regions. It is shown in [13]
that, in the asymptotic (m →+∞) case, H∗
m(Q) = chex
q
A
m
almost surely,
where chex ≈0.377 is the first moment of a hexagon of unit area about its
center. This optimal asymptotic value is achieved by placing the m points on
a regular hexagonal network within Q (the honeycomb heuristic). Working
towards the above result, it is also shown in [13] that for any m ∈N:
2
3
r
A
πm ≤H∗
m(Q) ≤c(Q)
r
A
m,
(1)
6
Ketan Savla
Emilio Frazzoli
where c(Q) is a constant depending on the shape of Q. In particular, for a
square Q, c(Q) ≈0.38.
We use two different superscripts on Topt for the two models of the robots,
i.e., we use T DI
opt for the DI robot and T DD
opt for the DD robot. Finally, we state
a lower bound on these quantities as follows.
Lemma 1. The coverage cost satisfies the following lower bound.
T DI
opt ≥H∗
m(Q)
vmax
,
T DD
opt ≥H∗
m(Q)
wmax
.
Proof. The proof follows trivially by relaxing the constraints on the robots
and allowing them to move like omni-directional robots with speeds vmax for
DI robots and wmax for DD robots. One can then adopt the lower bound on
coverage cost for omni-directional robot, e.g., [2] to arrive at the result.
Remark 1. Since from Equation (1), H∗
m(Q) ∈Ω(1/√m), Lemma 1 implies
that T DI
opt and T DD
opt also belong to Ω(1/√m).
This lower bound will be particularly useful for proving the optimality of
algorithms for sparse networks. We now proceed towards deriving a tighter
lower bound which will be relevant for dense networks. The reachable sets of
the two models of robots will play a crucial role in deriving the new lower
bound. We study them next.
Reachable Sets for the Robots
In this subsection, we state important properties of the reachable sets of the
double integrator and differential drive robots that are useful in obtaining
tighter lower bound.
Let τ : G × R2 →R+ be the minimum time required to steer a robot
from initial configuration g in G to a point q in the plane. For the DI robot,
G = R4 and for DD robots G = SE(2). With a slight abuse of terminology,
we define the reachable set of a robot, Rt(g), to be the set of all points q in
Q that are reachable in time t > 0 starting at configuration g. Note that, in
this definition, we do not put any other constraint (e.g., heading angle, etc.)
on the terminal point q. Formally, the reachable set is defined as
Rt(g) = {q ∈R2 | τ(g, q) ≤t}.
We now state a series of useful properties of the reachable sets.
Lemma 2 (Upper bound on the small-time reachable set area).
The area of the reachable set for a DI robot starting at a configuration
g = (x, y, ˙x, ˙y) ∈R4, with ˙x2 + ˙y2 = v0, satisfies the following upper bound.
Area(Rt(g)) ≤
2v0umaxt3 + o(t3),
as t →0+ for v0 > 0,
u2
maxt4
for v0 = 0.
On Endogenous Reconfiguration in Mobile Robotic Networks
7
The area of the reachable set for a DD robot starting at any configuration
g ∈SE(2) satisfies the following upper bound.
Area(Rt(g)) ≤5
6ρw3
maxt3 + o(t3),
as t →0+.
Proof. The result for the differential drive robot has been derived in [8]. We
derive the result for the double integrator robot here. Assume, without any
loss of generality, that the robot is initially placed at the origin with ve-
locity aligned with the x-axis. The maximum of the absolute value of the
x-coordinate and y-coordinate of all the points reachable in time t is less than
or equal to v0t + 1
2umaxt2 and 1
2umaxt2, respectively. Therefore, the area of
the reachable set is trivially upper bounded by 4(v0t + 1
2umaxt2)( 1
2umaxt2) =
2v0umaxt3 + u2
maxt4.
Lemma 3 (Lower bound on the reachable set area). The area of the
reachable set of a DI robot starting at a configuration g = (x, y, ˙x, ˙y) ∈R4,
with ˙x2 + ˙y2 = v0, satisfies the following lower bound.
Area(Rt(g)) ≥v0umax
3
t3
∀t ≤π
2
v2
0
umax
.
The area of the reachable set of a DD robot starting at any configuration
g ∈SE(2) satisfies the following lower bound.
Area(Rt(g)) ≥2
3ρw3
maxt3.
Lemma 4. The travel time to a point in the reachable set for a DI robot
starting at a configuration g = (x, y, ˙x, ˙y) ∈R4, with ˙x2 + ˙y2 = v0, satisfies
the following property.
Z
Rt(g)
τ(g, q)dq ≥v0umax
12
t4
∀t ≤π
2
v2
0
umax
.
The travel time to a point in the reachable set for a DD robot starting at any
configuration g ∈SE(2) satisfies the following property.
Z
Rt(g)
τ(g, q)dq ≥w3
max
6ρ t4.
Proof. For both the robots,
R
Rt(g) τ(g, q)dq =
R t
0 Area(Rs(g))ds. Using Lemma 3,
for a double integrator robot, for all t ≤π
2
v2
0
umax we have that,
Z
Rt(g)
τ(g, q)dq ≥v0umax
3
Z t
0
s3ds = v0umax
12
t4.
The proof for the differential drive robot follows along similar lines.
8
Ketan Savla
Emilio Frazzoli
We are now ready to state a new lower bound on the coverage cost.
Theorem 1 (Asymptotic lower bound on the coverage cost). The cov-
erage cost for a network of DI or DD robots satisfies the following asymptotic
lower bound.
lim inf
m→+∞T DI
optm1/3 ≥1
24

A
2vmaxumax
1/3
,
and
lim inf
m→+∞T DD
opt m1/3 ≥
1
5wmax
6ρA
5
1/3
.
Proof. We state the proof for the double integrator robot. The proof for the
differential drive robot follows along similar lines.
In the following, we use the notation Ai = Area(DVi(g)), where DVi(g) :=
{q ∈Q | τ(gi, q) ≤τ(gj, q)
∀j ̸= i}. We begin with
T DI
opt =
inf
g∈R4m
m
X
i
Z
DVi(g)
1
Aτ(gi, q) dq
≥
inf
g∈R4m
Z
Q
1
A
min
i∈{1,...,m} τ(gi, q)dq.
(2)
Let ¯RAi(gi) be the reachable set starting at configuration g and whose area
is Ai. Using the fact that, given an area Ai, the region with the minimum
integral of the travel time to the points in it is the reachable set of area Ai,
one can write Equation (2) as
T DI
opt ≥
inf
g∈R4m
m
X
i
Z
¯
RAi(gi)
1
Aτ(gi, q) dq.
(3)
Let ti be defined such that Area(Rti(gi)) = Ai. Lets assume that as m →+∞,
Ai →0+ (this point will be justified later on). In that case, we know from
Lemma 2 that, ti can be lower bounded as ti ≥

Ai
2viumax
1/3
, where vi is the
speed associated with the state gi. Therefore, from Equation (3) and Lemma 4,
one can write that
T DI
opt ≥inf
g∈R4m
m
X
i
Z
Rti(gi)
1
Aτ(gi, q) dq
≥inf
g∈R4m
m
X
i
1
A
viumax
12
t4
i .
(4)
Using the above mentioned lower bound on ti, Equation (4) can be written as
On Endogenous Reconfiguration in Mobile Robotic Networks
9
T DI
opt ≥
1
24
3√
2A
1
u1/3
max
inf
g∈R4m
A4/3
i
v1/3
i
≥
1
24
3√
2A
1
u1/3
maxv1/3
max
min
{A1,A2,...,Am}∈Rm
m
X
i
A4/3
i
subject to
m
X
i
Ai = A
and Ai ≥0
∀i ∈{1, . . . , m}.
Note that the function f(x) = x4/3 is continuous, strictly increasing and
convex. Thus by using the Karush-Kuhn-Tucker conditions [3], one can show
that the quantity Pm
i A4/3
i
is minimized with an equitable partition, i.e.,
Ai = A/m, ∀i. This also justifies the assumption that for m →+∞, Ai →0+.
Remark 2. Theorem 1 shows that both T DI
opt and T DD
opt belong to Ω(1/m1/3).
4 Algorithms and their Analyses
In this section, we propose novel algorithms, analyze their performance and
explain how the size of the network plays a role in selecting the right algorithm.
We start with an algorithm which closely resembles the one for omni-
directional robots. Before that, we first make a remark relevant for the analysis
of all the algorithms to follow.
Remark 3. Note that if n0 is the number of outstanding service requests at
initial time, then the time required to service all of them is finite (Q being
bounded). During this time period, the probability of appearance of a new
service requests appearing is zero (since we are dealing with the case when
the rate of generation of targets λ is arbitrarily close to zero). Hence, after an
initial transient, with probability one, all the robots will be in their stationary
locations at the appearance of the new target. Moreover, the probability of
number of outstanding targets being more than one is also zero. Hence, in the
analysis of the algorithms, without any loss of generality, we shall implicitly
assume that there no outstanding service requests initially.
The Median Stationing (MS) Algorithm
Place the m robots at rest at the m-median locations of Q. In case of the
DD robot, its heading is chosen arbitrarily. These m-median locations will be
referred to as the stationary locations of the robots. When a service request
appears, it is assigned to the robot whose stationary location is closest to
the location of the service request. In order to travel to the service location,
the robots use the fastest path with no terminal constraints at the service
location. In absence of outstanding service tasks, the robot returns to its
stationary location. The stationary configurations are depicted in Figure 1.
10
Ketan Savla
Emilio Frazzoli
Fig. 1. Depiction of typical stationary configurations for the Median Stationing
Algorithm. On the left: DI robots at rest at their stationary locations. On the right:
DD robots with arbitrary headings at their stationary locations. In both the figures,
the shaded cell represents a typical region of responsibility for a robot.
Let T DI
MS and T DD
MS be the coverage cost as given by the above policy for
the DI and DD robots, respectively.
Theorem 2 (Analysis of the MS algorithm). The coverage cost for a
network of DI and DD robots with the MS algorithm satisfies the following
bounds.
H∗
m(Q)
vmax
≤T DI
MS ≤H∗
m(Q)
vmax
+ vmax
2umax
+
s
2
√
2A
umax
.
H∗
m(Q)
wmax
≤T DD
MS ≤H∗
m(Q)
wmax
+
ρπ
2wmax
.
Proof. The lower bounds on T DI
MS and T DD
MS follow trivially from Lemma 1.
For a double integrator robot, the minimum travel time from rest at loca-
tion p to a point q is given by
τ((p, 0), q) ≤
(q
2∥p−q∥
umax
for ∥p −q∥≤
v2
max
2umax ,
∥p−q∥
vmax +
vmax
2umax otherwise.
Therefore, for any q, τ((p, 0), q) can be upper bounded as
τ((p, 0), q) ≤∥p −q∥
vmax
+ vmax
2umax
+
s
2∥p −q∥
umax
≤∥p −q∥
vmax
+ vmax
2umax
+
s
2
√
2A
umax
.
On Endogenous Reconfiguration in Mobile Robotic Networks
11
The upper bound on T DI
MS is then obtained by taking the expected value over
all q ∈Q while taking into consideration the assignment policies for the
services to robots. For a differential drive robot, the travel time from any
initial configuration (p, θ) to a point q can be upper bounded by ∥p−q∥
wmax +
πρ
2wmax .
The result follows by taking expected value of the travel time over all points
in Q.
Remark 4. Theorem 2 and Lemma 1 along with Equation (1) imply that,
lim
m/A→0+
T DI
MS
T DI
opt
= 1
and
lim
m/A→0+
T DD
MS
T DD
opt
= 1.
This implies that the MS algorithm is indeed a reasonable algorithm for sparse
networks, where the travel time for a robot to reach a service location is almost
the same as that for an omni-directional vehicle.
However, as the density of robots increases, the assigned service locations
to the robots start getting relatively closer. In that case, the motion con-
straints start having a significant effect on the travel time of the robots and
it is not obvious in that case that the MS algorithm is indeed the best one.
In fact, for dense networks, one can get a tighter lower bound on the
performance of the MS algorithm:
Theorem 3. The coverage cost of a dense network of DI and DD robots with
the MS algorithm satisfies the following bounds:
lim inf
m→∞T DI
MSm1/4 ≥0.321
 A
u2max
1/4
.
lim inf
m→∞T DD
MS ≥
πρ
4wmax
.
Proof. Let us consider the DI case first. The minimum travel time for the i-th
robot to reach a point q inside its region of responsibility Vi, starting from
rest at the median location pi is bounded by
τ((pi, 0), q) ≥max
(
∥pi −q∥
p
2umaxdVi
, ∥pi −q∥
vmax
)
,
(5)
where
dVi = max
q∈Vi ∥pi −q∥.
For large m, it is known that the honeycomb heuristic is optimal [13], yielding
lim
m→∞dVim1/2 =
s
2 A
3
√
3 ≈0.62
√
A,
∀i ∈{1, . . . , m}.
(6)
Clearly, in these conditions the first term in (5) is the dominant one.
12
Ketan Savla
Emilio Frazzoli
Another consequence of the optimality of the honeycomb heuristic is that
lim
m→∞H∗
m(Q)m1/2 = chex
√
A.
(7)
Integrating (5) over Q, multiplying both sides by m1/4, and taking the limit
as m →∞, we get
lim inf
m→∞T DI
MSm1/4 ≥lim inf
m→∞
H∗
m(Q)m1/2
p
2umaxdVim1/2 .
Finally, using (6) and (7), we get the desired result.
We will only sketch the proof for the DD case. The minimum travel time
for a DD robot can be decomposed into the sum of the cost of turning towards
the target point, plus the Euclidean distance between the robot and the target
point. The Euclidean term vanishes as m increases. The turning cost on the
other hand remains bounded away from zero. Since the robot’s initial heading
is chosen randomly, the expected turning angle is π/4, which combined with
the maximum turning rate wmax/ρ yields the stated result.
In other words, for DI robots, the MS algorithm requires them to stay sta-
tionary in absence of any outstanding service requests. Once a service request
is assigned to a robot, the amount of time spend in attaining the maximum
speed vmax becomes significant as the location of assigned service requests
start getting closer. Similar arguments hold for DD robots.
An alternate approach, as proposed in the next algorithm, is to keep the
robots moving rather than waiting in absence of outstanding service requests.
The algorithm assigns dynamic regions of responsibility to the robots.
The Strip Loitering (SL) Algorithm
This algorithm is an adaptation of a similar algorithm proposed in [7] for
Dubins vehicle, i.e., vehicles constrained to move forward with constant speeds
along paths of bounded curvature.
Let the robots move with constant speed v∗= min{vmax,
√√
Aumax
3.22
} and
follow a loitering path which is constructed as follows. Divide Q into strips
of width w where w = min
n
4
3√ρ∗
A+10.38ρ∗√
A
m
2/3
, 2ρ∗o
, where ρ∗:=
v∗2
umax .
Orient the strips along a side of Q. Construct a closed path which can be
traversed by a double integrator robot while always moving with constant
speed v∗. This closed path runs along the longitudinal bisector of each strip,
visiting all strips from top-to-bottom, making U-turns between strips at the
edges of Q, and finally returning to the initial configuration. The m robots
loiter on this path, equally spaced, in terms of path length. A depiction of the
Strip Loitering algorithm can be viewed in Figure 2. Moreover, in Figure 3
we define two distances that are important in the analysis of this algorithm.
On Endogenous Reconfiguration in Mobile Robotic Networks
13
Variable d2 is the length of the shortest path departing from the loitering path
and ending at the target (a circular arc of radius ρ∗). The robot responsible for
visiting the target is the one closest in terms of loitering path length (variable
d1) to the point of departure, at the time of target-arrival. Note that there
may be robots closer to the target in terms of the actual distance. However,
we find that the assignment strategy described above lends itself to tractable
analysis.
Fig. 2. Depiction of the loitering path for the double integrator robots. The segment
providing closure of the loitering path (returning the robots from the end of the last
strip to the beginning of the first strip) is not shown here for clarity of the drawing.
d2
d1
δ
target
point
of
departure
ρ
Fig. 3. Close-up of the loitering path with construction of the point of departure
and the distances δ, d1, and d2 for a given target, at the instant of appearance.
After a robot has serviced a target, it must return to its place in the
loitering path. We now describe a method to accomplish this task through
the example shown in Fig. 3. After making a left turn of length d2 to service
the target, the robot makes a right turn of length 2d2 followed by another left
turn of length d2, returning it to the loitering path. However, the robot has
fallen behind in the loitering pattern. To rectify this, as it nears the end of
the current strip, it takes its U-turn early.
14
Ketan Savla
Emilio Frazzoli
Let T DI
SL be the coverage cost as given by the above algorithm for DI robots.
We now state an upper bound on T DI
SL.
Theorem 4 (Analysis of the SL algorithm). The coverage cost for a team
of DI robots implementing the SL algorithm satisfies the following asymptotic
upper bound.
lim sup
m→+∞T DI
SLm1/3 ≤1.238
v∗
�ρ∗A + 10.38ρ∗2√
A

1/3.
Proof. Since a similar algorithm for Dubins vehicle was analyzed in [7], we
only outline the proof here and refer to [7] for more details. Denote the length
of the closed path as L1. Due to equal spacing of the robots along the loitering
path,
E[d1] = L1
2m.
(8)
We now calculate an upper bound on L1. To that effect, let Nstrips be the
number of strips, Lstrip be the length travelled along a single strip, Lu−turn
be the length of a u-turn and Lclosure be the length of the closure path. With
these notations, L1 can be bounded as
L1 ≤NstripsLstrip + (Nstrips −1)Lu−turn + Lclosure.
(9)
One can compute bounds for various terms on the right side of Equation (9).
Substituting these bounds into Equation (9) and taking into account Equa-
tion (8) we get that
E[d1] ≤A + 10.38ρ∗√
A
2mw
+ 2
√
A + 6.19ρ∗
m
.
(10)
To calculate E[d2] we define δ as the smallest distance from the target to any
point on the loitering path (see Fig. 3). Since d2(s) = 2ρ∗sin−1(
q
s
2ρ∗) for
s ≤ρ∗and δ is uniformly distributed between 0 and w/2,
E[d2] = 4ρ∗
w
Z w/2
0
sin−1
r s
2ρ∗

ds ≤3
4
√ρ∗w.
(11)
Therefore, the coverage cost is given by
T SL ≤E[d1] + E[d2]
v∗
.
(12)
Therefore, from Equations (12), (10) and (11) we get that for w ≤2ρ,
T DI
SL ≤A + 10.38ρ∗√
A
2mwv∗
+ 2
√
A + 6.19ρ∗
mv∗
+
3
4v∗
√ρ∗w.
(13)
In order to get the least upper bound, we minimize the right hand side of
Equation (13) with respect to w subject to the constraint that w ≤2ρ∗.
On Endogenous Reconfiguration in Mobile Robotic Networks
15
Remark 5. Theorem 4 and Theorem 1 imply that T DI
opt belongs to Θ(1/m1/3).
Moreover, Theorem 4 and Theorem 3 together with Equation 1 imply that
T DI
SL/T DI
MS →0+ as m →+∞. Hence, asymptotically, the SL algorithm out-
performs the MS algorithm and is within a constant factor of the optimal.
We now present the second algorithm for DD robots.
The Median Clustering (MC) Algorithm
Form as many teams of robots with k :=

4.09

ρ
√
A
2/3
m1/3

robots in each
team. If there are additional robots, group them into one of these teams. Let
n :=
 m
k

denote the total number of teams formed. Position these n teams at
the n-median locations of Q, i.e., all the robots in a team are co-located at the
median location of its team. Within each team j, j ∈{1, . . . , n}, the headings
of the robots belonging to that team are selected as follows. Let ℓj ≥k be the
number of robots in team j. Pick a direction randomly. The heading of one
robot is aligned with this direction. The heading of the second robot is selected
to be along a line making an angle π
ℓ, in the counter-clockwise direction, with
the first robot. The headings of the remaining robots are selected similarly
along directions making π
ℓ-angle with the previous one (see Figure 4). These
headings will be called the median headings of the robots. Each robot in
a team is assigned a dominance region which is the region formed by the
intersection of double cone making half angle of
π
2ℓwith its median heading
and the Voronoi cell belonging to the team (see Figure 4). When a service
request appears, it is assigned to the robot whose dominance region contains
its location. The assigned robot travels to the service location in the fastest
possible way and, upon the completion of the service, returns to the median
location of its team and aligns itself with its original median heading.
Fig. 4. Depiction of the Median Clustering Algorithm with teams of 4 robots each.
The shaded region represents a typical region of responsibility for a robot.
16
Ketan Savla
Emilio Frazzoli
Let T DD
MC be the coverage cost as given by the above policy. We now state
an upper bound on T DD
MC in the following theorem.
Theorem 5 (Analysis of the MC algorithm). The coverage cost for a
team of DD robots while implementing the MC algorithm satisfies the following
asymptotic upper bound.
lim sup
m→+∞T DD
MCm1/3 ≤1.15
wmax
(ρA)1/3.
Proof. The travel time for any robot from its median location p to the location
q of a service request is upper bounded by ∥p−q∥
wmax +
πρ
2wmaxk. Taking the expected
value of this quantity while taking into consideration the assignment policy
of the service requests gives us that
T DD
MC ≤H∗
n(Q)
wmax
+
πρ
2wmaxk .
(14)
From Equation (1), H∗
n(Q) ≤0.38
q
A
n . Moreover, for large m, n ≈m/k. This
combined with Equation (14), one can write that, for large m,
T DD
MC ≤0.38
wmax
s
A
m/k +
πρ
2wmaxk .
(15)
The right hand side of Equation (15) is minimized when k = 4.09

ρ
√
A
2/3
m1/3.
Substituting this into Equation (15), one arrives at the result.
Remark 6. Theorem 5 and Theorem 1 imply that T DD
opt belongs to Θ(1/m1/3).
Moreover, Theorem 5 and Theorem 3 together with Equation 1 imply that
T DD
MC/T DD
MS →0+ as m →+∞. Hence, asymptotically, the MC algorithm
outperforms the MS algorithm and is within a constant factor of the optimal.
5 Conclusion
In this paper, we considered a coverage problem for a mobile robotic network
modeled as double integrators and differential drives. We observe that the op-
timal algorithm for omni-directional robots is a reasonable solution for sparse
networks of double integrator or differential drive robots. However, these al-
gorithms do not perform well for large networks because they don’t take into
consideration the effect of motion constraints. We propose novel algorithms
that are within a constant factor of the optimal for the DI as well as DD
robots and prove that the coverage cost for both of these robots is of the
order 1/m1/3.
In future, we would like to obtain sharper bounds on the coverage cost
so that we can make meaningful predictions of the onset of reconfiguration
On Endogenous Reconfiguration in Mobile Robotic Networks
17
in terms of system parameters. It would be interesting to study the prob-
lem for non-uniform distribution of targets and for higher intensity of arrival.
Also, this research opens up possibilities of reconfiguration due to other con-
straints, like sensors (isotropic versus anisotropic), type of service requests
(distributable versus in-distributable), etc. Lastly, we plan to apply this re-
search in understanding phase transition in naturally occurring systems, e.g.,
desert locusts [4].
References
1. P. K. Agarwal and M. Sharir. Efficient algorithms for geometric optimization.
ACM Computing Surveys, 30(4):412–458, 1998.
2. D. J. Bertsimas and G. J. van Ryzin. A stochastic and dynamic vehicle routing
problem in the Euclidean plane. Operations Research, 39:601–615, 1991.
3. S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University
Press, 2004.
4. J. Buhl, D. J. Sumpter, I. D. Couzin, J. Hale, E. Despland, E. Miller, and S. J.
Simpson. From disorder to order in marching locusts. Science, 312:1402–1406,
2006.
5. J. Cort´es, S. Mart´ınez, T. Karatas, and F. Bullo. Coverage control for mobile
sensing networks. IEEE Transactions on Robotics and Automation, 20(2):243–
255, 2004.
6. Z. Drezner, editor. Facility Location: A Survey of Applications and Methods.
Springer Series in Operations Research. Springer Verlag, New York, 1995.
7. J. Enright, K. Savla, and E. Frazzoli. Coverage control for teams of nonholo-
nomic agents. In IEEE Conf. on Decision and Control, 2008. To appear.
8. J. J. Enright and E. Frazzoli. The stochastic traveling salesman problem for the
Reeds-Shepp car and the differential drive robot. In IEEE Conf. on Decision
and Control, 2006.
9. A. Kansal, W. Kaiser, G. Pottie, M. Srivastava, and G. Sukhatme.
Recon-
figuration methods for mobile sensor networks. ACM Transactions on Sensor
Networks, 3(4):22:1–22:28, 2007.
10. A. Okabe, B. Boots, K. Sugihara, and S. Chiu. Spatial tessellations: Concepts
and Applications of Voronoi diagrams. Wiley Series in Probability and Statis-
tics. John Wiley & Sons, Chichester, UK, second edition, 2000.
11. C. H. Papadimitriou. Worst-case and probabilistic analysis of a geometric loca-
tion problem. SIAM Journal on Computing, 10(3), August 1981.
12. H. Psaraftis. Dynamic vehicle routing problems. In B. Golden and A. Assad,
editors, Vehicle Routing: Methods and Studies, Studies in Management Science
and Systems. Elsevier, 1988.
13. E. Zemel.
Probabilistic analysis of geometric location problems.
Annals of
Operations Research, 1(3), October 1984.