1
Design of Stochastic Robotic Swarms for Target Performance
Metrics in Boundary Coverage Tasks
Ganesh P. Kumar and Spring Berman
School for Engineering of Matter, Transport and Energy, Arizona State University, Tempe, AZ 85287 USA
In this work, we analyze stochastic coverage schemes (SCS) for robotic swarms in which the robots randomly attach to a one-
dimensional boundary of interest using local communication and sensing, without relying on global position information or a
map of the environment. Robotic swarms may be required to perform boundary coverage in a variety of applications, including
environmental monitoring, collective transport, disaster response, and nanomedicine. We present a novel analytical approach to
computing and designing the statistical properties of the communication and sensing networks that are formed by random robot
configurations on a boundary. We are particularly interested in the event that a robot configuration forms a connected communication
network or maintains continuous sensor coverage of the boundary. Using tools from order statistics, random geometric graphs,
and computational geometry, we derive formulas for properties of the random graphs generated by robots that are independently
and identically distributed along a boundary. We also develop order-of-magnitude estimates of these properties based on Poisson
approximations and threshold functions. For cases where the SCS generates a uniform distribution of robots along the boundary, we
apply our analytical results to develop a procedure for computing the robot population size, diameter, sensing range, or communication
range that yields a random communication network or sensor network with desired properties.
Index Terms—Boundary coverage, distributed robot systems, swarm robotics, stochastic robotics, randomized algorithms
I. INTRODUCTION
Robotic swarms have the potential to collectively perform
tasks over very large domains and time scales, succeeding
even in the presence of failures, errors, and disturbances.
Low-cost miniature autonomous robots for swarm applica-
tions are currently being developed as a result of recent
advances in computing, sensing, actuation, power, control,
and manufacturing technologies. In addition, micro-nanoscale
platforms such as DNA machines, synthetic bacteria, magnetic
materials, and nanoparticles are being designed for biomedical
and manufacturing applications [1]–[3], in which they would
need to be deployed in massive numbers. Swarm robotic
platforms have limited onboard power that support only local
sensing capabilities and local inter-robot communication and
may preclude the use of GPS, or they may operate in GPS-
denied environments.
In this work, we consider boundary coverage (BC) tasks
for swarms of such resource-constrained robots. We define
a boundary coverage scheme (BCS) as a process by which
multiple robots autonomously allocate themselves around the
boundary of an object or region of interest. Robotic swarms
may be required to perform boundary coverage for mapping,
exploration, environmental monitoring, surveillance tasks such
as perimeter patrolling, and disaster response tasks such as
cordoning off a hazardous area or extinguishing a fire. Another
motivating application is collective payload transport [4]–
[6] for automated manipulation and assembly in uncertain,
unstructured environments. Furthermore, boundary coverage
behaviors will need to be controlled in micro- and nanoscale
systems that are designed for micro object manipulation,
molecular imaging, drug and gene delivery, therapeutics, and
diagnostics [7], [8]. For example, nanoparticles that are de-
signed for drug delivery and imaging can be coated with
ligands and antibodies in a specific way to facilitate selective
binding to tumor cell surfaces [9], [10].
We focus on stochastic coverage schemes (SCS), in which
the robots occupy random positions along a boundary. Since
swarm robotic platforms cannot perform precise navigation
and localization, randomness in their motion will arise from
noise due to sensor and actuator errors. Even if the robots
attempted to position themselves at equidistant locations along
the boundary, noise in their odometry would introduce un-
certainty into their resulting positions, such that each one
would be distributed according to a Gaussian [11]. In addition,
the robots may only encounter the boundary through local
sensing during exploration of an unknown environment, which
will introduce uncertainty in the locations of their interactions
with the boundary. In swarm applications at the nanoscale,
the effects of Brownian motion and chemical interactions
will contribute further sources of stochasticity in boundary
coverage.
We address the problem of designing parameters of a robotic
swarm that will produce desired statistical properties of the
communication and sensing networks that are formed by ran-
dom robot configurations around a boundary. These parameters
include the swarm population size and each robot’s physical
dimensions and sensing and communication radii, which we
assume are identical for all robots. The desired properties
pertain to the distribution of robots around a boundary that
result from an SCS; here we do not consider the process by
which the robots arrive at the boundary.
The novelty of our approach lies in our integration of a
variety of analytical tools to characterize properties of SCS,
as well as our application of these results to design robotic
swarms for desired SCS properties. We devise a geometric
approach to compute properties of the random graph generated
by robots that have attached to the boundary independently
of one another, in the case where robots may overlap. We
arXiv:1702.02511v1  [cs.RO]  8 Feb 2017
2
adapt this approach to the case where robots avoid conflicts,
i.e. they do not overlap with each other on the boundary. We
derive both closed-form expressions of SCS properties and
estimates of these properties based on Poisson approxima-
tions and threshold functions for Random Geometric Graphs
(RGGs). We combine these results to develop a new design
procedure for computing parameters of robotic swarms that
are guaranteed to achieve a specified SCS property.
The paper is structured as follows. We review related literature
in Sec. II and define the SCS properties that we seek to
compute and our problem statement in Sec. III. We introduce
relevant mathematical concepts in Sec. IV and provide formal
definitions of the SCS properties in Sec. V. In Sec. VI, we
summarize and extend a computational geometric formulation
of SCS, first presented in our work [12], that forms the basis
of our subsequent computations. In Sec.VII and Sec.VIII, we
derive formulas for SCS properties in cases where robots are
distributed uniformly randomly on a boundary. We develop
order-of-magnitude estimates for these formulas in Sec.IX. In
Sec. X, we apply our results to compute the number of robots
that should be used in a particular boundary coverage scenario
to yield desired SCS properties. Sec. XI extends the analysis
of Sec. VII and Sec. VIII to general non-uniform distributions
of robots on a boundary. Finally, Sec.XII concludes the paper
and discusses topics for future work.
II. RELATED WORK
A. Models of Adsorption Processes
Our boundary coverage approaches are mechanistically similar
to adsorption, the process of particles binding to a surface for
an amount of time that varies with system thermodynamic
parameters such as density, temperature, and pressure. The
resulting equilibrium distribution of particles on the surface
also varies with these thermodynamic properties. We could
emulate Langmuir adsorption [13] by programming the robots
to bind (adsorb) to the boundary with some probability and
then spontaneously unbind (desorb) after a particular mean
residence time. For instance, Langmuir processes have been
used to design nanoparticles that selectively target cell sur-
faces with high receptor densities [10]. However, achieving a
target equilibrium robot distribution around a boundary would
require strict control over the number of robots and charac-
terization of the thermodynamic variables of the environment
(such as tumor tissue).
Alternatively, we could emulate random sequential adsorp-
tion (RSA) [14], [15] by implementing a Langmuir adsorption
process in which unbinding occurs at a much greater time
scale than binding. The resulting robot allocation around the
boundary will saturate at some suboptimal packing, at which
point there is no room along the boundary for any additional
robots. This approximately irreversible binding of robots to
the boundary does not permit control of the equilibrium robot
distribution. R´enyi showed in [16] that when particles attach
sequentially at random locations along a line without overlap,
then the limiting fraction 0.747 of the line’s total length will
be occupied by particles. This fraction, called the parking
constant [17], [18], defines the maximum degree of boundary
coverage that is possible using an RSA strategy.
B. Stochastic Coverage Strategies for Robotic Swarms
In our previous work [19], [20], we developed a boundary
coverage approach for robotic swarms that combines classical
RSA with a second irreversible process in which free robots
can catalyze the detachment of bound robots. The robot-
catalyzed detachment behavior allows us to achieve any frac-
tion of boundary coverage between 0 and the parking constant.
This coverage is robust to environmental variations such as
the number of regions and the swarm size. In addition, the
approach does not require characterizing the rates at which
robots encounter boundaries and other robots, which can often
be done only through simulation [21]. In [22], we adapted our
coverage strategy to mimic the behaviors of ants performing
collective transport, which we had previously modeled as a
stochastic hybrid dynamical system [23].
This prior work focused on designing robot probabilities of
attachment and detachment that would achieve target fractions
of coverage around multiple boundaries. In [12], we investi-
gated the spatial distributions of robots that attach randomly
(without detachment) to a single boundary. We computed the
probability distributions of robot positions along the boundary
and distances between adjacent robots. We also derived the
probability that a random robot configuration is saturated,
meaning that each adjacent pair of robots along the boundary
lies within a threshold distance, which may represent the
diameter of a robot’s sensing or communication range. In the
current paper, we build on this prior analysis to develop design
procedures for computing robot parameters that will achieve
not only a specified probability of saturation, but also several
other statistics related to sensor coverage and communication
connectivity around a boundary.
Our focus on stochastic policies is distinct from many previ-
ous control approaches to decentralized multi-robot boundary
coverage, in which the goal is to drive robots to geometric
formations on a circle [24]. However, there is a significant
body of work on modeling robotic swarms with stochastic
behaviors and controller synthesis for desired collective tasks
in such systems [25], [26]. Encounter-dependent task allo-
cation strategies are most similar to our stochastic coverage
problem, but previous work either deals with scenarios where
encountered objects or regions are relatively small (on the
scale of one to several robots) [27]–[29] or where large objects
are covered dynamically by the robots [30]. In contrast to
this work, we address a static stochastic coverage scenario
in which the encountered object or region is large compared
to the robots. Other related work has addressed the specific
problem of optimal mobile sensor deployment along a line
with respect to a scalar density field, possibly in the presence
of measurement noise [31], sensor failures [32], and packet
loss [33].
3
x2
x1
x3
BW
x0
xn+1
BB
Fig. 1. Random configuration of robots on a boundary B.
x0 = 0
xn+1 = s
s1
x1
s2
x2
sn+1
xn
Fig. 2.
Configuration of n robot positions x := (x1,...,xn) on B, with
artificial robot positions x0 = 0 and xn+1 = s.
C. Analysis of Graphs and Mobile Networks
We use a variety of geometric and probabilistic tools in this
paper, which we review in Sec.IV. We apply the theory of ran-
dom graphs, primarily results on thresholds and sharp thresh-
olds from [34]. The graph representing the communication
network of a robot team is a Random Geometric Graph (RGG),
which is discussed extensively in [35]. Since many of the
formulas for the connectivity, vertex degrees, and components
of RGGs are unwieldy, it is more fruitful to determine trends of
these properties using Poisson approximation [35], [36]. When
robots cover a boundary, their communication network can be
modeled as a probability density function over a polytope. The
quantitative results established in this paper draw from two
disparate areas of literature: order statistics [37] and polytope
volume computation [38], [39].
Our work uses results from connectivity analysis of mobile
adhoc networks (MANETs), which has a large literature, e.g.
[40]–[42]. The work in [43] models wireless networks using
Poisson Point Processes (PPPs). We use results from [44] in
Sec.VII to count connected components of the communication
network. Our geometric approach differs from the primarily
combinatorial one of [44], although they lead to the same
formulas. Combinatorial approaches work well for determin-
ing coverage properties when robot positions on the boundary
are distributed according to a uniform parent distribution, but
they do not extend to non-uniform parents. Our geometric
approach, however, does extend to non-uniform parents. This
adaptability comes at the expense of requiring more labor
to derive formulas for the graph properties of interest in the
uniform case, compared to combinatorial approaches.
III. PROBLEM STATEMENT
In this section, we formalize the multi-robot boundary cover-
age problems that we address. Table I summarizes the notation
used in this paper.
A. Robot Capabilities
We consider a group of n disk-shaped robots, each with diam-
eter D, that are distributed throughout a bounded environment
at random locations. Each robot is equipped with Wi-fiwith a
communication radius of dc, and it can sense and identify other
TABLE I
NOTATION
Variable
Meaning
xi | xi
i-th Unordered | Ordered robot position
si
i-th slack
x | x
Unordered | Ordered position vector
s
Slack vector
P | S
Position simplex | Slack simplex
fX(x) | fXi(xi) Joint | Marginal pdf of ordered positions
Xi | Si
Random variables of i-th position | i-th Slack
fS(s) | fSi(si) Joint | Marginal pdf of slacks
H
Hypercuboid
F
Simplex - Hypercuboid intersection region
v
Bit vector of the form {0,1}n; e.g. 00110
Ver(A )
Vertex matrix of polytope A
ei
Unit vector along i-th coordinate axis
Notation
Meaning
ai:j
Subvector (ai,ai+1,...,a j) of a
a ≥b |a ≤b
For all i, ai ≥bi |ai ≤bi
R+
Nonnegative reals
Vol( f(x),Ω)
Volume under function f(x) over region Ω:
R
Ωf(x)dx
1X>a
Indicator random variable (rv) for the predicate X > a
objects (for instance, using a camera) within a sensing radius
of ds. For computational convenience, we assume that dc = ds
and label this radius as d. The robots have no knowledge of
their global positions, nor are they provided with offboard
sensing for localization. We make the simplifying assumption
that the robots form a synchronous network (i.e. they are
synchronized in time with respect to a global clock) and that
their controllers do not fail in the course of execution.
B. Notation and Terminology for Robot Configurations
The environment contains a line segment boundary B, whose
endpoints can be distinguished from each other by the robots.
For instance, one endpoint may be white and the other black,
which the robots could identify with their cameras. We label
these endpoints as BW and BB. Define the unordered position
xi of robot i, labeled Ri, to be that of the robot’s endpoint
closest to BW, as shown in Fig. 1. We define x = [x1 ... xn]T
as the vector of all the robots’ unordered positions. By sorting
the positions in x according to increasing distance from BW,
we obtain the ordered position vector x = [xi ... xn]T. We
define the distance between xi and xi+1 as the i-th slack, si.
We introduce two artificial robots R0 and Rn+1 at unordered
positions x0 = 0 and xn+1 = s, respectively, which create the
slacks s1 = x1 and sn+1 = s−xn. We define the slack vector as
s = [s1 ... sn+1]T. We say that slack si is connected if si ≤d,
and disconnected otherwise. Fig. 2 illustrates a configuration
of ordered robot positions and slacks.
When a coverage scheme does not permit robots to physically
overlap along the boundary, we refer to it as conflict-free
(CF); otherwise, we call it conflict-tolerant (CT). Although CT
schemes are not realistic for rigid-body robots that move in
the plane, they are easier to analyze than their CF equivalents,
4
and quantitative results on properties of CT schemes can be
readily extended to CF schemes.
We note that all our analysis can be adapted to boundaries that
are closed curves, as discussed in our previous work [12].
C. System Design for Desired Robot Configuration Properties
We now introduce terminology pertaining to the communica-
tion and sensing networks that are formed by a random robot
configuration on B. The communication graph G of a robot
configuration is a graph whose vertices are the robot positions
xi:1,...,n (excluding the artificial robot positions) and whose
edges are defined as (xi,xj) iff |xj −xi| ≤d. The vertex degree
(deg) of a robot is the number of neighboring robots along B
that are within its communication range. This property can
be used to estimate the number of robots that can detach
from B without G losing connectivity, and hence measures
the robustness of the network to node deletion and failure. We
define cmp to be the number of connected components of G .
This quantity can be used to estimate the number of additional
robots that are required to make G connected, which occurs
when cmp = 1. The sensed length (slen) of B is the total
length of the subset of B that is sensed by at least one robot.
We say that B is fully sensed iff every point on it is sensed. A
robot configuration monitors B iff it is connected and senses
the entirety of B. We define pcon as the probability that a
random robot configuration on B is connected and pmon as
the probability that a configuration monitors B.
In this paper, we derive analytical expressions or approxima-
tions of the following five properties of a robot configuration
generated by an SCS: pmon, pcon, and the expected values of
slen, cmp, and deg. As we will show, these properties are
functions of n, D, d, and s. We will present a procedure for
computing one of these four parameters, given values for the
other three, that will generate random robot configurations
with a desired value of one of the five properties.
IV. MATHEMATICAL PRELIMINARIES
We now introduce a number of concepts that will be used
throughout the paper.
A. Random Geometric Graphs (RGG)
Let X1:n be a vector of i.i.d. random variables (rv’s), and let
xi be a realization of Xi. Define a Random Geometric Graph
(RGG), denoted by G = G (n,d), with vertices {x1:n} and
edges consisting of vertex pairs (xi,xj) for which ||xi −xj|| ≤
d. The properties of general RGGs, including their number
of clusters, their probability of connectivity, and the size of
their largest connected component, are difficult to compute
precisely, but their asymptotics have been studied extensively
in [35]. We will derive exact formulas for the properties of G
where possible, and estimate these properties otherwise.
We use the following definitions from [34]. Consider the
property that G is connected. Since this property remains true
if a random edge is added to G , it is said to be monotone
increasing. Likewise, the property that G has at least k
components is monotone decreasing, since it remains true if a
random edge is removed.
Let G be an RGG with n vertices and m(n) edges, and let
P(G ∈P) denote the probability that G has the monotone
increasing property P. A function m∗(n) that satisfies the
following conditions is called a threshold function for P:
1) If m(n) = o(m∗(n)), then G /∈P almost surely (a.s.)
2) If m(n) = Ω(m∗(n)), then G ∈P a.s.
A threshold function m∗(n) for a monotone decreasing P is
defined exactly as above, but with o and Ωswitched. The
threshold function m∗(n) is called a sharp threshold for a
monotonically increasing property iff the following conditions
hold for all ε > 0 [34]:
1) if
m(n)
m∗(n) ≤1−ε, then G /∈P a.s., and
2) if
m(n)
m∗(n) ≥1+ε, then G ∈P a.s.
Theorem 1. Every monotone property of an RGG has a sharp
threshold [45].
B. Geometric Objects
1) Polytopes
A geometric shape P embedded in Rn is called a polytope
if it is bounded on all sides by hyperplanes; it is convex if it
can be expressed as an intersection of half-spaces [46, Ch.
1]. A convex polytope that is specified by a collection of
half-space inequalities is said to be in H (hyperplane) form.
Alternatively, it may be defined in the V (vertex) form as the
convex hull of a set of vertices. We will commonly describe
a polytope using its vertex matrix, Ver(P), each of whose
columns gives the coordinates of one of the vertices of P.
Software routines for converting P from one form to another
to determine its convex hull and find its volume Vol(P) are
available in computational geometric packages such as Sage
[47] and cddlib [48].
A polytope S with n+1 vertices embedded in Rn is called a
simplex. The canonical simplex is defined by
∆n = {x ∈Rn : 1Tx ≤1 and x ≥0}
(1)
in its H form, and its vertex matrix is the identity matrix In+1.
Every simplex in Rn is a linear transformation of ∆n. The
volume of a simplex may be determined in polynomial time
from its V form by a determinant [38].
2)
Simplex-Hypercube Intersection
The following result on computing the volume of intersection
between a half-space and the unit hypercube is quoted from
[38], [39]. Define a positive half-space by
T := {s ∈Rn : aTs ≤b}, where a > 0 and b > 0.
(2)
5
Let Fgen be the intersection of T with the unit hypercube
Hcube := [0,1]n. For every vertex v of Hcube, define the
simplex ∆(v) by
∆(v) = {s ∈T : s ≥v}∩Hcube.
(3)
The vertices of this simplex are v and the points pi = 1
ai (b−
aTv)ei, where each ei:1,...,n is a unit vector along the i-th axis.
Let v ∈{0,1}n denote an n-bit vector (i.e. a vector with n
entries that are zero or one) that iterates through the vertices
of Hcube.
Lemma 1. The volume of Fgen = T ∩Hcube is:
Vol(Fgen) =
∑
v∈{0,1}n
(−1)1T v Vol(∆(v))
=
1
n!∏ai
∑
v∈{0,1}n
(−1)1T v max(b−aTv,0)

