arXiv:1604.01452v1  [cs.RO]  5 Apr 2016
THE PROBABILISTIC ANALYSIS OF THE NETWORK GRAPH CREATED BY
DYNAMIC BOUNDARY COVERAGE
GANESH P. KUMAR ∗‡ AND SPRING BERMAN †‡
Abstract.
Key words.
AMS subject classifications.
1. Introduction.
1.1. Background. We address the problem of achieving boundary coverage with a
swarm of autonomous robots. In this task, a group of robots must allocate themselves around
the boundary of a region or object according to a desired configuration or density. We specifi-
cally consider problems of dynamic boundary coverage, in which robots asynchronously join
a boundary and later leave it to recharge or perform other tasks. Applications: mapping, ex-
ploration, environmental monitoring, surveillance, disaster response tasks such as cordoning
off hazardous areas; collective payload transport, in which the group cooperatively transports
a load to a destination, for automated manipulation, assembly, construction, and manufactur-
ing.
We focus on stochastic coverage schemes (SCS), in which robots probabilistically choose po-
sitions on the boundary. Our interest in SCS, as opposed to deterministic coverage schemes,
is motivated by the following reasons. First, they enable a probabilistic analysis of the graph
for different classes of inputs identified by the joint pdf of robot positions. Second, SCS al-
low us to model natural phenomena such as Random Sequential Adsorption (RSA) [30], the
clustering of ants around a food item [20], and Renyi Parking [6], the process by which a fleet
of cars parks without collisions on a parking lot. Lastly, results from SCS allow us to ana-
lyze the distributions of robots with noisy sensing and actuation, even though the underlying
coverage scheme may be deterministic.
1.1.1. Assumptions about Robot Capabilities. We assume that each robot can locally
sense its environment and communicate with other robots nearby.
Disk model of sens-
ing/communication. Robots can distinguish between other robots and a boundary of interest.
The robots lack global localization: highly limited onboard power may preclude the use of
GPS, or they may operate in GPS-denied environments. The robots also lack prior informa-
tion about their environment. Each robots exhibits random motion that may be programmed,
for instance to perform probabilistic search and tracking tasks, or that arises from inherent
sensor and actuator noise. This random motion produces uncertainty in the locations of robot
encounters with a boundary. For this reason, we refer to the task as stochastic boundary
†School of Computing, Informatics, and Decision Systems Engineering, Arizona State University, Tempe AZ
85287.
‡School for Engineering of Matter, Transport and Energy, Arizona State University, Tempe AZ 85287.
¶This work was supported by DARPA Young Faculty Award no. D14AP00054.
1
coverage. In addition, we assume the robots have sufficient memory to store certain data
structures.
1.2. Summary of Results. We devise a data structure to implement our coverage schemes,
and we compute the probabilities of connectivity of various coverage schemes.
1.3. Models of Boundary Coverage. We consider a team of robots, {Ri} ∈[1...n] in
a bounded environment E . Robots are provided only with their (perfect) odometric readings
and Wifimeasurements, and a camera for detecting landmarks. Each robot is a disk of di-
ameter R, and its Wi-fihas a coverage radius of d. They have no knowledge of their global
positions or other means to localize. In the environment is placed a load in the form of a
thin line, called the Boundary B, which is colored black, distinctively from the rest of the
environment. One endpoint of B is painted white.
Since the main thrust of this paper lies in the randomized analysis of the network created by
the robots, we will make the following simplifying assumptions. All robots are synchronized
in time, with respect to a global clock. No robot fails in the course of its execution. Dealing
with failures, and determining the success of boundary coverage in rugged environments
where Wifimay fail are issues to be addressed in our future work.
To begin with, we consider point robots, for which R = 0 and thus the issue of inter-robot
collisions does not arise. Let n of them attached to B at a time instant t ∈N [18]. Let the
position of robot i be xi. Define the vector of unordered positions to be x(t) :=
x1...n

T. It
will be convenient to make our computations if we sort this vector in nondecreasing order
to get its permutation x =

x1...n

