On Endogenous Reconfiguration in Mobile Robotic Networks  Ketan Savla 1   Emilio Frazzoli 1  Laboratory for Information and Decision Systems, Massachusetts Institute of Technology   { ksavla,frazzoli } @mit.edu  Abstract:   In this paper, our focus is on certain applications for mobile robotic networks, where reconfiguration is driven by factors intrinsic to the network rather than changes in the external environment. In particular, we study a version of the coverage problem useful for surveillance applications, where the objective is to po- sition the robots in order to minimize the average distance from a random point in a given environment to the closest robot. This problem has been well-studied for omni-directional robots and it is shown that optimal configuration for the network is a centroidal Voronoi configuration and that the coverage cost belongs to   Θ ( m − 1 / 2 ), where   m   is the number of robots in the network. In this paper, we study this problem for more realistic models of robots, namely the double integrator (DI) model and the differential drive (DD) model. We observe that the introduction of these motion constraints in the algorithm design problem gives rise to an interesting behavior. For a   sparser   network, the optimal algorithm for these models of robots mimics that for omni-directional robots. We propose novel algorithms whose performances are within a constant factor of the optimal asymptotically (i.e., as   m   →   + ∞ ). In particular, we prove that the coverage cost for the DI and DD models of robots is of order   m − 1 / 3 . Additionally, we show that, as the network grows, these novel algo- rithms outperform the conventional algorithm; hence necessitating a reconfiguration in the network in order to maintain optimal quality of service.  1 Introduction  The advent of large scale sensor and robotic networks has led to a surge of interest in reconfigurable networks. These systems are usually designed to reconfigure in a   reactive   way, i.e., as a response to changes in external condi- tions. Due to their importance in sensor network applications, reconfiguration algorithms have attracted a lot of attention, e.g., see [9]. However, there are very few instances in engineering systems, if any, that demonstrate an inter- nal reconfiguration in order to maintain a certain level of performance when certain   intrinsic   properties of the system are changed. However, examples of endogenous reconfiguration or phase transitions are abound in nature, e.g.,  arXiv:0807.2648v2 [cs.RO] 18 Jul 2008
2   Ketan Savla   Emilio Frazzoli  desert locusts [4] who switch between gregarious and social behavior abruptly, etc. An understanding of the phase transitions can not only provide insight into the reasons for transitions in naturally occurring systems but also iden- tify some design principles involving phase transition to maintain efficiency in engineered systems. In this paper, we observe such a phenomenon under a well-studied setting that is relevant for various surveillance applications. We consider a version of the so-called Dynamic Traveling Repairperson Problem, first proposed by [12] and later developed in [2]. In this problem, service requests are generated dynamically. In order to fulfill a request, one of the vehicles needs to travel to its location. The objective is to design strategies for task assignment and motion planning of the robots that minimizes the average waiting time of a service request. In this paper, we consider a special case of this problem when service requests are generated sparingly. This problem, also known as coverage problem, has been well-studied in the robotics and operations research com- munity. However, we consider the problem in the context of realistic models of robots: double integrator models and differential drive robots. Some pre- liminary work on coverage for curvature-constrained vehicles was reported in our earlier work [7]. In this paper, we observe that when one takes into con- sideration the motion constraints of the robots, the optimal solution exhibits a phase transition that depends on the size of the network. The contributions of this paper are threefold. First, we identify an interest- ing characteristic of the solution to the coverage problem for double integrator and differential drive robots, where reconfiguration is necessitated intrinsically by the growth of the network, in order to maintain optimality. Second, we pro- pose novel approximation algorithms for double integrator robots as well as differential drive robots and prove that they are within a constant factor of the optimal in the asymptotic ( m   →   + ∞ ) case. Moreover, we prove that, asymptotically, these novel algorithms will outperform the conventional al- gorithms for omni-directional robots. Lastly, we show that the coverage for both, double integrator as well as differential drive robots scales as 1 /m 1 / 3  asymptotically.  2 Problem Formulation and Preliminary Concepts  In this section, we formulate the problem and present preliminary concepts.  Problem Formulation  The problem that we consider falls into the general category of the so called  Dynamic Traveling Repairperson Problem , originally proposed in [12]. Let   Q ⊂  R 2   be a convex, compact domain on the plane, with non-empty interior; we will refer to   Q   as the   environment . For simplicity in presentation, we assume that  Q   is a square, although all the analysis presented in this paper carries through
On Endogenous Reconfiguration in Mobile Robotic Networks   3  for any convex and compact   Q   with non-empty interior in   R 2 . Let   A   be the area of   Q . A spatio-temporal Poisson process generates   service requests   with finite time intensity   λ >   0 and uniform spatial density inside the environment. In this paper, we focus our attention on the case when   λ   →   0 + , i.e., when the service requests are generated very rarely. These service requests are identical and are to be fulfilled by a team of   m   robots. A service request is fulfilled when one of   m   robots moves to the target point associated with it. We will consider two robot models: the double integrator model and the differential drive model. The double integrator (DI) model describes the dy- namics of a robot with significant inertia. The configuration of the robot is  g   = ( x, y, v x , v y   )   ⊂   R 4   where ( x, y ) is the position of the robot in Cartesian coordinates, and ( v x , v y   ) is its velocity. The dynamics of the DI robot are given by  ̇ x ( t ) =   v x ( t ) ,   ̇ y ( t ) =   v y   ( t ) ,   v x ( t ) 2   +   v y   ( t ) 2   ≤   v 2 max   ∀ t   ̇ v x ( t ) =   u x ( t ) ,   ̇ v y   ( t ) =   u y   ( t ) ,   u x ( t ) 2   +   u y   ( t ) 2   ≤   u 2 max   ∀ t,  where   v max   and   u max   are the bounds on the speed and the acceleration of the robots. The differential drive model describes the kinematics of a robot with two independently actuated wheels, each a distance   ρ   from the center of the robot. The configuration of the robot is a directed point in the plane,   g   = ( x, y, θ )   ⊂  SE(2) where ( x, y ) is the position of the robot in Cartesian coordinates, and  θ   is the heading angle with respect to the   x   axis. The dynamics of the DD robot are given by  ̇ x ( t ) = 1 2 ( w l ( t ) +   w r   ( t )) cos   θ ( t ) ,   ̇ y ( t ) = 1 2 ( w l ( t ) +   w r   ( t )) sin   θ ( t ) ,   ̇ θ ( t ) =   1 2 ρ   ( w r   ( t )   −   w l ( t )) ,   | w l ( t ) | ≤   w max ∀ t,   | w r   ( t ) | ≤   w max ∀ t,  where the inputs   w l   and   w r   are the angular velocities of the left and the right wheels, which we assume to be bounded by   w max . Here, we have also assumed that the robot wheels have unit radius. The robots are assumed to be identical. The strategies of the robots in the presence and absence of service requests are governed by their   motion coordination algorithm . A motion coordination algorithm is a function that determines the actions of each robot over time. For the time being, we will denote these functions as   π   = ( π 1 , π 2 , . . . , π m ), but do not explicitly state their domain; the output of these functions is a steering command for each vehicle. The objective is the design of motion coordination algorithms that allow the
4   Ketan Savla   Emilio Frazzoli  robots to fulfill service requests efficiently. To formalize the notion of efficiency, let   T j   be the time elapsed between the generation of the   j -th service request, and the time it is fulfilled and let   T π   := lim j → + ∞   lim λ → 0 +   E[ T j   ]   be defined as the system time under policy   π , i.e., the expected time a service request must wait before being fulfilled, given that the robots follow the algorithm defined by   π . We shall also refer to the average system time as the   coverage cost . Note that the system time   T π   can be thought of as a measure of the quality of service collectively provided by the robots. In this paper, we wish to devise motion coordination algorithms that yield a quality of service (i.e., system time) achieving, or approximating, the the- oretical optimal performance given by   T opt   = inf π   T π   . Since finding the opti- mal algorithm maybe computationally intractable, we are also interested in designing computationally efficient algorithms that are within a constant fac- tor of the optimal, i.e., policies   π   such that   T π   ≤   κT opt   for some constant  κ . Moreover, we are interested in studying the scaling of the performance of the algorithms with   m , i.e., size of the network, other parameters remaining constant. Since, we keep   A   fixed, this is also equivalent to study the scaling of the performance with respect to the density   m/ A   of the network. We now describe how a solution to this problem gives rise to an endogenous reconfiguration in the robotic network.  Endogenous Reconfiguration  The focus of this paper is on   endogenous   reconfiguration, that is a reconfig- uration necessitated by the growth of the network (as the term ‘endogenous’ implies in biology), as opposed to any external stimulus. We formally describe its meaning in the context of this paper. In the course of the paper, we shall propose and analyze various algorithms for the coverage problem. In particu- lar, for each model of the robot, we will propose two algorithms,   π 1   and   π 2 . The policy   π 1   closely resembles the omni-directional based policy, whereas the novel   π 2   policy optimizes the performance when the motion constraints of the robots start playing a significant role. We shall show that lim  m/ A→ 0 +  T π 1  T opt  = 1 ,   lim  m → + ∞  T π 2  T π 1  = 0 ,   lim sup  m → + ∞  T π 2  T opt  ≤   c   for some constant   c >   1 .  This shows that, for sparse networks, the omni-directional model based al- gorithm   π 1   is indeed a reasonable algorithm. However, as the network size increases, there is a phase transition, during which the motion constraints start becoming important and the   π 2   algorithm starts outperforming the   π 1  algorithm. Moreover, the   π 2   algorithm performs with a constant factor of the optimal in the asymptotic ( m   →   + ∞ ) case. Hence, in order to maintain ef- ficiency, one needs to switch away from the   π 1   policy as the network grows. It is in this sense that we shall use the term endogenous reconfiguration to denote a switch in the optimal policy with the growth of the network.
On Endogenous Reconfiguration in Mobile Robotic Networks   5  3 Lower Bounds  In this section, we derive lower bounds on the coverage cost for the robotic network that are independent of any motion coordination algorithm adopted by the robots. Our first lower bound is obtained by modeling the robots as  equivalent   omni-directional robots. Before stating the lower bounds formally, we need to briefly review a related problem from computational geometry which has direct consequences for the case omni-directional robots.  The Continuous   m -median Problem  Given a convex, compact set   Q ⊂   R 2   and a set of points   p   =   { p 1 , p 2 , . . . , p m } ∈ Q m , the expected distance between a random point   q , sampled from a uniform distribution over   Q , and the closest point in   p   is given by  H m ( p,   Q ) :=  ∫  Q  1  A   min  i ∈{ 1 ,...,m }   ‖ p i   −   q ‖   dq   =  m ∑  i =1  ∫  V i ( p )  1  A ‖ p i   −   q ‖   dq,  where   V ( p )   =   ( V 1 ( p ) ,   V 2 ( p ) , . . . ,   V m ( p )) is the   Voronoi (Dirichlet) parti- tion   [10] of   Q   generated by the points in   p , i.e.,  V i ( p ) =   { q   ∈ Q   :   ‖ q   −   p i ‖ ≤ ‖ q   −   p j   ‖ ,   ∀ j   ∈ { 1 , . . . , m }} ,   i   ∈ { 1 , . . . , m } .  The problem of choosing   p   to minimize   H m   is known in geometric optimiza- tion [1] and facility location [6] literature as the (continuous)   m -median prob- lem. The   m -median of the set   Q   is the global minimizer  p ∗  m ( Q ) = argmin p ∈Q m   H m ( p,   Q ) .  We let   H ∗  m ( Q ) =   H m ( p ∗  m ( Q ) ,   Q ) be the global minimum of   H m . The solution of the continuous   m -median problem is hard in the general case because the function   p   7   → H m ( p,   Q ) is not convex for   m >   1. However, gradient algorithms for the continuous multi-median problem can be designed [5]. We would not go further into the details of computing these   m -median locations and assume that these locations are given or that a computationally efficient algorithm for obtaining them is available. This particular problem formulation, with demand generated indepen- dently and uniformly from a continuous set, is studied thoroughly in [11] for square regions and [13] for more general compact regions. It is shown in [13] that, in the asymptotic ( m   →   + ∞ ) case,   H ∗  m ( Q ) =   c hex  √   A  m   almost surely, where   c hex   ≈   0 . 377 is the first moment of a hexagon of unit area about its center. This optimal asymptotic value is achieved by placing the   m   points on a regular hexagonal network within   Q   (the honeycomb heuristic). Working towards the above result, it is also shown in [13] that for any   m   ∈   N : 2 3  √   A  πm   ≤ H ∗  m ( Q )   ≤   c ( Q )  √   A  m ,   (1)
6   Ketan Savla   Emilio Frazzoli  where   c ( Q ) is a constant depending on the shape of   Q . In particular, for a square   Q ,   c ( Q )   ≈   0 . 38. We use two different superscripts on   T opt   for the two models of the robots, i.e., we use   T   DI opt   for the DI robot and   T   DD opt   for the DD robot. Finally, we state a lower bound on these quantities as follows.  Lemma 1.   The coverage cost satisfies the following lower bound.  T   DI opt   ≥ H ∗  m ( Q )  v max  ,   T   DD opt   ≥ H ∗  m ( Q )  w max  .  Proof.   The proof follows trivially by relaxing the constraints on the robots and allowing them to move like omni-directional robots with speeds   v max   for DI robots and   w max   for DD robots. One can then adopt the lower bound on coverage cost for omni-directional robot, e.g., [2] to arrive at the result.  Remark 1.   Since from Equation (1),   H ∗  m ( Q )   ∈   Ω (1 / √ m ), Lemma 1 implies that   T   DI opt   and   T   DD opt   also belong to   Ω (1 / √ m ). This lower bound will be particularly useful for proving the optimality of algorithms for sparse networks. We now proceed towards deriving a tighter lower bound which will be relevant for dense networks. The reachable sets of the two models of robots will play a crucial role in deriving the new lower bound. We study them next.  Reachable Sets for the Robots  In this subsection, we state important properties of the reachable sets of the double integrator and differential drive robots that are useful in obtaining tighter lower bound. Let   τ   :   G   ×   R 2   →   R +   be the minimum time required to steer a robot from initial configuration   g   in   G   to a point   q   in the plane. For the DI robot,  G   =   R 4   and for DD robots   G   = SE(2). With a slight abuse of terminology, we define the reachable set of a robot,   R t ( g ), to be the set of all points   q   in  Q   that are reachable in time   t >   0 starting at configuration   g . Note that, in this definition, we do not put any other constraint (e.g., heading angle, etc.) on the terminal point   q . Formally, the reachable set is defined as  R t ( g ) =   { q   ∈   R 2   |   τ   ( g, q )   ≤   t } .  We now state a series of useful properties of the reachable sets.  Lemma 2 (Upper   bound   on   the   small-time   reachable   set   area).  The area of the reachable set for a DI robot starting at a configuration  g   = ( x, y,    ̇ x,    ̇ y )   ∈   R 4 , with    ̇ x 2   +  ̇ y 2   =   v 0 , satisfies the following upper bound.  Area( R t ( g ))   ≤  {   2 v 0 u max t 3   +   o ( t 3 ) ,   as   t   →   0 +   for   v 0   >   0 , u 2  max t 4   for   v 0   = 0 .
On Endogenous Reconfiguration in Mobile Robotic Networks   7  The area of the reachable set for a DD robot starting at any configuration  g   ∈   SE(2)   satisfies the following upper bound.  Area( R t ( g ))   ≤   5 6 ρ w 3  max t 3   +   o ( t 3 ) ,   as   t   →   0 + .  Proof.   The result for the differential drive robot has been derived in [8]. We derive the result for the double integrator robot here. Assume, without any loss of generality, that the robot is initially placed at the origin with ve- locity aligned with the   x -axis. The maximum of the absolute value of the  x -coordinate and   y -coordinate of all the points reachable in time   t   is less than or equal to   v 0 t   +   1 2   u max t 2   and   1 2   u max t 2 , respectively. Therefore, the area of the reachable set is trivially upper bounded by 4( v 0 t   +   1 2   u max t 2 )(   1 2   u max t 2 ) = 2 v 0 u max t 3   +   u 2 max t 4 .  Lemma 3 (Lower bound on the reachable set area).   The area of the reachable set of a DI robot starting at a configuration   g   = ( x, y,    ̇ x,    ̇ y )   ∈   R 4 , with    ̇ x 2   +  ̇ y 2   =   v 0 , satisfies the following lower bound.  Area( R t ( g ))   ≥   v 0 u max  3   t 3   ∀ t   ≤   π  2  v 2 0  u max  .  The area of the reachable set of a DD robot starting at any configuration  g   ∈   SE(2)   satisfies the following lower bound.  Area( R t ( g ))   ≥   2 3 ρ w 3  max t 3 .  Lemma 4.   The travel time to a point in the reachable set for a DI robot starting at a configuration   g   = ( x, y,    ̇ x,    ̇ y )   ∈   R 4 , with    ̇ x 2   +  ̇ y 2   =   v 0 , satisfies the following property.  ∫  R t ( g )  τ   ( g, q ) dq   ≥   v 0 u max  12   t 4   ∀ t   ≤   π  2  v 2 0  u max  .  The travel time to a point in the reachable set for a DD robot starting at any configuration   g   ∈   SE(2)   satisfies the following property.  ∫  R t ( g )  τ   ( g, q ) dq   ≥   w 3  max  6 ρ   t 4 .  Proof.   For both the robots,   ∫  R t ( g )   τ   ( g, q ) dq   =   ∫   t  0   Area( R s ( g )) ds . Using Lemma 3, for a double integrator robot, for all   t   ≤   π  2  v 2 0  u max   we have that,  ∫  R t ( g )  τ   ( g, q ) dq   ≥   v 0 u max  3  ∫   t  0  s 3 ds   =   v 0 u max  12   t 4 .  The proof for the differential drive robot follows along similar lines.
8   Ketan Savla   Emilio Frazzoli  We are now ready to state a new lower bound on the coverage cost.  Theorem 1 (Asymptotic lower bound on the coverage cost).   The cov- erage cost for a network of DI or DD robots satisfies the following asymptotic lower bound.  lim inf  m → + ∞   T   DI opt m 1 / 3   ≥   1 24  (   A  2 v max u max  ) 1 / 3  ,   and  lim inf  m → + ∞   T   DD opt   m 1 / 3   ≥   1 5 w max  (   6 ρ A  5  ) 1 / 3  .  Proof.   We state the proof for the double integrator robot. The proof for the differential drive robot follows along similar lines. In the following, we use the notation A i   = Area( DV i ( g )), where   DV i ( g ) :=  { q   ∈ Q |   τ   ( g i , q )   ≤   τ   ( g j   , q )   ∀ j   6   =   i } . We begin with  T   DI opt   =   inf  g ∈ R 4 m  m ∑  i  ∫  DV i ( g )  1  A   τ   ( g i , q )   dq  ≥   inf  g ∈ R 4 m  ∫  Q  1  A   min  i ∈{ 1 ,...,m }   τ   ( g i , q ) dq.   (2) Let  ̄ R A i   ( g i ) be the reachable set starting at configuration   g   and whose area is A i . Using the fact that, given an area A i , the region with the minimum integral of the travel time to the points in it is the reachable set of area A i , one can write Equation (2) as  T   DI opt   ≥   inf  g ∈ R 4 m  m ∑  i  ∫   ̄ R A i   ( g i )  1  A   τ   ( g i , q )   dq.   (3) Let   t i   be defined such that Area( R t i   ( g i )) = A i . Lets assume that as   m   →   + ∞ , A i   →   0 +   (this point will be justified later on). In that case, we know from Lemma 2 that,   t i   can be lower bounded as   t i   ≥  (   A i  2 v i u max  ) 1 / 3  , where   v i   is the speed associated with the state   g i . Therefore, from Equation (3) and Lemma 4, one can write that  T   DI opt   ≥   inf  g ∈ R 4 m  m ∑  i  ∫  R ti   ( g i )  1  A   τ   ( g i , q )   dq  ≥   inf  g ∈ R 4 m  m ∑  i  1  A  v i u max  12   t 4  i   .   (4) Using the above mentioned lower bound on   t i , Equation (4) can be written as
On Endogenous Reconfiguration in Mobile Robotic Networks   9  T   DI opt   ≥   1 24   3  √ 2 A  1  u 1 / 3 max  inf  g ∈ R 4 m  A 4 / 3  i  v 1 / 3  i  ≥   1 24   3  √ 2 A  1  u 1 / 3 max v 1 / 3 max  min  { A 1 , A 2 ,..., A m   }∈ R m  m ∑  i  A 4 / 3  i  subject to  m ∑  i  A i   =   A   and A i   ≥   0   ∀ i   ∈ { 1 , . . . , m } .  Note that the function   f   ( x ) =   x 4 / 3   is continuous, strictly increasing and convex. Thus by using the Karush-Kuhn-Tucker conditions [3], one can show that the quantity   ∑ m i   A 4 / 3  i   is minimized with an equitable partition, i.e., A i   =   A /m,   ∀ i . This also justifies the assumption that for   m   →   + ∞ , A i   →   0 + .  Remark 2.   Theorem 1 shows that both   T   DI opt   and   T   DD opt   belong to   Ω (1 /m 1 / 3 ).  4 Algorithms and their Analyses  In this section, we propose novel algorithms, analyze their performance and explain how the size of the network plays a role in selecting the right algorithm. We start with an algorithm which closely resembles the one for omni- directional robots. Before that, we first make a remark relevant for the analysis of all the algorithms to follow.  Remark 3.   Note that if   n 0   is the number of outstanding service requests at initial time, then the time required to service all of them is finite ( Q   being bounded). During this time period, the probability of appearance of a new service requests appearing is zero (since we are dealing with the case when the rate of generation of targets   λ   is arbitrarily close to zero). Hence, after an initial transient, with probability one, all the robots will be in their stationary locations at the appearance of the new target. Moreover, the probability of number of outstanding targets being more than one is also zero. Hence, in the analysis of the algorithms, without any loss of generality, we shall implicitly assume that there no outstanding service requests initially.  The Median Stationing (MS) Algorithm  Place the   m   robots at rest at the   m -median locations of   Q . In case of the DD robot, its heading is chosen arbitrarily. These   m -median locations will be referred to as the   stationary locations   of the robots. When a service request appears, it is assigned to the robot whose stationary location is closest to the location of the service request. In order to travel to the service location, the robots use the fastest path with no terminal constraints at the service location. In absence of outstanding service tasks, the robot returns to its stationary location. The stationary configurations are depicted in Figure 1.
10   Ketan Savla   Emilio Frazzoli  Fig. 1.   Depiction of typical stationary configurations for the Median Stationing Algorithm. On the left: DI robots at rest at their stationary locations. On the right: DD robots with arbitrary headings at their stationary locations. In both the figures, the shaded cell represents a typical   region of responsibility   for a robot.  Let   T   DI MS   and   T   DD MS   be the coverage cost as given by the above policy for the DI and DD robots, respectively.  Theorem 2 (Analysis of the MS algorithm).   The coverage cost for a network of DI and DD robots with the MS algorithm satisfies the following bounds.  H ∗  m ( Q )  v max  ≤   T   DI MS   ≤ H ∗  m ( Q )  v max  +   v max  2 u max  +  √  2 √ 2 A  u max  .  H ∗  m ( Q )  w max  ≤   T   DD MS   ≤ H ∗  m ( Q )  w max  +   ρπ  2 w max  .  Proof.   The lower bounds on   T   DI MS   and   T   DD MS   follow trivially from Lemma 1. For a double integrator robot, the minimum travel time from rest at loca- tion   p   to a point   q   is given by  τ   (( p,   0) , q )   ≤  { √   2 ‖ p − q ‖  u max   for   ‖ p   −   q ‖ ≤   v 2 max  2 u max   ,  ‖ p − q ‖  v max   +   v max  2 u max   otherwise .  Therefore, for any   q ,   τ   (( p,   0) , q ) can be upper bounded as  τ   (( p,   0) , q )   ≤ ‖ p   −   q ‖  v max  +   v max  2 u max  +  √  2 ‖ p   −   q ‖  u max  ≤ ‖ p   −   q ‖  v max  +   v max  2 u max  +  √  2 √ 2 A  u max  .
On Endogenous Reconfiguration in Mobile Robotic Networks   11  The upper bound on   T   DI MS   is then obtained by taking the expected value over all   q   ∈ Q   while taking into consideration the assignment policies for the services to robots. For a differential drive robot, the travel time from any initial configuration ( p, θ ) to a point   q   can be upper bounded by   ‖ p − q ‖  w max   +   πρ  2 w max   . The result follows by taking expected value of the travel time over all points in   Q .  Remark 4.   Theorem 2 and Lemma 1 along with Equation (1) imply that, lim  m/ A→ 0 +  T   DI MS  T   DI opt  = 1   and   lim  m/ A→ 0 +  T   DD MS  T   DD opt  = 1 .  This implies that the MS algorithm is indeed a reasonable algorithm for sparse networks, where the travel time for a robot to reach a service location is almost the same as that for an omni-directional vehicle. However, as the density of robots increases, the assigned service locations to the robots start getting relatively closer. In that case, the motion con- straints start having a significant effect on the travel time of the robots and it is not obvious in that case that the MS algorithm is indeed the best one. In fact, for dense networks, one can get a tighter lower bound on the performance of the MS algorithm:  Theorem 3.   The coverage cost of a dense network of DI and DD robots with the MS algorithm satisfies the following bounds:  lim inf  m →∞   T   DI MS m 1 / 4   ≥   0 . 321  (   A  u 2  max  ) 1 / 4  .  lim inf  m →∞   T   DD MS   ≥   πρ  4 w max  .  Proof.   Let us consider the DI case first. The minimum travel time for the   i -th robot to reach a point   q   inside its region of responsibility   V i , starting from rest at the median location   p i   is bounded by  τ   (( p i ,   0) , q )   ≥   max  {  ‖ p i   −   q ‖  √ 2 u max d V i  ,   ‖ p i   −   q ‖  v max  }  ,   (5) where  d V i   = max  q ∈V i  ‖ p i   −   q ‖ .  For large   m , it is known that the honeycomb heuristic is optimal [13], yielding lim  m →∞   d V i   m 1 / 2   =  √  2   A  3 √ 3   ≈   0 . 62 √A ,   ∀ i   ∈ { 1 , . . . , m } .   (6) Clearly, in these conditions the first term in (5) is the dominant one.
12   Ketan Savla   Emilio Frazzoli  Another consequence of the optimality of the honeycomb heuristic is that lim  m →∞   H ∗  m ( Q ) m 1 / 2   =   c hex  √A .   (7) Integrating (5) over   Q , multiplying both sides by   m 1 / 4 , and taking the limit as   m   → ∞ , we get lim inf  m →∞   T   DI MS m 1 / 4   ≥   lim inf  m →∞  H ∗  m ( Q ) m 1 / 2  √ 2 u max d V i   m 1 / 2   .  Finally, using (6) and (7), we get the desired result. We will only sketch the proof for the DD case. The minimum travel time for a DD robot can be decomposed into the sum of the cost of turning towards the target point, plus the Euclidean distance between the robot and the target point. The Euclidean term vanishes as   m   increases. The turning cost on the other hand remains bounded away from zero. Since the robot’s initial heading is chosen randomly, the expected turning angle is   π/ 4, which combined with the maximum turning rate   w max /ρ   yields the stated result. In other words, for DI robots, the MS algorithm requires them to stay sta- tionary in absence of any outstanding service requests. Once a service request is assigned to a robot, the amount of time spend in attaining the maximum speed   v max   becomes significant as the location of assigned service requests start getting closer. Similar arguments hold for DD robots. An alternate approach, as proposed in the next algorithm, is to keep the robots moving rather than waiting in absence of outstanding service requests. The algorithm assigns dynamic regions of responsibility to the robots.  The Strip Loitering (SL) Algorithm  This algorithm is an adaptation of a similar algorithm proposed in [7] for Dubins vehicle, i.e., vehicles constrained to move forward with constant speeds along paths of bounded curvature. Let the robots move with constant speed   v ∗   = min { v max ,  √ √A u max  3 . 22   }   and follow a loitering path which is constructed as follows. Divide   Q   into strips of width   w   where   w   = min  {(   4 3 √ ρ ∗  A +10 . 38 ρ ∗   √A  m  ) 2 / 3  ,   2 ρ ∗  }  , where   ρ ∗   :=   v ∗   2  u max   . Orient the strips along a side of   Q . Construct a closed path which can be traversed by a double integrator robot while always moving with constant speed   v ∗ . This closed path runs along the longitudinal bisector of each strip, visiting all strips from top-to-bottom, making U-turns between strips at the edges of   Q , and finally returning to the initial configuration. The   m   robots loiter on this path, equally spaced, in terms of path length. A depiction of the Strip Loitering algorithm can be viewed in Figure 2. Moreover, in Figure 3 we define two distances that are important in the analysis of this algorithm.
On Endogenous Reconfiguration in Mobile Robotic Networks   13  Variable   d 2   is the length of the shortest path departing from the loitering path and ending at the target (a circular arc of radius   ρ ∗ ). The robot responsible for visiting the target is the one closest in terms of loitering path length (variable  d 1 ) to the point of departure, at the time of target-arrival. Note that there may be robots closer to the target in terms of the actual distance. However, we find that the assignment strategy described above lends itself to tractable analysis.  Fig. 2.   Depiction of the loitering path for the double integrator robots. The segment providing closure of the loitering path (returning the robots from the end of the last strip to the beginning of the first strip) is not shown here for clarity of the drawing. d   2  d   1   δ  target  p oin t  of  departure  ρ  Fig. 3.   Close-up of the loitering path with construction of the point of departure and the distances   δ ,   d 1 , and   d 2   for a given target, at the instant of appearance.  After a robot has serviced a target, it must return to its place in the loitering path. We now describe a method to accomplish this task through the example shown in Fig. 3. After making a left turn of length   d 2   to service the target, the robot makes a right turn of length 2 d 2   followed by another left turn of length   d 2 , returning it to the loitering path. However, the robot has fallen behind in the loitering pattern. To rectify this, as it nears the end of the current strip, it takes its U-turn early.
14   Ketan Savla   Emilio Frazzoli  Let   T   DI SL   be the coverage cost as given by the above algorithm for DI robots. We now state an upper bound on   T   DI SL   .  Theorem 4 (Analysis of the SL algorithm).   The coverage cost for a team of DI robots implementing the SL algorithm satisfies the following asymptotic upper bound.  lim sup  m → + ∞  T   DI SL   m 1 / 3   ≤   1 . 238  v ∗  ( ρ ∗ A   + 10 . 38 ρ ∗ 2 √A ) 1 / 3 .  Proof.   Since a similar algorithm for Dubins vehicle was analyzed in [7], we only outline the proof here and refer to [7] for more details. Denote the length of the closed path as   L 1 . Due to equal spacing of the robots along the loitering path, E[ d 1 ] =   L 1  2 m .   (8) We now calculate an upper bound on   L 1 . To that effect, let   N strips   be the number of strips,   L strip   be the length travelled along a single strip,   L u − turn  be the length of a u-turn and   L closure   be the length of the closure path. With these notations,   L 1   can be bounded as  L 1   ≤   N strips L strip   + ( N strips   −   1) L u − turn   +   L closure .   (9) One can compute bounds for various terms on the right side of Equation (9). Substituting these bounds into Equation (9) and taking into account Equa- tion (8) we get that E[ d 1 ]   ≤ A   + 10 . 38 ρ ∗ √A  2 mw   + 2 √A   + 6 . 19 ρ ∗  m   .   (10) To calculate E[ d 2 ] we define   δ   as the smallest distance from the target to any point on the loitering path (see Fig. 3). Since   d 2 ( s ) = 2 ρ ∗   sin − 1 (  √   s  2 ρ ∗   ) for  s   ≤   ρ ∗   and   δ   is uniformly distributed between 0 and   w/ 2, E[ d 2 ] = 4 ρ ∗  w  ∫   w/ 2 0  sin − 1  (√   s  2 ρ ∗  )  ds   ≤   3 4  √ ρ ∗ w.   (11) Therefore, the coverage cost is given by  T   SL   ≤   E[ d 1 ] + E[ d 2 ]  v ∗   .   (12) Therefore, from Equations (12), (10) and (11) we get that for   w   ≤   2 ρ ,  T   DI SL   ≤ A   + 10 . 38 ρ ∗ √A  2 mwv ∗   + 2 √A   + 6 . 19 ρ ∗  mv ∗   +   3 4 v ∗  √ ρ ∗ w.   (13) In order to get the least upper bound, we minimize the right hand side of Equation (13) with respect to   w   subject to the constraint that   w   ≤   2 ρ ∗ .
On Endogenous Reconfiguration in Mobile Robotic Networks   15  Remark 5.   Theorem 4 and Theorem 1 imply that   T   DI opt   belongs to   Θ (1 /m 1 / 3 ). Moreover, Theorem 4 and Theorem 3 together with Equation 1 imply that  T   DI SL   /T   DI MS   →   0 +   as   m   →   + ∞ . Hence, asymptotically, the SL algorithm out- performs the MS algorithm and is within a constant factor of the optimal. We now present the second algorithm for DD robots.  The Median Clustering (MC) Algorithm  Form as many teams of robots with   k   :=  ⌈  4 . 09  (   ρ √ A  ) 2 / 3  m 1 / 3  ⌉  robots in each team. If there are additional robots, group them into one of these teams. Let  n   :=   ⌊   m k  ⌋   denote the total number of teams formed. Position these   n   teams at the   n -median locations of   Q , i.e., all the robots in a team are co-located at the median location of its team. Within each team   j ,   j   ∈ { 1 , . . . , n } , the headings of the robots belonging to that team are selected as follows. Let   ` j   ≥   k   be the number of robots in team   j . Pick a direction randomly. The heading of one robot is aligned with this direction. The heading of the second robot is selected to be along a line making an angle   π `   , in the counter-clockwise direction, with the first robot. The headings of the remaining robots are selected similarly along directions making   π `   -angle with the previous one (see Figure 4). These headings will be called the   median headings   of the robots. Each robot in a team is assigned a   dominance region   which is the region formed by the intersection of double cone making half angle of   π  2 `   with its median heading and the Voronoi cell belonging to the team (see Figure 4). When a service request appears, it is assigned to the robot whose dominance region contains its location. The assigned robot travels to the service location in the fastest possible way and, upon the completion of the service, returns to the median location of its team and aligns itself with its original median heading.  Fig. 4.   Depiction of the Median Clustering Algorithm with teams of 4 robots each. The shaded region represents a typical   region of responsibility   for a robot.
16   Ketan Savla   Emilio Frazzoli  Let   T   DD MC   be the coverage cost as given by the above policy. We now state an upper bound on   T   DD MC   in the following theorem.  Theorem 5 (Analysis of the MC algorithm).   The coverage cost for a team of DD robots while implementing the MC algorithm satisfies the following asymptotic upper bound.  lim sup  m → + ∞  T   DD MC   m 1 / 3   ≤   1 . 15  w max  ( ρ A ) 1 / 3 .  Proof.   The travel time for any robot from its median location   p   to the location  q   of a service request is upper bounded by   ‖ p − q ‖  w max   +   πρ  2 w max k   . Taking the expected value of this quantity while taking into consideration the assignment policy of the service requests gives us that  T   DD MC   ≤ H ∗  n ( Q )  w max  +   πρ  2 w max k .   (14) From Equation (1),   H ∗  n ( Q )   ≤   0 . 38  √   A  n   . Moreover, for large   m ,   n   ≈   m/k . This combined with Equation (14), one can write that, for large   m ,  T   DD MC   ≤   0 . 38  w max  √  A  m/k   +   πρ  2 w max k .   (15) The right hand side of Equation (15) is minimized when   k   = 4 . 09  (   ρ √ A  ) 2 / 3  m 1 / 3 . Substituting this into Equation (15), one arrives at the result.  Remark 6.   Theorem 5 and Theorem 1 imply that   T   DD opt   belongs to   Θ (1 /m 1 / 3 ). Moreover, Theorem 5 and Theorem 3 together with Equation 1 imply that  T   DD MC   /T   DD MS   →   0 +   as   m   →   + ∞ . Hence, asymptotically, the MC algorithm outperforms the MS algorithm and is within a constant factor of the optimal.  5 Conclusion  In this paper, we considered a coverage problem for a mobile robotic network modeled as double integrators and differential drives. We observe that the op- timal algorithm for omni-directional robots is a reasonable solution for sparse networks of double integrator or differential drive robots. However, these al- gorithms do not perform well for large networks because they don’t take into consideration the effect of motion constraints. We propose novel algorithms that are within a constant factor of the optimal for the DI as well as DD robots and prove that the coverage cost for both of these robots is of the order 1 /m 1 / 3 . In future, we would like to obtain sharper bounds on the coverage cost so that we can make meaningful predictions of the onset of reconfiguration
On Endogenous Reconfiguration in Mobile Robotic Networks   17  in terms of system parameters. It would be interesting to study the prob- lem for non-uniform distribution of targets and for higher intensity of arrival. Also, this research opens up possibilities of reconfiguration due to other con- straints, like sensors (isotropic versus anisotropic), type of service requests (distributable versus in-distributable), etc. Lastly, we plan to apply this re- search in understanding phase transition in naturally occurring systems, e.g., desert locusts [4].  References  1. P. K. Agarwal and M. Sharir. Efficient algorithms for geometric optimization.  ACM Computing Surveys , 30(4):412–458, 1998. 2. D. J. Bertsimas and G. J. van Ryzin. A stochastic and dynamic vehicle routing problem in the Euclidean plane.   Operations Research , 39:601–615, 1991. 3. S. Boyd and L. Vandenberghe.   Convex Optimization .   Cambridge University Press, 2004. 4. J. Buhl, D. J. Sumpter, I. D. Couzin, J. Hale, E. Despland, E. Miller, and S. J. Simpson. From disorder to order in marching locusts.   Science , 312:1402–1406, 2006. 5. J. Cort ́ es, S. Mart ́ ınez, T. Karatas, and F. Bullo. Coverage control for mobile sensing networks.   IEEE Transactions on Robotics and Automation , 20(2):243– 255, 2004. 6. Z. Drezner, editor.   Facility Location: A Survey of Applications and Methods . Springer Series in Operations Research. Springer Verlag, New York, 1995. 7. J. Enright, K. Savla, and E. Frazzoli.   Coverage control for teams of nonholo- nomic agents. In   IEEE Conf. on Decision and Control , 2008. To appear. 8. J. J. Enright and E. Frazzoli. The stochastic traveling salesman problem for the Reeds-Shepp car and the differential drive robot.   In   IEEE Conf. on Decision and Control , 2006. 9. A. Kansal, W. Kaiser, G. Pottie, M. Srivastava, and G. Sukhatme.   Recon- figuration methods for mobile sensor networks.   ACM Transactions on Sensor Networks , 3(4):22:1–22:28, 2007. 10. A. Okabe, B. Boots, K. Sugihara, and S. Chiu.   Spatial tessellations: Concepts and Applications of Voronoi diagrams . Wiley Series in Probability and Statis- tics. John Wiley & Sons, Chichester, UK, second edition, 2000. 11. C. H. Papadimitriou. Worst-case and probabilistic analysis of a geometric loca- tion problem.   SIAM Journal on Computing , 10(3), August 1981. 12. H. Psaraftis.   Dynamic vehicle routing problems. In B. Golden and A. Assad, editors,   Vehicle Routing: Methods and Studies , Studies in Management Science and Systems. Elsevier, 1988. 13. E. Zemel.   Probabilistic analysis of geometric location problems.   Annals of Operations Research , 1(3), October 1984.