n . (4)
When v lies in T , we have (b−aTv) ≥0, and the resulting
simplex ∆(v) contributes a nonzero volume to Fgen. Other-
wise, the term b −aTv is negative, and the resulting ∆(v)
contributes nothing to Vol(Fgen). The sum in Eq.(4) has alter-
nating positive and negative terms that arise from the implicit
application of the Principle of Inclusion and Exclusion (PIE)
[49]. We will later express volumes of polytope intersections
as sums of terms with alternating opposite signs, similar to
Eq.(4). Note that the subset of T lying in the positive orthant
of Rn,
Tsimp = {s ∈Rn
+ : s ≥0 and aTs ≤b},
(5)
defines a simplex with vertices at 0 and at the n points
b
ai ei,
where T
intercepts each coordinate axis. Hence, we can
express Fgen as the simplex-hypercube intersection Tsimp ∩
Hcube, a fact which will be exploited in later sections. Finally,
we note that Eq. (4) takes Ω(2n) time to evaluate.
C. Probability Theory and Statistics
We write X ∼fX(x) : x ∈R to indicate that X is a real-valued
rv with probability density function (pdf) fX(x). Similarly, we
write X ∼fX(x) : x ∈Rn to indicate that X is a real-valued
random vector with pdf fX(x). We will use FX(x) to denote the
cumulative distribution function (CDF) associated with fX(x).
Let X be a real-valued rv defined as above. We use 1A to
denote the indicator function that is defined to be unity over
the region A in its subscript, and zero elsewhere. An indicator
rv such as 1X≥1 is one which is unity if the event in its
subscript occurs, and zero otherwise. Let fX(x) be the joint
pdf of the variables X1:n, whose support is a region Ω∈Rn.
If Ω′ is a subset of Ω, then the measure of Ω′ induced by f
is
R
Ω′ fX(x)dx. Since this integral gives the volume under the
pdf fX over Ω′, we will denote it by Vol( fX,Ω′).
1) Poissonization
Many of our later computations will involve sums such as
X1 + ... + Xn, where the Xi are dependent rv’s. Because of
this dependence, the strong laws of large numbers cannot be
directly applied to this sum. Instead, this sum can be approxi-
mated by a Poisson rv through a process called Poissonization,
which we will use in Sec. IX.
We say that the rv’s Xi:1,...,n, are negatively associated (n.a.)
if an increase (resp., decrease) in one of the rv’s causes the
others to decrease (resp., increase); the precise definition is
given in [36, p. 26]. Suppose that we have n.a. indicator
rv’s 1X1:n and let W := ∑n
i=1 1Xi. We may then approximate
fW(w) with a Poisson rv with the pdf Poi(λ), where λ :=
E(W) = ∑n
i=1 E(1Xi), which is justified as follows. First, we
define the total variation (TV) distance dTV( f,g) between two
probability measures f and g on a sample space ω equipped
with a sigma algebra σ. The TV distance is the maximum
possible difference between the probabilities assigned by f
and g to the same event:
dTV( f,g) = sup
E∈σ
|| f(E)−g(E)||.
(6)
Then we can apply the following result, which implies that
the TV distance between the pdf of W and Poi(λ) diminishes
exponentially as λ →∞.
Lemma 2. From [36],
dTV( fW(w),Poi(λ)) ≤(1−exp(−λ))

