SUBMITTED TO THE IEEE INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS) 2014   1  Route Swarm: Wireless Network Optimization through Mobility  Ryan K. Williams,   Student Member, IEEE , Andrea Gasparri,   Member, IEEE , and Bhaskar Krishnamachari,   Member, IEEE  Abstract —In this paper, we demonstrate a novel hybrid ar- chitecture   for   coordinating   networked   robots   in   sensing   and information   routing   applications.   The   proposed   IN formation and   S ensing driven   P hys I cally   RE configurable robotic network (INSPIRE), consists of a Physical Control Plane (PCP) which com- mands agent position, and an Information Control Plane (ICP) which regulates information flow towards communication/sensing objectives. We describe an instantiation where a mobile robotic network is dynamically reconfigured to ensure high quality routes between static wireless nodes, which act as source/destination pairs for information flow. The ICP commands the robots towards evenly distributed inter-flow allocations, with intra-flow configu- rations that maximize route quality. The PCP then guides the robots via potential-based control to reconfigure according to ICP commands. This formulation, deemed Route Swarm, decouples information flow and physical control, generating a feedback between routing and sensing needs and robotic configuration. We demonstrate our propositions through simulation under a realistic wireless network regime.  I. I NTRODUCTION  T RADITIONAL   work   on   distributed   cooperation   in robotics has focused on position and motion configuration of collections of robots using localized algorithms, typically involving iterative exchange of state variables with single-hop neighbors, e.g., research on swarming, flocking, and formation control [1]–[3]. The current state of the art on distributed cooperation in robotics, focused on using only localized communication, can effectively solve problems in scenarios where there are relatively simple global application related objectives that do not change over time. However, due to the difficulties in translating multiple dynamically varying global objectives into local control actions, the problem of utilizing these algorithms in more complex sensing and communication networks remains an open question. A recent advance in distributed cooperation techniques offers promise in utilizing simple swarm-like mobility in coordinating more complex tasks. A typical problem when considering only local communications is that global connectivity might be lost. Recent research has shown that this global property can be recovered even through local interactions [4]–[7]. We believe that this recent advance, enabling global connectivity to be maintained at all times while a collection of robots is moving, provides fundamental new opportunities as complex tasks can be decomposed into simple sub components, while maintaining overall network connectivity.  R. K. Williams and B. Krishnamachari are with the Department of Electrical Engineering at the University of Southern California, Los Angeles, CA 90089 USA (rkwillia@usc.edu; bkrishna@usc.edu). A. Gasparri is with the Department of Engineering, University of Roma Tre, Via della Vasca Navale, 79. Roma, 00146, Italy (gasparri@dia.uniroma3.it).  Toward such goals, we first introduce at a high level a novel hybrid architecture for command, control, and coordination of networked robots for sensing and information routing applications, called INSPIRE (for   IN formation and   S ensing driven   P hys I cally   RE configurable robotic network). In the INSPIRE architecture, we propose two levels of control. At the low level there is a Physical Control Plane (PCP), and at the higher level is an Information Control Plane (ICP). At the PCP, iterative local communications between neighboring robots is used to shape the physical network topology by manipulating agent position through motion. At the ICP, more sophisticated multi-hop network algorithms enable efficient sensing and information routing (e.g., shortest cost routing computation, time slot allocation for sensor data collection, task allocation, clock synchronization, network localization, etc.). Unlike traditional approaches to distributed robotics, the introduction of the ICP provides the benefit of being able to scalably configure the sensing tasks and information flows in the network in a globally coherent manner even in a highly dynamical context by using multi-hop communications. As a proof of concept of the INSPIRE architecture, we detail a simple instantiation, in which the robotic network is dynamically reconfigured in order to ensure high quality routes between a set of static wireless nodes (i.e. a   flow ) while preserving connectivity, where the number and composition of information flows in the network may change over time. In solving this problem, we propose ICP and PCP components that couple connectivity-preserving robot-to-flow allocations, with communication optimizing positioning through distributed mobility control; a heuristic we call   Route Swarm . Finally, we demonstrate our propositions through simulation, illustrating the INSPIRE architecture and the Route Swarm heuristic in a realistic wireless network regime. II. S TATE OF THE   A RT  Distributed mobility control has been well investigated in the robotics community in recent years. In the context of multi- robot systems, distributed coordination protocols endow agents with simple local interactions, yet yield fundamentally useful collective behaviors. Coordination algorithms can broadly be classified in three families, that is swarming, flocking and formation control. Swarming aims at achieving an aggregation of the team through local simple interaction [1], flocking is a form of collective behavior of a large number of agents with an agreement in the direction of motion and velocity [2], while formation control dictates the team reach a desired formation shape [3]. For all of these objectives, potential- based control techniques represent an effective solution [8],  arXiv:1308.0037v3 [cs.SY] 7 Feb 2014
SUBMITTED TO THE IEEE INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS) 2014   2  combining provable performance with ease of control. As robots are usually required to either communicate or sense each other for all time, the connectivity maintenance of the network topology also needs to be addressed. Recent algorithms have been proposed to preserve the connectivity of the network topology over time, with approaches ranging from the control of addition and removal of edges [9], to the estimation and control of the algebraic connectivity [7]. The integration of mobile robotics and wireless networking is an emerging domain. Researchers have previously investigated deploying mobile nodes to provide sensor coverage in wireless sensor networks [10], [11]. In [4], the authors present a work to ensure connectivity of a wireless network of mobile robots while reconfiguring it towards generic secondary objectives. Go- ing beyond connectivity, recently, research has also addressed how to control a team of robots to maintain certain desired end-to-end rates while moving robots to do other tasks, referred to as the problem of maintaining network integrity [12]. This is done by interleaving potential-field based motion control and at the higher level an iterative primal-dual algorithm for rate optimization. All of these works point to the need for a hybrid control framework where low-level motion control can be integrated with a higher-level network control plane such as the INSPIRE architecture illustrated in this work 1 . Closely related to our work is an early paper that advo- cated motion control as a network primitive in optimizing network information flows [13]. Although related in spirit, we provide in this work fundamental advances in flow-to-flow reallocations, dynamic and flexible connectivity maintenance allowing network reconfigurability, and refined potential-based control that requires only inter-agent distance in optimizing intra-flow positioning. Another, more recent work [14], focuses on a single-flow setting, but considers a more detailed fading model communication environment, and a slightly different path metric. In contrast to [14], we make novel contributions in multi-flow optimization which we have shown requires a more sophisticated network-layer information control plane. Moreover, the motion control presented in [14] can also be integrated with and adopted as a component of the PCP in the INSPIRE architecture presented here. III. B ACKGROUND   M ATERIAL  To begin, we give an overview of the background material and assumptions necessary for our contributions in this work.  A. Agent and Interaction Models  Consider a system of   n   =   m   +   s   agents consisting of   m  mobile robots indexed by   I M   ,   { 1 , . . . , m } , and   s   static sensors indexed by   I S   ,   { m   + 1 , . . . , m   +   s } . The mobile robots are assumed to have single integrator dynamics   ̇ x i   =   u i   (1) where   x i , u i   ∈   R 2   are the position and the velocity control input for an agent   i   ∈ I M   , respectively. Assume that all agents  1 A complete characterization and general analysis of the INSPIRE architec- ture is the topic of our future work. i  j  k  l  Repel  Connection  Avoid  ρ 2  ρ 1  ρ 0  Attract  Discernment  Fig.   1.   Agent interaction model with radii determining sensing and communication   ‖ x ij   ‖   ≤   ρ 2 , neighbor decisions relative to constraints  ρ 1   <   ‖ x il ‖ ≤   ρ 2 , link establishment   ‖ x ik   ‖ ≤   ρ 1 , and collision avoidance  ‖ x ij   ‖ ≤   ρ 0 .  can intercommunicate in a proximity-limited way, inducing interactions (or topology) of a time varying nature. Specifically, letting   d ij   ,   ‖ x ij   ‖   ,   ‖ x i   −   x j   ‖   denote the distance between agents   i   and   j , and   ( i, j )   a link between connected agents, the spatial neighborhood of each agent is partitioned by defining concentric radii   ρ 2   >   ρ 1   >   ρ 0   as in Fig. 1, where we refer to   ρ 2 , ρ 1 , ρ 0   as the   interaction ,   connection , and   collision avoidance   radii, respectively. The radii introduce a   hysteresis  in interaction by assuming that links   ( i, j )   are established only after   d ij   ≤   ρ 1 , with link loss then occurring when   d ij   > ρ 2 , generating the annulus of   ρ 2   −   ρ 1   where   decisions   on link additions and deletions are made (c.f. Section V-A). The above spatial interaction model is formalized by the  undirected dynamic graph ,   G   = ( V ,   E ) , with vertices (nodes)  V   indexed by   I M   ∪ I S   (the agents), and edges   E ⊆ V × V  such that   ( i, j )   ∈ E ⇔   ( ‖ x ij   ‖ ≤   ρ 2 )   ∧   σ ij   , with switching signals [15]:  σ ij   =  {   0 ,   ( i, j )   / ∈ E ∧ ‖ x ij   ‖   > ρ 1  1 ,   otherwise   (2) where   ( i, i )   / ∈ E   (no self-loops) and   ( i, j )   ∈ E ⇔   ( j, i )   ∈ E  (symmetry) hold for all   i, j   ∈ V . Nodes with   ( i, j )   ∈ E   are called   neighbors   and the neighbor set for an agent   i   is denoted  N i   =   { j   ∈ V |   ( i, j )   ∈ E} .  B. Assumptions and Problem Formulation  From the set of static sensors   I S   we construct   f   information flows   indexed by   I F   ,   { n   + 1 , . . . , n   +   f   } , each consisting of source-destination pairs defining a desired flow of network information. For a given flow   i   ∈ I F   , we use the following notation:   F i   ∈ I S   × I S   represents the source and destination nodes for flow   i , with   F s i   ∈ I S   and   F d i   ∈ I S   representing source and destination indices, respectively. Further, for conve- nience we use notation   x s i   , x d i   ∈   R 2   to represent the position of the source and destination for the flow   i   ∈ I F   . The set of flow pairs is denoted   F   ,   {F 1 , . . . ,   F f   } . At any time, a subset of these static pairs is active, forming the set of active
SUBMITTED TO THE IEEE INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS) 2014   3  flows   I F   , calling for dynamic configurability of the hybrid network, our contribution in this work. Thus, at a high level our system objective is to facilitate information flow for each source/destination pair by configuring the mobile robots such that each flow is   connected   and is at least approximately optimal in terms of data transmission, and that the entire network itself  G   is connected to guarantee complete network collaboration.  Assumption 1 (Connectedness):   It is assumed that the loca- tions of the static nodes and the cardinality of mobile nodes is such that the set of connected graphs   G   that could be formed is non-empty, and that their communication graph is initiated to be in this set. To measure link quality towards optimizing a given flow, we assume that each   ( i, j )   ∈ E   has a weight parameter   w ij   that describes their cost with respect to transmitting information. A commonly used metric for link quality is   ETX , i.e. the expected number of transmissions per successfully delivered packet. This can be modeled as the inverse of the successful packet reception rate   λ ij   over the link. As the expected packet reception rate has been empirically observed and analytically shown to be a sigmoidal function of distance decaying from 1 to 0 as distance   d ij   is increased [16], it can be modeled as follows:  λ ij   ≈   1   −   1 (1 +   e − a ( d ij   − b ) )   (3) where   a, b   ∈   R +   are shape and center parameters depending on the communication range and the variance of environmental fading. Accordingly, the link weights   w ij   , if chosen to represent ETX, can be modeled as a convex function of the inter-node distance   d ij   :  w ij   =   1  λ ij  =   1 1   −   1 1+ e − a ( dij   − b )  = 1 +   e a ( d ij   − b )   (4) The cost for flow   k   ∈ I F   is then taken to be the sum of ETX values on the path of the flow, i.e.:  W k   =   ∑  ( i,j ) ∈E k F  w ij   (5) where we apply notation   G k F   = ( V k F   ,   E k F   )   as the graph defining the interconnection over flow   k   ∈ I F   (we give a concrete definition of flow   membership   in Section   IV-A ). Our problem in this work is then formalized as follows:  Problem 1 (Multi-flow optimization):   The   network-wide goal then is to find an allocation and configuration of mobile agents so as to minimize the total cost function 2   ∑ f k =1   W k  while maintaining both intra-flow connectivity (to guarantee information delivery) and inter-flow connectivity (to guarantee flow-to-flow information passage/collaboration). IV. I NFORMATION   C ONTROL   P LANE   (ICP) There are two key elements in solving Problem 1: on the one hand, within a given flow   k   ∈ I F   , for a given allocation of a certain number of mobile nodes to that flow, node configuration should minimize the flow cost   W k . On the other hand, the number of mobile nodes allocated to each flow should minimize  2 The negative of the cost could be treated as a utility function. We therefore equivalently talk about cost minimization or utility maximization.  the overall cost   ∑  k   W k . We first consider these optimizations ideally, in the absence of connectivity constraints. The first, per- flow element of the network optimization dictates the desired spatial configuration of allocated mobile nodes within a flow.  Theorem 4.1 (Equidistant optima):   For a fixed number of mobile nodes   m k   ,   |V k F   |   allocated to a given flow and arranged on the line between the source and destination of that flow, the arrangement which minimizes   (5)   is one where the nodes are equally spaced.  Proof:   This follows from the following general result: to minimize a convex   y ( − → z   ) s.t.   ∑   z i   =   c , the first order condition (setting the partial derivative of the Lagrangian with respect to each element   z i   to 0) yields that   ∂y z i   =   μ   where   μ   is the Lagrange multiplier. Now if   ∂y ∂z i   is the same for all   z i , then the solution to this optimization is to set   z i   =   c  | z |   , i.e. all variables are made to be the same. The   z i   in the above correspond to the inter-node distances  d ij   , and the   y   corresponds to   (5) . Since   w ij   is a convex function of distance between neighboring nodes, the path metric   W k   is a convex function of the vector of inter-node distances. Further, since the sum of all inter-node distances is the total distance between the source and destination of the flow, which are static, it is constrained to be a constant   d k . Since the weight of each link is the same function of the inter-node distance,  ∂W k  d ij   is the same for all pairs of neighboring nodes. Therefore the intra-flow optimization (i.e., choosing node positions to minimize   W k ) is achieved by a equal spacing of the nodes. The second, global cross-flow element of the network optimization dictates the number of mobile nodes allocated to each flow. The goal is to minimize the total network cost ∑  k   W k . Our approach to solving this optimization is motivated by the following observation: When the intra-flow locations of the robots are optimized to be equally spaced,   W k   is a function of the number of nodes   m k   allocated to flow   k , and the total number of nodes allocated to all flows is constrained by the total number of mobile nodes. If we could show that   W k   is a convex function, then to minimize the total network cost we need to identify the allocation at which the marginal costs for all flows are as close to equal as possible (ideally, if   m k   was a continuous quantity, they would all be equal at the optimum point, but due to the discrete nature of   m k   this is generally not possibly). In the following, for ease of analysis, we consider the continuous relaxation of the problem, allowing   m k   to be a real number, and hence   W k   to be a continuous function.  Theorem 4.2 (Convexity):   For any flow   k   that has been optimized to have the lowest possible cost   W k   (i.e. all   m k  mobile nodes are equally spaced),   W k   is a convex function of  m k .  Proof:  W k   =   ( m k   + 1) w  (   d k  m k   + 1  )  (6)  ⇒   W   ′  k   =   w  (   d k  m k   + 1  )  −   d k  m k   + 1   w ′  (   d k  m k   + 1  )  (7)  ⇒   W   ′′  k   =   w ′′  (   d k  m k   + 1  )   d 2  ( m k   + 1) 3   (8)
SUBMITTED TO THE IEEE INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS) 2014   4  Since the link weight function   w ( · )   is a convex function of the internode distance, we have that   w ′′ (   d k  m k   +1   )   is positive, and therefore we have that   W   ′′  k   is positive, hence   W k   is convex in  m k . Note that in reality   m k   is a discrete quantity, but the above argument suffices to show that   W k   is a discrete convex function of   m k   (since convexity over a single real variable implies discrete convexity over the integer discretization of the variable).  Theorem 4.3 (Optimality):   The   problem   of   minimizing ∑  k   W k ( m k )   subject to a constraint on   ∑  k   m k   can be solved optimally in an iterative fashion by the following greedy algorithm: at each iteration, move one node from the flow where the removal induces the lowest increase in cost to the flow where its addition would yield the highest decrease in cost, so long as the latter’s decrease in cost is strictly higher in absolute value than the former’s increase in cost (i.e. so long as the move serves to reduce the overall cost). We omit the detailed proof due to space constraint, but intu- itively, this algorithm works by moving the system iteratively towards the optimum by following the steepest gradient in terms of cost reduction for the movement of each node. Since the overall optimization problem is convex, there is only a single optimum, to which this algorithm will converge. Moreover, since there is a strict improvement in each step and there are a finite number of nodes, the algorithm reaches the optimal arrangement in a finite number of steps. Thus far, we have described both the intra-flow and inter-flow optimization problems in an ideal setting where both problems are convex optimization problems and as such can be solved exactly. However, in the robotic system we are considering there is one significant source of non-ideality/non-convexity, which is that the network must be maintained at all times in a connected configuration. This has two consequences. First, some of the mobile nodes may be needed as   bridge   nodes that do not participate in any flow and are instead used to maintain connectivity across flows. Second, the locations of some of the nodes even within each flow may be constrained in order to maintain the connectivity requirement. The solution for the constrained problem therefore may not correspond exactly to the solutions of the ideal optimization problems described above. We therefore develop a heuristic solution that we refer to as  Route Swarm , which is inspired by and approximates the ideal optimizations above but is adapted to maintain connectivity. Route Swarm has both an intra-flow and inter-flow component. As per the INSPIRE architecture, the intra-flow function is performed by the PCP, while the inter-flow function is performed by ICP. The ICP algorithm, shown as pseudocode as Algorithm 1, approximates the ideal iterative optimization described above by allocating mobile robots between flows greedily on the basis of greatest cost-reduction; to handle the inter-flow connectivity constraint, it incorporates a subroutine (Algorithm 2) to detect which nodes are not mobile because they must act as bridge nodes. Moreover, it also allocates any nodes that are no longer required to support an inactive flow to join active flows. And within each flow, the PCP algorithm (Algorithm 7) attempts to keep the robots as close to evenly  Algorithm 1   ICP optimization algorithm.  1:   procedure   I NFORMATION C ONTROL P LANE 2:   .   Detect initial flow members based on shortest paths:  3:   for   i   ∈ I F   do  4:   M ←   S HORTEST P ATH ( G ,   F i )  5:   end for  6:   .   Detect flow-to-flow bridges for connectivity:  7:   b   ←   D ETECT B RIDGES ( G ,   F ,   M )  8:   .   Detect best connectivity-preserving flow detachment:  9:   d   ←   B EST D ETACHMENT ( G ,   F ,   M , b )  10:   .   Compute flow attachment with most utility:  11:   a   ←   B EST A TTACHMENT ( F ,   M )  12:   .   Ensure optimizing reconfiguration exists (weighted by   β   ∈   R + ) :  13:   if   a > βd   then  14:   .   Optimal command is best detach/attach pair:  15:   return   C d   ←   a  16:   end if  17:   end procedure Algorithm 2   ICP bridge detection.  1:   procedure   D ETECT B RIDGES ( G ,   F ,   M )  2:   .   Initialize supergraph with nodes for each flow:  3:   S   ←   ( { i   ∈ I F   } ,   ∅ )  4:   .   Append nodes/edges for non-flow members:  5:   S   ←   A DD N ON F LOW M EMBERS ( S ,   F ,   M )  6:   .   Append edges for flow members:  7:   S   ←   A DD F LOW M EMBERS ( S ,   F ,   M )  8:   .   Bridges lie on shortest path between all flow pairs:  9:   return   b   ←   S HORTEST P ATHS ( S ,   F )  10:   end procedure  spaced as possible while taking into account the inflexibility of the bridge nodes. The details of the route swarm algorithm are given below.  A. The Route Swarm Heuristic  In solving the connectivity constrained version of the flow optimization of Theorems 4.1, 4.2, and 4.3, due to problem complexity we provide a heuristic algorithm to solve the inter- flow allocation problem, leaving the intra-flow optimization to the PCP (Section V). Algorithm 1 depicts the high-level components of the proposed heuristic, each of which is detailed in the sequel. To begin, we define the flow membership for an agent as   i   ∈ I M   as   M i   ∈ I F   , where the set of memberships is   denoted   as   M   ,   {M 1 , . . . ,   M n } .   We   denote   with  G i F   = ( V i F   ,   E i F   )   the graph defining the interconnection over flow   i   ∈   I F   of agents   j   ∈   I S   ∪ I M   with   i   ∈   M j   . Thus   we   have   V i F   =   { j   ∈   I S   ∪ I M   |   i   ∈   M j   }   and  ( j, k )   ∈ E i F   ⇔   ( i   ∈ M j   ∩ M k )   ∧   ( j   ∈ N k ) , with   k   ∈ I S   ∪ I M   . Notice that by definition   G i F   ⊆   G . We will also refer to the collection of flow graphs simply by   G F   . We also have flow neighbors defined as   N   F i   =   { j   ∈ N i   | M j   ∩ M i   6   =   ∅} . Furthermore, we denote with   D i   ∈ I M   the detachable agents  j   ∈   I M   for flow   i   ∈   I F   , i.e. those agents for which
SUBMITTED TO THE IEEE INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS) 2014   5 }   b i   = 1 ⇒ G   S  Fig.   2.   Example supergraph construction for a network with   f   = 2   flows,  s   = 4   static nodes, and   m   = 6   mobile robots. Flow membership is denoted by color and node shape. Notice that a multi-hop bridge is detected via the shortest path between flows.  reconfiguration does not impact network connectedness. The set of detachments is denoted by   D   ,   {D 1 , . . . ,   D f   } . Due to the system connectivity constraint, the ICP is not free to select   any   mobile agent for flow reallocation, specifically as intra-flow connectivity or overall flow-to-flow connectivity may be lost. Thus, the ICP must detect   bridges , i.e., mobile nodes whose reconfiguration might break flow-to-flow connectivity over the network, and also consider   safe detachments   (flow- to-flow motion), i.e., a node whose reconfiguration in the workspace does not impact the connectivity of the source flow. Respecting our connectivity constraint, we first detect initial flow membership by computing the shortest path (in terms of link cost) for each source/destination pair per flow by using for example Dijkstra’s algorithm (lines 3-5 of Algorithm 1). This defines the connected   backbone   for each flow implic- itly identifying the mobile nodes required to maintain flow- connectivity. Additionally, we have optimality of the connected flow backbones as we maximize the link utility (or minimize path costs) between source and destination nodes. In detecting bridge agents we follow the process outlined by Algorithms 2, 3, and 4, where we denote by   b i   ∈ { 0 ,   1 }   the status of agent   i   ∈ I S   ∪I M   as a connectivity preserving bridge, with   b   =   { b 1 , . . . , b n } . Briefly speaking, the primary problem of this process is the construction of a   supergraph , denoted  S   = ( V S ,   E S ) , defining the interconnection of the flows. In this way, we can identify nodes which are critical in defining the flow-to-flow connectivity over the system. Figure 2 depicts an example of supergraph construction. We first add one node for each flow in the system, and then we add a node for each non-flow member in the system that represents potential bridge candidates. Edges between non-flow members are preserved, while there is only one edge between any given non-flow member and the node which represents a flow in the supergraph. Bridges can then be simply detected as the members of the shortest path between any pair of nodes representing flows in the supergraph (e.g. Fig. 2), where connectivity is guaranteed by construction:  Proposition 4.1 (Bridge detection):   Consider   the   graph  G c   ⊆   G   obtained by including all the flow-members for any flow and the non-flow members belonging to any shortest path of the supergraph   S . Then   G c   is a spanning-graph representing a connected component of the graph   G .  Proof:   In order to prove this result we must show that both intra-flow and inter-flow connectedness is ensured. The  Algorithm 3   ICP supergraph non-flow member nodes/edges.  1:   procedure   A DD N ON F LOW M EMBERS ( S ,   F ,   M )  2:   .   Add nodes for each non-leaf, non-flow member:  3:   V +   ← { i   ∈ I M   |   ( M i   =   ∅ )   ∧   ( N i   ≥   2) }  4:   V S   ← V S   ∪ V +  5:   .   Add edges between non-flow members:  6:   E S   ← E S   ∪ { ( i, j )   |   ( i, j   ∈ V + )   ∧   ( j   ∈ N i ) }  7:   .   Add non-flow member to flow member edges:  8:   E S   ← E S   ∪ { ( i, j )   |   ( i   ∈ V + )   ∧   ( j   ∈ N i )   ∧   ( M j   6   =   ∅ ) }  9:   return   S  10:   end procedure Algorithm 4   ICP supergraph flow member edges.  1:   procedure   A DD F LOW M EMBERS ( S ,   F ,   M )  2:   .   Add edges due to multiple flow memberships:  3:   for   i   ∈ I M   | |M i | ≥   2   do  4:   .   Add an edge for every membership pair:  5:   E S   ← E S   ∪ { ( i, j )   |   j   ∈ I F   ∩ M i }  6:   end for  7:   return   S  8:   end procedure  former follows directly from the flow-membership definition while the latter follows from the connectedness between any pair of flows. After identifying the bridge agents that maintain flow- to-flow connectivity and the safely detachable agents per- flow (those which are not on the backbone), the ICP issues reconfiguration commands   C i   ∈ I F   to mobile agents   i   ∈ I M  indicating a desired flow membership towards optimizing inter- flow agent allocation. Specifically, as detailed in Algorithms 5 and 6, and as motivated by Theorem 4.3, we compute the safe detachment having the least in-flow utility, and couple it with the flow attachment (i.e. the addition of a contributing flow member) which improves most in terms of link utility and flow alignment (the primary contributions a mobile agent can have in information flow). This decision, if feasible (utility of attachment outweighs cost of detachment), is then passed to the PCP to execute the mobility necessary for reconfiguration, achieving our goal of dynamic utility improving and connectivity preserving network configurations. V. P HYSICAL   C ONTROL   P LANE   (PCP) The complementary component to the ICP in the INSPIRE architecture is the PCP which coordinates via state feedback, i.e.   { x ,   G ,   G F   } , to generate swarming behaviors that optimize the network dynamically in response to ICP commands. Our desire for generality in coordinating behaviors dictates that the PCP takes on a   switching   nature, associating a distinct  behavior controller   with each of a finite set of discrete agent states. Specifically, define  S i   ∈   B   ,   { SWARMING ,   RECONFIGURE }   (9) as the   behavior state   of a mobile robot   i   ∈   I M   , where  B   is the space of discrete agent behaviors. Here, when  S i   =   SWARMING , agent   i   acts to optimize its assigned flow
SUBMITTED TO THE IEEE INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS) 2014   6  Algorithm 5   ICP best flow detachment.  1:   procedure   B EST D ETACHMENT ( G ,   F ,   M , b )  2:   .   Non-member, non-bridges are detachable:  3:   for   ( i   ∈ I M   )   ∧   ( M i   =   ∅ )   ∧   ( ¬ b i )   do  4:   j   ←   Flow most contributed to by agent   i   (utility)  5:   M i   ←   j  6:   D j   ← D j   ∪   i  7:   end for  8:   .   Best detachment has least in-flow utility:  9:   return   argmin i ∈D   ( ∑  j ∈N   F i  w ij   )  10:   end procedure Algorithm 6   ICP best flow attachment.  1:   procedure   B EST A TTACHMENT ( F ,   M )  2:   .   Determine utility of attachment per flow:  3:   for   i   ∈ I F   do  4:   .   Weigh added node utility against flow path alignment:  5:   a i   ←   ( |V i F   |   + 1)   ∑  j ∈V i F  1 / ‖ x j   −   1 / 2( x s i   +   x d i   ) ‖  6:   end for  7:   return   argmax i ∈I F   ( a i )  8:   end procedure  M i . Otherwise, when   S i   =   RECONFIGURE , agent   i   traverses the workspace fulfilling global allocation commands   C i   from the ICP. In this work, the state machine that drives the switching of the behavior controllers is depicted in Algorithm 7. Each component comprising the PCP switching is detailed in the sequel.  A. Constraining Agent Interaction  In order to control the properties of   G   (i.e. connectivity) we exploit the   constrained interaction   framework proposed by Williams and Sukhatme in [9]. The constrained interaction framework acts through hysteresis   (2)   to regulate links   spatially  with simple application of attraction and repulsion to retain established links or reject new links with respect to topological constraints. Define the   discernment region   ‖ x ij   ‖ ∈   ( ρ 1 , ρ 2 ] , where agent   i   decides relative to system constraints (here connectivity) whether agent   j   is a   candidate   for link addition ( j / ∈ N i ) or deletion ( j   ∈ N i ), or if agent   j   should be attracted (retain   ( i, j )   ∈ E ) or repelled (deny   ( i, j )   / ∈ E ). Define   predi- cates   for link addition and deletion,   P   a ij   , P   d ij   :   V × V → { 0 ,   1 } , activated at   ρ 2   and   ρ 1 , respectively, that indicate constraint violations if the link   ( i, j )   were allowed to be either created or destroyed, i.e.   ‖ x ij   ‖   transits   ρ 1   or   ρ 2 . The predicates designate for the   i th agent the membership of nearby agents in link addition and deletion candidate sets   C a i   ,   C d i   , and attraction and repulsion sets   D a i   ,   D r i   . Link control is then achieved by choosing control   u i   having attractive and repulsive   potential fields   between members of   D a i   ,   D r i   , respectively. In particular, to regulate network topology spatially, we design the agent controls as follows:  u i   =   u e i   + u o i   −∇ x i    ∑  j ∈D a i  ψ a ij   +   ∑  j ∈D r i  ψ r ij   +   ∑  j ∈ Π i  ψ c  ij      (10)  Algorithm 7   PCP switching logic.  1:   procedure   P HYSICAL C ONTROL P LANE 2:   for   i   ∈ I M   do   .   Control mobile agents  3:   .   Reconfiguration Commanded:  4:   if   C i   6   =   ∅   then  5:   Set waypoint to target flow   C i   ∈ I F  6:   S i   ←   RECONFIGURE  7:   end if  8:   .   Flow members, to-flow maneuver:  9:   if   M i   6   =   ∅ ∧ S i   6   =   RECONFIGURE   then  10:   if   ¬ ( On Path Connecting Flow   M i )   then  11:   Set waypoint to flow   M i   ∈ I F  12:   S i   ←   RECONFIGURE  13:   else  14:   S i   ←   SWARMING  15:   end if  16:   end if  17:   .   Agent Behaviors:  18:   if   S i   =   SWARMING   then  19:   Run dispersion controller optimizing flow   M i  20:   end if  21:   if   S i   =   RECONFIGURE   then  22:   Run waypoint controller for reconfiguration  23:   if   At Waypoint   then  24:   S i   ←   SWARMING  25:   end if  26:   end if  27:   end for  28:   end procedure  with   potentials   ψ a ij   , ψ r ij   , ψ c ij   :   R +   →   R + , serving the pur- poses of attraction, repulsion, and collision avoidance, where  Π i   =   { j   ∈ V | ‖ x ij   ‖ ≤   ρ 0 }   is the collision avoidance set for agent   i . Further, each agent can also apply (based on  S i ) an exogenous objective (i.e. non-cooperative) controller  u e i   ∈   R 2   and an inter-agent coordination objective   u o i   ∈   R 2   (e.g. dispersion as will be seen in Section   V-D ). An appropriate attractive potential which we adopt for this work takes the following form:  ψ a ij   =   1  ρ 2 2   − ‖ x ij   ‖ 2   + Ψ a ,   if   ‖ x ij   ‖ ∈   [ ρ 1 , ρ 2 )   (11) where   Ψ a ( ‖ x ij   ‖ )   is chosen such that   (11)   is smooth over the   ρ 1  transitions. Similar to the attractive potential   (11)   , the repulsive potential takes the form  ψ r ij   =   1  ‖ x ij   ‖ 2   −   ρ 2 1  + Ψ r   ,   if   ‖ x ij   ‖ ∈   ( ρ 1 , ρ 2 )   (12) where   Ψ r   is chosen to guarantee   ψ r ij   is smooth over the   ρ 2  transition. Finally, a basic collision avoidance is given by potential  ψ c ij   =   1  ‖ x ij   ‖ 2   + Ψ c ,   if   ‖ x ij   ‖ ∈   (0 , ρ 0 )   (13) with   Ψ r   chosen to guarantee   ψ c ij   is smooth over the   ρ 0  transition.
SUBMITTED TO THE IEEE INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS) 2014   7  The attractive and repulsive potentials are constructed such that   ψ a ij   → ∞   as   d ij   →   ρ 2   and   ψ r ij   → ∞   as   d ij   →   ρ 1 , guar- anteeing link retention and denial, respectively, and allowing us through predicates   P   a ij   , P   d ij   to control desired properties of  G   (e.g. connectivity).  B. Connectivity Maintenance  Notice that in   maintaining   network connectivity, we require  only   link retention action, allowing us to immediately choose  P   a ij   ,   0 ,   ∀   i   ∈ I M   , j   ∈ I M   ∪ I S   ,   ( S i ,   S j   )   ∈   B   ×   B   (14) for the link addition predicates, effectively allowing link additions to occur between all interacting agents across all network states 3 . Now, in accordance with Algorithm 7, the link deletion predicates are given by:  P   d ij   ,            1 ,   ( S i   ∨ S j   =   SWARMING )   ∧  (( M i   ∩ M j   6   =   ∅ )   ∨   ( b i   ∨   b j   = 1)) 0 ,   otherwise (15) where by assumption   i, j   ∈ I M   , i.e. only mobile agents apply controllers. We choose link retention   (15)   to guarantee that connectivity is maintained both within flows across   G F   , and from flow to flow across bridge agents over the supergraph   S , noting that idle agents with   M i   =   ∅   and reconfiguring agents with   S i   =   RECONFIGURE   are free to lose links as they have been deemed redundant by the ICP with respect to network connectivity.  C. Flow Reconfiguration Maneuvers  While maintaining connectivity as above, each agent further acts according to ICP reconfiguration commands towards optimizing inter-flow allocations. Specifically, in response to   command   C i ,   agent   i   enters   the   reconfiguration   state  S i   ←   RECONFIGURE , and begins to apply a   waypoint  controller as follows (c.f. lines 4-7 of Algorithm 7). When  S i   =   RECONFIGURE , agent   i   applies exogenous objective controller  u e i   ,   x w   −   x i  ‖ x w   −   x i ‖ −    ̇ x i   (16) where   x w   ∈   R 2   is the target waypoint calculated as the midpoint of target flow   C i . The input   (16)   is a velocity damped waypoint seeking controller, having unique critical point   x i   →   x w   (i.e. a point at which   u e i   =   0 ), guaranteeing that the target intra-flow positioning (and thus membership) for agent   i   is achieved. As the convergence of   x i   →   x w   is asymptotic in nature, to guarantee finite convergence and state switching, we apply a saturation   ‖ x w   −   x i ‖ ≤    w   with   0   <  w   <<   1   to detect waypoint convergence, initiating a switch to   S i   ←   SWARMING  as in lines 23-25 of Algorithm 7.  3 Although in this work we allow all link additions, link addition control could be useful for example in regulating neighborhood sizes to mitigate spatial interference, or to disallow interaction between certain agents.  D. Intra-Flow Controllers  Once the ICP has assigned flow memberships   M i   ∀   i   ∈ I M  and all   commanded   reconfigurations   C i   have been completed, the mobile agents begin to seek to optimize the flow to which they are a member. First, we assume that flow mem- bers must configure along the line segment connecting flow source/destination pairs, yielding in the case of proximity- limited communication, a line-of-sight or beamforming style heuristic. The membership of an agent   i   ∈ I M   to a flow  j   ∈ M i   thus initiates a check to determine if   x i   lies on the flow path   x s j   +   τ x d j   , within a margin   0   <  F   <<   1   (c.f. lines 9- 16, Algorithm 7). To do so, the projection of   x i   onto   x s j   +   τ x d j  is determined first by computing  τ   ,   ( x i   −   x s j   )   ·   ( x d j   −   x s j   )  ‖ x d j   −   x s j   ‖ 2   (17) defining whether the projection will lie within or outside of the flow path. Then we have the saturated projection  x i →F j   =            x s j   −   ατ   ( x d j   −   x s j   ) ,   τ <   0  x d j   −   ατ   ( x d j   −   x s j   ) ,   τ >   1  x s j   +   τ   ( x d j   −   x s j   ) ,   τ   ∈   (0 ,   1)  (18) where   α >   0   is a biasing term such that the projection does not intersect   x s j   or   x d j   . We then have the state transition condition  ‖ x i →F j   −   x i ‖ ≤    F   (19) which when satisfied gives   S i   ←   SWARMING   (line 14, Algo- rithm 7, and described below). If condition   (19)   is not satisfied, agent   i   transitions to state   S i   ←   RECONFIGURE , applying waypoint controller   (16)   with   x w   ,   x i →F j   , guaranteeing a reconfiguration, in a shortest path manner, to a point on the line segment defining its assigned flow   M i . Finally,   when   an   agent   i   is   in   the   swarming   state  S i   =   SWARMING   (lines   18-20,   Algorithm   7),   after   all necessary reconfigurations have been made (either by the ICP via   C i   or internally by flow alignment), a   dispersive   inter- neighbor controller is applied in order to optimize the assigned flow. Specifically, each swarming agent   i   ∈ I M   applies a coordination controller (regardless of bridge status   b i ):  u o i   ,   −∇ x i  ∑  j ∈N   A i  1  ‖ x ij   ‖ 2   −   ∑  j ∈N   S i  ∇ x j  1  ‖ x ji ‖ 2   (20) where  N   A i   ,   { j   ∈ N i   |   ( M j   ∩ M i   6   =   ∅ )   ∧  [( S j   =   SWARMING )   ∨   ( j   ∈ I S   )] }   (21) is the set of neighbors that share membership in flow   M i , and who are either   in flow   and   actively   swarming (i.e. by condition (19)   ), or are a static source/destination node. Further, we define  N   S i   ,   { j   ∈ N   A i   |   j   ∈ I S   }   (22) as the set of static in flow neighbors for which compensation (Remark 5.1, below) must be applied. Controller   (20)   dictates that mobile flow members disperse equally only with fellow flow members and also with the source/destination nodes of their assigned flow   M i .
SUBMITTED TO THE IEEE INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS) 2014   8 Time = 0.00 / 1500.00 30   40   50   60 50 55 60 65 70 75 80  (a) Time = 100.00 / 1500.00 30   40   50   60 50 55 60 65 70 75 80   (b) Time = 450.00 / 1500.00 30   40   50   60 50 55 60 65 70 75 80   (c) Time = 650.00 / 1500.00 30   40   50   60 50 55 60 65 70 75 80  (d) Time = 850.00 / 1500.00 30   40   50   60 50 55 60 65 70 75 80   (e) Time = 1500.00 / 1500.00 30   40   50   60 50 55 60 65 70 75 80   (f) Fig.   3.   Network progression for the simulated execution described in Section VI. Flow membership is indicated by color, where square nodes are the flow backbone, triangle nodes are redundant with respect to connectivity, and diamond nodes are bridges. Note that flow   F 3   is initially inactive and becomes active at   t   = 450 , while   F 2   is initially active and deactivates at   t   = 850 .  Remark 5.1 (Energy compensation):   The inclusion of sup- plementary control terms for interactions with static neighbors  j   ∈ N i   ∩ I S   in   (20)   acts to retain the inter-agent symmetry required for the application of constrained interaction [9], specifically as static agents do not contribute to the system energy. We refer to this control action as   energy compensation , an idea that will evolve in future work by Williams and Gasparri to treat systems with asymmetry in sensing, communication, or mobility. While dispersive controllers generally yield equilibria in which inter-agent distant is maximized (up to   ρ 2 ) [17], as each flow is constrained by static source/destination nodes, the dispersion   (20)   generates our desired equidistant intra-flow configuration as formalized below:  Proposition 5.1 (Equidistant dispersion):   Consider the ap- plication of coordination objective   (20)   to a set of mobile agents   i   ∈ I M   within the context of interaction controller   (10) , each sharing membership to a flow   k   ∈ I F   , i.e.   M i   =   k,   ∀   i . It follows that at equilibrium the agents are configured such that the   equidistant spacing   condition  ‖ x ij   ‖ → ‖ x d k   −   x s k ‖ |V k F   | −   2   ,   ∀   i   |   j   ∈ N   F i   (23) holds asymptotically over flow   k . A formal proof is beyond the scope of this work 4 , however note that our controllers operate using   only   inter-agent distance, an advancement beyond related works such as [13]. VI. S IMULATION   R ESULTS  In this section, we present a simulated execution of our described INSPIRE proof-of-concept, Route Swarm. Consider a system operating over a workspace in   R 2 , having   n   = 15   total agents,   m   = 9   of which are mobile and   s   = 6   of which are static information source/destinations. Assume we have   f   = 3  flows (green, red, and blue indicate flow membership), with the initial system configuration depicted as in Fig. 3a (notice that   G   is initially connected), with the system dynamics shown in Fig. 3b through 3f. We simulate a scenario in which   F 3   is initially   inactive   (gray), allowing the ICP to optimize agent allocation over only   f   = 2   flows, as in Fig. 3b to 3c. By Fig. 3c, flows   F 1   and   F 2   have been assigned an evenly distributed allocation of mobile agents, where the PCP has provided equidistant agent spacing for each flow. At this same time (650 time steps), the flow   F 3   activates, initiating a reconfiguration by  4 Informally, an energy balancing argument establishes the result.
SUBMITTED TO THE IEEE INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS) 2014   9 F 3  F 2  F 1  Flow Utility Simulation Time  0   500   1000   1500 0 2 4 6 8 10 12  Fig.   4.   Flow utilities for the simulated execution described in Section VI.  the ICP to optimize the newly added flow, as in Fig. 3d, noting that initially in Fig. 3c,   F 3   is poorly served by the network configuration. Finally, in Fig. 3e, flow   F 2   is deactivated, forcing another reconfiguration yielding the equilibrium shown in Fig. 3f. The per-flow utility over the simulation, given for a flow   i   ∈ I F   by   ∑  ( j,k ) ∈E |   i ∈M j   ∩M k   w ij   (the sum of the link utilities associated with each flow), is depicted in Fig. 4. Finally, to better illustrate the dynamics of our proposed algorithms, we direct the reader to   http://anrg.usc.edu/www/Downloads   for the associated simulation video.  Remark 6.1 (Dynamic vs. static):   The   optimizations   pro- posed in this work are advantageous in terms of dynamic information flow needs and changing system objectives, when compared to static solutions. On flow switches, static place- ments fail to fulfill the information flow needs of the altered system configuration. Additionally, our methods allow for dynamics in   I M   itself, as the ICP can adaptively reconfigure the system to utilize the available agents across the network flows. VII. C ONCLUSION  In this paper, we illustrated a novel hybrid architecture for command, control, and coordination of networked robots for sensing and information routing applications, called INSPIRE (for INformation and Sensing driven PhysIcally REconfigurable robotic network). INSPIRE provides of two control levels, namely Information Control Plane and Physical Control Plane, so that a feedback between information and sensing needs and robotic configuration is established. An instantiation was provided as a proof of concept where a mobile robotic network is dynamically reconfigured to ensure high quality routes between static wireless nodes, which act as source/destination pairs for information flow. Future work will be focused on the validation of the proposed architecture in a real-world scenario having mobile robotic interaction with a sensor network testbed. R EFERENCES [1]   V. Gazi and K. Passino, “Stability analysis of swarms,”   Automatic Control, IEEE Transactions on , vol. 48, no. 4, pp. 692–697, 2003. [2]   R. Olfati-Saber, “Flocking for multi-agent dynamic systems: algorithms and theory,”   Automatic Control, IEEE Transactions on , vol. 51, no. 3, pp. 401–420, 2006. [3]   J. Fax and R. Murray, “Information flow and cooperative control of vehicle formations,”   Automatic Control, IEEE Transactions on , vol. 49, no. 9, pp. 1465–1476, 2004. [4]   M. M. Zavlanos and G. J. Pappas, “Distributed connectivity control of mobile networks,”   Trans. Rob. , vol. 24, no. 6, pp. 1416–1428, Dec. 2008. [Online]. Available: http://dx.doi.org/10.1109/TRO.2008.2006233 [5]   R. K. Williams and G. S. Sukhatme, “Locally Constrained Connectivity Control in Mobile Robot Networks,” in   IEEE International Conference on Robotics and Automation , 2013. [6]   P. Yang, R. A. Freeman, G. J. Gordon, K. M. Lynch, S. S. Srinivasa, and R. Sukthankar, “Brief paper: Decentralized estimation and control of graph connectivity for mobile sensor networks,”   Automatica , vol. 46, no. 2, pp. 390–396, Feb. 2010. [7]   L. Sabattini, C. Secchi, N. Chopra, and A. Gasparri, “Distributed control of multirobot systems with global connectivity maintenance,”   Robotics, IEEE Transactions on , pp. 1–6, 2013. [8]   D. Dimarogonas and K. Kyriakopoulos, “Connectedness preserving distributed swarm aggregation for multiple kinematic robots,”   Robotics, IEEE Transactions on , vol. 24, no. 5, pp. 1213–1223, 2008. [9]   R. Williams and G. Sukhatme, “Constrained interaction and coordination in proximity-limited multiagent systems,”   Robotics, IEEE Transactions on , pp. 1–15, 2013. [10]   G. Wang, G. Cao, P. Berman, and T. La Porta, “Bidding protocols for deploying mobile sensors,”   Mobile Computing, IEEE Transactions on , vol. 6, no. 5, pp. 563–576, 2007. [11]   A. Gasparri, B. Krishnamachari, and G. S. Sukhatme, “A framework for multi-robot node coverage in sensor networks,”   Annals of Mathematics and Artificial Intelligence , vol. 52, no. 2-4, pp. 281–305, Apr. 2008. [12]   N. Chatzipanagiotis, M. M. Zavlanos, and A. Petropulu, “A distributed algorithm for cooperative relay beamforming,” in   American Control Conference , Washington, DC, June 2013. [13]   D. K. Goldenberg, J. Lin, A. S. Morse, B. E. Rosen, and Y. R. Yang, “Towards mobility as a network control primitive,” in   Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing , ser. MobiHoc ’04.   ACM, 2004, pp. 163–174. [14]   Y. Yan and Y. Mostofi, “Robotic router formation in realistic communi- cation environments,”   Robotics, IEEE Transactions on , vol. 28, no. 4, pp. 810–827, 2012. [15]   M. Ji and M. Egerstedt, “Distributed Coordination Control of Multiagent Systems   While   Preserving   Connectedness,”   IEEE   Transactions   on Robotics , vol. 23, no. 4, pp. 693–703, 2007. [16]   M. Z. Zamalloa and B. Krishnamachari, “An analysis of unreliability and asymmetry in low-power wireless links,”   ACM Trans. Sen. Netw. , vol. 3, no. 2, Jun. 2007. [Online]. Available: http://doi.acm.org/10.1145/ 1240226.1240227 [17]   D. Dimarogonas and K. Kyriakopoulos, “Inverse agreement protocols with application to distributed multi-agent dispersion,”   Automatic Control, IEEE Transactions on , vol. 54, no. 3, pp. 657–663, 2009.