arXiv:1604.01452v1 [cs.RO] 5 Apr 2016  THE PROBABILISTIC ANALYSIS OF THE NETWORK GRAPH CREATED BY DYNAMIC BOUNDARY COVERAGE  GANESH P. KUMAR   ∗ ‡   AND   SPRING BERMAN   †‡  Abstract. Key words. AMS subject classifications.  1. Introduction. 1.1. Background.   We address the problem of achieving   boundary coverage   with a swarm of autonomous robots. In this task, a group of robots must allocate themselves around the boundary of a region or object according to a desired configuration or density. We specifi- cally consider problems of   dynamic   boundary coverage, in which robots asynchronously join a boundary and later leave it to recharge or perform other tasks. Applications: mapping, ex- ploration, environmental monitoring, surveillance, disaster response tasks such as cordoning off hazardous areas; collective payload transport, in which the group cooperatively transports a load to a destination, for automated manipulation, assembly, construction, and manufactur- ing. We focus on   stochastic coverage schemes (SCS) , in which robots probabilistically choose po- sitions on the boundary. Our interest in SCS, as opposed to deterministic coverage schemes, is motivated by the following reasons. First, they enable a probabilistic analysis of the graph for different classes of inputs identified by the joint pdf of robot positions. Second, SCS al- low us to model natural phenomena such as   Random Sequential Adsorption   (RSA) [ 30 ], the clustering of ants around a food item [ 20 ], and   Renyi Parking   [ 6 ], the process by which a fleet of cars parks without collisions on a parking lot. Lastly, results from SCS allow us to ana- lyze the distributions of robots with noisy sensing and actuation, even though the underlying coverage scheme may be deterministic.  1.1.1. Assumptions about Robot Capabilities.   We assume that each robot can locally sense its environment and communicate with other robots nearby.   Disk model of sens- ing/communication. Robots can distinguish between other robots and a boundary of interest. The robots lack global localization: highly limited onboard power may preclude the use of GPS, or they may operate in GPS-denied environments. The robots also lack prior informa- tion about their environment. Each robots exhibits random motion that may be programmed, for instance to perform probabilistic search and tracking tasks, or that arises from inherent sensor and actuator noise. This random motion produces uncertainty in the locations of robot encounters with a boundary.   For this reason, we refer to the task as   stochastic boundary  † School of Computing, Informatics, and Decision Systems Engineering, Arizona State University, Tempe AZ 85287.  ‡ School for Engineering of Matter, Transport and Energy, Arizona State University, Tempe AZ 85287.  ¶ This work was supported by DARPA Young Faculty Award no. D14AP00054. 1
coverage .   In addition, we assume the robots have sufficient memory to store certain data structures.  1.2. Summary of Results.   We devise a data structure to implement our coverage schemes, and we compute the probabilities of connectivity of various coverage schemes.  1.3. Models of Boundary Coverage.   We consider a team of robots,   { R i } ∈   [ 1   . . .   n ]   in a bounded environment   E   . Robots are provided only with their (perfect) odometric readings and Wifi measurements, and a camera for detecting landmarks. Each robot is a disk of di- ameter   R , and its Wi-fi has a coverage radius of   d . They have no knowledge of their global positions or other means to localize. In the environment is placed a load in the form of a thin line, called the   Boundary   B , which is colored black, distinctively from the rest of the environment. One endpoint of   B   is painted white. Since the main thrust of this paper lies in the randomized analysis of the network created by the robots, we will make the following simplifying assumptions. All robots are synchronized in time, with respect to a global clock. No robot fails in the course of its execution. Dealing with failures, and determining the success of boundary coverage in rugged environments where Wifi may fail are issues to be addressed in our future work. To begin with, we consider point robots, for which   R   =   0 and thus the issue of inter-robot collisions does not arise. Let   n   of them attached to   B   at a time instant   t   ∈   N   [ 18 ]. Let the position of robot   i   be   x i . Define the vector of   unordered   positions to be   x ( t )   : =   [ x 1 ... n  ]   T. It will be convenient to make our computations if we sort this vector in nondecreasing order to get its permutation   x   =   [ x 1 ... n  ]   T, whose entry   x i   is the   i -th robot from the left, and not necessarily the position of   R i . Since   x i   forms the   i -th smallest of the   n   entries of   x , it is called the   i -th   order statistic   of the positions [ 5 ]. We may think of   x   (and   x ) as the realization of a PP in   B n , so that   x   forms a point in   B n . Define the random variable associated with   x i   to be  X i , and place all these rv’s in a vector   X   that defines the PP. For convenience, we introduce two artificial robots   x 0   =   0 and   x n + 1   =   s   stationed at the endpoints of   B . Since connectivity deals with inter-robot distances, it helps to think of them directly rather than in terms of   x . Define the   i -th   slack s i   to be the distance from   x i   to   x i + 1 , and the   slack vector   s s 1: n + 1   : =   x 1: n + 1   −   x 0: n   to be the vector of all slacks. Analogous to the rv’s associated with positions, define the rv’s   S i   and the vector   S . We may think of   s   as a point in   B n + 1 . Now we introduce the notion of connectivity by defining a   communication range d   ∈   [ 0 ,   s ] . Two robots   x i   and   x   j   are connected iff   | x i   −   x   j | ≤   d . We model connectivity by a graph   G   ( x ) , whose nodes are   x i   (or   x i ) , and edges are formed by pairs of connected robots. Since each node is a geometric position,   G   ( X )   forms a   Geometric Graph . We define a position vector   x  to be connected iff   G   ( x )   has a path from   x 0   to   x n + 1 , and disconnected otherwise. When robot positions are chosen randomly, this graph becomes a Random Geometric Graph (RGG) [ 27 ]. We will now make the transition from point robots to   R -sized ones on the boundary. Define the   position   of a robot as that of its left end, so that robot   R i   located at   x i   occupies the interval  I 0 i   = [ x i ,   x i   +   R ] . The support of an attached robot position is   B ′   = [ 0 ,   s   −   R ]   (or a subset of it), so that the robot does not fall of the boundary endpoint   x   =   s . We define the position vector   x   of   n   robots to be   feasible   if there are no interrobot collisions, i.e. each slack   s i   is at least   R . When a robot attaches to the boundary, it selects an   interval   of the boundary of length   R   lying completely within the boundary. We will generally be able to abstract intervals into points,  2
and consequently think of a SCS as the choice of multiple random   points   on the boundary. Formally, a SCS is a   one-dimensional Point Process (PP)   [ 12 ] realized on the boundary. A special case of a PP involves robots attaching to a boundary at predefined locations. We will be interested chiefly in the   Poisson Point Process (PPP)   in which robots attach independently to the boundary, and its generalizations such as the   Markov Process   [ 12 ]. The independent attachments in PPPs make them easy to analyze; on the other hand, interactions between robots are harder to handle and require generalizations of PPPs. To simplify our analysis, we will first work with point robots in   Sec.3   which have   ∆   =   0, and consequently preclude inter-robot collisions.   Point robots are an idealization of   finite  robots which have nonzero diameter; they also provide useful approximations to the behavior of finite robots when   ∆   ≪   s . We will compute the   connectivity properties   of each SCS that we address, which include the probability of saturation, the distribution of distances to the nearest neighbor, and the joint and marginal pdfs of robot positions and inter-robot distances.  1.4. Problem Statement.   We require the robots to perform the following tasks: P ROBLEM   1.  1. Form a connected network at the white endpoint of   B . 2. Attach to the boundary, forming a connected network, or cover as much of the boundary as possible. 3. Efficiently the list of positions taken up by the team on   B  4. Be able to update the map efficiently as robots join and leave the boundary 5. Determine at any point of time the network graph, including the following proper- ties: coverage length, number of redundant robots (i.e. those that can be removed without loss of coverage).  P ROBLEM   2.   Compute the network properties for a random attachment scenario.  1.5. Related Work. 1.5.1. Control of Multi-Robot Systems.   Previous work on decentralized multi-robot boundary coverage has focused on controlling robots to converge to uniform or arbitrary formations on a circle [ 32 ]. In contrast to this work, we consider cases where there is inherent and/or programmed stochasticity in the robots’ motion, and our objective is to achieve robot configurations with   target statistical properties .   We assume that every robot has minimal capabilities: no global position information, and sensing or communication only within a small radius. Task allocation strategies that are suitable for such scenarios often derive robot control policies from a continuum model of the swarm population dynamics, or   macroscopic model , in order to enable the control policies to scale with the swarm size. Various stochastic approaches to robot task allocation have focused on optimizing the task-switching rates of such macroscopic models [ 2 ,   4 ,   21 ,   22 ,   26 ]. Macroscopic models have also been applied to problems of robotic assembly of products, as well as robotic self-assembly [ 9 ,   17 ,   23 ,   25 ].  1.5.2. Wireless Networks.   Since our interest lies in getting a robot team to form a connected Wi-fi network around a boundary, we will dwell on data structures for routing in Mobile Ad Hoc Networks ( MANETs ) [ 15 ]. However, our main focus lies in analyzing the properties of the Geometric Graph (GG) formed by the multi-robot network. Our probabilistic analysis borrows heavily from the formalism of   Poisson Point Processes (PPP)   [ 28 ], a class  3
of spatial stochastic processes in which each robot takes positions independently of others. The network induced by a PPP is a   Random Geometric Graph   ( RGG ) [ 28 ]. When attachments are required to be   collison-free ), i.e. have no colliding pairs of robots, they are characterized by a Matern hard core process ( HCP ). These spatial processes and their resulting RGGs have been extensively used in the wireless communication literature [ 12 ].  1.5.3. Computational Geometry.   All our results that compute   p con ( G ) , the connectiv- ity probability of   G   , involve the order statistical properties of the pdf governing the attach- ment of individual robots, called the   parent pdfs , or parents for short [ 5 ]. The order statistics of a collection of random variables   X 1: n   are generated by sorting them in nondecreasing or- der to get their permutation   X . The order statistics of uniform iid parents are the easiest to analyze; moreover,nonuniform iid parents of other forms may be readily converted to their uniform counterparts using the   probability integral transform   [ 5 ]. We use the computations in [ 8 ] to derive a pseudo- P   lower bound for computing   p con ( G   )   for uniform parents in   ?? . Further, we demonstrate that determining   p con ( G   )   for arbitrary iid pdfs is # PH , by reduction from a result in [ 7 ,   8 ]. The analogous computation of   p con ( G   )   for independent, non-identical (inid) pdfs is consider- ably more complicated, and uses the   Bapat-Beg theorem   [ 10 ]. This computation is governed by a [ ? ]. We show in   Sec.5.3   by a reduction from the boolean permanent problem [ ? ] that computing   p con   is # PH . Our results for the Stochastic Coverage Scheme (SCS) involving Renyi parking stems from the work of Renyi [ 29 ] and Dvoretzky et al. [ 6 ]. The Renyi Parking Problem (RPP) defined in   Sec.4   has been extensively studied in the physics literature under the name   Random Se- quential Adsorption (RSA) , the process by which molecules get adsorbed onto a substrate surface [ 30 ,   31 ].   The delay differential equation that governs the mean number of parked cars is extensively analyzed in [ 6 ,   30 ]; moreover, [ 30 ] computes the asymptotic properties of an interval tree that stores the occupied subintervals of the parking lot. To our knowledge, however, there has been no analysis of the spatial probability density functions (pdfs) gen- erated by the RPP. We derive an algorithm for computing this pdf using results from order statistics [ 5 ].  2. Deterministic Coverage Strategy (DCS) for   B .   We will first provide a DCS for a group of finite-sized robots to form a connected network with uniform inter-robot spacing along a boundary   B . This algorithm starts with a simple procedure, detailed in   Algorithm 1  below, that is guaranteed to make all robots join the same network. Assuming there are no faults,   Algorithm 1   will terminate with all robots joining the network created by robot   R 1 . In this MANET,   every   node acts as a router. Once the robot team forms a connected network after the execution of   Algorithm 1 , the ID of every robot in the network is determined by flooding. This set of IDs is stored in the routing table of every robot. Subsequently, one robot (say,   R 1 ) leaves the network to determine the length   s   of the boundary using its odometry, and then rejoins the network by following the boundary back to its white endpoint. The maximum number of robots that can possibly attach to   B   is  n max   =   ⌊   s   −   R  R   ⌋ . (2.1) The minimum number of robots required to ensure connectivity is  n min   =   ⌊   s  d   ⌋ . (2.2)  4
Algorithm 1  1:   procedure   F ORM A CONNECTED NETWORK ( i ,   n )  2:   state   ←   EXPLORE  3:   while   Black Boundary not seen   do  4:   Execute Lawnmower walk  5:   while   White endpoint not seen   do  6:   Traverse   B  7:   if   id   =   1   then  8:   Create Wifi network  9:   else  10:   while   network not created   do  11:   Wait  12:   Join Wifi network  13:   state   ←   CONNECTED  Based on these limits, the connectivity of the robot network falls into three categories:  Case 1 : If   n   <   n min , then at most   nd   of the boundary can be covered.  Case 2 : If   n   ∈   [ n min ,   n max ] , then all robots can be accommodated, and can cover the boundary entirely.  Case 3 : If   n   >   n max , then   n   −   n max   robots have to be dropped from coverage. In this case, the first   n max   robots attach to the boundary, and the remaining are dropped. Robots subsequently take up positions that are spaced   d   apart, so that   x i   = ( i   −   1 ) d , using their odometry, with the white endpoint being considered   x 0   =   0. Afterwards, the robots can coordinate to attach to, or detach from,   B . This DCS can be easily adapted to any SCS as follows. Instead of taking up equidistant positions, the robot team collectively samples from a joint pdf of their positions on   B , and attaches to these positions in order. The initial step of forming a connected network makes it easy to execute either coverage scheme.  2.1. Determining properties of   G   .   The robots can use the   Optimized Link State Rout- ing (OLSR)   protocol [ 13 ,   14 ] to determine the connectivity, coverage length, and number of edges of   G   at any instant. OLSR is a proactive, table-driven routing protocol, each of whose nodes maintains a table of 1-hop neighbors, which are found by flooding   HELLO   messages through the network. When a new node joins or an existing one leaves the network, a set of   TC   (Topology Control) messages are initiated by the neighbors of this node, flooding the network with updated routing tables. Robots can determine the properties of the network as follows: 1.   Decide network connectivity : Every robot floods the network with a message con- sisting of its id and its position. The flooding of the network is deemed to stop after a timeout  τ , known to all robots, at which time every robot compiles a table of robot positions and id’s.   From this table, the leftmost and rightmost robot IDs,   x 1   and  x n , are identified. If   x i   ≤   d   and   x n   ≥   s   −   d , then the entire network is connected. Otherwise, each robot deems the network to be disconnected as a whole. 2.   Number of Connected Components:   Each robot can determine its own connected component from the routing table. If the connected component of any robot covers both end-points of   B , then the network as a whole is connected. Otherwise, after  5
a timeout period  τ   that is known to all robots, one robot (say   R 1 ) detaches and tra- verses the boundary, querying the nearest robots about their connected components. After one full traversal of   B ,   R 1   computes the total number of connected compo- nents and updates. It subsequently updates other robots of this number in a second traversal of   B . 3.   Number of edges:   This is a variant of the approach for computing the number of connected components. Each connected component may determine the number of edges in it independently of others. As before,   R 1   detaches and traverses   B   to query the number of edges in each connected component, which is then broadcast to each robot.  2.2. Creating and updating a list of robot positions.   Each robot   R i   in the network maintains data about robot positions along the boundary in the form of an   interval tree   [ 1 ]. If this position data is too large to fit into the memory of a robot, it will keep track only of its   m  nearest neighbors, where the size   m   is the maximum allowable size of the tree. The interval tree handles insertions, deletions and search queries in   O ( log   m )   time. An incoming robot that wishes to attach to   B , say   R n + 1 , will approach   B   and send a broad- cast query to the network to determine the locations of slacks that are large enough for it to attach. A subset of the attached robots will then respond to   R n + 1   with a list of slacks where it may attach. Subsequently,   R n + 1   attaches and broadcasts its position to its neighbors, who in turn update their position data. Likewise, an outgoing robot   R 1   notifies its neighbors of its impending detachment. The neighbors recompute the resulting slacks, making note of any disconnected slacks introduced by the detachment of   R 1 . They subsequently clear   R 1 for detachment, following which   R 1   detaches.  2.3. Discussion.   This section has presented only a high level view of the BC protocol. We have deliberately processor failures, asynchrony, and anonymity for the sake of simplicity. A detailed discussion of these issues would distract from our objective of analyzing   G   .  3. IID Coverage by Homogeneous Point Robots.   In this section, we consider an SCS driven by a Poisson Point Processes (PPP), in which every robot attaches independently to   B , following the same spatial parent pdf. In other words,   X   consists of iid random variables, and defines a PPP on   B . Specifically, suppose that the parent pdf and cdf are   p   f   ( x )   and   p F ( x )  respectively, both supported on   B . Then the number of points N falling on a subinterval   [ a ,   b ]  of   B   is a Poisson random variable with underlying pdf   p   f   ( x ) : N ( a ,   b )   ∼   Poi (  λ   )   where  λ   = p   F ( b )   − p   F ( a ) . (3.1) We derive connectivity results for this SCS for a fixed team of   n   robots and then generalize these results to a case of dynamic attachment and detachment. Our primary parameters of interest are the connectivity properties of   G   ( X ) , namely the probability   p con   of connectivity, the expected degree of a vertex, and the number of clusters, all of which . Subsequently, we determine the   spatial pdfs   of   X   and   S , both for connected and unconnected components of   G   . We then apply these results to analyze the   temporal properties , such as recurrence times, of dynamic scenarios in which robots attach and detach probabilistically. [ 18 ,   19 ].  3.1. Geometric interpretation of connectivity.   We interpret   x   and   s   as points in   R n  and   R n + 1 , respectively. The entries of   x   are nondecreasing, and thereby define the   position  6
simplex   [ 19 ]  P   =   { x 1: n   : for all   i   : 1   ≤   i   ≤   n ,   we have that 0   ≤   x i   ≤   x i + 1   ≤   s } . (3.2) Likewise, all valid slack vectors, i.e. those that arise from a robot configuration on   B , have entries whose sum is the boundary length   s . Geometrically,   s   defines a point on a simplex   S  that we call the   slack simplex   [ 18 ], given by  S   : =   { s   :   1 T   s   =   s ,   and   0   ≤   s   ≤   s 1 }   =   s   ·   ∆ n , (3.3) where  ∆ n   : =   { s   :   1 T   s   =   1 ,   and   0   ≤   s   ≤   1 } (3.4) is the canonical simplex in   R n . The vertices of   S   are  V ( S   ) =   s   ·   I n + 1   =   s   ·   [   ˆ e 1   . . .   ˆ e n + 1  ]   , (3.5) where ˆ e i   is the unit vector along the   i -th axis.   Eq.(3.3)   expresses   S   as a degenerate simplex, with Lebesgue measure zero in   R n + 1 . For our computations, we will need to express   S   in full-dimensional form as  S   =   { s 1: n   ∈   R n   :   0 T   ≤   s ,   and   1 T   s   ≤   s } , (3.6) by dropping the last slack   s n + 1 , which is determined by its predecessors. Observe that all connected configurations, regardless of whether they are valid, fall within the hypercube  H   : =   { 0   ≤   s   ≤   d 1 T   }   =   d   ·   C n , (3.7) where   C n   is the unit hypercube   [ 0 ,   1 ] n . A valid slack vector has to lie in the intersection   S   ∩   H   to represent a connected con- figuration.   Define the   connected region   as   F   =   S   ∩   H   and the   disconnected region   as  U   : =   S   \   F   . We show in [ 18 ] that   d   falls into three ranges,  d   ∈        [ 0 ,   s  n + 1   ] ,   for which   F   =   ∅   and   p con   =   0;  (   s  n + 1   ,   1 ) ,   for which   F   (   S   and   p con   ∈   ( 0 ,   1 ) ;  [ 1 ,   ∞ ) ,   for which   F   =   S   and   p con   =   1 .  (3.8) We may express   F   as  F   =   { s 1: n   ∈   S   :   s   −   d   ≤   1 T   s 1: n   and   s   ≤   d 1 T   } . (3.9) The parent   p   f   generates the joint pdf [ 5 ]  f X ( x ) =   n !   ∏  1 ≤ i ≤ n  f   ( x i ) I P   . (3.10) over the the position simplex, where   I   denotes the   indicator function   over the region in its subscript. This pdf is called the Janossy pdf [ 12 ] of the PPP. Changing the argument from   x  to   s   gives us  f S ( s 1: n ) =   n !   ∏  1 ≤ i ≤ n  f   (  i  ∑  j = 1  s   j   ) 1 S   . (3.11)  7
We will compute the properties of   G   in the coming subsections, starting with   p con . The for- mula for finding   p con   provides us with a template for partitioning   S   into regions that are amenable to computing the following properties of   G   : the number of connected components of   G   , the coverage induced by   G   , and the edge count of   G   . While these quantities are nontriv- ial to compute for RGGs of arbitrary dimension [ 27 ], there exist straightforward, if tedious, algorithms to compute them for a single dimension. All these algorithms essentially involve computing the ratio of integrals of the joint pdf  ̃ s   over a subset of   S   .  3.2. Probability of connectivity.   The probability of connectivity   p con   is the ratio of the volume of the joint pdf lying over   F   to that over   S   :  p con   : =   Leb ( S ,   F   )  Leb ( S ,   S   ) =  ∫  F   f S ( s ) d s  ∫  S   f S ( s ) d s   . (3.12) where Leb ( S ,   S   )   computes the Lebesgue measure of the joint pdf of   S   over   S   . The denom- inator is relatively easy to evaluate analytically using barycentric coordinates [ 11 ], while the integral over   F   is harder to compute, since there is no obvious way to decompose it into sim- plices. A naive algorithm that triangulates   F   into simplices will take a long time in practice when   n   is large. Instead, we may write Leb ( S ,   F   ) =   Leb ( S ,   S   )   −   Leb ( S ,   U   ) , decompose   U  into simplices rather than   F   [ 19 ] , and finally compute   p con   =   1   −   Leb ( S , U   )  Leb ( S , S   )   . This decomposition of   U   will result in   overlapping   simplices, whose measures we can com- bine using the combinatorial approach described in [ 19 ].  U   =   ⋃  v ∈{ 0 , 1 } n \{ 0 }  U   ( v ) , (3.13) where   U   ( v )   forms a simplex of side   ( s   −   d 1 T   v ) , with the vertices  V ( U   ( v )) = ( s   −   d 1 T   v ) I n + 1   +   v . (3.14) This expression is nonnegative when   s   ≥   d 1 T   v , so that only those vertices with at most   n min   =  ⌊   s  d   ⌋   d ’s in them need be considered. The value   n min   is the minimum number of robots required for connectivity, as well as the maximum possible number of disconnected slacks. We call the simplex   U   ( v )   the   compatible simplex   of   v . Compatible simplices overlap, so the sum of their measures exceeds that of   U   . We first decompose   U   using the inclusion-exclusion principle (IEP) as:  U   =   ⋃  odd   v  U   ( v )   \   ⋃  even   v  U   ( v ) (3.15) where the (even or odd) parity of   v   is that of its number of 1-bits. We immediately have Leb ( S ,   U   ) =   ∑  v ∈{ 0 , 1 } n + 1  ( − 1 ) 1 T   v Leb ( S ,   U   ( v )) . (3.16) Our remaining computations will rely heavily on the decomposition of   S   into   U   ( v ) .  8
3.3. Number of Components.   A slack vector   s   has a single connected component iff it is connected, i.e if   s   ∈   F   . Each unsaturated slack in   s   inserts a new connected component into   G   . Define the component counting function cmp :   S   7   →   N   with cmp ( s ) =  n + 1  ∑  i  {  1 if   s i   ≤   d  0 otherwise .  (3.17) where   N   =   { 0 ,   1 ,   2 , . . . } . By definition, we have cmp   =   n   +   1   −   1 T   v   identically over   U   ( v ) . We may then compute the expectation of cmp over   S   by writing   S   =   U   ∪   F   , and consequently get  E ( cmp ) =   Leb ( cmp ,   S   ) =   ∑  v ∈{ 0 , 1 } n + 1 : 1 T   v ≤ n min  ( − 1 ) 1 T   v  ∫  U   ( v )  ( n   +   1   −   1 T   v )   f S ( s ) d s . (3.18)  3.4. Coverage Length.   To determine the length of the   B   covered by   s , we will intro- duce the   coverage function   cov ( s ) . If   s   is connected, then its coverage length cov ( s )   is the boundary length   s . If   s   has a disconnected slack   s i , a length of   s i   −   d   is left without coverage. This motivates us to define cov by cov :   S   7   →   R   with cov ( s ) =   s   −  n + 1  ∑  i  max ( s i   −   d ,   0 ) . (3.19) Computing   E ( cov )   over   S   does not get simplified by the decomposition   S   : =   U   ∪   F   , for cov is non-constant over   U   . A straightforward integration gives us  E ( cov ) =   Leb ( cov   ·   S ,   S   ) =   s   ·   Leb ( S ,   S   )   −  n + 1  ∑  i = 1  max ( 0 ,   s i   −   d )   f S ( s ) d s . (3.20)  3.5. Number of edges of   G   .   We will define the edge counting function edg ( . )   over positions rather than slacks. Given the position vector   x , there exists an edge between   x i   and  x   j   iff   x   j   −   x i   ≤   d . Accordingly, we have edg :   P   7   →   N ,   with edg ( x )   : =  n − 1  ∑  i = 1  n  ∑  j = i + 1  1   −   max ( x   j   −   x i   −   d ,   0 ) (3.21) with   E ( edg )   being the integral of   Eq.(3.21)   over   P :  E ( edg ) =   Leb ( X ,   P )   −  ∫  P   ∑  i ,   j :1 ≤ i <   j ≤ n  max ( x   j   −   x i )   f X ( x ) d x . (3.22)  3.6. Dynamic coverage with iid attachment.   Now we will examine a strategy in which the robot team dynamically attaches and detaches from the boundary, with their spatial attach- ment pdfs being iid on   B .  9
3.6.1. Dynamic attachment.   We first consider the case in which robots attach to the boundary without detaching. One robot position is chosen at every time step using the parent pdf   p   f   until connectivity is achieved. We compute the expected time until connectivity, or the expected   stopping time   of the SCS. To determine the stopping time, we consider the sequence  ( p i ) i ∈ N , where   p i   is the probability of connectivity with   i   robots. Irrespective of the parent pdf   p   f   , having more robots on   B   leads to a greater probability of connectivity. Consequently, the sequence   ( p i )   is monotonically increasing on the support   [ n min ,   ∞ )   and tends to unity as   i  grows without bound. We also know that   p i : i ≤ n min   =   0. Consequently, the attachment process will terminate (resp. fail to terminate) at   i   ≥   n min   robots with probability   p i   (resp. 1   −   p i ). The probability of connectivity being attained at   i   robots is: τ i   =  {  0   for 1   ≤   i   <   n min  ( 1   −   p i − 1 ) p i   for   i   ≥   n min  (3.23) Thus,  τ i   is a generalized geometric random variable whose probability of success in a trial is distinct from that in its previous one. The expected stopping time is  E (  τ ) =  ∞  ∑  i = n min  i  τ i . (3.24) Since   p i   >   p n min   for   i   >   n min , we expect quicker connectivity than that of a geometric random variable whose parameter is   p n min   E  τ   ≤   1  p n min  .  3.6.2. Stopping time of connectivity for Uniform parent.   The uniform parent has the special property that   S   is jointly uniform over   S   , with each slack being identically distributed (though not iid) as scaled exponentials of the form   s   ·   Exp ( 1 ) . Further, the   order statistics   of the slacks, represented by the vector   s , formed by sorting   s   in increasing order, obey the relations [ 5 ]:  E ( S i ) =   s  n   +   1  n + 1  ∑  j = 1  1  j   =   s  n   +   1 ( H n + 1   −   H i ) (3.25)  V   ( S i ) =  n + 1  ∑  j = i  1  j 2  (3.26) where   H n   denotes the harmonic numbers.   The longest slack   S n + 1   has the expected value  sH n + 1  n + 1   . To have   s n + 1   ≤   d , we need   H n + 1  n + 1   ≤   d  s   , which may be solved numerically to get the expected hitting time of   F   . We may also estimate   n   if   n   is large by approximating   H n   with log   n , providing log ( n   +   1 )  n   +   1   ≤   d  s   = ⇒   n   =   exp ( − W   (   d  s   ))   −   1 , (3.27) where   W   is the   Lambert W function .  3.6.3. Dynamic attachment and detachment.   We now extend the results in   Sec.3.6  to a scenario in which we require robots to strike a balance between forming a connected network on the boundary and exploring the surrounding environment of the boundary. For- mally, we are given that at every time instant   t   ∈   R + , a robot may be either attached to  10
the load or detached from it; in other words, the robot has a temporal state alphabet   Σ   : =  { A   ( attached ) ,   D   ( detached ) } . P ROBLEM   3.   Design the rates of switching between states, with a guarantee on the expected amount of time that the boundary will have a connected network.  To analyze the behavior of the robots, we introduce the temporal state N ( t ) =   [ N A ( t )   N D ( t ) ] T   , whose entries denote the number of robots in states   A   and   D , respectively. We assume that the total number of robots is conserved, which implies that (3.28)   N A ( t ) +   N D ( t ) =   N A ( 0 ) +   N D ( 0 ) .  Now we suppose that robots change state per the chemical reactions  A   r AD  − − →   D   and   D   r DA  − − →   A (3.29) where   r i j , the reaction rate constant, is the probability per unit time of a robot in state   i   to switch to state   j . The populations of robots in both states evolve over time as d  d t   N ( t ) =  [ − r AD   r DA  r AD   − r DA  ]  N ( t ) . (3.30) At equilibrium,   d  d t   N ( t ) =   0 , and so   Eq.(3.30)   yields  N A ∗  N D ∗   =   r DA  r AD  . (3.31) We solve for   N A ∗   and   N D ∗   using   Eq.(3.28)   and   Eq.(3.31) .  4. Uniform Coverage by Homogeneous Finite Robots.   We now consider SCS with  finite robots , each of which has a nonzero diameter   R . Unlike the case of point robots, the  maximum number   of attached robots is finite and given by  n max   =   ⌊   s  R   ⌋ . (4.1) Collision-free positions are a realization of a   Matern hard-core PP   [ 12 ], which prohibits its points from lying within a threshold distance of each other.   The valid range for   n   is  [ n min ,   n max ] . When   d   ≤   R , every feasible configuration becomes a saturated one, causing   n min  to coincide with   n max . The case   d   =   R   is of special interest to us, since it is an instance of Renyi’s Parking Problem. P ROBLEM   4.   Renyi’s Parking Problem [ 6 ,   30 ] Cars of unit length park uniformly randomly on a segment of length s, avoiding collisions, until no parking space is available for the next car. Analyze the pmf of the final number of parked cars,   N .  The mean number of parked cars,   E N, obeys a delay integral equation with the asymptotic solution lim  s → ∞   E N   =   n pc   ·   s   ≈   0 . 748 s . (4.2) where   n pc   is Renyi’s parking constant [ 29 ]. This result implies that we expect 75% of the segment to be occupied by cars at the point where there is no more room to accommodate another car. An exact solution for   E N leads to an intractable   ⌊ s ⌋ -dimensional integral [ 24 ]. Our SCS with fixed   n   and uniformly random attachments is a special case of Renyi’s Parking Problem in which N is trivial to compute. However, to our knowledge, there has been no analysis of the spatial pdfs that are generated by the parked cars in this problem, which we provide in   Sec.4.1 .  11
4.1. Connectivity of Collision-Free Parking.   We now formulate the CF equivalent of the point-robot attachment in   Sec.3 .   Define the   position   of a robot as that of its left end, so that robot   R i   located at   x i   occupies the interval   [ x i ,   x i   +   R ] . The support of all attached robot positions is   B ′   = [ 0 ,   s   −   R ] , which ensures that no robot extends beyond the boundary endpoint   x   =   s . We introduce two artificial robots at   x 0   =   − R   and   x n + 1   =   s . Define   x   to be  collison-free (CF)   iff (4.3)   0   ≤   x 0 ,   x n   ≤   s   −   R ,   and   x i   −   x i − 1   ≥   R ,   for   i   =   1   . . .   n ,  and define   P CF   to be the set of CF position vectors. Likewise define the CF subset of   S   and the resulting favorable region by  S CF   : =   { s   ∈   S   :   R   ·   1 T   ≤   s } (4.4)  F CF   : =   S CF   ∩   H   =   { s   ∈   S   :   R   ·   1 T   ≤   s   ≤   d   ·   1 T   } . (4.5) Geometrically,   S CF   is a simplex with the hypercuboids   0   ≤   s i   ≤   R   removed. Reasoning as in   Sec.3 , we have   p con ( G   ) =   Vol ( F CF ) / Vol ( S CF ) ; however, we are unable to simplify this formula further as we did there. The lack of a simplifying expression for   p con   means that the computation of   p con ( G   )   has to involve the triangulation of   F CF   into simplices, a time- consuming operation that we explicitly avoided in   Eq.(3.13) . Likewise, expressions for the order statistics and slacks of CF positions are obtained by integrating the uniform joint pdf over   S CF   instead of   S   , as do the formulae for the properties of   G   .  5. Complexity Results of SCS. 5.1. Computing   p con   for uniform iid parents.   We now investigate the complexity of exactly computing the integrals in   Eq.(3.16) . We begin with a pseudo- P   lower bound for com- puting Vol ( F   ) , and consequently   PCON   for the uniform parent. We will then discuss lower bounds for non-uniform parents. Define the complexity theoretic problem   PCON (   f   ,   s ,   d ,   n )   7   →  p con , with Input: Parameters of SCS : encoding of   p   f   , ;   s ,   d   ∈   Q +   ;   n   ∈   N  Output: Probability of connectivity   p con   ∈   Q +  Rational inputs and outputs are specified as exact reduced fractions; for example   s   is input as the pair   ( num ( s ) ,   den ( s )) . Let   PCON ( U )   denote that subproblem of   PCON   over a uniform SCS. T HEOREM   5.1.   PCON ( U )   can be solved in   Ω ( n )   and O ( n   log   n )   time.  Applying   Eq.(3.16)   gives us [ 18 ] Vol ( S   ) =   s n   · √ n   +   1  n !   , (5.1) Vol ( U   ) =  n min  ∑  k = 1  ( − 1 ) k − 1  ( n   +   1  k  )   ( s   −   kd ) n √ n   +   1  n !   , (5.2)  PCON   =   Vol ( F   )  Vol ( S   ) =   1   −  n min  ∑  k = 1  ( − 1 ) k − 1  ( n   +   1  k  )( 1   −   kd  s  ) n .  Proof .   Upper bound:   Eq.(5.1)   is a possible solution for   PCON ( U ) ; therefore, its worst-case running time forms an upper bound for   PCON ( U ) .   Eq.(5.1)   runs in   O ( n min   log   n )   time; its  12
worst-case instances, which have   n   >   n min   take   O ( n   log   n )   time, which forms an upper bound for any solution to   PCON . Note that   Eq.(5.1)   forms a pseudo- P   algorithm for   PCON .  Lower bound:   Consider   PCON ( U )   instances with   s   =   4  3   d , for which  PCON   =   1   −   ( n   +   1 )   ·   1  4 n   ≈   1   −   n  4 n  (5.3) The input size for these instances is   O ( log   n ) , but the output size is exponential in the input size, implying an   Ω ( n )   lower bound for any algorithm for   PCON ( U ) .   The upper bound of   O ( n   log   n )   is off from the lower bound   Ω ( n )   only by a polynomial in the input size of  PCON ( U ) , implying that algorithms for   PCON   consume more time in outputting the solution rather than computing it. The lower bound is an exponential function of the input size, hence  PCON ( U )   ∈   # EXP .  Time complexity of computing   Vol ( F   ) : The   √ n   in the formula for Vol ( F   )   makes it impos- sible to provide a bounded decimal expansion to Vol ( F   ) , hence the complexity of writing down Vol ( F   )   is   infinite , except when   n   is a square. Remedying this unbounded expansion requires us to compute   Vol ( F   )   ·   n ! √ n + 1   , for which the same bounds as   PCON ( U )   apply. The same bounds apply to Vol ( U   )   ·   n ! √ n + 1   .  5.2. Generalized Simplex Hypercube intersection.   In the coming sections, we will demonstrate that our problems are # PH   by reduction from the   VHSP   problem. L EMMA   5.2.   Define the problem   VHSP : Input: Parameters   a 1: n ,   b of the halfspace   T   : =   { s   ∈   R n   :   a T   s 1: n   ≤   b } , with   a   and b are positive rationals Output: Volume of intersection of   T   with the unit hypercube   C   : = [ 0 ,   1 ] n  The solution to   VHSP   given by  Vol ( T   ∩   C   ) =   n !  n  ∏  i = 1  ∑  v ∈ [ 0 , 1 ] n  ( − 1 ) 1 T   v   max (( b   −   a T   s ) n ,   0 ) . (5.4)  is   # PH . Equivalently, it is   # PH   to find the probability that a random point in   C   satisfies a single linear inequality.  It will be useful to redefine   VHSP   as an intersection between a half-space with unit coef- ficients and a generic hypercuboid. Introduce the primed variables   s ′  i   : =   a i s i , and note that  VHSP   asks for Vol ( T   ′   ∪   C   ′ ) , where  T   ′   : =   { s ′   ∈   R n   :   1 T   s ′   ≤   b }   and (5.5)  C   ′   : =   ∏ [ 0 ,   a i ] . (5.6)  5.2.1. Nonuniform iid parents.   We will now give an example of a nonuniform parent whose   p con   is # PH   to compute. For this purpose, define a   k -piecewise uniform ( k -PWU) over a finite support   [ 0 ,   L ]   as follows. Partition the support into   k   nonempty subintervals as  [ 0 ,   L ]   : = [ 0 ,   L 1 ]   ∪   [ L 1 ,   L 2 ]   . . .   ∪   [ L k ,   s ] . (5.7)  13
On the   i -th subinterval,   f   ( x )   is defined to be the constant   p i   ∈   [ 0 ,   1 ] , which are chosen to satisfy   ∑   p i ( L i   −   L i − 1 ) =   1, and consequently   f   is a pdf on   B . T HEOREM   5.3.   PCON ( n U )   is   # PH . Proof . Given the   VHSP   instance with the dimension   n   +   1, having the hypercuboid   C   ′   : =  ∏ 1 ≤ i ≤ n + 1 [ 0 ,   l i ]   and the half-space sum   b .   Let   L   : =   ∑   l i .   Define the equivalent instance of  PCON   to have the parameters  s   : =   b  L   ,   d   : =   1   ,   and   p   f   : =   l i  L   if   x   ∈   [ i ,   i   +   1 ] (5.8) Define   Y i   ∼ p   F ( X i )   to be the probability integral transform of   X i . From the definition of   Y i , we have that   P ( x i   ∈   [ i ,   i   +   1 ]) =   P ( y i   ∈   [ 0 ,   l i  L   )] . It follows that if   X   is connected, then   Y   lies within   C   ′ . Moreover,   Y   is jointly uniform on the half-space  T   ′   =   { y   ∈   R n   :   y   ≥   0 and   ∑ y i   ≤   s } . (5.9) Thus,   p con   =   Vol ( T   ′   ∪   C   ′ ) / Vol ( C   ′ ) , from which the solution to   VHSP   can be computed in  P   time.  5.2.2. Extensions of   Theorem 5.3 .   We may extend   Theorem 5.3   to more general par- ents satisfying the constraints that:  d ∫  ( i − 1 ) d p   f   ( x ) dx   =   l i ,   for all   i   =   1 , . . . ,   n ,   where   l i   ≥   0 and   ∑ l i   =   1 . (5.10) Since   Eq.(5.10)   provides us with   n   constraint equations,   p   f   needs to have at least   n   param- eters to fit them, e.g. polynomials of degree   n , with arbitrary coefficients. More generally, if   f 1 , . . . ,   f n   are arbitrary pdfs with unit supports, each having at least one parameter, their mixture  p   f   ( x ) =   f i ( x )   if   x   ∈   [ i   −   1 ,   i ) I B   ,   where   B   = [ 0 ,   n   +   1 ] (5.11) may be fit to obey   Eq.(5.10) . Consequently, computing   PCON   for this mixture is # PH . On the other hand, problems with a constant number of parameters fail to admit such a reduc- tion analogous to   Theorem 5.3 , fail to be # PH   even though they may not exhibit an explicit formula for # PH .   For example, we do not know a short formula for computing   p con   for Renyi parking, as mentioned in   Sec.4.1 . Nonetheless, the problem lacks sufficiently many free coefficients to admit a reduction, and consequently is not # PH . Likewise is the case of nonuniform parents such as Beta, Triangular, and clipped Gaussian pdfs on   B .  5.2.3. Robots with heterogeneous connectivity thresholds.   We now consider a   Het- erogeneous   robot team whose Wifi adapters have different transmission power, so that   R i  has connectivity threshold   d i . We call   R i   weaker   (resp.   stronger ) than   R   j   iff   d i   <   d   j   (resp.  d i   >   d   j ) . If   d i   =   d   j   we say that the two robots have equal power. Then the robot network is represented by the digraph   G   , whose directed edges are of the form   i   →   j   iff   R i   can transmit to   R   j . In general, edges are not bidirectional, since a weaker robot will not sense a stronger  14
one, even though the converse holds true. Suppose without losing generality that the   d i ’s form a strictly positive, non-decreasing sequence. Consider a configuration in which the robots are arranged from left to right in increasing order of their index. A connected configuration satisfies the   n   +   1 constraints  s 2 i − 1 ,   s 2 i   ≤   d i   for all   i   : 1 , . . . ,   ⌊ n / 2 ⌋ ,   and in addition (5.12)  s n + 1   ≤   d n / 2   if   n   is even .  In general, a connected configuration will have two distinct slacks   s i 1 ,   s i 2   each less than   d i . Further, the connected region is the intersection of   S   with the union of hypercuboids, each of which has two dimensions equal to   d i , and an extra dimension equal to   d n / 2   if   n   is even. Define   H   to be:  H   =   ⋃  ∏ [ 0 ,   a i ] ,   where the   a i   are a permutation of the   d i . (5.13) The number of hypercuboids in   H   is at most   n !, which is the case when all   d i ’s are distinct. We will assume that the   d i ’s are distinct unless mentioned otherwise. Since   H   is nonconvex in general, so is   F   =   H   ∩   S   . When   s   is sufficiently large that all   n   robots are required to connect it,   F   becomes the disjoint union of   n ! pieces, each of which is the intersection of   S  with one of the component hypercuboids of   H   . Then we have that Vol ( F   ) =   n !Vol ( S   ∩ C   ′ ) , where   C   ′   is the hypercube with dimensions   d 1   ×   d 1   . . .   ×   d n   ×   d n . T HEOREM   5.4.   PCON   is   # PH   for heterogeneous connectivity. Proof . Consider the odd-numbered instance of   VHSP   in dimension 2 n   +   1, with hypercuboid dimensions   l 1 ,   l 1 , . . . ,   l n ,   l n ,   l n + 1   and slack sum   b . Assume that the   l i ’s are distinct. It is clear that this instance of   VHSP   is at least as hard as its counterpart in   R n   with dimensions   l 1 , . . . ,   l n , and thus is # PH . The equivalent instance of   s   =   b  L   +   1 and   ( d i ) 1 ≤ i ≤ n   =   l i / L , where   L   =   ∑   l i  as before. The solution of   VHSP   is now   n ! p con Vol ( C   ′ ) , which is computable in   P   time from the solution to   PCON .  It is immediately clear that finding Vol ( F   )   and Vol ( U   )   is # PH   for heterogeneous connec- tivity.   With homogeneous robots,   F   was more symmetric compared to its heterogeneous counterpart.   Exploiting this symmetry led to relatively short formulae for   PCON   and the like.   On the other hand a heterogeneous swarm is sufficiently diverse that its connected region be an arbitrary half-space. We pay for this expressiveness by making the connectiv- ity problems harder. Computing   p con   has a Fully Polynomial Randomized Approximation Scheme (FPRAS), which samples a uniform pdf over a subset of   F   in   P , using the Markov Chain Monte Carlo (MCMC) method [ 16 ]. Combining MCMC with Inverse CDF Sampling enables us to sample arbitrary IID pdfs over   F   . This approach is sufficiently general that it adapts to arbitrary joint pdfs over   F   , in which case it becomes the Metropolis-Hastings sampling [ 3 ].  5.3. Inid parents.   We will finally relax the iid assumption by assuming that position   X i  has the parent pdf   p   f i , and is chosen independently of others. We denote the vector of parent pdfs and cdfs by   p f 1: n   and   p F 1: n   respectively. T HEOREM   5.5.   PCON -inid, the version of   PCON   generated by the inid parents   X   ∼ p   f 1: n , where each parent is supported on   B , is   # PH .  15
Proof .   We reduce a # PH   subset of   PCON ( n U )   to   PCON -inid.   Let the given instance of  PCON ( n U )   have the boundary length   s   =   n   +   1, and the parent defined by the   n   +   1 pieces  p   f i :1 ... n   =   p i   over   [ i   −   1 ,   i ] , with   ∑   p i   =   1. The equivalent instance of   PCON -inid will have 2U parents and a boundary length   s ′   =   n   +   2. Define the   i -th parent   p   f   ′  i   of the inid instance to be  p   f   ′  i   =        p i   for   x   ∈   [ i   −   1 ,   i ]  1   −   p i   for   x   ∈   [ n   +   1 ,   n   +   2 ]  0 elsewhere on   [ 0 ,   n   +   2 ] .  (5.14) It is clear that   p   f   ′  i   has unit measure on its support, and is thus a pdf. Further, if the original   n U instance is connected, then so is the inid instance   on the interval   [ 0 ,   n   +   1 ] , with connectivity on the last segment   [ n   +   1 ,   n   +   2 ]   ignored . The unrestricted connectivity of the last segment has no effect on the complexity of the problem.  REFERENCES [1]   M ARK   D E   B ERG , O TFRIED   C HEONG , M ARK   V AN   K REVELD ,   AND   M ARK   O VERMARS ,   Computational Geometry: Algorithms and Applications , Springer-Verlag TELOS, Santa Clara, CA, USA, 3rd ed., 2008. [2]   S PRING   B ERMAN ,  ́ A D    ́ AM   H AL    ́ ASZ , M. A NI   H SIEH ,   AND   V IJAY   K UMAR ,   Optimized stochastic policies for task allocation in swarms of robots , IEEE Trans. Robot., 25 (2009), pp. 927–937. [3]   S IDDHARTHA   C HIB AND   E DWARD   G REENBERG ,   Understanding the Metropolis-Hastings algorithm , The American Statistician, 49 (1995), pp. 327–335. [4]   N IKOLAUS   C ORRELL ,   Parameter estimation and optimal control of swarm-robotic systems: a case study in distributed task allocation , in Proceedings of the 2008 IEEE International Conference on Robotics and Automation, Pasadena, CA, USA, May 19–23, 2008, pp. 3302–3307. [5]   H.A. D AVID AND   H.N. N AGARAJA ,   Order Statistics , John Wiley and Sons, Hoboken, NJ, USA, 2003. [6]   A. D VORETZKY AND   H. R OBBINS ,   On the parking problem , Publications of the Mathematical Institute of the Hungarian Academy of Sciences, (1964), pp. 209 – 224. [7]   M ARTIN   D YER AND   A LAN   F RIEZE ,   Computing the volume of convex bodies: a case where randomness provably helps , Probabilistic combinatorics and its applications, 44 (1991), pp. 123–170. [8]   M. E. D YER AND   A. M. F RIEZE ,   On the complexity of computing the volume of a polyhedron , SIAM J. Comput., 17 (1988), pp. 967–974. [9]   W ILLIAM   C. E VANS , G R    ́ EGORY   M ERMOUD ,   AND   A LCHERIO   M ARTINOLI ,   Comparing and modeling dis- tributed control strategies for miniature self-assembling robots , in Proceedings of the 2010 IEEE Interna- tional Conference on Robotics and Automation, Anchorage, AK, USA, May 3–7, 2010, pp. 1438–1445. [10]   D EBORAH   H G LUECK , A NIS   K ARIMPOUR -F ARD , J AN   M ANDEL , L ARRY   H UNTER ,   AND   K EITH   E M ULLER ,   Fast computation by block permanents of cumulative distribution functions of order statistics from several populations , Communications in Statistics-Theory and Methods, 37 (2008), pp. 2815–2824. [11]   N ICK   G RAVIN , D MITRII   V P ASECHNIK , B ORIS   S HAPIRO ,   AND   M ICHAEL   S HAPIRO ,   On moments of a polytope , arXiv preprint arXiv:1210.3193, (2012). [12]   M ARTIN   H AENGGI ,   Stochastic Geometry for Wireless Networks , Cambridge University Press, 2012. [13]   I NTERNET   E NGINEERING   T ASK   F ORCE ,   Optimized   link   state   routing:   RFC   7181 .  http://tools.ietf.org/html/rfc7181 , 2014. [14]   P HILIPPE   J ACQUET , P AUL   M  ̈ UHLETHALER , T HOMAS   C LAUSEN , A NIS   L AOUITI , A MIR   Q AYYUM ,   AND  L AURENT   V IENNOT ,   Optimized link state routing protocol for ad hoc networks , in Multi Topic Con- ference, 2001. IEEE INMIC 2001. Technology for the 21st Century. Proceedings. IEEE International, IEEE, 2001, pp. 62–68. [15]   A BBAS   J AMALIPOUR AND   Y AOZHU   M A ,   Intermittently Connected Mobile Ad Hoc Networks: from Routing to Content Distribution , (SpringerBriefs in Computer Science), Springer Science, 2011. [16]   M ARK   J ERRUM ,   Counting, Sampling, and Integrating:Algorithms and Complexity , Lectures in Mathematics, Birkhauser Verlag, 2003. [17]   E RIC   K LAVINS , S AMUEL   B URDEN ,   AND   N ILS   N APP ,   Optimal rules for programmed stochastic self- assembly , in Proceedings of Robotics: Science and Systems, Philadelphia, PA, USA, August 2006. [18]   G ANESH   P K UMAR AND   S PRING   B ERMAN ,   Analytical results and algorithms for stochastic boundary cov- erage by robotic swarms , Submitted to IEEE Transactions on Robotics, (2014). 16
USING SIAM’S L A TEX MACROS   17  [19]   G ANESH   P. K UMAR AND   S PRING   B ERMAN ,   Statistical analysis of stochastic multi-robot boundary cover- age , in Int’l. Conf. on Robotics and Automation (ICRA), 2014, pp. 74–81. [20]   G ANESH   P. K UMAR , A UR    ́ ELIE   B UFFIN , T HEODORE   P. P AVLIC , S TEPHEN   C. P RATT ,   AND   S PRING   M. B ERMAN ,   A stochastic hybrid system model of collective transport in the desert ant Aphaenogaster cock- erelli , in Proc. 16th Int’l. Conf. on Hybrid Systems: Computation and Control (HSCC), 2013, pp. 119– 124. [21]   W ENGUO   L IU AND   A LAN   F. T. W INFIELD ,   Modeling and optimization of adaptive foraging in swarm robotic systems , Int. J. Robot. Res., 29 (2010), pp. 1743–1760. [22]   T. W ILLIAM   M ATHER AND   M. A NI   H SIEH ,   Distributed robot ensemble control for deployment to multiple sites , in Proceedings of Robotics: Science and Systems, Los Angeles, CA, USA, June 2011. [23]   L O  ̈ IC   M ATTHEY , S PRING   B ERMAN ,   AND   V IJAY   K UMAR ,   Stochastic strategies for a swarm robotic assembly system , in Proceedings of the 2009 IEEE International Conference on Robotics and Automation, Kobe, Japan, May 12–17, 2009, pp. 1953–1958. [24]   G REG   M ULLER ,   The efficiency of random parking .   http://tiny.cc/7r8a7x , 2007. [25]   N ILS   N APP , S AMUEL   B URDEN ,   AND   E RIC   K LAVINS ,   Setpoint regulation for stochastically interacting robots , in Proceedings of Robotics: Science and Systems, Seattle, WA, USA, June 2009. [26]   L AEL   U. O DHNER AND   H ARRY   A SADA ,   Stochastic recruitment control of large ensemble systems with limited feedback , J. Dyn. Syst., Meas., Control., 132 (2010). [27]   M ATTHEW   P ENROSE ,   Random Geometric Graphs , Oxford Studies in Probability, Oxford University Press, 2003. [28]   ,   Random Geometric Graphs , Oxford Studies in Probability, Oxford University Press, 2003. [29]   A LFR    ́ ED   R  ́ ENYI ,   On a one-dimensional problem concerning random space-filling , Publ. Math. Inst. Hung. Acad. Sci., 3 (1958), pp. 109–127. [30]   M ATHIEU   D UTOUR   S IKIRIC AND   Y OSHIAKI   I TOH ,   Random Sequential Packing of Cubes , World Scientific Publishing Company, 2011. [31]   J T ALBOT , G T ARJUS , PR V AN   T ASSEL ,   AND   P V IOT ,   From car parking to protein adsorption: an overview of sequential adsorption processes , Colloids and Surfaces A: Physicochemical and Engineering Aspects, 165 (2000), pp. 287–324. [32]   C HEN   W ANG , G UANGMING   X IE ,   AND   M ING   C AO ,   Controlling anonymous mobile agents with unidirec- tional locomotion to form formations on a circle , Automatica, 50 (2014), pp. 1100 – 1108.