1−V(W)
λ

,
(7)
where V(W) is the variance of W.
2) Order Statistics
Suppose the rv’s Xi in the vector X1:n in Sec. IV-A are drawn
from the same pdf g(x) : x ∈R. This pdf is called the parent
pdf (or just parent, when the context is clear) of the rv’s. The
ordered rv Xi is called the i-th order statistic of the parent
variable Xi and is the i-th smallest of the n components of X.
The joint pdf of the n order statistics and the marginal pdf of
the i-th order statistic Xi are given by [37]
fX(x)
=
n!
n
∏
i=1
g(t)1x1≤x2...xn−1≤xn,
fXi(xi)
=
n
∑
j=i
n
j

G(t)j(1−G(t))n−j,
(8)
where G is the parent CDF.
V. DEFINITION OF COVERAGE PROPERTIES
In this section, we give general definitions of the coverage
properties of interest in terms of indicator rv’s. These formulas
will be applied in Sections VII, VIII, IX, and XI to derive the
properties for different coverage scenarios.
6
A. Definitions of events con, sen, and mon
Let con be the event that a robot configuration on B is
connected. This event can be expressed as
con :=
n
∏
i=2
1Si≤d.
(9)
The event that B is fully sensed is:
sen := 1S1≤d1Sn+1≤d ·
n
∏
i=2
1Si≤2d.
(10)
Likewise, the event that B is monitored is:
mon :=
n+1
∏
i=1
1Si≤d.
(11)
B. Numbers of connected, fully sensed, and monitored slacks
The events con, sen, and mon are all products of indicator
functions, which cannot be Poissonized using Lemma 2. On
the other hand, the following functions, defined as sums of
indicators, can be Poissonized:
Ncon
:=
n
∑
i=2
1Si≤d,
(12)
Nsen
:=
∑
i=1,n+1
1Si≤d +
n
∑
i=2
1Si≤2d,
(13)
Nmon
:=
n+1
∑
i=1
1Si≤d.
(14)
Here, Ncon, Nsen, and Nmon are the numbers of slacks that
are connected, fully sensed, and monitored, respectively, by a
robot configuration.
C. Sensed Length, slen
We compute the sensed length slen of a robot configuration
by summing the lengths of B that are sensed by the robots on
each slack. The first robot x1 senses length min(s1,d) on the
slack s1. Every slack si:2,...,n will be sensed by the two robots at
xi and xi+1, which will together sense a length of min(si,2d)
on it. Likewise, the last robot xn senses length min(sn+1,d)
on sn+1. The total sensed length is thus
slen := ∑
i=1,n+1
min(si,d)+
n
∑
i=2
min(si,2d).
(15)
Defining psen as the probability of the event sen in Eq. (10),
we may express the expectation of slen as
E(slen) = psen ·s.
(16)
x1
x3
x0 = 0
x4 = s
s1
s3
˜s2
˜s4
Fig. 3. Slacks (blue) and free slacks (red) of the robot configuration in Fig.1.
D. Number of Connected Components, cmp
Using the fact that each disconnected slack increments the
number of connected components (cmp) in G , we may write
cmp = 1+
n
∑
i=2
1Si>d,
(17)
Applying the linearity of expectation to Eq. (17), we find the
expected value of cmp to be
E(cmp) = 1+
n
∑
i=2
E(1Si>d) = 1+
n
∑
i=2
P(Si > d).
(18)
E. Vertex Degree, deg
The vertex degree (deg) of a robot at position xi is
deg(xi) =
∑
1≤j≤n, j̸=i
1|xi−x j|≤d.
(19)
Applying the linearity of expectation to Eq.(19), the expected
value of deg is
E(deg) = (n−1)P(|Xi −Xj| ≤d),
(20)
where Xi and Xj are any two unordered positions on B.
VI. GEOMETRIC FORMULATION
We now present a geometric formulation of robot positions and
slacks as points in high-dimensional spaces. This geometric
approach will be used in Sec. VII through Sec. XI to compute
the properties given in Sec. V for different problem scenarios.
Consider the vector of robot positions x as a point in Rn, and
neglect CF requirements. Every valid position vector on B
satisfies the constraints
0 ≤x1 ≤... ≤xn ≤s.
(21)
Eq. (21) gives the H form of a simplex in Rn, which we refer
to as the position simplex P. We could alternatively consider
the slack vector defined by x,
s1:n+1 := x1:n+1 −x0:n.
(22)
Representing s as a point in Rn+1, we observe that a valid
slack vector satisfies the constraints
0 ≤s
and
n+1
∑
i=1
si = 1Ts = s.
(23)
These inequalities define the H form of a degenerate n-
dimensional simplex S embedded in Rn+1, since s can be
completely specified by n slacks instead of n+1. By dropping
sn+1, we may redefine S as
Sfull := {s ∈Rn : 0 ≤s and 1Ts ≤s},
(24)
7
(0,0)
(0,1)
(1,1)
P
(1,0,0)
(0,1,0)
(0,0,1)
S
Fig. 4. Position simplex and slack simplex for n = 2 robots and s = 1.
which is a full-dimensional irregular simplex in Rn. Eq. (23)
defines the regular simplex s · ∆n in Rn+1, which scales
the canonical simplex ∆n by a factor of s. This regularity
often simplifies connectivity-related computations. The full-
dimensional form Sfull represents the last slack sn+1 implicitly,
and so constraints on sn+1 must be treated separately. It
is easier to use software libraries to compute volumes and
integrals over Sfull than over the degenerate form S . We
shall prefer one representation over the other depending upon
convenience. Fig. 4 illustrates P and S for n = 2 robots.
We now describe how CF coverage, connectivity, and the con-
dition of monitoring can be expressed in terms of constraints
over P or S .
a) CF Constraints: CF constraints prohibit robots of diam-
eter D from extending beyond B and from conflicting (i.e.,
overlapping). These constraints are defined as
xi −xi−1
≥
D,
i = 1,...,n+1.
(25)
Note that Eq. (25) enforces x1 ≥D and xn ≤s−D to ensure
against conflicts with the virtual robots at x0 = 0 and xn+1 = s.
The conflict-free subset of P (and S ) satisfies Eq. (21) and
Eq. (25).
b) Connectivity and Monitoring Constraints: For a robot
configuration to be connected, the slack vector must satisfy
the constraint
s2:n ≤d1T.
(26)
For a configuration to monitor G , we require in addition that
the slacks s1 and sn+1 be connected, leading to
s1:n+1 ≤d1T.
(27)
Monitoring requires s to lie within the (n + 1)-dimensional
hypercube Hmon = [0,d]n+1. On the other hand, connectivity
places no constraints on the extremal slacks, which may lie
in [0,s]; the resulting s lies within the hypercuboid Hcon =
[0,s]×[0,d]n−1 ×[0,s]. Note that a minimum of nmin := ⌊s/d⌋
robots is required to monitor B.
VII. CT COVERAGE WITH UNIFORM I.I.D. PARENTS
In this section, we analyze conflict-tolerant (CT) coverage
schemes with a uniform i.i.d. parent pdf. Since the uni-
form measure of a polytope is proportional to its volume,
the probability of an event F ⊆S can be computed as
Vol(F)/Vol(S ), a fact that does not hold for general i.i.d.
parents. Consequently, this case will generally involve the
simplest computations.
A. Spatial pdfs of Robot Positions and Slacks
The uniform parent is defined by g := 1
s 1B. From Eq. (8), the
joint pdf of robot positions is uniform over P, and Xi has a
Beta pdf:
fX(x)
=
n!
sn 1P
(28)
fXi(xi)
=
s·Beta(i,n−i+1).
(29)
Making the change of variables Si = Xi −Xi−1 in Eq. (28), we
find that fS(s) is uniform over the slack simplex S :
fS(s) ∼
n!
sn+1 1S .
(30)
Since the slacks are not subject to ordering constraints, they
are exchangeable rv’s and thus are identically distributed. In
particular, Si ∼S1, and since S1 = X1, we have by Eq.(29) that
fSi(si) = s·Beta(1,n).
(31)
The mean positions at E(Xi) =
s·i
n+1 subdivide B into n + 1
equal slacks, each of length E(Si) =
s
n+1, as we would expect
of robot configurations on average for a uniform parent pdf.
As n and d increase, we expect pmon, pcon, slen, and deg to
increase monotonically regardless of the parent pdf g. The
property cmp decreases monotonically with d, but as we will
see in Sec. X, it does not vary monotonically with n. We will
now derive each of these graph properties for the uniform
parent.
B. Probability of Monitoring, pmon
From Eq. (27), the subset of S whose configurations monitor
B is Fmon := S ∩Hmon, which we refer to as the favorable
region for monitoring. Since Fmon is the intersection of two
convex polytopes, it is a convex polytope as well. We then
have pmon = Vol(Fmon)/Vol(S ). While we may determine
Vol(Fmon) by first triangulating it into simplices, in practice
this procedure is computationally intensive. Instead, we com-
pute this volume using an approach that we developed in [12],
which we summarize here.
Let F mon := S \Fmon be the exterior of Fmon. This region
consists of all slack vectors with at least one disconnected
slack. We will express F mon as the union of intersecting
simplices. Consider that subset of F mon which has slack
vectors with a single disconnected slack sk. Define s′
k = sk −d,
and note that all such slack vectors satisfy
s′
k +
∑
1≤j≤n+1, j̸=k
sj = s−d,
(32)
8
forming a regular simplex of side
√
2(s−d). We will call this
simplex the exterior simplex of sk and denote it by F mon(sk >
d). It is clear that
F mon =
n+1
[
k=1
F mon(sk > d).
(33)
However, because the simplices F mon(sk > d) overlap,
n+1
∑
k=1
Vol(F mon(sk > d)) > Vol(F mon).
Consequently, finding Vol(F mon) requires applying the PIE.
To do so, let v ∈{0,1}n+1, and define its associated exterior
simplex F mon(v) by
F mon(v) := {s ∈F mon : s ≥dv}.
(34)
Every 1-bit component vi = 1 in v causes the corresponding
slack si to be disconnected in the exterior simplex; other
slacks, associated with the 0-bits, are unrestricted. Analo-
gously to Eq. (32), F mon(v) is a regular simplex of side
√
2(s−kd), and its volume is
Vol(F mon(v)) = (s−kd)n√n+1
n!
.
(35)
In Eq. (34), we need only consider those vectors v with at
most nmin bits set to 1, since a larger number of disconnected
slacks would cause s to fall outside S . Applying the PIE, we
compute
Vol(F mon)
=
∑
v∈{0,1}n+1: 1≤1T v≤nmin
Vol(F mon(v))
=
nmin
∑
k=1
(−1)k−1
n+1
k

(s−kd)n
√n+1
n!
.
(36)
Finally, we obtain an expression for pmon:
pmon
=
Vol(Fmon)
Vol(S )
= 1−Vol(F mon)
Vol(S )
=
1−
nmin
∑
k=1
(−1)k−1
n+1
k

1−kd
s
n
.
(37)
Alternatively, we can use Lemma 1 to compute Vol(Fmon) as
follows. We define Fmon in its full-dimensional form as the
intersection between the cube Hcube = [0,d]n and two regions:
Ffull,mon = Sfull ∩Sfull(sn+1 ≤d)∩Hcube
(38)
Here, the region
Sfull(sn+1 ≤d) := {s1:n ∈Sfull : 0 ≤(s−1Ts1:n) ≤d} (39)
captures the connectivity of sn+1. To compute Vol(Ffull,mon),
we first define the region Sfull(sn+1 > d) to be the subset of
Sfull over which sn+1 is disconnected. We note that
Ffull,mon = (Sfull \Sfull(sn+1 > d))∩Hcube;
(40)
exploiting the fact that Sfull(sn+1 > d) is a simplex, we obtain
Vol(Ffull,mon) = Vol(Sfull ∩Hcube)
−Vol(Sfull(sn+1 > d)∩Hcube)
(41)
by applying Lemma 1 once for each volume of intersection.
C. Probability of Connectivity, pcon
From Eq.(26), connectivity of the graph G does not place any
constraints on s1 and sn+1. Instead, we define the connected
region Fcon to be the subset of S consisting of connected
slack vectors, analogous to Fmon. We may write Fcon in
full-dimensional form as Fcon := Sfull ∩Hcon, where Hcon
is defined in Sec. VI. The region Fcon does not constrain s1,
since it requires that s1 not exceed s, which follows from the
fact that s ∈S . Neither does Fcon constrain sn+1. We will
now prove an intermediate result from which pcon follows; we
extend this result to non-uniform i.i.d. parent pdfs in Sec. XI.
We define the simplex T ′
simp and the generic hypercuboid Hgen
as:
T ′
simp
:=
{s1:n ∈Rn
+ : 1Ts1:n ≤b},
(42)
Hgen
:=
n
∏
i=1
[0,ai].
(43)
Let F ′
gen := T ′
simp ∩Hgen and a =

a1
...
an
T.
Lemma 3. The volume of F ′
gen is given by
Vol(F ′
gen) = 1
n!
∑
v∈{0,1}n
(−1)1T v max(b−aTv,0)

n .
(44)
Proof. Define Tsimp and Hcube as in Sec. IV-B2. Transform
the coordinates s1:n to s′
1:n, where s′
i := aisi, and note that
the transformed simplex and hypercube are T ′
simp and Hgen,
respectively. Defining Jn×n as the Jacobian matrix of the
transformation, we then have
Vol(Fgen) = det(J)·Vol(F ′
gen).
(45)
The diagonal entries of J are Ji,i = 1
ai , and the off-diagonal
entries of J are zero. It follows that det(J) = ∏1
ai . Eq. (44)
follows immediately from Eq. (4).
The slack simplex Sfull and the hypercuboid Hcon correspond
to T ′
simp and Hgen, respectively. Define a ∈Rn as a vector with
a1 = s and a2:n = d. From Eq. (44), we have:
Vol(Fcon) = 1
n! ∑
v∈Hcon
(−1)1T v(max(s−aTv,0))n.
(46)
Observing that when v1 = 1, we have that
aTv = s+
n
∑
i=2
dvi ≥s =⇒s−aTv ≤0,
so that the resulting simplex contributes no volume to Fcon.
Now suppose that v1 = 0 and that k bits among v2:n are ones.
The resulting simplex contributes a volume proportional to
(s −kd)n, and there are
n−1
k


such simplices. Summing the
volumes of these simplices using the PIE, we get Vol(Fcon),
from which we obtain
pcon := Vol(Fcon)
Vol(Sfull) =
nmin
∑
i=0
(−1)i
n−1
i

1−id
s
n
,
(47)
which agrees with the result in [44].
9
D. Number of Connected Components, cmp
We will first determine the probability mass function (pmf)
P(cmp = k) of the discrete rv cmp. First, note that P(cmp =
1) is equal to pcon. If cmp = k + 1, then s2:n has exactly k
disconnected slacks. Let F(cmp = k + 1) denote the subset
of Sfull consisting of these slacks, and let F(v) denote the
subset of Sfull consisting of slack vectors that obey s1:n ≥dv.
The subset F(cmp = k) has k −1 disconnected slacks, not
including the first unconstrained slack s1. Let V(k) denote the
set of bit vectors encoding the indices of disconnected slacks
in slack vectors with k disconnected slacks (or equivalently,
slack vectors having k +1 components):
V(k) = {v ∈{0,1}n : v0 = 0 and 1Tv = k},
(48)
so that
F(cmp = k) =
[
v∈V(k−1)
F(v).
(49)
Following the same reasoning as in Sec. VII-B, the quantity
∑F(v) overestimates Vol(F(cmp = k)); applying the PIE
gives us
Vol(F(cmp = k)) = 1
n!
∑
v∈V(k−1,nmin−1)
(−1)1T v(s−d1Tv)n,
(50)
where
V(k −1,nmin −1) :=
nmin−1
[
i=k−1
V(i).
(51)
We can then derive P(cmp = k) = Vol(F(cmp=k))
Vol(Sfull)
, which sim-
plifies to the expression
P(cmp = k) =
nmin−1
∑
j=k−1
(−1)j+k−1
n−1
j

j
k −1

1−jd
s
n
,
(52)
which agrees with the corresponding formula in [44]. We omit
the full derivation for conciseness.
Proof: quote Feller Volume 1 , page 106: Combinations of
Events
Now we will compute E(cmp). If a particular slack sj is
disconnected, irrespective of the other slacks, then the resulting
slack vector obeys the constraint 1Tsj̸=i ≤(s −d). From
Sec. VII-B, this smaller simplex has a volume proportional
to (s−d)n, so that
P(Si > d) =

1−d
s
n
and
P(Si ≤d) = 1−

1−d
s
n
.
(53)
Then, by Eq. (18),
E(cmp) = 1+(n−1)

1−d
s
n
.
(54)
E. Sensed Length, slen
We define Fsen as the subset of S for which the boundary
is fully sensed. Analogous to Fmon, we express Fsen as the
intersection between S and the sensing hypercuboid Hsen =
[0,d] × [0,2d]n+1 × [0,d]. The volume of Fsen is computed
from Lemma 3. The value of E(slen) can then be determined
from Eq. (16).
Theorem 2. The probability psen that B is fully sensed is:
psen = 1−
nmin
∑
i=1
(−1)i−1
n−1
i

max

1−2id
s ,0
n
+ 2
n−1
i−1

max

1−(2i−1)d
s ,0
n
+
n−1
i−2

max

1−(2i+1)d
s ,0
n 
.
(55)
Here we adopt the convention that
n−1
i−2


= 0 for i = 1.
Proof. We derive Eq. (55) by analogy with pmon. When
computing pmon, every bit vector with i ones led to a choice
of
n+1
i


simplices in Eq. (36), each contributing a probability
of max(1 −id/s,0)n in Eq. (37). Here, we need to treat the
slacks s1 and sn+1 differently from the others. Consider the
set of all n-bit vectors v1:n that iterate through the vertices of
Hsen.
1) If v1 = vn+1 = 0, then i of the remaining n−1 bits must be
equal to 1. The set of all such v creates
n−1
i


simplices
of the form vTs = s−2id that contribute to Vol(Fsen).
2) If v1 = 0, vn+1 = 1 or v1 = 1, vn+1 = 0, then i−1 of the
remaining bits must be equal to 1. The set of all such v
creates 2
n−1
i−1


simplices of the form vTs = s−(2i−1)d
that contribute to Vol(Fsen) .
3) If v1 = vn+1 = 1, then i −2 of the remaining n −1 bits
are equal to 1. Consequently, the set of all such v creates
n−1
i−2