T, whose entry xi is the i-th robot from the left, and not
necessarily the position of Ri. Since xi forms the i-th smallest of the n entries of x, it is called
the i-th order statistic of the positions [5]. We may think of x (and x) as the realization of a
PP in Bn, so that x forms a point in Bn. Define the random variable associated with xi to be
Xi, and place all these rv’s in a vector X that defines the PP.
For convenience, we introduce two artificial robots x0 = 0 and xn+1 = s stationed at the
endpoints of B. Since connectivity deals with inter-robot distances, it helps to think of them
directly rather than in terms of x. Define the i-th slack si to be the distance from xi to xi+1,
and the slack vector s s1:n+1 := x1:n+1 −x0:n to be the vector of all slacks. Analogous to the
rv’s associated with positions, define the rv’s Si and the vector S. We may think of s as a point
in Bn+1.
Now we introduce the notion of connectivity by defining a communication range d ∈[0,s].
Two robots xi and x j are connected iff |xi −x j| ≤d. We model connectivity by a graph G (x),
whose nodes are xi (or xi) , and edges are formed by pairs of connected robots. Since each
node is a geometric position, G (X) forms a Geometric Graph. We define a position vector x
to be connected iff G (x) has a path from x0 to xn+1, and disconnected otherwise. When robot
positions are chosen randomly, this graph becomes a Random Geometric Graph (RGG) [27].
We will now make the transition from point robots to R-sized ones on the boundary. Define
the position of a robot as that of its left end, so that robot Ri located at xi occupies the interval
I0i = [xi,xi + R]. The support of an attached robot position is B′ = [0,s −R] (or a subset
of it), so that the robot does not fall of the boundary endpoint x = s. We define the position
vector x of n robots to be feasible if there are no interrobot collisions, i.e. each slack si is at
least R.
When a robot attaches to the boundary, it selects an interval of the boundary of length R lying
completely within the boundary. We will generally be able to abstract intervals into points,
2
and consequently think of a SCS as the choice of multiple random points on the boundary.
Formally, a SCS is a one-dimensional Point Process (PP) [12] realized on the boundary. A
special case of a PP involves robots attaching to a boundary at predefined locations. We will
be interested chiefly in the Poisson Point Process (PPP) in which robots attach independently
to the boundary, and its generalizations such as the Markov Process [12]. The independent
attachments in PPPs make them easy to analyze; on the other hand, interactions between
robots are harder to handle and require generalizations of PPPs.
To simplify our analysis, we will first work with point robots in Sec.3 which have ∆= 0,
and consequently preclude inter-robot collisions. Point robots are an idealization of finite
robots which have nonzero diameter; they also provide useful approximations to the behavior
of finite robots when ∆≪s. We will compute the connectivity properties of each SCS that
we address, which include the probability of saturation, the distribution of distances to the
nearest neighbor, and the joint and marginal pdfs of robot positions and inter-robot distances.
1.4. Problem Statement. We require the robots to perform the following tasks:
PROBLEM 1.
1. Form a connected network at the white endpoint of B.
2. Attach to the boundary, forming a connected network, or cover as much of the
boundary as possible.
3. Efficiently the list of positions taken up by the team on B
4. Be able to update the map efficiently as robots join and leave the boundary
5. Determine at any point of time the network graph, including the following proper-
ties: coverage length, number of redundant robots (i.e. those that can be removed
without loss of coverage).
PROBLEM 2. Compute the network properties for a random attachment scenario.
1.5. Related Work.
1.5.1. Control of Multi-Robot Systems. Previous work on decentralized multi-robot
boundary coverage has focused on controlling robots to converge to uniform or arbitrary
formations on a circle [32]. In contrast to this work, we consider cases where there is inherent
and/or programmed stochasticity in the robots’ motion, and our objective is to achieve robot
configurations with target statistical properties. We assume that every robot has minimal
capabilities: no global position information, and sensing or communication only within a
small radius. Task allocation strategies that are suitable for such scenarios often derive robot
control policies from a continuum model of the swarm population dynamics, or macroscopic
model, in order to enable the control policies to scale with the swarm size. Various stochastic
approaches to robot task allocation have focused on optimizing the task-switching rates of
such macroscopic models [2, 4, 21, 22, 26]. Macroscopic models have also been applied to
problems of robotic assembly of products, as well as robotic self-assembly [9,17,23,25].
1.5.2. Wireless Networks. Since our interest lies in getting a robot team to form a
connected Wi-finetwork around a boundary, we will dwell on data structures for routing
in Mobile Ad Hoc Networks (MANETs) [15]. However, our main focus lies in analyzing the
properties of the Geometric Graph (GG) formed by the multi-robot network. Our probabilistic
analysis borrows heavily from the formalism of Poisson Point Processes (PPP) [28], a class
3
of spatial stochastic processes in which each robot takes positions independently of others.
The network induced by a PPP is a Random Geometric Graph (RGG) [28]. When attachments
are required to be collison-free), i.e. have no colliding pairs of robots, they are characterized
by a Matern hard core process (HCP). These spatial processes and their resulting RGGs have
been extensively used in the wireless communication literature [12].
1.5.3. Computational Geometry. All our results that compute pcon(G), the connectiv-
ity probability of G , involve the order statistical properties of the pdf governing the attach-
ment of individual robots, called the parent pdfs, or parents for short [5]. The order statistics
of a collection of random variables X1:n are generated by sorting them in nondecreasing or-
der to get their permutation X. The order statistics of uniform iid parents are the easiest to
analyze; moreover,nonuniform iid parents of other forms may be readily converted to their
uniform counterparts using the probability integral transform [5]. We use the computations
in [8] to derive a pseudo-P lower bound for computing pcon(G ) for uniform parents in ??.
Further, we demonstrate that determining pcon(G ) for arbitrary iid pdfs is #PH, by reduction
from a result in [7,8].
The analogous computation of pcon(G ) for independent, non-identical (inid) pdfs is consider-
ably more complicated, and uses the Bapat-Beg theorem [10]. This computation is governed
by a [?]. We show in Sec.5.3 by a reduction from the boolean permanent problem [?] that
computing pcon is #PH.
Our results for the Stochastic Coverage Scheme (SCS) involving Renyi parking stems from
the work of Renyi [29] and Dvoretzky et al. [6]. The Renyi Parking Problem (RPP) defined
in Sec.4 has been extensively studied in the physics literature under the name Random Se-
quential Adsorption (RSA), the process by which molecules get adsorbed onto a substrate
surface [30, 31]. The delay differential equation that governs the mean number of parked
cars is extensively analyzed in [6,30]; moreover, [30] computes the asymptotic properties of
an interval tree that stores the occupied subintervals of the parking lot. To our knowledge,
however, there has been no analysis of the spatial probability density functions (pdfs) gen-
erated by the RPP. We derive an algorithm for computing this pdf using results from order
statistics [5].
2. Deterministic Coverage Strategy (DCS) for B. We will first provide a DCS for a
group of finite-sized robots to form a connected network with uniform inter-robot spacing
along a boundary B. This algorithm starts with a simple procedure, detailed in Algorithm 1
below, that is guaranteed to make all robots join the same network. Assuming there are no
faults, Algorithm 1 will terminate with all robots joining the network created by robot R1.
In this MANET, every node acts as a router. Once the robot team forms a connected network
after the execution of Algorithm 1, the ID of every robot in the network is determined by
flooding. This set of IDs is stored in the routing table of every robot. Subsequently, one robot
(say, R1) leaves the network to determine the length s of the boundary using its odometry, and
then rejoins the network by following the boundary back to its white endpoint. The maximum
number of robots that can possibly attach to B is
nmax = ⌊s−R
R
⌋.
(2.1)
The minimum number of robots required to ensure connectivity is
nmin = ⌊s
d ⌋.
(2.2)
4
Algorithm 1
1: procedure FORM A CONNECTED NETWORK(i,n)
2:
state ←EXPLORE
3:
while Black Boundary not seen do
4:
Execute Lawnmower walk
5:
while White endpoint not seen do
6:
Traverse B
7:
if id = 1 then
8:
Create Wifinetwork
9:
else
10:
while network not created do
11:
Wait
12:
Join Wifinetwork
13:
state ←CONNECTED
Based on these limits, the connectivity of the robot network falls into three categories:
Case 1: If n < nmin, then at most nd of the boundary can be covered.
Case 2: If n ∈[nmin,nmax], then all robots can be accommodated, and can cover the boundary
entirely.
Case 3: If n > nmax, then n−nmax robots have to be dropped from coverage. In this case, the
first nmax robots attach to the boundary, and the remaining are dropped.
Robots subsequently take up positions that are spaced d apart, so that xi = (i −1)d, using
their odometry, with the white endpoint being considered x0 = 0. Afterwards, the robots can
coordinate to attach to, or detach from, B. This DCS can be easily adapted to any SCS as
follows. Instead of taking up equidistant positions, the robot team collectively samples from
a joint pdf of their positions on B, and attaches to these positions in order. The initial step of
forming a connected network makes it easy to execute either coverage scheme.
2.1. Determining properties of G . The robots can use the Optimized Link State Rout-
ing (OLSR) protocol [13, 14] to determine the connectivity, coverage length, and number of
edges of G at any instant. OLSR is a proactive, table-driven routing protocol, each of whose
nodes maintains a table of 1-hop neighbors, which are found by flooding HELLO messages
through the network. When a new node joins or an existing one leaves the network, a set
of TC (Topology Control) messages are initiated by the neighbors of this node, flooding the
network with updated routing tables. Robots can determine the properties of the network as
follows:
1. Decide network connectivity: Every robot floods the network with a message con-
sisting of its id and its position. The flooding of the network is deemed to stop after
a timeout τ, known to all robots, at which time every robot compiles a table of robot
positions and id’s. From this table, the leftmost and rightmost robot IDs, x1 and
xn, are identified. If xi ≤d and xn ≥s −d, then the entire network is connected.
Otherwise, each robot deems the network to be disconnected as a whole.
2. Number of Connected Components: Each robot can determine its own connected
component from the routing table. If the connected component of any robot covers
both end-points of B, then the network as a whole is connected. Otherwise, after
5
a timeout period τ that is known to all robots, one robot (say R1) detaches and tra-
verses the boundary, querying the nearest robots about their connected components.
After one full traversal of B, R1 computes the total number of connected compo-
nents and updates. It subsequently updates other robots of this number in a second
traversal of B.
3. Number of edges: This is a variant of the approach for computing the number of
connected components. Each connected component may determine the number of
edges in it independently of others. As before, R1 detaches and traverses B to query
the number of edges in each connected component, which is then broadcast to each
robot.
2.2. Creating and updating a list of robot positions. Each robot Ri in the network
maintains data about robot positions along the boundary in the form of an interval tree [1]. If
this position data is too large to fit into the memory of a robot, it will keep track only of its m
nearest neighbors, where the size m is the maximum allowable size of the tree. The interval
tree handles insertions, deletions and search queries in O(logm) time.
An incoming robot that wishes to attach to B, say Rn+1, will approach B and send a broad-
cast query to the network to determine the locations of slacks that are large enough for it to
attach. A subset of the attached robots will then respond to Rn+1 with a list of slacks where
it may attach. Subsequently, Rn+1 attaches and broadcasts its position to its neighbors, who
in turn update their position data. Likewise, an outgoing robot R1 notifies its neighbors of
its impending detachment. The neighbors recompute the resulting slacks, making note of any
disconnected slacks introduced by the detachment of R1. They subsequently clear R1 for
detachment, following which R1 detaches.
2.3. Discussion. This section has presented only a high level view of the BC protocol.
We have deliberately processor failures, asynchrony, and anonymity for the sake of simplicity.
A detailed discussion of these issues would distract from our objective of analyzing G .
3. IID Coverage by Homogeneous Point Robots. In this section, we consider an SCS
driven by a Poisson Point Processes (PPP), in which every robot attaches independently to B,
following the same spatial parent pdf. In other words, X consists of iid random variables, and
defines a PPP on B. Specifically, suppose that the parent pdf and cdf are p f(x) and pF(x)
respectively, both supported on B. Then the number of points N falling on a subinterval [a,b]
of B is a Poisson random variable with underlying pdf p f(x):
N(a,b) ∼Poi(λ) where λ =p F(b)−p F(a).
(3.1)
We derive connectivity results for this SCS for a fixed team of n robots and then generalize
these results to a case of dynamic attachment and detachment. Our primary parameters of
interest are the connectivity properties of G (X), namely the probability pcon of connectivity,
the expected degree of a vertex, and the number of clusters, all of which . Subsequently, we
determine the spatial pdfs of X and S, both for connected and unconnected components of G .
We then apply these results to analyze the temporal properties, such as recurrence times, of
dynamic scenarios in which robots attach and detach probabilistically. [18,19].
3.1. Geometric interpretation of connectivity. We interpret x and s as points in Rn
and Rn+1, respectively. The entries of x are nondecreasing, and thereby define the position
6
simplex [19]
P = {x1:n : for all i : 1 ≤i ≤n, we have that 0 ≤xi ≤xi+1 ≤s}.
(3.2)
Likewise, all valid slack vectors, i.e. those that arise from a robot configuration on B, have
entries whose sum is the boundary length s. Geometrically, s defines a point on a simplex S
that we call the slack simplex [18], given by
S := {s : 1Ts = s, and 0 ≤s ≤s1} = s·∆n,
(3.3)
where
∆n := {s : 1Ts = 1, and 0 ≤s ≤1}
(3.4)
is the canonical simplex in Rn. The vertices of S are
V(S ) = s·In+1 = s·
ˆe1 ... ˆen+1

