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. I NTRODUCTION  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. R ELATED   W ORK  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  x 2   x 1   x 3  B W  x 0   x n + 1  B B  Fig. 1.   Random configuration of robots on a boundary   B .  x 0   =   0   x n + 1   =   s  s 1  x 1  s 2  x 2  s n + 1  x n Fig. 2.   Configuration of   n   robot positions   x   : = ( x 1 , . . . ,   x n )   on   B , with artificial robot positions   x 0   =   0 and   x n + 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. P ROBLEM   S TATEMENT  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-fi with a communication radius of   d c , and it can sense and identify other  TABLE I N OTATION  Variable   Meaning  x i   |   x i   i -th Unordered   |   Ordered robot position  s i   i -th slack  x   |   x   Unordered   |   Ordered position vector  s   Slack vector  P   |   S   Position simplex   |   Slack simplex  f X ( x )   |   f X i   ( x i )   Joint   |   Marginal pdf of ordered positions  X i   |   S i   Random variables of   i -th position   |   i -th Slack  f S ( s )   |   f S i   ( s i )   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  e i   Unit vector along   i -th coordinate axis  Notation   Meaning a i :   j   Subvector   ( a i ,   a i + 1 , . . . ,   a   j   )   of   a a   ≥   b   | a   ≤   b   For all   i ,   a i   ≥   b i   | a i   ≤   b i  R +   Nonnegative reals Vol (   f   ( x ) ,   Ω )   Volume under function   f   ( x )   over region   Ω   :   ∫  Ω   f   ( x ) d x  1 X > a   Indicator random variable (rv) for the predicate   X   >   a  objects (for instance, using a camera) within a sensing radius of   d s . For computational convenience, we assume that   d c   =   d s  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   B W   and   B B . Define the unordered position  x i   of robot   i , labeled   R i , to be that of the robot’s endpoint closest to   B W   , as shown in Fig. 1. We define   x   = [ x 1   ...   x n ] T  as the vector of all the robots’ unordered positions. By sorting the positions in   x   according to increasing distance from   B W   , we obtain the ordered position vector   x   = [ x i   ...   x n ] T   . We define the distance between   x i   and   x i + 1   as the   i -th   slack ,   s i . We introduce two artificial robots   R 0   and   R n + 1   at unordered positions   x 0   =   0 and   x n + 1   =   s , respectively, which create the slacks   s 1   =   x 1   and   s n + 1   =   s   −   x n . We define the   slack vector   as  s   = [ s 1   ...   s n + 1 ] T   . We say that slack   s i   is   connected   if   s i   ≤   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  x i :1 ,..., n   (excluding the artificial robot positions) and whose edges are defined as   ( x i ,   x   j )   iff   | x   j   − x i | ≤   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   p con   as the probability that a random robot configuration on   B   is connected and   p mon   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:   p mon ,   p con , 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. M ATHEMATICAL   P RELIMINARIES  We now introduce a number of concepts that will be used throughout the paper.  A. Random Geometric Graphs (RGG)  Let   X 1: n   be a vector of i.i.d. random variables (rv’s), and let  x i   be a realization of   X i . Define a   Random Geometric Graph  (RGG), denoted by   G   =   G   ( n ,   d ) , with vertices   { x 1: n }   and edges consisting of vertex pairs   ( x i ,   x   j )   for which   || x i   −   x   j || ≤  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   R n   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   R n   is called a  simplex . The   canonical simplex   is defined by  ∆ n   =   { x   ∈   R n   :   1 T   x   ≤   1 and   x   ≥   0 }   (1) in its   H   form, and its vertex matrix is the identity matrix   I n + 1 . Every simplex in   R n   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   ∈   R n   :   a T   s   ≤   b } ,   where   a   >   0   and   b   >   0 .   (2)
5  Let   F gen   be the intersection of   T   with the unit hypercube  H cube   : = [ 0 ,   1 ] n . For every vertex   v   of   H cube , define the simplex   ∆ ( v )   by  ∆ ( v ) =   { s   ∈   T   :   s   ≥   v } ∩   H cube .   (3) The vertices of this simplex are   v   and the points   p i   =   1  a i   ( b   −  a T   v ) e i , where each   e i :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   H cube .  Lemma 1.   The volume of   F gen   =   T   ∩   H cube   is:  Vol ( F gen ) =   ∑  v ∈{ 0 , 1 } n  ( − 1 ) 1 T   v   Vol ( ∆ ( v )) =   1  n !   ∏   a i   ∑  v ∈{ 0 , 1 } n  ( − 1 ) 1 T   v   ( max ( b   −   a T   v ,   0 ) ) n   .   (4) When   v   lies in   T   , we have   ( b   −   a T   v )   ≥   0, and the resulting simplex   ∆ ( v )   contributes a nonzero volume to   F gen . Other- wise, the term   b   −   a T   v   is negative, and the resulting   ∆ ( v )  contributes nothing to Vol ( F gen ) . 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   R n ,  T simp   =   { s   ∈   R n  +   :   s   ≥   0 and   a T   s   ≤   b } ,   (5) defines a simplex with vertices at   0   and at the   n   points   b a i   e i , where   T   intercepts each coordinate axis. Hence, we can express   F gen   as the simplex-hypercube intersection   T simp   ∩  H cube , a fact which will be exploited in later sections. Finally, we note that Eq. (4) takes   Ω ( 2 n )   time to evaluate.  C. Probability Theory and Statistics  We write   X   ∼   f X   ( x )   :   x   ∈   R   to indicate that   X   is a real-valued rv with probability density function (pdf)   f X   ( x ) . Similarly, we write   X   ∼   f X ( x )   :   x   ∈   R n   to indicate that   X   is a real-valued random vector with pdf   f X ( x ) . We will use   F X   ( x )   to denote the cumulative distribution function (CDF) associated with   f X   ( x ) . Let   X   be a real-valued rv defined as above. We use   1 A   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   1 X ≥ 1   is one which is unity if the event in its subscript occurs, and zero otherwise. Let   f X ( x )   be the joint pdf of the variables   X 1: n , whose support is a region   Ω   ∈   R n . If   Ω ′   is a subset of   Ω , then the measure of   Ω ′   induced by   f  is   ∫  Ω ′   f X ( x ) d x . Since this integral gives the volume under the pdf   f X   over   Ω ′ , we will denote it by Vol (   f X ,   Ω ′ ) .  1) Poissonization  Many of our later computations will involve sums such as  X 1   +   . . .   +   X n , where the   X i   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   X i :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   1 X 1: n   and let   W   : =   ∑ n i = 1   1 X i   . We may then approximate  f W   ( w )   with a Poisson rv with the pdf Poi ( λ   ) , where   λ   : =  E ( W   ) =   ∑ n i = 1   E ( 1 X i   ) , which is justified as follows. First, we define the   total variation (TV) distance d TV   (   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:  d TV   (   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], d TV   (   f W   ( w ) ,   Poi ( λ   ))   ≤   ( 1   −   exp ( − λ   ))  (  1   −   V ( W   )  λ  )  ,   (7) where   V ( W   )   is the variance of   W   .  2) Order Statistics  Suppose the rv’s   X i   in the vector   X 1: 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   X i   is called the   i -th   order statistic   of the parent variable   X i   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   X i   are given by [37]  f X ( x )   =   n !  n  ∏  i = 1  g ( t ) 1 x 1 ≤ x 2 ... x n − 1 ≤ x n   ,  f X i   ( x i )   =  n  ∑  j = i  ( n j  )  G ( t )   j ( 1   −   G ( t )) n −   j ,   (8) where   G   is the parent CDF. V. D EFINITION OF   C OVERAGE   P ROPERTIES  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  1 S i ≤ d   .   (9) The event that   B   is   fully sensed   is: sen : =   1 S 1 ≤ d   1 S n + 1 ≤ d   ·  n  ∏  i = 2  1 S i ≤ 2 d   .   (10) Likewise, the event that   B   is   monitored   is: mon : =  n + 1  ∏  i = 1  1 S i ≤ 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: N con   : =  n  ∑  i = 2  1 S i ≤ d   ,   (12) N sen   : =   ∑  i = 1 , n + 1  1 S i ≤ d   +  n  ∑  i = 2  1 S i ≤ 2 d   ,   (13) N mon   : =  n + 1  ∑  i = 1  1 S i ≤ d   .   (14) Here, N con , N sen , and N mon   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   x 1   senses length min ( s 1 ,   d )   on the slack   s 1 . Every slack   s i :2 ,..., n   will be sensed by the two robots at  x i   and   x i + 1 , which will together sense a length of min ( s i ,   2 d )  on it. Likewise, the last robot   x n   senses length min ( s n + 1 ,   d )  on   s n + 1 . The total sensed length is thus slen : =   ∑  i = 1 , n + 1  min ( s i ,   d ) +  n  ∑  i = 2  min ( s i ,   2 d ) .   (15) Defining   p sen   as the probability of the event sen in Eq. (10), we may express the expectation of slen as  E ( slen ) =   p sen   ·   s .   (16)  x 1   x 3 x 0   =   0   x 4   =   s  s 1   s 3  ̃ s 2    ̃ s 4  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  1 S i > 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 ( 1 S i > d   ) =   1   +  n  ∑  i = 2  P ( S i   >   d ) .   (18)  E. Vertex Degree,   deg The   vertex degree ( deg )   of a robot at position   x i   is deg ( x i ) =   ∑  1 ≤   j ≤ n ,   j 6   = i  1 | x i − x   j   |≤ d   .   (19) Applying the linearity of expectation to Eq. (19), the expected value of deg is  E ( deg ) = ( n   −   1 ) P ( | X i   −   X j | ≤   d ) ,   (20) where   X i   and   X j   are any two unordered positions on   B . VI. G EOMETRIC   F ORMULATION  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   R n , and neglect CF requirements. Every valid position vector on   B  satisfies the constraints 0   ≤   x 1   ≤   . . .   ≤   x n   ≤   s .   (21) Eq. (21) gives the   H   form of a simplex in   R n , which we refer to as the   position simplex   P . We could alternatively consider the slack vector defined by   x ,  s 1: n + 1   : =   x 1: n + 1   −   x 0: n .   (22) Representing   s   as a point in   R n + 1 , we observe that a valid slack vector satisfies the constraints  0   ≤   s   and  n + 1  ∑  i = 1  s i   =   1 T   s   =   s .   (23) These inequalities define the   H   form of a   degenerate n - dimensional simplex   S   embedded in   R n + 1 , since   s   can be completely specified by   n   slacks instead of   n   +   1. By dropping  s n + 1 , we may redefine   S   as  S full   : =   { s   ∈   R n   :   0   ≤   s   and   1 T   s   ≤   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   R n . Eq. (23) defines   the   regular   simplex   s   ·   ∆ n   in   R n + 1 ,   which   scales the canonical simplex   ∆ n   by a factor of   s . This regularity often simplifies connectivity-related computations. The full- dimensional form   S full   represents the last slack   s n + 1   implicitly, and so constraints on   s n + 1   must be treated separately. It is easier to use software libraries to compute volumes and integrals over   S full   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  x i   −   x i − 1   ≥   D ,   i   =   1 , . . . ,   n   +   1 .   (25) Note that Eq. (25) enforces   x 1   ≥   D   and   x n   ≤   s   −   D   to ensure against conflicts with the virtual robots at   x 0   =   0 and   x n + 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  s 2: n   ≤   d 1 T   .   (26) For a configuration to monitor   G   , we require in addition that the slacks   s 1   and   s n + 1   be connected, leading to  s 1: n + 1   ≤   d 1 T   .   (27) Monitoring requires   s   to lie within the   ( n   +   1 ) -dimensional hypercube   H mon   = [ 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   H con   = [ 0 ,   s ]   ×   [ 0 ,   d ] n − 1   ×   [ 0 ,   s ] . Note that a minimum of   n min   : =   b s / d c  robots is required to monitor   B . VII. CT C OVERAGE WITH   U NIFORM   I.I.D. P ARENTS  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   1 B   . From Eq. (8), the joint pdf of robot positions is uniform over   P , and   X i   has a Beta pdf:  f X ( x )   =   n !  s n   1 P   (28)  f X i   ( x i )   =   s   ·   Beta ( i ,   n   −   i   +   1 ) .   (29) Making the change of variables   S i   =   X i   −   X i − 1   in Eq. (28), we find that   f S ( s )   is uniform over the slack simplex   S   :  f S ( s )   ∼   n !  s n + 1   1 S   .   (30) Since the slacks are not subject to ordering constraints, they are   exchangeable   rv’s and thus are identically distributed. In particular,   S i   ∼   S 1 , and since   S 1   =   X 1 , we have by Eq. (29) that  f S i   ( s i ) =   s   ·   Beta ( 1 ,   n ) .   (31) The mean positions at   E ( X i ) =   s · i n + 1   subdivide   B   into   n   +   1 equal slacks, each of length   E ( S i ) =   s n + 1   , as we would expect of robot configurations on average for a uniform parent pdf. As   n   and   d   increase, we expect   p mon ,   p con , 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, p mon  From Eq. (27), the subset of   S   whose configurations monitor  B   is   F mon   : =   S   ∩   H mon , which we refer to as the   favorable region   for monitoring. Since   F mon   is the intersection of two convex polytopes, it is a convex polytope as well. We then have   p mon   =   Vol ( F mon ) / Vol ( S   ) . While we may determine Vol ( F mon )   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   \   F mon   be the exterior of   F mon . 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   s k . Define   s ′  k   =   s k   −   d , and note that all such slack vectors satisfy  s ′  k   +   ∑  1 ≤   j ≤ n + 1 ,   j 6   = k  s   j   =   s   −   d ,   (32)
8  forming a regular simplex of side   √ 2 ( s   −   d ) . We will call this simplex the   exterior simplex   of   s k   and denote it by   F   mon ( s k   >  d ) . It is clear that  F   mon   =  n + 1 ⋃  k = 1  F   mon ( s k   >   d ) .   (33) However, because the simplices   F   mon ( s k   >   d )   overlap,  n + 1  ∑  k = 1  Vol ( F   mon ( s k   >   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   ≥   d v } .   (34) Every 1-bit component   v i   =   1 in   v   causes the corresponding slack   s i   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   n min   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 ≤ 1 T   v ≤ n min  Vol ( F   mon ( v )) =  n min  ∑  k = 1  ( − 1 ) k − 1  ( n   +   1  k  )  ( s   −   kd ) n  √ n   +   1  n !   .  (36) Finally, we obtain an expression for   p mon :  p mon   =   Vol ( F mon )  Vol ( S   )   =   1   −   Vol ( F   mon )  Vol ( S   ) =   1   −  n min  ∑  k = 1  ( − 1 ) k − 1  ( n   +   1  k  ) (  1   −   k d s  ) n  .   (37) Alternatively, we can use Lemma 1 to compute Vol ( F mon )   as follows. We define   F mon   in its full-dimensional form as the intersection between the cube   H cube   = [ 0 ,   d ] n   and   two   regions:  F full , mon   =   S full   ∩   S full ( s n + 1   ≤   d )   ∩   H cube   (38) Here, the region  S full ( s n + 1   ≤   d )   : =   { s 1: n   ∈   S full   : 0   ≤   ( s   −   1 T   s 1: n )   ≤   d }   (39) captures the connectivity of   s n + 1 . To compute Vol ( F full , mon ) , we first define the region   S full ( s n + 1   >   d )   to be the subset of  S full   over which   s n + 1   is disconnected. We note that  F full , mon   = ( S full   \   S full ( s n + 1   >   d ))   ∩   H cube ;   (40) exploiting the fact that   S full ( s n + 1   >   d )   is a simplex, we obtain Vol ( F full , mon ) =   Vol ( S full   ∩   H cube )  −   Vol ( S full ( s n + 1   >   d )   ∩   H cube )   (41) by applying Lemma 1 once for each volume of intersection.  C. Probability of Connectivity, p con  From Eq. (26), connectivity of the graph   G   does not place any constraints on   s 1   and   s n + 1 . Instead, we define the connected region   F con   to be the subset of   S   consisting of connected slack vectors, analogous to   F mon . We may write   F con   in full-dimensional form as   F con   : =   S full   ∩   H con , where   H con  is defined in Sec. VI. The region   F con   does not constrain   s 1 , since it requires that   s 1   not exceed   s , which follows from the fact that   s   ∈   S   . Neither does   F con   constrain   s n + 1 . We will now prove an intermediate result from which   p con   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   H gen  as:  T   ′  simp   : =   { s 1: n   ∈   R n  +   :   1 T   s 1: n   ≤   b } ,   (42)  H gen   : =  n  ∏  i = 1  [ 0 ,   a i ] .   (43) Let   F   ′  gen   : =   T   ′  simp   ∩   H gen   and   a   =   [ a 1   . . .   a n  ] T   .  Lemma 3.   The volume of   F   ′  gen   is given by  Vol ( F   ′  gen ) =   1  n !   ∑  v ∈{ 0 , 1 } n  ( − 1 ) 1 T   v   ( max ( b   −   a T   v ,   0 ) ) n   .   (44)  Proof.   Define   T simp   and   H cube   as in Sec. IV-B2. Transform the coordinates   s 1: n   to   s ′  1: n , where   s ′  i   : =   a i s i , and note that the transformed simplex and hypercube are   T   ′  simp   and   H gen , respectively. Defining   J n × n   as the Jacobian matrix of the transformation, we then have Vol ( F gen ) =   det ( J )   ·   Vol ( F   ′  gen ) .   (45) The diagonal entries of   J   are   J i , i   =   1  a i   , and the off-diagonal entries of   J   are zero. It follows that det ( J ) =   ∏   1  a i   . Eq. (44) follows immediately from Eq. (4). The slack simplex   S full   and the hypercuboid   H con   correspond to   T   ′  simp   and   H gen , respectively. Define   a   ∈   R n   as a vector with  a 1   =   s   and   a 2: n   =   d . From Eq. (44), we have: Vol ( F con ) =   1  n !   ∑  v ∈ H con  ( − 1 ) 1 T   v ( max ( s   −   a T   v ,   0 )) n .   (46) Observing that when   v 1   =   1, we have that  a T   v   =   s   +  n  ∑  i = 2  dv i   ≥   s   = ⇒   s   −   a T   v   ≤   0 ,  so that the resulting simplex contributes no volume to   F con . Now suppose that   v 1   =   0 and that   k   bits among   v 2: 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 ( F con ) , from which we obtain  p con   : =   Vol ( F con )  Vol ( S full ) =  n min  ∑  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   p con . If cmp   =   k   +   1, then   s 2: n   has exactly   k  disconnected slacks. Let   F   ( cmp   =   k   +   1 )   denote the subset of   S full   consisting of these slacks, and let   F   ( v )   denote the subset of   S full   consisting of slack vectors that obey   s 1: n   ≥   d v . The subset   F   ( cmp   =   k )   has   k   −   1 disconnected slacks, not including the first unconstrained slack   s 1 . 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   :   v 0   =   0 and   1 T   v   =   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 , n min − 1 )  ( − 1 ) 1 T   v ( s   −   d 1 T   v ) n ,  (50) where  V ( k   −   1 ,   n min   −   1 )   : =  n min − 1 ⋃  i = k − 1  V ( i ) .   (51) We can then derive   P ( cmp   =   k ) =   Vol ( F   ( cmp = k ))  Vol ( S full )   , which sim- plifies to the expression  P ( cmp   =   k ) =  n min − 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   s   j   is disconnected, irrespective of the other slacks, then the resulting slack   vector   obeys   the   constraint   1 T   s   j 6   = i   ≤   ( s   −   d ) .   From Sec. VII-B, this smaller simplex has a volume proportional to   ( s   −   d ) n , so that  P ( S i   >   d ) =  (  1   −   d s  ) n  and   P ( S i   ≤   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   F sen   as the subset of   S   for which the boundary is fully sensed. Analogous to   F mon , we express   F sen   as the intersection between   S   and the sensing hypercuboid   H sen   = [ 0 ,   d ]   ×   [ 0 ,   2 d ] n + 1   ×   [ 0 ,   d ] . The volume of   F sen   is computed from Lemma 3. The value of   E ( slen )   can then be determined from Eq. (16).  Theorem 2.   The probability p sen   that   B   is fully sensed is: p sen   =   1   −  n min  ∑  i = 1  ( − 1 ) i − 1  [( n   −   1  i  )  max  (  1   −   2 i d s   ,   0  ) n  +   2  ( n   −   1  i   −   1  )  max  (  1   −   ( 2 i   −   1 )   d s   ,   0  ) n  +  ( n   −   1  i   −   2  )  max  (  1   −   ( 2 i   +   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   p mon .   When computing   p mon , 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   s 1   and   s n + 1   differently from the others. Consider the set of all   n -bit vectors   v 1: n   that iterate through the vertices of  H sen . 1) If   v 1   =   v n + 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   v T   s   =   s   −   2 id   that contribute to Vol ( F sen ) . 2) If   v 1   =   0 ,   v n + 1   =   1 or   v 1   =   1 ,   v n + 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   v T   s   =   s   −   ( 2 i   −   1 ) d  that contribute to Vol ( F sen )   . 3) If   v 1   =   v n + 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   v T   s   =   s   −  ( 2 i   +   1 ) d   and contributes to Vol ( F sen ) .  F. Vertex Degree,   deg When two points   ( x 1 ,   x 2 )   are selected at random on   [ 0 ,   s ] , we may write their joint pdf in terms of their order statistics:  f   ( x 1 ,   x 2 ) =   2  s 2   1 0 ≤ x 1 ≤ x 2 ≤ s .   (56) Using Eq. (56), the probability term in Eq. (20) is  P   ( | X 1   −   X 2 | ≤   d ) =   2  s 2  ( ∫   s − d  x i = 0  ∫   x 1 + d  x 2 = x 1  d x 2 d x 1   +  ∫   s  x 1 = s − d  ∫   s  x 2 = x 1  d x 2 d x 1  )  =   2 ds   −   d 2  s 2   ,   (57) which yields  E ( deg ) = ( n   −   1 )   2 ds   −   d 2  s 2   .   (58)
10  x 1   x 2   x 3 x 0   =   0   x 4   =   s  s 1   s 3  ̃ s 2    ̃ s 4  Fig. 5. Slacks (blue) and free slacks (red) of the robot configuration in Fig. 1.  VIII. CF C OVERAGE WITH   I.I.D. U NIFORM   P ARENTS  We will now analyze the graph   G   of a CF configuration and the resulting CF geometric objects. In Fig. 5, the left virtual robot   R 0   has position   x 0   =   x 0   =   0 and occupies the interval  [ 0 ,   D ] ; the right virtual robot is located at   x n + 1   =   s , occupying the interval   [ s ,   s   +   D ] . Robots   R 1: n   are located at positions on the interval   [ D ,   s   −   D ] , which has length   s   −   2 D . We define   S CF   to be the subset of   S   consisting of CF slack vectors. An alternative way to characterize   S CF , to be used later, is through   free slacks . We define the   free slack   ̃ s i   associated with   s i   to be the length of that subinterval of  [ x i − 1 ,   x i ]   that falls outside the body of any robot. From Fig. 5, we see that  ̃ s i   =   s i   −   D . We define the vector of free slacks as  ̃ s 1: n + 1 , which must satisfy  1 T    ̃ s 1: 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  S full , we define the full-dimensional equivalent of   S CF , full   by  S CF , full   : =   {  ̃ s 1: n   ∈   R n  +   :   1 T    ̃ s   ≤    ̃ s } .   (60) The volume of   S CF   remains the same regardless of whether it is expressed in terms of free slacks or slacks, so that Vol ( S CF , full ) =    ̃ s n  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   s n + 1   ∈   [ D ,   d ]   on the last slack, which can be handled in a fashion similar to equations (38) and (41).  A. Probabilities p mon   and p con  We will first introduce the geometric concepts for computing  p mon . Analogous to the CT case, we define the monitoring hypercube to be   H CF , mon   = [ D ,   d ] n + 1   and the favorable region for monitoring to be   F CF , mon   : =   S full   ∩   H CF , mon . Note that the CF constraint is handled in the hypercube, and not in the slack simplex. Since   H CF , mon   is not of the form   [ 0 ,   c ] n + 1  for some constant   c , the regions defined by   S   ( v )   : =   { s   ∈  S   :   s   ≥   d v } ∩   H CF , mon   are no longer simplices, and so we cannot apply Lemma 1 directly to compute Vol ( F CF , mon ) . This problem cannot be remedied by transforming slacks into free slacks. Instead, we extend Lemma 1 to the case where the simplex   T simp , defined in Eq. (5), is intersected with a  displaced   hypercuboid. We define a displaced hypercuboid by specifying its diagonally opposite vertices,   v c   and   v   f   , which  ( 0 ,   0 )   s 1  s 2  ( s ,   0 )  ( 0 ,   s )  ( D ,   D )  ( d ,   d )  H CF , mon  S full  Fig. 6.   Illustration of Algorithm 1 for   n   =   2. The simplex   S full   and the hypercube   H CF , mon   are represented in full-dimensional form, and constraints on   s 3   are   not   shown   for   simplicity.   S full   is   the   triangle   with   vertices  { ( 0 ,   0 ) ,   ( 0 ,   s ) ,   ( s ,   0 ) }   and   H CF , mon   is the square   [ D ,   d ] 2 . Algorithm 1 computes the area of intersection of   S full   with   [ 0 ,   d ] 2 , from which it subtracts the area of  S full   under the hatched region to obtain the area of the red triangle   F CF , mon .  are respectively its closest vertex to   0   and its farthest vertex away from   0 :  H v c , v   f   =   { s 1: n   ∈   R n  +   :   0   ≤   v c   ≤   s   ≤   v   f   } .   (62) The vertex pair   ( v c ,   v   f   )   encodes all information about the faces of the hypercuboid. Now we will use Algorithm 1 to compute the volume of the intersection   F   : =   T simp   ∩   H v c , v   f   . To do so, the algorithm computes the volume of   T simp   ∩   H 0 , v   f   , which overestimates Vol ( F   ) , in step 3. Subsequently, it subtracts the volumes of overlap between   T simp   and the exterior of   H v c , v   f   , i.e. the region   H 0 , v   f   \   H v c , v   f   , using the PIE. This exterior is the union of hypercuboids   H b , i   that lie between   H v c , v   f   and   0 . The volume of intersection of   T simp   with this exterior, denoted by   H inter , 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( T simp ( a ,   b ) ,   H v c , v   f   )  2:   d 1: n   ←   v   f   −   v c   .   Edges of   H v c , v   f  3:   V   ←   Vol ( T simp   ∩   H 0 , v   f   )   .   Compute using Lemma 3  4:   for   i   ←   1   . . .   n   do  5:   H b , i   =   H 0 , v i   where   v i   =   v c   + ( v   f   , i   −   v c , i ) e i  6:   end for  7:   for v   ∈ { 0 ,   1 } n   do  8:   H inter ( v )   ←   ⋂  v i = 1   H b , i  9:   Compute Vol ( T simp   ∩   H inter )   using Lemma 3  10:   V   ←   V   + ( − 1 ) 1 T   v Vol ( H inter )  11:   end for  12:   Return   V  13:   end procedure
11  The hypercube   H CF , mon   is an instance of   H v c , v   f   with   v c   =   D 1 T  and   v   f   =   d 1 T   . Since   H CF , mon   = [ D ,   d ] n   is a hypercube, it has identical faces, so each of the hypercuboids   H b , i   has the same set of edges. Further, the simplex   S   is an instance of   T simp  with   a   =   1 ; since the coefficients   a i   are all unity, it follows that   H inter ( v )   and   H inter ( 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   H inter ( 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   ∑ ij = 1   e   j . We thus have Vol ( F CF , mon ) =   Vol ( S   ∩   [ 0 ,   d ] n + 1 ) −  n + 1  ∑  i = 1  ( − 1 ) i  ( n   +   1  i  )  Vol  (  S   ∩   H inter (  i  ∑  j = 1  e   j )  )  ,   (63) and   p mon   =   Vol ( F CF , mon )  Vol ( S   )   . Running Algorithm 1 with inputs   T simp   : =   S full   and   H v c , v   f   : =  H CF , con   = [ D ,   s ]   ×   [ D ,   d ] n − 1   furnishes the volume of the favor- able region   F CF , con   for a connected CF configuration, and thereby   p con .  B. Probability p sen  Computing   p sen   requires us to consider the intersection be- tween   S   and the hypercuboid  H CF , sen   : = [ D ,   d ]   ×   [ D ,   2 d ] n − 1   ×   [ D ,   d ] .   (64) Both   S   and   H CF , sen   are degenerate polytopes. To compute their   volume   of   intersection,   we   express   the   intersection  F CF , sen   in   full-dimensional   form,   as   in   Eq. (38).   Define  H full   : = [ D ,   d ]   ×   [ D ,   2 d ] n − 1   to be the full-dimensional form of  H CF , sen . Following the approach of Eq. (38), we can compute the full-dimensional form of   F CF , sen   as  F full , sen   : =   H full   ∩   S full   ∩   S full ( s n + 1   ∈   [ D ,   d ]) ,   (65) where   S full ( s n + 1   ∈   [ D ,   d ])   is defined as the subset of   S full   in which the last slack   s n + 1   =   s   −   1 T   s 1: n   lies in   [ D ,   d ] . Then we can determine the volume of   F full , sen   as: Vol ( F full , sen ) =   Vol ( S full   ∩   H full )  −   Vol ( S full ( s n + 1   >   d )   ∩   H full )  −   Vol ( S full ( s n + 1   <   D )   ∩   H full ) ,   (66) where the region   S full ( s n + 1   >   d )   is the subset of   S full   over which   s n + 1   is disconnected, and likewise   S full ( s n + 1   <   D )   is the subset of   S full   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 ( F full , sen ) . We can then compute   p sen   =  Vol ( F CF , sen )  Vol ( S full )   and, by Eq. (16),   E ( slen ) =   s   ·   p sen .  C. Number of Connected Components,   cmp Proceeding as in Sec.VII-D, we define   F CF ( cmp   =   k )   to be the subset of   S CF   whose slacks have   k   connected components. We now write the CF equivalent of Eq.(50), replacing   F   ( cmp   =   k )  with its CF counterpart   F CF ( cmp   =   k ) . To compute the volume of this region, we can use Algorithm 1 with the inputs  T simp   : =   S full   and   H v c , 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   p mon   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  F CF , mon   by    ̃ F CF , mon , defined as the intersection between the free slack simplex    ̃ S   and the hypercube    ̃ H mon   : = [ 0 ,    ̃ d ] n + 1 , where    ̃ d   : =   d   −   D . Likewise, by intersecting    ̃ S   with    ̃ H con   : = [ 0 ,    ̃ s ]   ×   [ 0 ,    ̃ d ] n − 1   ×   [ 0 ,    ̃ s ] , we obtain an approximation of the favorable region of connectivity,    ̃ F CF,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    ̃ p mon   and    ̃ p con , can be expressed as the equations (37) and (47) for   p mon   and   p con   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 ) ,   p sen   (and thus   E ( slen ) ), and   E ( deg ) , respectively. We call this approxi- mation the   free slack approximation   (FSA) for the CF case. IX. A PPROXIMATIONS OF   C OVERAGE   P ROPERTIES  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 ( S i )   =   s n   +   1  n + 1  ∑  j = i  1  j   =   s n   +   1   ( H n + 1   −   H i ) ,   (67)  V ( S i )   =  n + 1  ∑  j = i  1  j 2   ,   (68) where   H n   denotes the harmonic numbers. If   n   is large, we may approximate   H n   by log   n . The longest slack   S n + 1   has the expected value   E ( S n + 1 ) =   s n + 1   H n + 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 ( S n + 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  log   n   )   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   =   Θ ( s   log   s ) .   (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 (   log   n n   )   cause   E ( deg )   to have growth of order   O ( log   n )   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   =   Ω (   log   n n   ) , which ensures that   G   has no isolated vertices a.s. Likewise, the   subconnectivity regime   with   d   =   o (   log   n n   )   ensures that   G   has one or more isolated vertices a.s.  C. Poisson Approximation of Coverage Properties 1) Poissonizing   N mon   and   N con  We derive Poisson estimates for N mon   and N con   using re- sults from [36, Ch.7]. The key observation is that the slack rv’s   S i :1 ,..., n + 1 , are negatively associated, since an increase in one slack leads to a corresponding decrease in the others. Applying Lemma 2 to N mon , we see that N mon   is approxi- mately distributed as Poi ( λ mon )   with   λ mon   =   ∑ n + 1  i = 1   E ( 1 S i ≤ d   ) . The   slacks’   exchangeability   implies   that   S 1   ∼   S i ,   so   that  λ mon   = ( n   +   1 ) P ( S 1   ≤   d ) . From Eq. (53), we obtain  λ mon   = ( n   +   1 )  (  1   −  (  1   −   d s  ) n )  .   (71) Using Eq. (12), the analogous Poisson rv for N con   has mean  λ con   = ( n   −   1 ) P ( S 1   ≤   d ) . These Poisson approximations are valid for regimes   ( n ,   d )   for which [36, Ch.7]  n   →   ∞ ,   d s   →   0 ,   and   n d s   →   λ ∞   +   o ( 1 )  n   ,   (72) where   λ ∞   is a finite constant. We may approximate   p mon   using N mon   by noting that when N mon   =   n   +   1,   the   entirety   of   B   is   monitored.   Let   Λ   ∼  Poi ( λ mon ) ; then we have that  p mon   : =   P ( N mon   =   n   +   1 )   ≈   P ( Λ   =   n   +   1 ) =   λ   n + 1 mon   exp ( − λ mon ) ( n   +   1 ) !   .   (73) Likewise, we have for   p con   :  p con   : =   P ( N con   =   n   −   1 )   ≈   λ   n − 1 con   exp ( − λ con ) ( n   −   1 ) !   .   (74)  2) Poissonizing   N sen  Reasoning similarly for   p con , we have N sen   ∼   Poi ( λ sen ) , where  λ sen   =  n  ∑  i = 2  E ( 1 S i ≤ 2 d   ) +   E ( 1 S 1 ≤ d   ) +   E ( 1 S n + 1 ≤ d   ) =   n  (  1   −  (  1   −   2 d s  ) n )  +   2  (  1   −  (  1   −   d s  ) n )  ,   (75) and thereby approximate   p sen   as  p sen   =   P ( N sen   =   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   p mon   and   p con   to obtain cmp   ∼   Poi ( λ cmp ) , where  λ cmp   =   1   + ( n   −   1 ) E ( 1 S 1 > d   ) =   1   + ( n   −   1 )  (  1   −   d s  ) n  .   (77) X. D ESIGN FOR   T ARGET   C OVERAGE   P ROPERTIES  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   p con , 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)   p mon   =   0 . 80, (2)   p con   =  0 . 70, (3)   E ( cmp ) =   4, (4)   E ( slen ) =   0 . 6 s , and (5)   E ( deg ) =   5. 1)   p mon   =   0 . 80: To compute an initial guess of   n   for the solver   fsolve , we note that a length of   s mon   =   sp mon   =  200 ( 0 . 80 ) =   160 needs to be monitored on average. Using Eq. (69), we solve for an initial guess   n 0   that satisfies log ( n 0   +   1 ) / ( n 0   +   1 ) =   d / s mon , which yields   n 0   =   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)   p con   =   0 . 70: We again use the initial guess   n 0   =   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   n max   =   39 . 49. In addition,   E ( cmp ) =   0 at   n   =   0 and lim n → ∞   E ( cmp ) =   0. Thus, there are two values of   n   at which   E ( cmp ) =   4:   n low   ∈   ( 0 ,   n max )   and   n high   ∈   ( n max ,   ∞ ) . In the CT case, initializing   fsolve   with   n 0 , low   =   1 gave  n low   =   4 . 34, and initializing with   n 0 , high   =   162 . 00 (as for the previous two properties) gave   n high   =   155 . 74. In the CF case, these two initial values   n 0 , low   and   n 0 , high  produced   n low   =   4 . 27 and   n high   =   90 . 98, respectively. 4)   E ( slen ) =   0 . 6 s   =   120: We have   p sen   =   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   n 0  from   nd   =   s   log   s   in Eq. (70), instead of from Eq. (69), yields the same answers as above for both the CF and CT cases. XI. C OVERAGE WITH   N ON -U NIFORM   I.I.D. P ARENTS  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   p mon   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  f S ( s ) =   g ( s 1 ) g ( s 1   +   s 2 )   . . .   g (  n  ∑  i = 1  s i ) 1 S   .   (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   S i   : =   X i + 1   −   X i   by noting that the joint pdf of   X i   and  X i + 1   is [37, Ch.2]  f X i , X i + 1   ( x i ,   x i + 1 ) =   n !  ( i   −   1 ) ! ( n   −   i   −   1 ) !   ×  g ( x i ) g ( x i + 1 ) G i − 1 ( x i )( 1   −   G ( x i + 1 )) n − i − 1 ,   (79) so that  f S i   ( s i ) =  ∫   s t = 0  f X i , X i + 1   ( t , t   +   s i ) dt .   (80) Here,   G   is the CDF of   g .  2) Probabilities p mon , p con , and p sen  The measure of a subset   F gen   of   S   induced by   f S ( s )   is given by Vol (   f S ( s ) ,   F gen ) . Using Lemma 1, we may express this measure in terms of measures over simplices: Vol (   f S ( s ) ,   F gen ) =   ∑  v ∈{ 0 , 1 } n  ( − 1 ) 1 T   v   Vol (   f S ( s ) ,   ∆ ( v )) .   (81) This expression requires the computation of   O ( 2 n )   integrals. We can obtain the formulas for   p mon ,   p con , and   p sen   by replacing Vol ( ∆ ( v ))   by Vol (   f S ( s ) ,   ∆ ( v ))   in equations (37), (47) and (55) respectively. For instance,   p mon   and   p con   are given by:  p mon   =   1   −   ∑  v ∈{ 0 , 1 } n :1 ≤ 1 T   v ≤ n min  ( − 1 ) 1 T   v − 1 Vol (   f S ( s ) ,   F   ( v )) ,  (82)  p con   =   ∑  v ∈ Ver ( H con )  ( − 1 ) 1 T   v Vol (   f S ( s ) ,   ∆ ( v )) .   (83) We may approximate these probabilities using N con , N mon   and N sen . We first derive the probabilities that slack   S i   is connected and disconnected:  P ( S i   ≤   d ) =  ∫   d s i = 0  f S i   ( s i ) ds i ,  P ( S i   >   d ) =   1   −  ∫   d s i = 0  f S i   ( s i ) ds i .   (84) Now, proceeding as in Sec. IX-C, we have that N mon   is approximately distributed as Poi ( λ mon ) , where  λ mon   =  n + 1  ∑  i = 1  P ( S i   ≤   d ) ,   (85) whose approximation error tends to zero when Eq. (72) holds. We   may   then   approximate   p mon   by   Eq. (73).   Analogous expressions may be derived for   p con   and   p sen .  3) Number of Connected Components,   cmp By Eq. (18), we have that  E ( cmp ) =   1   +  n  ∑  i = 2  P ( S i   >   d ) ,   (86) which may be determined from Eq. (84).  4) Vertex Degree,   deg By Eq.(20), we can compute   E ( deg )   from   P ( | X i   − X j | ≤   d ) .The joint pdf of two unordered positions can be rewritten in terms of their order statistics:  f X 1 , X 2   ( x 1 ,   x 2 ) =   2! g ( x 1 ) g ( x 2 ) 1 0 ≤ x 1 ≤ x 2 ≤ s .   (87)
14  We now obtain  P ( | X 2   −   X 1 | ≤   d ) =   2  ∫   s − d  x 1 = 0  ∫   x 1 + d  x 2 = x 1  g ( x 1 ) g ( x 2 ) d x 1 d x 2  +   2  ∫   d  x 1 = s − d  ∫   s  x 2 = x 1  g ( x 1 ) g ( x 2 ) d x 1 d x 2 ,   (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 (   f S ( 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   p con ,   p mon , and   p sen   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. C ONCLUSIONS AND   F UTURE   W ORK  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   R i   has a distinct communication range   d i . 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   R 1 ,   R 2 , and   R 3   whose communication ranges satisfy   d 1   >   d 2   and   d 3   >   d 2 . Suppose further that   R 1 , but not   R 3 , is within the range of   R 2 . Then   R 2   may route packets destined for   R 3   through   R 1 , thereby creating a connected   G   . Such a scenario does not arise when each robot has the same range   d . The inclusion of heterogeneous ranges   d i   entails the loss of symmetry of the favorable region   F mon   which was exploited in Sec. VII to compute   p con   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   D i , the CF polytope   S CF   becomes a simplex with hypercuboidal holes. Computing Vol ( S CF   )   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   f X ( 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-fi transmitters 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   R 2   and   R 3  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. A CKNOWLEDGMENTS  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  R EFERENCES [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.