simplices. Each simplex has the form vTs = s −
(2i+1)d and contributes to Vol(Fsen).
F. Vertex Degree, deg
When two points (x1,x2) are selected at random on [0,s], we
may write their joint pdf in terms of their order statistics:
f(x1,x2) = 2
s2 10≤x1≤x2≤s.
(56)
Using Eq. (56), the probability term in Eq. (20) is
P (|X1 −X2| ≤d)
=
2
s2
Z s−d
xi=0
Z x1+d
x2=x1
dx2dx1 +
Z s
x1=s−d
Z s
x2=x1
dx2dx1

=
2ds−d2
s2
,
(57)
which yields
E(deg) = (n−1)2ds−d2
s2
.
(58)
10
x1
x2
x3
x0 = 0
x4 = s
s1
s3
˜s2
˜s4
Fig. 5. Slacks (blue) and free slacks (red) of the robot configuration in Fig.1.
VIII. CF COVERAGE WITH I.I.D. UNIFORM PARENTS
We will now analyze the graph G of a CF configuration and
the resulting CF geometric objects. In Fig. 5, the left virtual
robot R0 has position x0 = x0 = 0 and occupies the interval
[0,D]; the right virtual robot is located at xn+1 = s, occupying
the interval [s,s+D]. Robots R1:n are located at positions on
the interval [D,s−D], which has length s−2D.
We define SCF to be the subset of S consisting of CF
slack vectors. An alternative way to characterize SCF, to be
used later, is through free slacks. We define the free slack
˜si associated with si to be the length of that subinterval of
[xi−1,xi] that falls outside the body of any robot. From Fig.5,
we see that ˜si = si −D. We define the vector of free slacks as
˜s1:n+1, which must satisfy
1T ˜s1:n+1 = ˜s := s−(n+1)D.
(59)
Here, ˜s is the total free slack, which is the effective amount
of slack in a CF robot configuration. We call the set of slacks
obeying Eq. (59) the free slack simplex
˜
S . Analogously to
Sfull, we define the full-dimensional equivalent of SCF,full by
SCF,full := {˜s1:n ∈Rn
+ : 1T ˜s ≤˜s}.
(60)
The volume of SCF remains the same regardless of whether
it is expressed in terms of free slacks or slacks, so that
Vol(SCF,full) = ˜sn
n!.
(61)
We will assume that S and F are represented in full-
dimensional form throughout this section. For simplicity, we
will not discuss the constraint sn+1 ∈[D,d] on the last slack,
which can be handled in a fashion similar to equations (38)
and (41).
A. Probabilities pmon and pcon
We will first introduce the geometric concepts for computing
pmon. Analogous to the CT case, we define the monitoring
hypercube to be HCF,mon = [D,d]n+1 and the favorable region
for monitoring to be FCF,mon := Sfull ∩HCF,mon. Note that
the CF constraint is handled in the hypercube, and not in
the slack simplex. Since HCF,mon is not of the form [0,c]n+1
for some constant c, the regions defined by S (v) := {s ∈
S : s ≥dv} ∩HCF,mon are no longer simplices, and so we
cannot apply Lemma 1 directly to compute Vol(FCF,mon).
This problem cannot be remedied by transforming slacks into
free slacks. Instead, we extend Lemma 1 to the case where
the simplex Tsimp, defined in Eq. (5), is intersected with a
displaced hypercuboid. We define a displaced hypercuboid by
specifying its diagonally opposite vertices, vc and vf , which
(0,0)
s1
s2
(s,0)
(0,s)
(D,D)
(d,d)
HCF,mon
Sfull
Fig. 6.
Illustration of Algorithm 1 for n = 2. The simplex Sfull and the
hypercube HCF,mon are represented in full-dimensional form, and constraints
on s3 are not shown for simplicity. Sfull is the triangle with vertices
{(0,0),(0,s),(s,0)} and HCF,mon is the square [D,d]2. Algorithm 1 computes
the area of intersection of Sfull with [0,d]2, from which it subtracts the area of
Sfull under the hatched region to obtain the area of the red triangle FCF,mon.
are respectively its closest vertex to 0 and its farthest vertex
away from 0:
Hvc,v f = {s1:n ∈Rn
+ : 0 ≤vc ≤s ≤vf }.
(62)
The vertex pair (vc,vf ) encodes all information about the faces
of the hypercuboid. Now we will use Algorithm 1 to compute
the volume of the intersection F := Tsimp ∩Hvc,v f . To do so,
the algorithm computes the volume of Tsimp ∩H0,v f , which
overestimates Vol(F), in step 3. Subsequently, it subtracts the
volumes of overlap between Tsimp and the exterior of Hvc,v f ,
i.e. the region H0,v f \ Hvc,v f , using the PIE. This exterior is
the union of hypercuboids Hb,i that lie between Hvc,v f and 0.
The volume of intersection of Tsimp with this exterior, denoted
by Hinter, is computed using the PIE in step 9, and either
added to or deducted from V in step 10. Fig. 6 illustrates the
operation of Algorithm 1 in two dimensions.
Algorithm 1 Find volume of intersection between a general
simplex and a displaced hypercuboid
1: procedure FIND-INTER-VOL(Tsimp(a,b),Hvc,v f )
2:
d1:n ←vf −vc
▷Edges of Hvc,v f
3:
V ←Vol(Tsimp ∩H0,v f ) ▷Compute using Lemma 3
4:
for i ←1...n do
5:
Hb,i = H0,vi where vi = vc +(vf,i −vc,i)ei
6:
end for
7:
for v ∈{0,1}n do
8:
Hinter(v) ←T
vi=1 Hb,i
9:
Compute Vol(Tsimp ∩Hinter) using Lemma 3
10:
V ←V +(−1)1T vVol(Hinter)
11:
end for
12:
Return V
13: end procedure
11
The hypercube HCF,mon is an instance of Hvc,v f with vc = D1T
and v f = d1T. Since HCF,mon = [D,d]n is a hypercube, it has
identical faces, so each of the hypercuboids Hb,i has the same
set of edges. Further, the simplex S is an instance of Tsimp
with a = 1; since the coefficients ai are all unity, it follows
that Hinter(v) and Hinter(v′) are congruent for any two n-
bit vectors v and v′ with the same number of 1-bits. Thus, we
need to compute the volumes of regions of the form Hinter(v),
where v consists of a set of successive ones followed by zeros;
for example, v = (1,1,...,1,0,...,0). In other words, v can be
expressed as the sum of unit vectors ∑i
j=1 ej. We thus have
Vol(FCF,mon) = Vol(S ∩[0,d]n+1)−
n+1
∑
i=1
(−1)i
n+1
i