,
(3.5)
where ˆei is the unit vector along the i-th axis. Eq.(3.3) expresses S as a degenerate simplex,
with Lebesgue measure zero in Rn+1. For our computations, we will need to express S in
full-dimensional form as
S = {s1:n ∈Rn : 0T ≤s, and 1Ts ≤s},
(3.6)
by dropping the last slack sn+1, which is determined by its predecessors. Observe that all
connected configurations, regardless of whether they are valid, fall within the hypercube
H := {0 ≤s ≤d1T} = d ·Cn,
(3.7)
where Cn is the unit hypercube [0,1]n.
A valid slack vector has to lie in the intersection S ∩H to represent a connected con-
figuration. Define the connected region as F = S ∩H and the disconnected region as
U := S \ F. We show in [18] that d falls into three ranges,
d ∈





[0,
s
n+1], for which F = ∅and pcon = 0;
(
s
n+1,1), for which F ⊊S and pcon ∈(0,1);
[1,∞), for which F = S and pcon = 1.
(3.8)
We may express F as
F = {s1:n ∈S : s−d ≤1Ts1:n and s ≤d1T}.
(3.9)
The parent p f generates the joint pdf [5]
fX(x) = n! ∏
1≤i≤n
f(xi)IP.
(3.10)
over the the position simplex, where I denotes the indicator function over the region in its
subscript. This pdf is called the Janossy pdf [12] of the PPP. Changing the argument from x
to s gives us
fS(s1:n) = n! ∏
1≤i≤n
f(
i
∑
j=1
sj)1S .
(3.11)
7
We will compute the properties of G in the coming subsections, starting with pcon. The for-
mula for finding pcon provides us with a template for partitioning S into regions that are
amenable to computing the following properties of G : the number of connected components
of G , the coverage induced by G , and the edge count of G . While these quantities are nontriv-
ial to compute for RGGs of arbitrary dimension [27], there exist straightforward, if tedious,
algorithms to compute them for a single dimension. All these algorithms essentially involve
computing the ratio of integrals of the joint pdf ˜s over a subset of S .
3.2. Probability of connectivity. The probability of connectivity pcon is the ratio of the
volume of the joint pdf lying over F to that over S :
pcon := Leb(S,F)
Leb(S,S ) =
R
F fS(s)ds
R
S fS(s)ds.
(3.12)
where Leb(S,S ) computes the Lebesgue measure of the joint pdf of S over S . The denom-
inator is relatively easy to evaluate analytically using barycentric coordinates [11], while the
integral over F is harder to compute, since there is no obvious way to decompose it into sim-
plices. A naive algorithm that triangulates F into simplices will take a long time in practice
when n is large. Instead, we may write Leb(S,F) = Leb(S,S )−Leb(S,U ), decompose U
into simplices rather than F [19] , and finally compute pcon = 1 −Leb(S,U )
Leb(S,S ).
This decomposition of U will result in overlapping simplices, whose measures we can com-
bine using the combinatorial approach described in [19].
U =
[
v∈{0,1}n\{0}
U (v),
(3.13)
where U (v) forms a simplex of side (s−d1Tv), with the vertices
V(U (v)) = (s−d1Tv)In+1 + v.
(3.14)
This expression is nonnegative when s ≥d1Tv, so that only those vertices with at most nmin =
⌊s
d ⌋d’s in them need be considered. The value nmin is the minimum number of robots required
for connectivity, as well as the maximum possible number of disconnected slacks. We call
the simplex U (v) the compatible simplex of v. Compatible simplices overlap, so the sum
of their measures exceeds that of U . We first decompose U using the inclusion-exclusion
principle (IEP) as:
U =
[
odd v
U (v)\
[
even v
U (v)
(3.15)
where the (even or odd) parity of v is that of its number of 1-bits. We immediately have
Leb(S,U ) =
∑
v∈{0,1}n+1
(−1)1T vLeb(S,U (v)).
(3.16)
Our remaining computations will rely heavily on the decomposition of S into U (v).
8
3.3. Number of Components. A slack vector s has a single connected component iff
it is connected, i.e if s ∈F. Each unsaturated slack in s inserts a new connected component
into G . Define the component counting function
cmp : S 7→N with cmp(s) =
n+1
∑
i
(
1 if si ≤d
0 otherwise.
(3.17)
where N = {0,1,2,...}. By definition, we have cmp = n+1−1Tv identically over U (v). We
may then compute the expectation of cmp over S by writing S = U ∪F, and consequently
get
E(cmp) = Leb(cmp,S ) =
∑
v∈{0,1}n+1:1T v≤nmin
(−1)1T v
Z
U (v)(n + 1 −1Tv)fS(s)ds.
(3.18)
3.4. Coverage Length. To determine the length of the B covered by s, we will intro-
duce the coverage function cov(s). If s is connected, then its coverage length cov(s) is the
boundary length s. If s has a disconnected slack si, a length of si −d is left without coverage.
This motivates us to define cov by
cov : S 7→R with cov(s) = s−
n+1
∑
i
max(si −d,0).
(3.19)
Computing E(cov) over S does not get simplified by the decomposition S := U ∪F, for
cov is non-constant over U . A straightforward integration gives us
E(cov) = Leb(cov·S,S ) = s·Leb(S,S )−
n+1
∑
i=1
max(0,si −d)fS(s)ds.
(3.20)
3.5. Number of edges of G . We will define the edge counting function edg(.) over
positions rather than slacks. Given the position vector x, there exists an edge between xi and
x j iff x j −xi ≤d. Accordingly, we have
edg : P 7→N, with edg(x) :=
n−1
∑
i=1
n
∑
j=i+1
1 −max(x j −xi −d,0)
(3.21)
with E(edg) being the integral of Eq.(3.21) over P:
E(edg) = Leb(X,P)−
Z
P
∑
i,j:1≤i< j≤n
max(x j −xi)fX(x)dx.
(3.22)
3.6. Dynamic coverage with iid attachment. Now we will examine a strategy in which
the robot team dynamically attaches and detaches from the boundary, with their spatial attach-
ment pdfs being iid on B.
9
3.6.1. Dynamic attachment. We first consider the case in which robots attach to the
boundary without detaching. One robot position is chosen at every time step using the parent
pdf p f until connectivity is achieved. We compute the expected time until connectivity, or the
expected stopping time of the SCS. To determine the stopping time, we consider the sequence
(pi)i∈N, where pi is the probability of connectivity with i robots. Irrespective of the parent
pdf p f, having more robots on B leads to a greater probability of connectivity. Consequently,
the sequence (pi) is monotonically increasing on the support [nmin,∞) and tends to unity as i
grows without bound. We also know that pi:i≤nmin = 0. Consequently, the attachment process
will terminate (resp. fail to terminate) at i ≥nmin robots with probability pi (resp. 1 −pi).
The probability of connectivity being attained at i robots is:
τi =
(
0 for 1 ≤i < nmin
(1 −pi−1)pi for i ≥nmin
(3.23)
Thus, τi is a generalized geometric random variable whose probability of success in a trial is
distinct from that in its previous one. The expected stopping time is
E(τ) =
∞
∑
i=nmin
iτi.
(3.24)
Since pi > pnmin for i > nmin, we expect quicker connectivity than that of a geometric random
variable whose parameter is pnmin Eτ ≤
1
pnmin .
3.6.2. Stopping time of connectivity for Uniform parent. The uniform parent has the
special property that S is jointly uniform over S , with each slack being identically distributed
(though not iid) as scaled exponentials of the form s·Exp(1). Further, the order statistics of
the slacks, represented by the vector s, formed by sorting s in increasing order, obey the
relations [5]:
E(Si) =
s
n + 1
n+1
∑
j=1
1
j =
s
n + 1(Hn+1 −Hi)
(3.25)
V (Si) =
n+1
∑
j=i
1
j2
(3.26)
where Hn denotes the harmonic numbers. The longest slack Sn+1 has the expected value
sHn+1
n+1 . To have sn+1 ≤d, we need Hn+1
n+1 ≤d
s , which may be solved numerically to get the
expected hitting time of F. We may also estimate n if n is large by approximating Hn with
logn, providing
log(n + 1)
n + 1
≤d
s =⇒n = exp(−W(d
s ))−1,
(3.27)
where W is the Lambert W function.
3.6.3. Dynamic attachment and detachment. We now extend the results in Sec.3.6
to a scenario in which we require robots to strike a balance between forming a connected
network on the boundary and exploring the surrounding environment of the boundary. For-
mally, we are given that at every time instant t ∈R+, a robot may be either attached to
10
the load or detached from it; in other words, the robot has a temporal state alphabet Σ :=
{A (attached), D (detached)}.
PROBLEM 3. Design the rates of switching between states, with a guarantee on the expected
amount of time that the boundary will have a connected network.
To analyze the behavior of the robots, we introduce the temporal state N(t) =

NA(t)
ND(t)
T,
whose entries denote the number of robots in states A and D, respectively. We assume that
the total number of robots is conserved, which implies that
(3.28)
NA(t)+ ND(t) = NA(0)+ ND(0).
Now we suppose that robots change state per the chemical reactions
A
rAD
−−→D and D
rDA
−−→A
(3.29)
where rij, the reaction rate constant, is the probability per unit time of a robot in state i to
switch to state j. The populations of robots in both states evolve over time as
d
dt N(t) =
−rAD
rDA
rAD
−rDA

N(t).
(3.30)
At equilibrium, d
dt N(t) = 0, and so Eq.(3.30) yields
NA∗
ND∗= rDA
rAD
.
(3.31)
We solve for NA∗and ND∗using Eq.(3.28) and Eq.(3.31).
4. Uniform Coverage by Homogeneous Finite Robots. We now consider SCS with
finite robots, each of which has a nonzero diameter R. Unlike the case of point robots, the
maximum number of attached robots is finite and given by
nmax = ⌊s
R⌋.
(4.1)
Collision-free positions are a realization of a Matern hard-core PP [12], which prohibits
its points from lying within a threshold distance of each other. The valid range for n is
[nmin,nmax]. When d ≤R, every feasible configuration becomes a saturated one, causing nmin
to coincide with nmax. The case d = R is of special interest to us, since it is an instance of
Renyi’s Parking Problem.
PROBLEM 4. Renyi’s Parking Problem [6,30] Cars of unit length park uniformly randomly
on a segment of length s, avoiding collisions, until no parking space is available for the next
car. Analyze the pmf of the final number of parked cars, N.
The mean number of parked cars, EN, obeys a delay integral equation with the asymptotic
solution
lim
s→∞EN = npc ·s ≈0.748s.
(4.2)
where npc is Renyi’s parking constant [29]. This result implies that we expect 75% of the
segment to be occupied by cars at the point where there is no more room to accommodate
another car. An exact solution for EN leads to an intractable ⌊s⌋-dimensional integral [24].
Our SCS with fixed n and uniformly random attachments is a special case of Renyi’s Parking
Problem in which N is trivial to compute. However, to our knowledge, there has been no
analysis of the spatial pdfs that are generated by the parked cars in this problem, which we
provide in Sec.4.1.
11
4.1. Connectivity of Collision-Free Parking. We now formulate the CF equivalent of
the point-robot attachment in Sec.3. Define the position of a robot as that of its left end,
so that robot Ri located at xi occupies the interval [xi, xi + R]. The support of all attached
robot positions is B′ = [0,s −R], which ensures that no robot extends beyond the boundary
endpoint x = s. We introduce two artificial robots at x0 = −R and xn+1 = s. Define x to be
collison-free (CF) iff
(4.3)
0 ≤x0,
xn ≤s−R, and xi −xi−1 ≥R, for i = 1...n,
and define PCF to be the set of CF position vectors. Likewise define the CF subset of S and
the resulting favorable region by
SCF := {s ∈S : R·1T ≤s}
(4.4)
FCF := SCF ∩H = {s ∈S : R·1T ≤s ≤d ·1T}.
(4.5)
Geometrically, SCF is a simplex with the hypercuboids 0 ≤si ≤R removed. Reasoning as
in Sec.3, we have pcon(G ) = Vol(FCF)/Vol(SCF); however, we are unable to simplify this
formula further as we did there. The lack of a simplifying expression for pcon means that
the computation of pcon(G ) has to involve the triangulation of FCF into simplices, a time-
consuming operation that we explicitly avoided in Eq.(3.13). Likewise, expressions for the
order statistics and slacks of CF positions are obtained by integrating the uniform joint pdf
over SCF instead of S , as do the formulae for the properties of G .
5. Complexity Results of SCS.
5.1. Computing pcon for uniform iid parents. We now investigate the complexity of
exactly computing the integrals in Eq.(3.16). We begin with a pseudo-P lower bound for com-
puting Vol(F), and consequently PCON for the uniform parent. We will then discuss lower
bounds for non-uniformparents. Define the complexity theoretic problem PCON(f,s,d,n) 7→
pcon, with
Input: Parameters of SCS : encoding of p f, ; s,d ∈Q+ ; n ∈N
Output: Probability of connectivity pcon ∈Q+
Rational inputs and outputs are specified as exact reduced fractions; for example s is input as
the pair (num(s),den(s)). Let PCON(U) denote that subproblem of PCON over a uniform
SCS.
THEOREM 5.1. PCON(U) can be solved in Ω(n) and O(nlogn) time.
Applying Eq.(3.16) gives us [18]
Vol(S ) = sn ·
√
n + 1
n!
,
(5.1)
Vol(U ) =
nmin
∑
k=1
(−1)k−1
n + 1
k
(s−kd)n√n + 1
n!
,
(5.2)
PCON = Vol(F)
Vol(S ) = 1 −
nmin
∑
k=1
(−1)k−1
n + 1
k
1 −kd
s

n.
Proof. Upper bound: Eq.(5.1) is a possible solution for PCON(U); therefore, its worst-case
running time forms an upper bound for PCON(U). Eq.(5.1) runs in O(nmin logn) time; its
12
worst-case instances, which have n > nmin take O(nlogn) time, which forms an upper bound
for any solution to PCON. Note that Eq.(5.1) forms a pseudo-P algorithm for PCON.
Lower bound: Consider PCON(U) instances with s = 4
3d, for which
PCON = 1 −(n + 1)· 1
4n ≈1 −n
4n
(5.3)
The input size for these instances is O(logn), but the output size is exponential in the input
size, implying an Ω(n) lower bound for any algorithm for PCON(U). The upper bound
of O(nlogn) is off from the lower bound Ω(n) only by a polynomial in the input size of
PCON(U), implying that algorithms for PCON consume more time in outputting the solution
rather than computing it. The lower bound is an exponential function of the input size, hence
PCON(U) ∈#EXP.
Time complexity of computing Vol(F): The √n in the formula for Vol(F) makes it impos-
sible to provide a bounded decimal expansion to Vol(F), hence the complexity of writing
down Vol(F) is infinite, except when n is a square. Remedying this unbounded expansion
requires us to compute Vol(F)·
n!
√n+1, for which the same bounds as PCON(U) apply. The
same bounds apply to Vol(U )·
n!
√n+1.
5.2. Generalized Simplex Hypercube intersection. In the coming sections, we will
demonstrate that our problems are #PH by reduction from the VHSP problem.
LEMMA 5.2. Define the problem VHSP:
Input: Parameters a1:n,b of the halfspace T := {s ∈Rn : aTs1:n ≤b}, with a and b are
positive rationals
Output: Volume of intersection of T with the unit hypercube C := [0,1]n
The solution to VHSP given by
Vol(T ∩C ) = n!
n
∏
i=1 ∑
v∈[0,1]n
(−1)1T v max((b −aTs)n,0).
(5.4)
is #PH. Equivalently, it is #PH to find the probability that a random point in C satisfies a
single linear inequality.
It will be useful to redefine VHSP as an intersection between a half-space with unit coef-
ficients and a generic hypercuboid. Introduce the primed variables s′
i := aisi, and note that
VHSP asks for Vol(T ′ ∪C ′), where
T ′ := {s′ ∈Rn : 1Ts′ ≤b} and
(5.5)
C ′ := ∏[0,ai].
(5.6)
5.2.1. Nonuniform iid parents. We will now give an example of a nonuniform parent
whose pcon is #PH to compute. For this purpose, define a k-piecewise uniform (k-PWU) over
a finite support [0,L] as follows. Partition the support into k nonempty subintervals as
[0,L] := [0,L1]∪[L1,L2]...∪[Lk,s].
(5.7)
13
On the i-th subinterval, f(x) is defined to be the constant pi ∈[0,1], which are chosen to
satisfy ∑pi(Li −Li−1) = 1, and consequently f is a pdf on B.
THEOREM 5.3. PCON(nU) is #PH.
Proof. Given the VHSP instance with the dimension n + 1, having the hypercuboid C ′ :=
∏1≤i≤n+1[0,li] and the half-space sum b. Let L := ∑li. Define the equivalent instance of
PCON to have the parameters
s := b
L, d := 1 ,and p f := li
L if x ∈[i,i+ 1]
(5.8)
Define Yi ∼p F(Xi) to be the probability integral transform of Xi. From the definition of Yi,
we have that P(xi ∈[i,i + 1]) = P(yi ∈[0, li
L)]. It follows that if X is connected, then Y lies
within C ′. Moreover, Y is jointly uniform on the half-space
T ′ = {y ∈Rn : y ≥0 and ∑yi ≤s}.
(5.9)
Thus, pcon = Vol(T ′ ∪C ′)/Vol(C ′), from which the solution to VHSP can be computed in
P time.
5.2.2. Extensions of Theorem 5.3. We may extend Theorem 5.3 to more general par-
ents satisfying the constraints that:
d
Z
(i−1)d
p f (x)dx = li, for all i = 1,...,n, where li ≥0 and∑li = 1.
(5.10)
Since Eq.(5.10) provides us with n constraint equations, p f needs to have at least n param-
eters to fit them, e.g. polynomials of degree n, with arbitrary coefficients. More generally,
if f1,..., fn are arbitrary pdfs with unit supports, each having at least one parameter, their
mixture
p f(x) = fi(x) if x ∈[i−1,i)IB, where B = [0,n + 1]
(5.11)
may be fit to obey Eq.(5.10). Consequently, computing PCON for this mixture is #PH.
On the other hand, problems with a constant number of parameters fail to admit such a reduc-
tion analogous to Theorem 5.3, fail to be #PH even though they may not exhibit an explicit
formula for #PH. For example, we do not know a short formula for computing pcon for
Renyi parking, as mentioned in Sec.4.1. Nonetheless, the problem lacks sufficiently many
free coefficients to admit a reduction, and consequently is not #PH. Likewise is the case of
nonuniform parents such as Beta, Triangular, and clipped Gaussian pdfs on B.
5.2.3. Robots with heterogeneous connectivity thresholds. We now consider a Het-
erogeneous robot team whose Wifiadapters have different transmission power, so that Ri
has connectivity threshold di. We call Ri weaker (resp. stronger) than R j iff di < d j (resp.
di > d j). If di = d j we say that the two robots have equal power. Then the robot network is
represented by the digraph G , whose directed edges are of the form i →j iff Ri can transmit
to R j. In general, edges are not bidirectional, since a weaker robot will not sense a stronger
14
one, even though the converse holds true. Suppose without losing generality that the di’s form
a strictly positive, non-decreasing sequence.
Consider a configuration in which the robots are arranged from left to right in increasing order
of their index. A connected configuration satisfies the n + 1 constraints
s2i−1, s2i ≤di for all i : 1,...,⌊n/2⌋, and in addition
(5.12)
sn+1 ≤dn/2 if n is even.
In general, a connected configuration will have two distinct slacks si1,si2 each less than di.
Further, the connected region is the intersection of S with the union of hypercuboids, each
of which has two dimensions equal to di, and an extra dimension equal to dn/2 if n is even.
Define H to be:
H =
[∏[0,ai],where the ai are a permutation of the di.
(5.13)
The number of hypercuboids in H is at most n!, which is the case when all di’s are distinct.
We will assume that the di’s are distinct unless mentioned otherwise. Since H is nonconvex
in general, so is F = H ∩S . When s is sufficiently large that all n robots are required to
connect it, F becomes the disjoint union of n! pieces, each of which is the intersection of S
with one of the component hypercuboidsof H . Then we have that Vol(F) = n!Vol(S ∩C ′),
where C ′ is the hypercube with dimensions d1 × d1...× dn × dn.
THEOREM 5.4. PCON is #PH for heterogeneous connectivity.
Proof. Consider the odd-numbered instance of VHSP in dimension 2n+1, with hypercuboid
dimensions l1,l1,...,ln,ln,ln+1 and slack sum b. Assume that the li’s are distinct. It is clear
that this instance of VHSP is at least as hard as its counterpart in Rn with dimensions l1,...,ln,
and thus is #PH. The equivalent instance of s = b
L + 1 and (di)1≤i≤n = li/L, where L = ∑li
as before. The solution of VHSP is now n!pconVol(C ′), which is computable in P time from
the solution to PCON.
It is immediately clear that finding Vol(F) and Vol(U ) is #PH for heterogeneous connec-
tivity. With homogeneous robots, F was more symmetric compared to its heterogeneous
counterpart. Exploiting this symmetry led to relatively short formulae for PCON and the
like. On the other hand a heterogeneous swarm is sufficiently diverse that its connected
region be an arbitrary half-space. We pay for this expressiveness by making the connectiv-
ity problems harder. Computing pcon has a Fully Polynomial Randomized Approximation
Scheme (FPRAS), which samples a uniform pdf over a subset of F in P, using the Markov
Chain Monte Carlo (MCMC) method [16]. Combining MCMC with Inverse CDF Sampling
enables us to sample arbitrary IID pdfs over F. This approach is sufficiently general that
it adapts to arbitrary joint pdfs over F, in which case it becomes the Metropolis-Hastings
sampling [3].
5.3. Inid parents. We will finally relax the iid assumption by assuming that position Xi
has the parent pdf p fi, and is chosen independently of others. We denote the vector of parent
pdfs and cdfs by pf1:n and pF1:n respectively.
THEOREM 5.5. PCON-inid, the version of PCON generated by the inid parents X ∼p f1:n,
where each parent is supported on B, is #PH.
15
Proof. We reduce a #PH subset of PCON(nU) to PCON-inid. Let the given instance of
PCON(nU) have the boundary length s = n + 1, and the parent defined by the n + 1 pieces
p fi:1...n = pi over [i−1,i], with ∑pi = 1. The equivalent instance of PCON-inid will have 2U
parents and a boundary length s′ = n + 2. Define the i-th parent p f ′
i of the inid instance to be
p f ′
i =





pi for x ∈[i−1,i]
1 −pi for x ∈[n + 1,n + 2]
0 elsewhere on [0,n + 2].
(5.14)
It is clear that p f ′
i has unit measure on its support, and is thus a pdf. Further, if the original nU
instance is connected, then so is the inid instance on the interval [0,n+1], with connectivity
on the last segment [n + 1,n + 2] ignored. The unrestricted connectivity of the last segment
has no effect on the complexity of the problem.
REFERENCES
[1] MARK DE BERG, OTFRIED CHEONG, MARK VAN KREVELD, AND MARK OVERMARS, Computational
Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA, USA, 3rd ed., 2008.
[2] SPRING BERMAN, ´AD ´AM HAL ´ASZ, M. ANI HSIEH, AND VIJAY KUMAR, Optimized stochastic policies for
task allocation in swarms of robots, IEEE Trans. Robot., 25 (2009), pp. 927–937.
[3] SIDDHARTHA CHIB AND EDWARD GREENBERG, Understanding the Metropolis-Hastings algorithm, The
American Statistician, 49 (1995), pp. 327–335.
[4] NIKOLAUS CORRELL, Parameter estimation and optimal control of swarm-robotic systems: a case study in
distributed task allocation, in Proceedings of the 2008 IEEE International Conference on Robotics and
Automation, Pasadena, CA, USA, May 19–23, 2008, pp. 3302–3307.
[5] H.A. DAVID AND H.N. NAGARAJA, Order Statistics, John Wiley and Sons, Hoboken, NJ, USA, 2003.
[6] A. DVORETZKY AND H. ROBBINS, On the parking problem, Publications of the Mathematical Institute of
the Hungarian Academy of Sciences, (1964), pp. 209 – 224.
[7] MARTIN DYER AND ALAN FRIEZE, Computing the volume of convex bodies: a case where randomness
provably helps, Probabilistic combinatorics and its applications, 44 (1991), pp. 123–170.
[8] M. E. DYER AND A. M. FRIEZE, On the complexity of computing the volume of a polyhedron, SIAM J.
Comput., 17 (1988), pp. 967–974.
[9] WILLIAM C. EVANS, GR´EGORY MERMOUD, AND ALCHERIO MARTINOLI, Comparing and modeling dis-
tributed control strategies for miniature self-assembling robots, in Proceedings of the 2010 IEEE Interna-
tional Conference on Robotics and Automation, Anchorage, AK, USA, May 3–7, 2010, pp. 1438–1445.
[10] DEBORAH H GLUECK, ANIS KARIMPOUR-FARD, JAN MANDEL, LARRY HUNTER, AND KEITH E
MULLER, Fast computation by block permanents of cumulative distribution functions of order statistics
from several populations, Communications in Statistics-Theory and Methods, 37 (2008), pp. 2815–2824.
[11] NICK GRAVIN, DMITRII V PASECHNIK, BORIS SHAPIRO, AND MICHAEL SHAPIRO, On moments of a
polytope, arXiv preprint arXiv:1210.3193, (2012).
[12] MARTIN HAENGGI, Stochastic Geometry for Wireless Networks, Cambridge University Press, 2012.
[13] INTERNET
ENGINEERING
TASK
FORCE,
Optimized
link
state
routing:
RFC
7181.
http://tools.ietf.org/html/rfc7181, 2014.
[14] PHILIPPE JACQUET, PAUL M ¨UHLETHALER, THOMAS CLAUSEN, ANIS LAOUITI, AMIR QAYYUM, AND
LAURENT VIENNOT, Optimized link state routing protocol for ad hoc networks, in Multi Topic Con-
ference, 2001. IEEE INMIC 2001. Technology for the 21st Century. Proceedings. IEEE International,
IEEE, 2001, pp. 62–68.
[15] ABBAS JAMALIPOUR AND YAOZHU MA, Intermittently Connected Mobile Ad Hoc Networks: from Routing
to Content Distribution, (SpringerBriefs in Computer Science), Springer Science, 2011.
[16] MARK JERRUM, Counting, Sampling, and Integrating:Algorithms and Complexity, Lectures in Mathematics,
Birkhauser Verlag, 2003.
[17] ERIC KLAVINS, SAMUEL BURDEN, AND NILS NAPP, Optimal rules for programmed stochastic self-
assembly, in Proceedings of Robotics: Science and Systems, Philadelphia, PA, USA, August 2006.
[18] GANESH P KUMAR AND SPRING BERMAN, Analytical results and algorithms for stochastic boundary cov-
erage by robotic swarms, Submitted to IEEE Transactions on Robotics, (2014).
16
USING SIAM’S LATEX MACROS
17
[19] GANESH P. KUMAR AND SPRING BERMAN, Statistical analysis of stochastic multi-robot boundary cover-
age, in Int’l. Conf. on Robotics and Automation (ICRA), 2014, pp. 74–81.
[20] GANESH P. KUMAR, AUR´ELIE BUFFIN, THEODORE P. PAVLIC, STEPHEN C. PRATT, AND SPRING M.
BERMAN, A stochastic hybrid system model of collective transport in the desert ant Aphaenogaster cock-
erelli, in Proc. 16th Int’l. Conf. on Hybrid Systems: Computation and Control (HSCC), 2013, pp. 119–
124.
[21] WENGUO LIU AND ALAN F. T. WINFIELD, Modeling and optimization of adaptive foraging in swarm robotic
systems, Int. J. Robot. Res., 29 (2010), pp. 1743–1760.
[22] T. WILLIAM MATHER AND M. ANI HSIEH, Distributed robot ensemble control for deployment to multiple
sites, in Proceedings of Robotics: Science and Systems, Los Angeles, CA, USA, June 2011.
[23] LO¨IC MATTHEY, SPRING BERMAN, AND VIJAY KUMAR, Stochastic strategies for a swarm robotic assembly
system, in Proceedings of the 2009 IEEE International Conference on Robotics and Automation, Kobe,
Japan, May 12–17, 2009, pp. 1953–1958.
[24] GREG MULLER, The efficiency of random parking. http://tiny.cc/7r8a7x, 2007.
[25] NILS NAPP, SAMUEL BURDEN, AND ERIC KLAVINS, Setpoint regulation for stochastically interacting
robots, in Proceedings of Robotics: Science and Systems, Seattle, WA, USA, June 2009.
[26] LAEL U. ODHNER AND HARRY ASADA, Stochastic recruitment control of large ensemble systems with
limited feedback, J. Dyn. Syst., Meas., Control., 132 (2010).
[27] MATTHEW PENROSE, Random Geometric Graphs, Oxford Studies in Probability, Oxford University Press,
2003.
[28]
, Random Geometric Graphs, Oxford Studies in Probability, Oxford University Press, 2003.
[29] ALFR´ED R´ENYI, On a one-dimensional problem concerning random space-filling, Publ. Math. Inst. Hung.
Acad. Sci., 3 (1958), pp. 109–127.
[30] MATHIEU DUTOUR SIKIRIC AND YOSHIAKI ITOH, Random Sequential Packing of Cubes, World Scientific
Publishing Company, 2011.
[31] J TALBOT, G TARJUS, PR VAN TASSEL, AND P VIOT, From car parking to protein adsorption: an overview
of sequential adsorption processes, Colloids and Surfaces A: Physicochemical and Engineering Aspects,
165 (2000), pp. 287–324.
[32] CHEN WANG, GUANGMING XIE, AND MING CAO, Controlling anonymous mobile agents with unidirec-
tional locomotion to form formations on a circle, Automatica, 50 (2014), pp. 1100 – 1108.