Vol
 
S ∩Hinter(
i
∑
j=1
ej)
!
,
(63)
and pmon = Vol(FCF,mon)
Vol(S )
.
Running Algorithm 1 with inputs Tsimp := Sfull and Hvc,v f :=
HCF,con = [D,s]×[D,d]n−1 furnishes the volume of the favor-
able region FCF,con for a connected CF configuration, and
thereby pcon.
B. Probability psen
Computing psen requires us to consider the intersection be-
tween S and the hypercuboid
HCF,sen := [D,d]×[D,2d]n−1 ×[D,d].
(64)
Both S and HCF,sen are degenerate polytopes. To compute
their volume of intersection, we express the intersection
FCF,sen in full-dimensional form, as in Eq. (38). Define
Hfull := [D,d]×[D,2d]n−1 to be the full-dimensional form of
HCF,sen. Following the approach of Eq. (38), we can compute
the full-dimensional form of FCF,sen as
Ffull,sen := Hfull ∩Sfull ∩Sfull(sn+1 ∈[D,d]),
(65)
where Sfull(sn+1 ∈[D,d]) is defined as the subset of Sfull in
which the last slack sn+1 = s−1Ts1:n lies in [D,d]. Then we
can determine the volume of Ffull,sen as:
Vol(Ffull,sen) = Vol(Sfull ∩Hfull)
−Vol(Sfull(sn+1 > d)∩Hfull)
−Vol(Sfull(sn+1 < D)∩Hfull),
(66)
where the region Sfull(sn+1 > d) is the subset of Sfull over
which sn+1 is disconnected, and likewise Sfull(sn+1 < D) is
the subset of Sfull for which the last slack results in a conflict.
We run Algorithm 1 once for each volume of intersection in
Eq. (66) to obtain Vol(Ffull,sen). We can then compute psen =
Vol(FCF,sen)
Vol(Sfull)
and, by Eq. (16), E(slen) = s· psen.
C. Number of Connected Components, cmp
Proceeding as in Sec.VII-D, we define FCF(cmp = k) to be the
subset of SCF whose slacks have k connected components. We
now write the CF equivalent of Eq.(50), replacing F(cmp = k)
with its CF counterpart FCF(cmp = k). To compute the volume
of this region, we can use Algorithm 1 with the inputs
Tsimp := Sfull and Hvc,v f := [0,s]×[d −D]n−1,
and execute the loop in step 7 of Algorithm 1 only over bit
vectors obeying Eq. (51).
D. Free Slack Approximation of Coverage Properties
The probability pmon is more complex to compute in the CF
case, where Algorithm 1 must be used, than in the CT case,
where Eq. (37) can be applied. To aid the design and im-
plementation of algorithms for CF coverage, we approximate
FCF,mon by
˜
FCF,mon, defined as the intersection between the
free slack simplex
˜
S and the hypercube
˜
Hmon := [0, ˜d]n+1,
where ˜d := d −D. Likewise, by intersecting
˜
S with
˜
Hcon :=
[0, ˜s] × [0, ˜d]n−1 × [0, ˜s], we obtain an approximation of the
favorable region of connectivity,
˜
FCF,con. The volumes of
both these intersections have the form of Eq. (4). Hence,
the formulas for the resulting probabilities of monitoring and
connectivity, denoted by ˜pmon and ˜pcon, can be expressed as
the equations (37) and (47) for pmon and pcon with (˜s, ˜d)
substituted for (s,d).
Similarly, we can use these parameter substitutions in equa-
tions (54), (55), and (58) to approximate E(cmp), psen (and
thus E(slen)), and E(deg), respectively. We call this approxi-
mation the free slack approximation (FSA) for the CF case.
IX. APPROXIMATIONS OF COVERAGE PROPERTIES
In this section, we develop order-of-magnitude approximations
of the graph properties derived in Sec. VII and Sec. VIII,
using the concepts of threshold functions [34], [45], [50] and
Poissonization [36] that are described in Sec. IV. We will use
threshold functions in our design procedure in Sec.X. We note
that the estimates below are also valid for CF configurations
when the FSA substitutions (s,d) →(˜s, ˜d) are applied.
A. Connectivity and Monitoring Thresholds
The uniform parent pdf has the special property that the slack
vector S is jointly uniform over S , with each slack being
identically distributed (though not independent) as scaled
exponentials of the form s·Exp(1). Suppose we sort the slacks
in S in increasing order to obtain the vector of their order
statistics, S. Then we find that [37]
E(Si)
=
s
n+1
n+1
∑
j=i
1
j =
s
n+1(Hn+1 −Hi),
(67)
V(Si)
=
n+1
∑
j=i
1
j2 ,
(68)
where Hn denotes the harmonic numbers. If n is large, we
may approximate Hn by logn. The longest slack Sn+1 has
the expected value E(Sn+1) =
s
n+1Hn+1 ≈
s
n+1 log(n + 1) for
large n. To enforce the monitoring condition, we impose
12
the constraint that the expected longest slack E(Sn+1) is
connected,
log(n+1)
n+1
≤d
s
=⇒n = exp

−W
d
s

−1,
(69)
where W is the Lambert W function [51].
From [35], a pair (n,d) with d = O(
n
logn) forms a connectivity
threshold for G , implying that the estimate for n is sharp.
Further, since this function thresholds connectivity, it auto-
matically thresholds monitoring too. We can use a result from
[50] to determine that a triple (n,d,s) satisfying
nd = Θ(slogs).
(70)
forms a sharp monitoring threshold.
B. Threshold for E(deg)
From [35], a sequence of pairs (n,d) satisfying d = O( 1
n)
results in E(deg) tending to a positive constant, and this
sequence is called the thermodynamic limit. Likewise, pairs
(n,d) that obey d = O( logn
n ) cause E(deg) to have growth of
order O(logn) and comprise the connectivity regime, which is
a threshold for the property that G has no isolated vertices
(i.e. vertices of zero degree). A superconnectivity regime has
d = Ω( logn
n ), which ensures that G has no isolated vertices a.s.
Likewise, the subconnectivity regime with d = o( logn
n ) ensures
that G has one or more isolated vertices a.s.
C. Poisson Approximation of Coverage Properties
1) Poissonizing Nmon and Ncon
We derive Poisson estimates for Nmon and Ncon using re-
sults from [36, Ch.7]. The key observation is that the slack
rv’s Si:1,...,n+1, are negatively associated, since an increase in
one slack leads to a corresponding decrease in the others.
Applying Lemma 2 to Nmon, we see that Nmon is approxi-
mately distributed as Poi(λmon) with λmon = ∑n+1
i=1 E(1Si≤d).
The slacks’ exchangeability implies that S1 ∼Si, so that
λmon = (n+1)P(S1 ≤d). From Eq. (53), we obtain
λmon = (n+1)

1−

1−d
s
n
.
(71)
Using Eq. (12), the analogous Poisson rv for Ncon has mean
λcon = (n −1)P(S1 ≤d). These Poisson approximations are
valid for regimes (n,d) for which [36, Ch.7]
n →∞, d
s →0, and nd
s →λ∞+o(1)
n
,
(72)
where λ∞is a finite constant.
We may approximate pmon using Nmon by noting that when
Nmon = n + 1, the entirety of B is monitored. Let Λ ∼
Poi(λmon); then we have that
pmon := P(Nmon = n+1) ≈P(Λ = n+1)
= λ n+1
mon exp(−λmon)
(n+1)!
.
(73)
Likewise, we have for pcon :
pcon := P(Ncon = n−1) ≈λ n−1
con exp(−λcon)
(n−1)!
.
(74)
2) Poissonizing Nsen
Reasoning similarly for pcon, we have Nsen ∼Poi(λsen), where
λsen =
n
∑
i=2
E(1Si≤2d)+E(1S1≤d)+E(1Sn+1≤d)
= n

1−

1−2d
s
n
+2

1−

1−d
s
n
,
(75)
and thereby approximate psen as
psen = P(Nsen = n+1) ≈λ n+1
sen exp(−λsen)
(n+1)!
,
(76)
whose approximation error tends to zero when Eq.(72) holds.
3) Poissonizing cmp
Using definition Eq. (17) for cmp, we can apply our approach
for estimating pmon and pcon to obtain cmp ∼Poi(λcmp), where
λcmp = 1+(n−1)E(1S1>d) = 1+(n−1)

1−d
s
n
.
(77)
X. DESIGN FOR TARGET COVERAGE PROPERTIES
We now apply our analytical results to select the number of
robots n that will achieve target properties of G , such as a
specified value of pcon, when performing stochastic boundary
coverage. Our design problems require inverting the equations
that we have derived for these properties. Although here
we assume that the robot diameter D, robot communication
radius d, and boundary length s are fixed, as will be the
case in many coverage applications, in general we may also
use our procedure to compute these parameters to achieve
specified properties of G . Due to the nonlinear dependency
of each property on the parameters (s,n,D,d), the inversion is
performed using numerical methods. Our source code in [52]
implements this inversion procedure using the scipy fsolve
numerical solver.
We illustrate the computation of n in both conflict-tolerant (CT,
Sec. VII) and conflict-free (CF, Sec. VIII) coverage scenarios
with a uniform i.i.d. parent pdf. Our solver source code for
these two cases can be accessed at [53] and [54], respectively.
In the CF case, we use the free slack approximation (FSA) to
compute n for each property.
In our example, we assume that s = 200, d = 5, and D = 1. Our
objective is to compute the value of n that yields each of the
following properties separately: (1) pmon = 0.80, (2) pcon =
0.70, (3) E(cmp) = 4, (4) E(slen) = 0.6s, and (5) E(deg) = 5.
1) pmon = 0.80: To compute an initial guess of n for the
solver fsolve, we note that a length of smon = spmon =
200(0.80) = 160 needs to be monitored on average. Using
Eq. (69), we solve for an initial guess n0 that satisfies
log(n0 +1)/(n0 +1) = d/smon, which yields n0 = 162.00.
13
In the CT case, we numerically invert Eq. (37) to find
n = 283.15, and in the CF case, we compute n = 120.74.
2) pcon = 0.70: We again use the initial guess n0 = 162.00.
In the CT case, we invert Eq. (47) to obtain n = 261.58,
and in the CF case, we compute n = 116.84.
3) E(cmp) = 4: From Eq.(54), we observe that for the given
values of d and s, E(cmp) has a maximum of 15.53
at nmax = 39.49. In addition, E(cmp) = 0 at n = 0 and
limn→∞E(cmp) = 0. Thus, there are two values of n at
which E(cmp) = 4: nlow ∈(0,nmax) and nhigh ∈(nmax,∞).
In the CT case, initializing fsolve with n0,low = 1 gave
nlow = 4.34, and initializing with n0,high = 162.00 (as
for the previous two properties) gave nhigh = 155.74. In
the CF case, these two initial values n0,low and n0,high
produced nlow = 4.27 and nhigh = 90.98, respectively.
4) E(slen) = 0.6s = 120: We have psen = 0.6. In the CT case,
inverting Eq. (55) yields n = 111.77, and in the CF case,
we compute n = 79.08.
5) E(deg) = 5: In the CT case, Eq.(58) can be directly solved
for n = 102.26. In the CF case, we compute n = 77.93.
Observe that for each property, the n obtained in the CF case is
always less than the n in the CT case. This is as expected, since
the robots in the CF case can occupy an effective boundary
length of ˜s < s. For this example, we found that defining n0
from nd = slogs in Eq. (70), instead of from Eq. (69), yields
the same answers as above for both the CF and CT cases.
XI. COVERAGE WITH NON-UNIFORM I.I.D. PARENTS
In general, the case where robot positions on B are distributed
according to a non-uniform parent pdf is more computationally
complex than the case of a uniform parent pdf. For instance,
we proved in [55], [56] that computing pmon for a certain
class of parent pdfs is #P-Hard. In this section, we extend the
results in Sec. VII and Sec. VIII to the case of nonuniform
i.i.d. parents g(x).
A. CT Coverage
1) Spatial pdfs of Robot Positions and Slacks
The joint and marginal pdfs of the ordered robot positions are
given by Eq. (8). The joint pdf of the slacks is
fS(s) = g(s1)g(s1 +s2)...g(
n
∑
i=1
si)1S .
(78)
The slacks in Eq. (78) are not exchangeable, unlike those
induced by the uniform parent. Consequently, Eq.(78) is more
complicated to integrate than Eq. (30). We will find the pdf
of slack Si := Xi+1 −Xi by noting that the joint pdf of Xi and
Xi+1 is [37, Ch.2]
fXi,Xi+1(xi,xi+1) =
n!
(i−1)!(n−i−1)!×
g(xi)g(xi+1)Gi−1(xi)(1−G(xi+1))n−i−1,
(79)
so that
fSi(si) =
Z s
t=0 fXi,Xi+1(t,t +si)dt.
(80)
Here, G is the CDF of g.
2) Probabilities pmon, pcon, and psen
The measure of a subset Fgen of S induced by fS(s) is given
by Vol(fS(s),Fgen). Using Lemma 1, we may express this
measure in terms of measures over simplices:
Vol( fS(s),Fgen) =
∑
v∈{0,1}n
(−1)1T v Vol(fS(s),∆(v)). (81)
This expression requires the computation of O(2n) integrals.
We can obtain the formulas for pmon, pcon, and psen by
replacing Vol(∆(v)) by Vol( fS(s),∆(v)) in equations (37), (47)
and (55) respectively. For instance, pmon and pcon are given
by:
pmon = 1−
∑
v∈{0,1}n:1≤1T v≤nmin
(−1)1T v−1Vol( fS(s),F(v)),
(82)
pcon =
∑
v∈Ver(Hcon)
(−1)1T vVol(fS(s),∆(v)).
(83)
We may approximate these probabilities using Ncon, Nmon and
Nsen. We first derive the probabilities that slack Si is connected
and disconnected:
P(Si ≤d) =
Z d
si=0 fSi(si)dsi,
P(Si > d) = 1−
Z d
si=0 fSi(si)dsi.
(84)
Now, proceeding as in Sec. IX-C, we have that Nmon is
approximately distributed as Poi(λmon), where
λmon =
n+1
∑
i=1
P(Si ≤d),
(85)
whose approximation error tends to zero when Eq.(72) holds.
We may then approximate pmon by Eq. (73). Analogous
expressions may be derived for pcon and psen.
3) Number of Connected Components, cmp
By Eq. (18), we have that
E(cmp) = 1+
n
∑
i=2
P(Si > d),
(86)
which may be determined from Eq. (84).
4) Vertex Degree, deg
By Eq.(20), we can compute E(deg) from P(|Xi−Xj| ≤d).The
joint pdf of two unordered positions can be rewritten in terms
of their order statistics:
fX1,X2(x1,x2) = 2!g(x1)g(x2)10≤x1≤x2≤s.
(87)
14
We now obtain
P(|X2 −X1| ≤d) = 2
Z s−d
x1=0
Z x1+d
x2=x1
g(x1)g(x2)dx1dx2
+ 2
Z d
x1=s−d
Z s
x2=x1
g(x1)g(x2)dx1dx2,
(88)
which cannot be simplified further.
B. CF Coverage and Approximations of Coverage Properties
We can obtain the coverage properties for the CF case by
replacing Vol(∆(v)) by Vol(fS(s),∆(v)) in the formulas in
Sec. VIII. In contrast to the results in Sec. VIII, we would
not expect the free slack approximation to hold, because g
is not a constant function. It is unlikely that such an ap-
proximation exists for all non-uniform parent pdfs; a separate
approximation would have to be devised for each parent.
Poisson approximations for pcon, pmon, and psen are derived
in Sec.XI-A2. The connectivity threshold and thermodynamic
limit that are defined in Sec. IX apply to g [35]. We are
unaware of an equivalent to the monitoring threshold of
Eq. (70) for g.
XII. CONCLUSIONS AND FUTURE WORK
We have presented an approach to characterizing and design-
ing statistical properties of random multi-robot networks that
are formed around boundaries by stochastic coverage schemes.
This work will enable the designer of a swarm robotic system
to select the number of robots and the robot diameter, sensing
range, and communication range that are guaranteed to yield
target statistics of sensor coverage or communication connec-
tivity around a boundary. We have developed and validated
this approach for robot configurations that are generated by
uniform parent pdfs, which will occur in scenarios where
there is a spatially homogeneous density of robots around the
boundary. We also extended the results to scenarios with robots
that are distributed according to non-uniform parent pdfs.
We were able to develop these theoretical results because
of the simplifying assumptions made in Sec. III: robots are
homogeneous in terms of their parent pdf g, diameter D, and
communication/sensing range d, and they can communicate
perfectly within a disk of radius d. In practice, none of these
assumptions may hold; hence, extending our results to scenar-
ios with heterogenous robots and realistic communication is
an important direction of our future work. In addition, we will
also consider problems where robots cover an area or volume
as opposed to a one-dimensional boundary. We describe our
future work on these topics in more detail below.
A. Heterogeneous d, D, and parent pdfs
Suppose that each robot Ri has a distinct communication
range di. Now the RGG G can be connected through multi-
hop messages, even when there are robots that are unable to
communicate directly with at most one of their neighbors.
For example, consider three robots R1, R2, and R3 whose
communication ranges satisfy d1 > d2 and d3 > d2. Suppose
further that R1, but not R3, is within the range of R2.
Then R2 may route packets destined for R3 through R1,
thereby creating a connected G . Such a scenario does not
arise when each robot has the same range d. The inclusion
of heterogeneous ranges di entails the loss of symmetry of
the favorable region Fmon which was exploited in Sec. VII to
compute pcon in pseudo-polynomial time. Our work in [55],
[56] shows that computing the probability that G is connected
through 1-hop messages is #P-Hard. Likewise, when the robots
have distinct diameters Di, the CF polytope SCF becomes a
simplex with hypercuboidal holes. Computing Vol(SCF) thus
has the same complexity as finding the volume of a general
simplex-hypercuboid intersection.
The assumption of i.i.d parents is a major simplification that
enables the analysis of the RGG G . Since robot positions are
not necessarily i.i.d. in general, their joint pdf fX(x) does not
factorize into marginals as in Eq. (8). When parent pdfs are
distinct, the joint cdf of their order statistics is given by the
Bapat-Beg theorem, which requires the evaluation of a matrix
permanent [37]. Since computing permanents can be #P-Hard
in general, determining the properties of G becomes intractable
for this case as well, forcing us to resort to approximations.
B. Modeling realistic wireless communication
Wireless signals are electromagnetic waves, and consequently
suffer from phenomena such as path loss, propagation loss,
and Rayleigh fading. Furthermore, multiple Wi-fitransmitters
that are placed close together will interfere constructively or
destructively with each other. These effects have been modeled
using general PPPs [43], but we do not know how these
losses will affect an RGG G . Including these effects in our
models will involve a tradeoff between model expressiveness
and tractability.
C. Boundary coverage (BC) in R2 and R3
The geometric formulation of one-dimensional BC in Sec. VI
yielded closed-form formulas for the volumes of polytopes.
We would not expect to be able to derive such formulas
for two- and three-dimensional variants of BC, and instead
would have to use the theory of RGGs much more extensively
than we did here. Developing these results will allow us to
design multi-robot systems for stochastic coverage tasks over
terrestrial surfaces and within three-dimensional volumes in
the air or underwater.
ACKNOWLEDGMENTS
We gratefully acknowledge Dr. Theodore P. Pavlic and Sean
Wilson for useful discussions. This work was supported in
part by the DARPA YFA under Award No. D14AP00054.
Approved for public release; distribution is unlimited.
15
REFERENCES
[1] C. Mavroidis and A. Ferreira, “Nanorobotics: Past, present, and future,”
in Nanorobotics, C. Mavroidis and A. Ferreira, Eds.
Springer New
York, 2013, pp. 3–27.
[2] E. Diller and M. Sitti, “Micro-scale mobile robotics,” Foundations and
Trends in Robotics, vol. 2, pp. 143–259, 2013.
[3] S. Bauer, S. Bauer-Gogonea, I. Graz, M. Kaltenbrunner, C. Keplinger,
and R. Schw¨odiauer, “25th anniversary article: A soft future: From
robots and sensor skin to energy harvesters,” Advanced Materials,
vol. 26, no. 1, pp. 149–162, 2014.
[4] C. R. Kube and E. Bonabeau, “Cooperative transport by ants and robots,”
Robot. Auton. Syst., vol. 30, no. 1–2, pp. 85–101, 2000.
[5] R. O’Grady, C. Pinciroli, R. Groß, A. L. Christensen, F. Mondada,
M. Bonani, and M. Dorigo, “Swarm-bots to the rescue,” in Proc. 10th
European Conference on Artificial Life (ECAL), ser. LNCS, vol. 5777.
Budapest, Hungary: Springer-Verlag, Sept. 13–16, 2009, pp. 165–172.
[6] J. Chen, M. Gauci, W. Li, A. Kolling, and R. Groß, “Occlusion-based
cooperative transport with a swarm of miniature mobile robots,” IEEE
Trans. on Robotics, pp. 1–15, March 2015.
[7] S. Tong, E. Fine, Y. Lin, T. J. Cradick, and G. Bao, “Nanomedicine:
Tiny particles and machines give huge gains,” Annals of Biomedical
Engineering, pp. 1–17, 2013.
[8] S. Hauert, S. Berman, R. Nagpal, and S. N. Bhatia, “A computational
framework for identifying design guidelines to increase the penetration
of targeted nanoparticles into tumors,” Nano Today, vol. 8, no. 6, pp.
566–576, 2013.
[9] R. Sinha, G. J. Kim, S. Niel, and D. M. Shin, “Nanotechnology in
cancer therapeutics: bioconjugated nanoparticles for drug delivery,” Mol.
Cancer Ther., vol. 5, Aug. 2006.
[10] S. Wang and E. E. Dormidontova, “Selectivity of ligand-receptor inter-
actions between nanoparticle and cell surfaces,” Phys. Rev. Lett., vol.
109, p. 238102, Dec 2012.
[11] A. W. Long, K. C. Wolfe, M. J. Mashner, and G. S. Chirikjian, “The
banana distribution is Gaussian: a localization study with exponential
coordinates,” Robotics: Science and Systems (RSS) VIII, p. 265, 2013.
[12] G. P. Kumar and S. Berman, “Statistical analysis of stochastic multi-
robot boundary coverage,” in Proc. of the Int’l. Conf. on Robotics and
Automation (ICRA), 2014, pp. 74–81.
[13] I. Langmuir, “The adsorption of gases on plane surfaces of glass, mica
and platinum,” J. Am. Chem. Soc., vol. 40, no. 9, pp. 1361–1403, 1918.
[14] J. W. Evans, “Random and cooperative sequential adsorption,” Rev. Mod.
Phys., vol. 65, no. 4, pp. 1281–1329, October 1993.
[15] J. Talbot, G. Tarjus, P. R. Van Tassel, and P. Viot, “From car parking
to protein adsorption: an overview of sequential adsorption processes,”
Colloids Surfaces, A: Physicochem. Eng. Asp., vol. 165, no. 1–3, pp.
287–324, May 30, 2000.
[16] A. R´enyi, “On a one-dimensional problem concerning random space-
filling,” Publ. Math. Inst. Hung. Acad. Sci., vol. 3, pp. 109–127, 1958.
[17] H. Solomon and H. Weiner, “A review of the packing problem,”
Commun. in Stat.–Theory Methods, vol. 15, no. 9, pp. 2571–2607, 1986.
[18] S. R. Finch, Mathematical Constants, ser. Encyclopedia of Mathematics
and its Applications.
Cambridge University Press, 2003, vol. 94.
[19] T. P. Pavlic, S. Wilson, G. P. Kumar, and S. Berman, “An enzyme-
inspired approach to stochastic allocation of robotic swarms around
boundaries,” in Int’l. Symp. on Robotics Res. (ISRR), Singapore, 2013.
[20] ——, “Control of stochastic boundary coverage by multirobot systems,”
ASME J. Dyn. Sys. Meas. Control, vol. 137, no. 3, p. 034505, Oct. 2014.
[21] E. Gurarie, “Models and analysis of animal movements: From individual
tracks to mass dispersal,” Ph.D. dissertation, Univ. of Washington, 2008.
[22] S. Wilson, T. P. Pavlic, G. P. Kumar, A. Buffin, S. C. Pratt, and
S. Berman, “Design of ant-inspired stochastic control policies for
collective transport by robotic swarms,” Swarm Intelligence, vol. 8, no. 4,
pp. 303–327, 2014.
[23] G. P. Kumar, A. Buffin, T. P. Pavlic, S. C. Pratt, and S. M. Berman, “A
stochastic hybrid system model of collective transport in the desert ant
Aphaenogaster cockerelli,” in Proc. 16th Int’l. Conf. on Hybrid Systems:
Computation and Control (HSCC), 2013, pp. 119–124.
[24] C. Wang, G. Xie, and M. Cao, “Controlling anonymous mobile agents
with unidirectional locomotion to form formations on a circle,” Auto-
matica, vol. 50, pp. 1100 – 1108, 2014.
[25] M. Brambilla, E. Ferrante, M. Birattari, and M. Dorigo, “Swarm
robotics: a review from the swarm engineering perspective,” Swarm
Intelligence, vol. 7, no. 1, pp. 1–41, 2013.
[26] N. Correll and H. Hamann, “Probabilistic modeling of swarming sys-
tems: From non-spatial to spatial dynamics,” in Springer Handbook of
Computational Intelligence, J. Kacprzyk and W. Pedrycz, Eds., 2015.
[27] A. Martinoli, K. Easton, and W. Agassounon, “Modeling swarm robotic
systems: A case study in collaborative distributed manipulation,” Int’l.
Journal of Robotics Research, vol. 23, pp. 415–436, 2004.
[28] T. H. Labella, M. Dorigo, and J.-L. Deneubourg, “Division of labor in a
group of robots inspired by ants’ foraging behavior,” ACM Trans. Auton.
Adapt. Syst., vol. 1, no. 1, pp. 4–25, 2006.
[29] N. C. A. Kanakia, J. Klingner, “A response threshold sigmoid function
model for swarm robot collaboration,” in Proc. of the Int’l. Symp. on
Distributed Autonomous Robotic Systems (DARS).
Springer Tracts on
Advanced Robotics, 2014.
[30] N. Correll and A. Martinoli, “Modeling and optimization of a swarm-
intelligent inspection system,” in Proc. of the Int’l. Symp. on Distributed
Autonomous Robotic Systems (DARS).
Springer, 2007, pp. 369–378.
[31] P. Davison, N. Leonard, A. Olshevsky, and M. Schwemmer, “Nonuni-
form line coverage from noisy scalar measurements,” IEEE Trans. on
Automatic Control, vol. 60, no. 7, pp. 1975–1980, July 2015.
[32] P. Frasca, F. Garin, B. Gerencs´er, and J. M. Hendrickx, “Optimal one-
dimensional coverage by unreliable sensors,” SIAM Journal on Control
and Optimization, vol. 53, no. 5, pp. 3120–3140, 2015.
[33] J. Cort´es, “Deployment of an unreliable robotic sensor network for
spatial estimation,” Systems & Control Letters, vol. 61, no. 1, pp. 41–49,
2012.
[34] A. Frieze and M. Karonski, Introduction to Random Graphs. Cambridge
University Press, 2016.
[35] M. Penrose, Random Geometric Graphs, ser. Oxford Studies in Proba-
bility.
Oxford University Press, 2003.
[36] A. D. Barbour, L. Holst, and S. Janson, Poisson Approximation. Claren-
don Press Oxford, 1992.
[37] H. David and H. Nagaraja, Order Statistics.
Hoboken, NJ, USA: John
Wiley and Sons, 2003.
[38] M. E. Dyer and A. M. Frieze, “On the complexity of computing the
volume of a polyhedron,” SIAM J. Comput., vol. 17, no. 5, pp. 967–
974, 1988.
[39] ——, “Computing the volume of convex bodies: a case where random-
ness provably helps,” Probabilistic Combinatorics and its Applications,
vol. 44, pp. 123–170, 1991.
[40] M. Franceschetti, L. Booth, M. Cook, R. Meester, and J. Bruck, “Per-
colation in multi-hop wireless networks,” IEEE Trans. on Information
Theory, Tech. Rep., 2003.
[41] F. Xue and P. R. Kumar, “The number of neighbors needed for
connectivity of wireless networks,” Wireless Networks, vol. 10, no. 2,
pp. 169–181, 2004.
[42] R. Hekmat and P. Van Mieghem, “Degree distribution and hopcount in
wireless ad-hoc networks,” in Proc. of the IEEE Int’l. Conf. on Networks
(ICON), Sydney, Australia, 2003, pp. 603–609.
16
[43] M. Haenggi, Stochastic Geometry for Wireless Networks.
Cambridge
University Press, 2012.
[44] E. Godehardt and J. Jaworski, “On the connectivity of a random interval
graph,” Random Structures & Algorithms, vol. 9, no. 1-2, pp. 137–161,
1996.
[45] A. Goel, S. Rai, and B. Krishnamachari, “Sharp thresholds for monotone
properties in random geometric graphs,” in Proc. of the 36th Annual
ACM Symposium on Theory of Computing (STOC), 2004, pp. 580–586.
[46] B. Gr¨unbaum, Convex Polytopes, 2nd ed.
Springer-Verlag New York
Inc., 2002.
[47] The
Sage
Development
Team
(2016),
SageMath:
Open
Source
Mathematical
System,
“Polyhedra”.
[On-
line].
Available:
http://doc.sagemath.org/html/en/reference/geometry/
sage/geometry/polyhedron/constructor.html
[48] K. Fukuda. (2015) cddlib Polyhedral Computation Library. [Online].
Available:
https://www.inf.ethz.ch/personal/fukudak/cdd home/index.
html
[49] J. van Lint and R. Wilson, A Course in Combinatorics.
New York,
NY, USA: Cambridge University Press, 2001.
[50] S. Muthukrishnan and G. Pandurangan, “The bin-covering technique for
thresholding random geometric graph properties,” in Proc. of the 16th
Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 989–
998.
[51] S. Yi, Time-Delay Systems: Analysis and Control using the Lambert W
Function.
World Scientific, 2010.
[52] G. P. Kumar, “Polytope Computations Repository,” Jun 2016. [Online].
Available: https://gitlab.com/thedragondraco/polytope-comps
[53] ——,
“Solver
for
uniform
CT
attachments,”
Jun
2016.
[Online]. Available: https://gitlab.com/thedragondraco/polytope-comps/
blob/master/numsolve/unif-ct.py
[54] ——,
“Solver
for
uniform
CF
attachments,”
Jun
2016.
[Online]. Available: https://gitlab.com/thedragondraco/polytope-comps/
blob/master/numsolve/unif-cf.py
[55] G.
P.
Kumar
and
S.
Berman,
“Probabilistic
analysis
of
the
communication network created by dynamic boundary coverage,”
arXiv, 2016. [Online]. Available: https://arxiv.org/abs/1604.01452
[56] G. P. Kumar, “Development and analysis of stochastic boundary cover-
age strategies for multi-robot systems,” Ph.D. dissertation, Arizona State
University, 2016.
Ganesh P. Kumar (M’12) received the B.Tech.
degree in computer science from Kerala University,
Trivandrum, Kerala, India, in 2004 and the M.Tech.
degree in computer science from the International In-
stitute of Information Technology, Hyderabad, India,
in 2006. He received the Ph.D. degree in computer
science and engineering from Arizona State Univer-
sity, Tempe, AZ in 2016.
From 2006 to 2010, he held positions as a Soft-
ware Engineer at CA Technologies and a Senior
Software Engineer at Yahoo! and the erstwhile Mo-
torola Mobility Solutions. He is currently an Assistant Research Scientist in
Prof. Spring Berman’s group at Arizona State University. His research focuses
on computational problems in swarm robotics, and he is interested in both the
theoretical and practical aspects of designing software for robotic swarms.
Dr. Kumar is a member of ACCU, the Association for Computing Machin-
ery (ACM), and the American Helicopter Society (AHS). He was a recipient
of the Government of India’s Department of Science and Technology (DST)
award for the period 2005-2006.
Spring Berman (M’07) received the B.S.E. de-
gree in mechanical and aerospace engineering from
Princeton University, Princeton, NJ, in 2005 and the
M.S.E. and Ph.D. degrees in mechanical engineer-
ing and applied mechanics from the University of
Pennsylvania, Philadelphia, PA, in 2008 and 2010,
respectively.
From 2010 to 2012, she was a Postdoctoral Re-
searcher in Computer Science at Harvard Univer-
sity, Cambridge, MA. Since 2012, she has been an
Assistant Professor of Mechanical and Aerospace
Engineering with the School for Engineering of Matter, Transport and Energy
(SEMTE), Arizona State University, Tempe, AZ. Her research focuses on the
modeling and analysis of behaviors in biological and engineered collectives
and the synthesis of control strategies for robotic swarms.
Prof. Berman is a recipient of the 2014 Defense Advanced Research
Projects Agency Young Faculty Award and the 2016 Office of Naval Research
Young Investigator Award.