arXiv:1402.5639v1 [cs.SY] 23 Feb 2014  Decentralized Rendezvous of Nonholonomic Robots with  Sensing and   Connectivity Constraints  Zhen Kan   a , Justin Klotz   a , Eduardo L. Pasiliao Jr   b , John M. Shea   c , Warren E. Dixon   a ,  a Department of Mechanical and Aerospace Engineering, University of Florida, Gainesville, USA  b Munitions Directorate, Air Force Research Laboratory, Eglin AFB, FL 32542, USA.  c Department of Electrical and Computer Engineering, University of Florida, Gainesville, USA  Abstract  A group of wheeled robots with nonholonomic constraints is considered to rendezvous at a common specified setpoint with a desired orientation while maintaining network connectivity and ensuring collision avoidance within the robots. Given communication and sensing constraints for each robot, only a subset of the robots are aware or informed of the global destination, and the remaining robots must move within the network connectivity constraint so that the informed robots can guide the group to the goal. The mobile robots are also required to avoid collisions with each other outside a neighborhood of the common rendezvous point. To achieve the rendezvous control objective, decentralized time-varying controllers are developed based on a navigation function framework to steer the robots to perform rendezvous while preserving network connectivity and ensuring collision avoidance. Only local sensing feedback, which includes position feedback from immediate neighbors and absolute orientation measurement, is used to navigate the robots and enables radio silence during navigation. Simulation results demonstrate the performance of the developed approach.  1   Introduction  Distributed   cooperative control   of   networked multi- agent systems has attracted considerable interest. One particular cooperative control problem is the rendezvous problem, where a number of agents arrive at a predefined destination simultaneously, ideally using limited infor- mation from the environment and team members. Some example applications of the rendezvous problem are co- operative strike and cooperative jamming in [1] and [2]. In the cooperative strike scenario, multiple strikes are executed on a target simultaneously by firing from dif- ferent locations. In cooperative jamming of a wireless communication network with eavesdroppers, noisy sig- nals are transmitted to jam the eavesdroppers at the  Email addresses:   kanzhen0322@ufl.edu   (Zhen Kan),  jklotz@ufl.edu   (Justin Klotz),   pasiliao@eglin.af.mil  (Eduardo L. Pasiliao Jr),   jshea@ece.ufl.edu   (John M. Shea),   wdixon@ufl.edu   (Warren E. Dixon).  1   This research is supported in part by NSF award numbers 1161260, 1217908, and a contract with the AFRL Mathe- matical Modeling and Optimization Institute. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsoring agency.  same time when the source transmits the message sig- nal. Spacecraft docking, air-to-air refueling, and the in- terception of an incoming missile can also be considered as rendezvous problems. In these applications, coordina- tion and collaboration are crucial to performance, and agents are required to communicate and coordinate their movements with others to achieve rendezvous. Several rendezvous results are reported in [3–5]. Conver- gence to a common point for a group of autonomous mo- bile agents is studied in [3]. In [4] and [5], synchronized and unsynchronized strategies are developed to drive mobile agents to a single unspecified location by using only position feedback from its sensing regions. A com- mon assumption in [3–5] is that the network remains con- nected during the motion evolution, allowing constant interaction between agents. However, the assumption of network connectivity is not always practical. Typically, each agent can only make decisions based on the local information from immediate neighbors within a certain region due to sensing and communication constraints. Since communication/sensing links generally depend on the distance between agents, agent motion may cause the underlying network to disconnect. If the network discon- nects, certain agents may no longer be able to commu-  Preprint submitted to Automatica   August 13, 2018
nicate and coordinate their motion, leading to a failure of cooperative tasks. Recent results such as [6–11] have focused on maintain- ing network connectivity when performing rendezvous tasks. A circumcenter algorithm is proposed in [6] to avoid the loss of existing links between agents. In [7–9] a potential field-based distributed approach is devel- oped to prevent partitioning in the underlying graph by using local information from each agent’s immedi- ate neighbors. The results in [10] provide a connectivity- preserving protocol for rendezvous of a discrete-time multi-agent system, and a hybrid dynamic rendezvous protocol is designed in [11] to address finite-time ren- dezvous problems while preserving network connectivity. However, most of the aforementioned works only con- sider linear motion models. Although agents with non- holonomic kinematics are considered in [7], like other results such as [3–5, 11], the agents can only converge to a destination determined by the initial deployment. A dipolar navigation function was proposed and a dis- continuous time-invariant controller was developed for a multi-robot system in [12] to perform nonholonomic navigation for networked robots. The dipolar navigation function is a particular class of potential functions, which is developed from [13] and [14] such that the negative gradient field does not have local minima, and the closed- loop navigation function guarantees convergence to the global minimum. The result in [12] was then extended to navigate a nonholonomic system in three dimensions in [15]. Other recent results focused on nonholonomic systems with various cooperative tasks such as formation control and flocking are reported in [16–19]. However, network connectivity is not considered in [12, 15–19]. The rendezvous problem for mobile robots with non- holonomic constraints is studied in this work, and the objective is to reach a common specified setpoint with a desired orientation. Only a small subset of robots (i.e., informed agents) are assumed to be equipped with ad- vanced sensors (e.g., GPS) and provided with global knowledge of the destination, while the remaining robots (i.e., followers) only have a range sensor (e.g., a passive range sensor such as a camera, or active sensors such as sonar, laser, or radar), which provides local feedback of the relative trajectory of other robots within a limited sensing region. Since the follower robots are not aware of the global position of the destination, they have to stay connected with the informed agents when perform- ing rendezvous. To avoid collision among robots, the workspace is divided into a collision-free region and a rendezvous region. Particularly, the robots are required to avoid collisions with other robots outside a neigh- borhood of the common goal. Based on our prelimi- nary efforts in [20–22], a decentralized time-varying con- troller, using only local sensing feedback from its im- mediate neighbors, is designed to stabilize the robots at the specified destination while preserving network con- nectivity and ensuring collision avoidance. The devel- oped decentralized controller only uses local sensing in- formation and no inter-agent communication is required (i.e., communication-free global decentralized group be- havior). Although network connectivity is maintained so that radio communication is available when required for various tasks, communication is not required for nav- igation. Using the navigation function framework, the multi-robot system is guaranteed to rendezvous at a common destination with a desired orientation without being trapped by local minima from almost all initial conditions, excluding a set of measure zero. Compared to [22] where the formation control for a group of agents with fully actuated dynamics is investigated, networked mobile robots with nonholonomic constraints are con- sidered in this work. Unlike our centralized result in [20] or our preliminary result in [21] in which all the robots are required to know the goal destination and only undi- rected interaction between robots are considered, the current result models the interaction among robots as a digraph, and only requires a subset of the robots (i.e., one or more) to have knowledge of the global position of the destination and the desired orientation. This advance- ment reduces required resources and sensor loads on the remaining robots. Within this setting, the informed sub- set of robots can perform a task-level controller, while the remaining robots just execute a local interaction- based strategy. Moreover, the developed controller al- lows the robots to rendezvous at any desired destination, versus an unspecified destination determined by their initial deployment as in [3–5,7,11]. The result can also be extended by replacing the objective function in the nav- igation function to accommodate different tasks, such as formation control, flocking, and other applications.  2   Problem Formulation  Consider   N   networked mobile robots operating in a workspace   F   , where   F   is a bounded disk area with ra- dius   R w   . Each robot in   F   moves according to the follow- ing nonholonomic kinematics:   ̇ q i   =       cos   θ i   0 sin   θ i   0 0   1      [   v i   ( t )  ω i   ( t )  ]  , i   = 1 ,   · · ·   , N   (1) where   q i   ( t )   ,  [  p T i   ( t )   θ i   ( t )  ] T  ∈   R 3   denotes the states of robot   i,   with   p i   ( t )   ,  [  x i   ( t )   y i   ( t )  ] T  ∈   R 2   denoting the position of robot   i , and   θ i   ( t )   ∈   ( − π, π ]   denoting the robot orientation with respect to the global coordinate frame in   F   . In (1),   v i   ( t )   , ω i   ( t )   ∈   R   are the control inputs that represent the linear and angular velocity of robot   i,   respectively. The subsequent development is based on the assumption that all robots have equal actuation capabilities and each  2
robot has sensing and communication limitations en- coded by a disk area with radius   R,   which indicates that two moving robots can sense and communicate with each other as long as they stay within a distance of   R.   We also assume that only a subset of the robots, called informed robots, are provided with knowledge of the destination, while the other robots can only use local state feedback (i.e., position feedback from immediate neighbors and absolute orientation measurement). Furthermore, while multiple informed robots may be used for rendezvous, the analysis and results of this work are focused on a single informed robot. The techniques proposed in this work could be extended to the case of multiple informed robots by using containment control, as explained in Re- mark 2. The interaction among the robots is modeled as a directed graph   G   ( t ) = ( V ,   E ( t )) , where the node set  V   =   { 1 ,   · · ·   , N   }   represents the group of robots, and the edge set   E ( t )   denotes time-varying edges. The set of in- formed robots and followers are denoted as   V L   and   V F   , respectively, such that   V L   ∪ V F   =   V   and   V L   ∩ V F   =   ∅ . Let   V L   =   { 1 }   and   V F   =   { 2 ,   · · ·   , N   } . A directed edge  ( i, j )   ∈ E   in   G   ( t )   exists between node   i   and   j   if their relative distance   d ij   ,   ‖ p i   −   p j   ‖ ∈   R +   is less than   R . The directed edge   ( i, j )   indicates that node   i   is able to access the states (i.e., position and orientation) of node  j   through local sensing, but not vice versa .   Accordingly, node   j   is a neighbor of node   i   (also called the parent of node   i ), and the neighbor set of node   i   is denoted as  N i   =   { j   |   ( i, j )   ∈ E} , which includes the nodes that can be sensed. A directed spanning tree is a directed graph, where every node has one parent except for one node, called the root, and the root node has directed paths to every other node in the graph. Since the follower robots are not aware of the destination, they have to stay con- nected with the informed robot either directly or indi- rectly through concatenated paths, such that the knowl- edge of the destination can be delivered to all the nodes through the connected network. Hence, to complete the desired tasks, maintaining connectivity of the underly- ing graph is necessary. Collision avoidance among robots has not been consid- ered for rendezvous problems in existing literature (e.g., [4–9]), since it conflicts with the objective of meeting at a common goal. To enable collision avoidance in this work, the workspace   F   is divided into a collision-free region   Ω c  and a rendezvous region   Ω r   , such that   Ω c   ∪   Ω r   =   F   . The rendezvous region   Ω r   is a bounded disk area with radius  R r   centered at the common destination   p ∗ , while the re- maining area in   F   is the collision-free region   Ω c . Assume that the workspace   F   and the rendezvous region   Ω r   sat- isfy that   R w   ≫   R r   and   R r   > R   ( N   −   1) . The classical rendezvous problem enables the robots to rendezvous at  p ∗   with a desired orientation   θ ∗   in   Ω r , we additionally constraint this model by requiring collision avoidance among robots outside the neighborhood of common   p ∗  (i.e.,   Ω c ). The main contribution of this work is to derive a set of distributed controllers using only local informa- tion (i.e., position feedback from immediate neighbors and the absolute orientation measurement) to perform rendezvous, ensure network connectivity, and avoid col- lisions. To achieve these goals, the following assumptions are required in the subsequent development.  Assumption 1   The initial graph   G   (0)   has a directed spanning tree with the informed node as the root.  Assumption 2   The destination   p ∗   and desired orienta- tion   θ ∗   are achievable, which implies that   p ∗   and   θ ∗   do not coincide with some unstable equilibria (i.e., saddle points).  3   Control Design  3.1   Dipolar Navigation Function  Artificial potential field-based methods that use attrac- tive and repulsive potentials have been widely used to control multi-robot systems. Due to the existence of lo- cal minima when attractive and repulsive force are com- bined, robots can be trapped by local minima and are not guaranteed to reach the global minimum of the po- tential field. A navigation function is a particular cate- gory of potential functions where the potential field does not have local minima and the negative gradient vector field of the potential field guarantees almost global con- vergence to a desired destination, along with (guaran- teed) collision avoidance, if the initial conditions do not lie within the sets of measure zero. Formally, a naviga- tion function is defined as follows:  Definition 1   [13] [14] Let   F   be a compact connected analytic manifold with a boundary   ∂ F   , and   q d   be a goal point in the interior of   F   . A mapping   φ   :   F →   [0 ,   1]   is a Navigation Function, if it satisfies the following condi- tions: 1) smooth on   F   (at least a   C 2   function); 2) admis- sible on   F   , (uniformly maximal on the manifold bound- ary   ∂ F   and constraint boundary); 3) polar on   F   ,   ( q d   is a unique minimum); and 4) a Morse function, (critical points of the navigation function are non-degenerate).  The second condition in Definition 1 establishes that the generated trajectories are collision-free, since the result- ing vector field is transverse to the boundary of   F   . The third point indicates that, using a polar function on a compact connected manifold with a boundary, all initial conditions are either brought to a saddle point or to the unique minimum   q d . The requirement that the naviga- tion function is a Morse function ensures that the initial conditions that bring the system to saddle points are sets of measure zero [13]. Given this property, all initial conditions not within sets of measure zero are brought to the unique minimum. The navigation function introduced in [13] and [14] en- sures global convergence of the closed-loop system; how-  3
−5  0  5  −5  0  5  0  0.5  1  X axis Y axis  Potential Value  Figure 1. An example of a dipolar navigation function with a workspace of   R w   = 5   and destination located at the origin with a desired orientation   θ ∗   = 0 .  ever, the approach is not suitable for nonholonomic sys- tems, since the feedback law generated from the gradient of the navigation function can lead to undesirable be- haviors, which may be overcome by extending the orig- inal navigation function to a Dipolar Navigation Func- tion in [23] and [24]. The flow lines created in the poten- tial field resemble a dipole, so that the flow lines are all tangent to the desired orientation at the origin and uti- lized by the vehicle to achieve the desired orientation. An example of the dipolar navigation is shown in Fig. 3.1, where the potential field has a unique minimum at the destination (i.e.,   p ∗   = [0 ,   0] T   and   θ ∗   = 0 ) ,   and achieves the maxima at the workspace boundary of   R w   = 5 . Note that the surface   x   = 0   divides the workspace into two parts and forces all the flow lines to approach the desti- nation parallel to the   y -axis. Inspired by the work in [23] and [24], the control strat- egy here is to develop a dipolar navigation function for the informed robot, which creates a feasible nonholo- nomic trajectory for the nonholonomic robot and guar- antees the achievement of the specified destination with a desired orientation, while other follower robots aim to achieve consensus with the informed robot and main- tain network connectivity by using only local interaction with neighboring robots. Following this idea, the dipo- lar navigation function is designed for the informed node  i   ∈ V L   as   φ d i   ( t ) :   F →   [0 ,   1] , φ d i   =   γ d  ( γ α d   +   H d   ·   β d ) 1 /α   ,   (2) where   α   ∈   R +   is a tuning parameter. The goal func- tion   γ d   ( t ) :   R 2   →   R +   in (2) encodes the control objec- tive of achieving the desired destination, which is spec- ified by the distance from   p i   ( t )   ∈   R 2   to the destination  p ∗   ∈   R 2 ,   and is designed as   γ d   =   ‖ p i   ( t )   −   p ∗ ‖ 2 . The factor   H d   ( t )   ∈   R +   in (2) creates a repulsive potential to align the trajectory of node   i   at the destination with the desired orientation. The repulsive potential factor is designed as  H d   =   ε nh   +  (  ( p i   −   p ∗ ) T   ·   n d  ) 2  ,   (3) where   ε nh   is   a   small   positive   constant,   and   n d   =  [  cos ( θ ∗ ) sin ( θ ∗ )  ] T  ∈   R 2 .   A small disk area with radius  δ 1   < R   centered at node   i   is denoted as a collision re- gion. To prevent a potential collision between node   i   and the workspace boundary, the function   β d   :   R 2   →   [0 ,   1]  in (2) is designed as  β d   =   1  1 +   e −   2  δ 1   log (   1 − ǫ  ǫ   )( d i 0 −   1  2   δ 1   )   (4) where   0   < ǫ   ≪   1   is a positive constant, and   d i 0   ,  R w   − ‖ p i ‖ ∈   R   is the relative distance of node   i   to the workspace boundary. Since   γ d   and   β d   in (2) are guaranteed to not be zero simultaneously by Assumption 2, the navigation func- tion candidate in (2) achieves its minimum of   0   when  γ d   = 0   and its maximum of   1   when   β d   = 0 . Our previous work in [22] proves that the original navigation function with the form of   φ i   =   γ i  ( γ α i   + β i ) 1 /α   is a qualified naviga- tion function. It is also shown in [12] that the naviga- tion properties are not affected by the modification to a dipolar navigation with the design of (3), as long as the workspace is bounded,   H d   in (2) can be bounded in the workspace, and   ε nh   is a small positive constant. As a re- sult, the decentralized navigation function   φ d i   proposed in (2) can be proven to be a qualified navigation function by following a similar procedure in [12] and [22]. From the properties of the navigation function, it is known that almost all initial positions (except for a set of mea- sure zero points) asymptotically approach the desired destination. To achieve consensus with the informed node while en- suring network connectivity and collision avoidance, a local interaction rule is designed for each follower node  i   ∈ V F   as   φ f i   ( t ) :   F →   [0 ,   1] , φ f i   =   γ i  ( γ α i   +   β i ) 1 /α   ,   (5) where   α   ∈   R +   is a tuning parameter. The goal function  γ i   ( t ) :   R 2   →   R +   in (5) encodes the control objective of achieving consensus on the position between node   i   and neighboring nodes   j   ∈ N i , which is designed as  γ i   =   ∑  j ∈N i  ‖ p i   ( t )   −   p j   ( t ) ‖ 2   .   (6)  4
Assume each node   i   has a collision region defined as a small disk with radius   δ 1   < R , and an escape region defined as the outer ring of the sensing area centered at the node with radius   r, R − δ 2   < r < R,   where   δ 2   ∈   R +   is a predetermined buffer distance. Any node   j   ∈ N i   inside the collision region has the potential to collide with node  i , and each edge formed by node   i   and   j   ∈ N i   in the escape region has the potential to break connectivity. To ensure collision avoidance and network connectivity, the constraint function   β i   :   R 2 N   →   [0 ,   1]   in (5) is designed as  β i   =   ∏  j ∈N i  b ij   B ij   ,   (7) by only accounting for nodes within its sensing area. Particularly,   b ij   ( p i , p j   ) :   R 2   →   [0 ,   1]   in (7) is a continu- ously differentiable sigmoid function, designed as  b ij   =   1  1 +   e −   2  δ 2   log (   1 − ǫ  ǫ   )( R −   1  2   δ 2 − d ij   )   ,   (8) where   0   < ǫ   ≪   1   is a positive constant. The designed  b ij   ensures connectivity of nodes   i   and its neighboring nodes   j   ∈ N i   (i.e., nodes   j   ∈ N i   will never leave the sensing and communication zone of node   i   if node   j   is initially connected to node   i ). Since collision avoidance among robots are only required in   Ω c ,   B ij   ( p i , p j   ) :   R 2   →   [0 ,   1]   in (7) is designed as  B ij   =   1  1 +   e −   2  δ 1   log (   1 − ǫ  ǫ   )( d ij   −   1  2   δ 1   )   (9) which indicates that collision avoidance is activated if the robots are in   Ω c , i.e., node   i   is repulsed from other nodes to prevent a collision in   Ω c . If the robots are in   Ω r , the collision avoidance is deactivated by removing   B ij  from   β i   in (7). Since   Ω r   is defined by the distance to the destination and only the leader in the group is informed about the destination, the collision avoidance scheme designed in (9) is deactivated only when the leader is close enough to the destination in   Ω r   2   . That is   β i   in (5) for   ∀ i   ∈   V F   switches from   β i   = ∏  j ∈N i   b ij   B ij   to   β i   =   ∏  j ∈N i   b ij   if the leader is close enough to the destination in   Ω r   , so that collision avoid- ance among robots is not considered any more. The   b ij  and   B ij   are illustrated in Fig. 2. Note that the constraint function in (7) is designed to vanish whenever node   i   in- tersects with one of the constraints in the environment,  2   The network will be proven to be connected all the time in the subsequent analysis, which implies that the distance between any two nodes is bounded by   R   ( N   −   1) . To ensure all followers are in   Ω r   when the collision avoidance scheme is deactivated, the leader is required to deactivate the collision avoidance when its distance to the destination is less than  R r   −   R   ( N   −   1) .  0   0.5   1   1.5   2  0  0.2  0.4  0.6  0.8  1  d ij  b ij  (a) Network Connectivity  0   0.5   1   1.5   2  0  0.2  0.4  0.6  0.8  1  d ij  B ij  (b) Collision Avoidance  Figure 2. The plot of   b ij   and   B ij   with   δ 1   = 0 . 5 ,   δ 2   = 1 ,  R   = 2 , and   ǫ   = 0 . 01 .  (i.e., if node   i   touches another node in   Ω c , or separates from adjacent nodes   j   ∈ N i   by distance of   R c ). Since   γ i  and   β i   in (5) will not be zero simultaneously from their definitions, it is clear that   φ f i   achieves its minimum of   0  if   γ i   = 0   (i.e., consensus is reached between node   i   and its immediate neighbors), and   φ f i   achieves its maximum of   1   if   β i   = 0   (i.e., either the network connectivity or collision constraint is met).  3.2   Control Development  For brevity,   φ i   is used to represent the potential function designed for each node   i , where particularly   φ i   =   φ d i   in (2) if   i   ∈ V L , and   φ i   =   φ f i   in (5) if   i   ∈ V F   .   The de- sired orientation for any robot   i   ∈ V , denoted by   θ di   ( t )   ,  is defined as a function of the negative gradient of the decentralized function   φ i   as,  θ di   ,   arctan 2  (  −   ∂φ i  ∂y i   ,   −   ∂φ i  ∂x i  )  ,   (10) where the mapping   arctan 2 ( · ) :   R 2   →   R   denotes the four quadrant inverse tangent function, and   θ di   ( t )   is confined to the region of   ( − π, π ] . By defining   θ di   | p ∗   = arctan 2 (0 ,   0) =   θ i   | p ∗   ,   θ di   remains continuous along any approaching direction to the goal position. Based on the definition of   θ di   in (10)  ∇ i φ i   =   − ‖∇ i φ i ‖  [  cos ( θ di ) sin ( θ di )  ] T  ,   (11) where   ∇ i φ i   =  [   ∂φ i  ∂x i  ∂φ i  ∂y i  ] T  denotes the partial deriva- tive of   φ i   with respect to   p i , and   ‖∇ i φ i ‖   denotes the Euclidean norm of   ∇ i φ i . The difference between the cur- rent orientation and the desired orientation for robot   i  at each time instant is defined as   ̃ θ i   ( t ) =   θ i   ( t )   −   θ di   ( t )   ,   (12)  5
where   θ di   ( t )   is generated from the decentralized naviga- tion function   φ i   and (10). Based on the open-loop sys- tem in (1), the controller for each robot (i.e., the linear and angular velocity of robot   i ) is designed as  v i   =   k v,i   ‖∇ i φ i ‖   cos  ̃ θ i ,   (13)  ω i   =   − k w,i    ̃ θ i   +  ̇ θ di ,   (14) where   k v,i ,   k w,i ∈   R +   denote the control gains for robot  i . The term    ̇ θ di   in (14) is determined as   ̇ θ di   =   k v,i   cos( ̃ θ i )  [   sin ( θ di )  −   cos ( θ di )  ] T  ∇ 2  i   φ i  [   cos ( θ i ) sin ( θ i )  ]  ,  (15) where   ∇ 2  i   φ i   denotes the Hessian matrix of   φ i   with re- spect to   p i . Note that the computation of   ∇ i φ i ,    ̃ θ i , and   ̇ θ di   only requires local position feedback and does not depend on communication with any neighbors, which highlights the decentralized nature of the controllers in (13) and (14). Although the switch of   β i   will result in a discontinuity of the controller in (13) and (14) when the leader enters   Ω r   from   Ω c , the controller remains contin- uous within   Ω r   and   Ω c   respectively. Substituting (13) into (1), the closed-loop system for robot   i   can be ob- tained as   ̇ p i   =  [    ̇ x i   ̇ y i  ]  =   k v,i   ‖∇ i φ i ‖   cos  ̃ θ i  [   cos   θ i  sin   θ i  ]  .   (16) After   using   the   fact   that  [  cos   θ i   sin   θ i  ]  ∇ i φ i   =  − ‖∇ i φ i ‖   cos  ̃ θ i   from (11), the closed-loop error systems can be expressed as   ̇ p i   =   − k v,i ∇ i φ i , i   ∈ V .   (17)  4   Connectivity and Convergence Analysis  4.1   Connectivity Analysis  Theorem 1   The controller in (13) and (14) ensures that the initially connected spanning tree structure is pre- served when performing rendezvous for nodes with kine- matics given by (1), as well as collision avoidance among robots in   Ω c .  PROOF.   The spanning tree structure in Assumption 1 ensures that there exists a path from the informed node to every follower node in   G   (0) . To show every existing edge in the directed spanning tree in   G   (0)   is preserved, consider a follower   i   ∈ V F   located at a position   p 0   ∈ F   that causes   β i   = 0 , which will be true when either only one node   j   is about to disconnect from node   i   or when multiple nodes are about to disconnect with node  i   simultaneously. If   β i   = 0 , the navigation function   φ i  designed in (5) will achieve its maximum value. Driven by the negative gradient of   φ i   in (17), no open set of initial conditions can be attracted to the maxima of the navigation function [14]. Therefore, every edge in   G   is maintained and the directed spanning tree structure is preserved for all time. Similar to the proof of the preservation of each link, if two nodes   i   and   j   are about to collide in   Ω c , that is  B ij   ( p i , p j   ) = 0   from (9), then the potential function   φ i  in (5) will reach its maximum. Based on the properties of a navigation function driven by the vector field in (17), the system will not achieve its maximum. Hence, collision among nodes is avoided.   ✷  4.2   Convergence Analysis  Lemma 1   [25, 26] Let   G   be a directed graph of or- der   n   and   L   ∈   R n × n   be the associated (non-symmetric) Laplacian   matrix. Consider a linear system    ̇ x   ( t )   =  − L   ( t )   x   ( t )   ,   where   x   ( t ) =   [ x 1 , . . . , x n ] T   ∈ R n . If the time-varying matrix   L   ( t )   ∈   R n × n   is a piecewise contin- uous function of time with bounded elements, and   G   has a directed spanning tree for all   t   ≥   0 , then consensus is exponentially achieved, i.e.,   x 1   =   · · ·   =   x n .  Theorem 2   Provided that   G   has a spanning tree with the informed node as the root, the controller in (13) and (14) ensures that all robots with kinematics given by (1) converge to a common point with a desired orientation, in the sense that   ‖ p i   ( t )   −   p ∗ ‖ →   0   and  ∣ ∣ ∣  ̃ θ i   ( t )  ∣ ∣ ∣   →   0   as  t   → ∞ ∀ i   ∈   V   .  PROOF.   For the follower robots   i   ∈ V F   , the term   ∇ i φ i  in (17) is computed from (5) as  ∇ i φ i   =   αβ i ∇ i γ i   −   γ i ∇ i β i  α ( γ α i   +   β i )   1  α   +1   ,   (18) where   ∇ i γ i   and   ∇ i β i   are bounded in the workspace   F  from (6) and (7), and   ∇ i γ i   and   ∇ i β i   in (18) can be determined as  ∇ i γ i   = 2   ∑  j ∈N i  ( p i   −   p j   )   ,   (19) and  ∇ i β i   = 2   ∑  j ∈N i  (   ∂b ij  ∂d ij  )    ̄ b ij  ‖ p i − p j   ‖   ( p i   −   p j   )   ,   (20)  6
respectively, where    ̄ b ij   ,   ∏  l ∈N i   ,l 6   = j   b il .   In (20),   ∂b ij  ∂d ij   is  ∂b ij  ∂d ij  =   −   2  δ 2   log (   1 − ǫ  ǫ   ) e −   2  δ 2 log (   1 − ǫ  ǫ   )( R −   1  2   δ 2 − dij   )  (  1+ e −   2  δ 2 log (   1 − ǫ  ǫ   )( R −   1  2   δ 2 − dij   ) ) 2   ,   (21) which   is   negative,   since   δ 2 ,   2  δ 2   log   (   1 − ǫ  ǫ  ) ,   and  e −   2  δ 2   log (   1 − ǫ  ǫ   )( R −   1  2   δ 2 − d ij   )   are all positive terms. Substi- tuting (19) and (20) into (18),   ∇ i φ i   is rewritten as  ∇ i φ i   =   ∑  j ∈N i  m ij   ( p i   −   p j   )   ,   (22) where  m ij   = 2 αβ i   −   2  (   ∂b ij  ∂d ij  )    ̄ b ij  ‖ p i − p j   ‖   γ i  α ( γ α i   +   β i )   1  α   +1   (23) is non-negative, based on the definitions of   γ i ,   β i ,   α ,    ̄ b ij   , and   ∂b ij  ∂d ij   in (21). Using (17) and (22) yields the closed- loop system for each node   i   as:       ̇ p i ( t ) =   − k v,i ∇ i φ d i   ,   i   ∈ V L   ̇ p i ( t ) =   −   ∑  j ∈N i  k v,i m ij   ( p i   −   p j   )   , i   ∈ V F   ,   (24) which can be rewritten in a compact form as   ̇ p   ( t ) =   −   ( π   ( t )   ⊗   I 2 )   p   ( t ) +   F d ,   (25) where   p   ( t )   =  [  p T  1   ,   · · ·   , p T N  ] T  ∈   R 2 N   denotes the stacked vector of   p i ,   F d   =  [  − k v,i ∇ T i   φ d i   ,   0 ,   · · ·   ,   0  ] T  ∈  R 2 N   for   i   = 1   (recall that   V L   =   { 1 }   from Section 2),   I 2   is a   2 × 2   identity matrix, and the elements of   π   ( t )   ∈   R N   × N  are defined as  π ik   ( t ) =         ∑  j ∈N i   k v,i m ij   ,   i   =   k  − k v,i m ik ,   k   ∈ N i , i   6   =   k  0 ,   k / ∈ N i , i   6   =   k.  (26) Using the fact that   m ij   is non-negative from (23), and  k v,i   is a positive constant gain in (13), the off-diagonal elements of   π   ( t )   are negative or zero, and its row sums are zero. Hence,   π   ( t )   is a Laplacian matrix. Since the in- formed node acts as the root in the spanning tree struc- ture in   G , the first row of   π   ( t )   is composed of all ze- ros, which indicates that the motion of the informed node is not dependent upon the motion of the followers. From Lemma 1 and the properties of the dipolar nav- igation function in (2), the first term in (25) indicates that   p 1   =   · · ·   =   p N   ,   and the second term implies that  p 1   →   p ∗ ,   and hence,   p i   →   p ∗   ∀   i   ∈ V . Note that the properties of the developed dipolar nav- igation function in (2) ensure that the informed node achieves the specified destination with the desired ori- entation. If the informed node always tracks its desired orientation   θ di   and all the followers move along with the informed node, the group will achieve the destination with desired orientation. To show that  ∣ ∣ ∣  ̃ θ i  ∣ ∣ ∣   →   0   , we take the time derivative of    ̃ θ i   ( t )   in (12) and use (1) to develop the open-loop orientation tracking error system as  ·   ̃ θ i   =   ω i   −    ̇ θ di . Using (14), the closed-loop orientation tracking error is   ·   ̃ θ i   =   − k w    ̃ θ i ,   (27) which has the exponentially decaying solution    ̃ θ i   ( t ) =  ̃ θ i   (0)   e − k w   t .   ✷  Remark 1   Since the network is proven to be connected in Theorem 1, the distance between any two nodes is bounded by   R   ( N   −   1) , where   R   is the sensing radius and  N   is the number of nodes. By requiring the informed robot to move within a region with a distance to the workspace boundary greater than   R   ( N   −   1) , the followers are guar- anteed to avoid collision with the workspace boundary by achieving consensus with the informed robot.  Remark 2   The previous analysis is based on the simpli- fication that only one informed node is considered. The result can be generalized to multiple informed nodes by using containment control theory. Containment control is a particular class of consensus problems in which all nodes are grouped into followers and leaders, and the fol- lowers, under the influence of leaders through local in- formation exchange, converge to a desired region (i.e., a convex hull) formed by the leaders’ states. Some recent results are reported in [27–29] for containment control. In our recent work in [30], a decentralized method is devel- oped to influence followers in a social network to reach a common desired state (i.e., within a convex hull spanned by the leaders), while maintaining interaction among the followers and leaders. As a special case of [30], if each leader is assigned the same destination, the convex hull formed by leaders will shrink to the common destination, and the followers will converge to this desired destina- tion. Therefore, following a similar approach in [30], all nodes can be proven to converge to the common destina- tion, if multiple informed nodes are considered.  Remark 3   The switch of the controller (13) and (14) from   Ω c   to   Ω r   will not affect the stability of the system. Theorem 3.2 in [31] states that a switched nonlinear sys- tem is stable if the associated Lyapunov-like function   V i  in each region   Ω i   is nonincreasing, and   V i   is also nonin- creasing when switching occurs. It is proven that   ∑ N i   φ i  is a qualified Lyapunov function in [22], and following a similar approach as [22],   ∑ N i   φ i is nonincreasing in   Ω c  and   Ω r   , respectively. To show that the Lyapunov func- tion   ∑ N i   φ i   is nonincreasing when switching occurs, note that the denominator of   φ f i   in (5) is nondecreasing when  7
switching from   Ω c   to   Ω r   due to the fact that   B ij   ∈   [0 ,   1] , which results in a nonincreasing   φ f i   . By invoking Theo- rem 3.2 in [31], the system remains stable when the switch occurs from   Ω c   to   Ω r   .  5   Simulation  The following numerical simulation demonstrates the performance of the controller developed in (13) and (14) in a scenario in which a group of six mobile robots with the kinematics in (1) are navigated to the common desti- nation   p ∗   =  [  0 0  ] T  with the desired orientation   θ ∗   = 0 .  The limited communication and sensing zone for each robot is assumed as   R   = 2   m and   δ 1   =   δ 2   = 0 . 4   m The tuning parameter   α   in (2) is selected to be   α   = 1 . 2 . The workspace   F   is a disk area centered at the origin with radius   R w   = 50 ,   and the rendezvous region is a disk area with radius   R r   = 11 . 5 . The collison avoidance scheme of the group is deactivated only when the informed robot is within a distance less than 1.5 to the common des- tination. The group of mobile robots is arbitrarily de- ployed in the workspace and forms a connected graph. The interaction between nodes is described by the net- work topology with a spanning tree as shown in Fig. 5, where the light dots denote the follower robots and the dark dot denotes the informed node. The informed node is randomly selected from the group, and is the only node aware of the desired destination   p ∗   and orientation   θ ∗ . The control laws in (13) and (14) yield the simulation re- sults shown in Fig. 5 and Fig. 5. Fig. 5 shows the trajec- tory for each robot, where the associated arrows indicate the initial or final orientation. To demonstrate the colli- sion avoidance among robots and connectivity of existing links, the evolution of the inter-robot distance is plotted in Fig. 5. As shown in Fig. 5, the inter-robot distance de- creases significantly for the first few seconds. Since the robots are moving in the collision free region initially, where collision avoidance is activated, the inter-robot distance stops to decrease when two robots are close to each other. Once the robots enter the rendezvous re- gion, where collision avoidance is deactivated, the inter- robot distance decreases again to perform the desired rendezvous. Note that inter-robot distance is maintained less than the radius   R   = 2   m, which indicates that con- nectivity of the underlying graph is preserved.  6   Conclusion  A decentralized dipolar navigation function-based time- varying controller is developed to navigate a network of mobile robots to a common destination with a desired orientation while ensuring network connectivity and col- lision avoidance, using only local sensing information  Figure 3. Network topology with directed edges indicating the directed interaction between two nodes.  −4.5   −4   −3.5   −3   −2.5   −2   −1.5   −1   −0.5   0   0.5  −2  −1.5  −1  −0.5  0  0.5  1  1.5  2  x−axis (m) y−axis (m)  Trajectory of IR  Trajectory of FR  Figure 4. Plot of robot trajectories with solid line and dot– dash line indicating the trajectory of the informed robot (IR) and the follower robot (FR), respectively.  0   5   10   15   20   25   30   35   40   45   50  −0.2  0  0.2  0.4  0.6  0.8  1  1.2  1.4  1.6  1.8  time (sec) inter−robot distance (m)  Figure 5. The evolution of inter-robot distance.  from one-hop neighbors. A distinguishing feature of the developed decentralized approach is that no inter-agent communication is required to complete the network con- sensus objective. Another distinguishing feature is that the more general problem of directed networks is con- sidered, where only one robot is informed of the global objective while other robots coordinate their motions to perform the cooperative task by using local informa-  8
tion feedback from immediate neighbors. Although con- sensus among robots is ensured in this work, the rate of convergence is not considered. Generally, the rate of convergence depends on the network topology, which is a function of the roles of nodes (i.e., informed nodes or followers) and their interactions. A different set of in- formed nodes may lead to different convergence rates. Additional methods could be developed to optimize per- formance metrics such as the degree of connectivity and the convergence rate of the network in scenarios where the set of informed nodes can be determined and/or po- sitioned a prior.  References  [1]   T.   McLain   and   R.   Beard,   “Coordination   variables, coordination functions, and cooperative-timing missions,”   J. Guid. Contr. Dynam. , vol. 28, no. 1, pp. 150–161, 2005. [2]   E. Tekin and A. Yener,   “The general   Gaussian multiple- access and two-way wiretap channels: Achievable rates and cooperative   jamming,”   IEEE Trans. Inf. Theory   , vol. 54, no. 6, pp. 2735–2751, 2008. [3]   Z. Lin, M. Broucke, and B. Francis, “Local control strategies for   groups   of   mobile   autonomous   agents,”   IEEE   Trans. Autom. Control   , vol. 49, no. 4, pp. 622–629, 2004. [4]   J.   Lin,   A.   Morse,   and   B.   Anderson,   “The   multi-agent rendezvous problem. Part 1: The synchronous case,”   SIAM J. Control Optim. , vol. 46, no. 6, pp. 2096–2119, 2007. [5]   ——,   “The   multi-agent   rendezvous   problem.   part   2:   The asynchronous case,”   SIAM J. Control Optim. , vol. 46, no. 6, pp. 2120–2147, 2007. [6]   J. Cortés, S. Martínez, and F. Bullo, “Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions,”   IEEE Trans. Autom. Control   , vol. 51, no. 8, pp. 1289–1298, 2006. [7]   D.   V.   Dimarogonas   and   K.   J.   Kyriakopoulos,   “On   the rendezvous   problem   for   multiple   nonholonomic   agents,”  IEEE Trans. Automat. Control   , vol. 52, no. 5, pp. 916–922, May 2007. [8]   H. Su, X. Wang, and G. Chen, “Rendezvous of multiple mobile agents with preserved network connectivity,”   Syst. Control Lett. , vol. 59, no. 5, pp. 313–322, 2010. [9]   T.   Gustavi,   D.   Dimarogonas,   M.   Egerstedt,   and   X.   Hu, “Sufficient   conditions   for   connectivity   maintenance   and rendezvous in leader–follower networks,”   Automatica , vol. 46, no. 1, pp. 133–139, 2010. [10] F. Xiao, L. Wang, and T. Chen, “Connectivity preservation for multi-agent rendezvous with link failure,”   Automatica , vol. 48, pp. 25–35, Jan. 2012. [11] Q.   Hui,   “Finite-time   rendezvous   algorithms   for   mobile autonomous agents,”   IEEE Trans. Autom. Control   , vol. 56, no. 1, pp. 207–211, 2011. [12] S.   Loizou and K. Kyriakopoulos,   “Navigation of multiple kinematically   constrained   robots,”   IEEE   Trans.   Robot , vol. 24, no. 1, pp. 221 –231, 2008. [13] D. E. Koditschek and E. Rimon, “Robot navigation functions on manifolds with boundary,”   Adv. Appl. Math. , vol. 11, pp. 412–442, Dec 1990. [14] E. Rimon and D. Koditschek, “Exact robot navigation using artificial potential functions,”   IEEE Trans. Robot. Autom. , vol. 8, no. 5, pp. 501–518, Oct 1992. [15] G. Roussos, D. Dimarogonas, and K. Kyriakopoulos, “3D navigation   and   collision   avoidance   for   a   non-holonomic vehicle,” in   Proc. Am. Control Conf. , 2008, pp. 3512 –3517. [16] T.   Liu   and   Z.   Jiang,   “Distributed   formation   control of   nonholonomic   mobile   robots   without   global   position measurements,”   Automatica , vol. 49, no. 2, pp. 592–600, 2013. [17] W. Dong and J. Farrell, “Cooperative control of multiple nonholonomic mobile agents,”   IEEE Trans. Autom. Contr. , vol. 53, no. 6, pp. 1434–1448, 2008. [18] ——,   “Decentralized   cooperative   control   of multiple nonholonomic dynamic systems with uncertainty,”  Automatica , vol. 45, no. 3, pp. 706–710, 2009. [19] L. Consolini, F. Morbidi, D. Prattichizzo, and M. Tosques, “Leader-follower formation control of nonholonomic mobile robots with input constraints,”   Automatica , vol. 44, no. 5, pp. 1343–1349, 2008. [20] Z.   Kan,   A.   Dani,   J.   Shea,   and   W.   E.   Dixon,   “Ensuring network   connectivity   for   nonholonomic   robots   during rendezvous,” in   Proc. IEEE Conf. Decis. Control   , Orlando, FL, 2011, pp. 2369–2374. [21] Z.   Kan,   J.   Klotz,   T.-H.   Cheng,   and   W.   E.   Dixon, “Ensuring   network   connectivity   for   nonholonomic   robots during   decentralized   rendezvous,”   in   Proc.   Am.   Control Conf. , Montréal, Canada, June 2012, pp. 3718–3723. [22] Z. Kan, A. Dani, J. M. Shea, and W. E. Dixon, “Network connectivity preserving formation stabilization and obstacle avoidance   via   a   decentralized   controller,”   IEEE   Trans. Automat. Control   , vol. 57, no. 7, pp. 1827– 1832, 2012. [23] H. Tanner   and K. Kyriakopoulos,   “Nonholonomic motion planning for mobile manipulators,”   in   IEEE International Conference on Robotics and Automation , vol. 2, 2000, pp. 1233 –1238 vol.2. [24] H. Tanner, S. Loizou, and K. Kyriakopoulos, “Nonholonomic navigation and control of cooperating mobile manipulators,”  IEEE Trans. Robot. Autom. , vol. 19, no. 1, pp. 53–64, Feb 2003. [25] L.   Moreau,   “Stability   of   continuous-time   distributed consensus algorithms,” in   Proc. IEEE Conf. Decis. Control   , 2004, pp. 3998–4003. [26] ——, “Stability of multiagent systems with time-dependent communication links,”   IEEE Trans. Autom. Control   , vol. 50, no. 2, pp. 169–182, February 2005. [27] G. Notarstefano, M. Egerstedt, and M. Haque, “Containment in leader-follower networks with switching communication topologies,”   Automatica , vol. 47, no. 5, pp. 1035–1040, 2011. [28] Y. Cao and W. Ren, “Containment control with multiple stationary or dynamic leaders under a directed interaction graph,” in   Proc. IEEE Conf. Decis. Control   , 2009, pp. 3014– 3019. [29] J. Mei, W. Ren, and G. Ma, “Distributed containment control for Lagrangian networks with parametric uncertainties under a directed graph,”   Automatica , vol. 48, no. 4, pp. 653–659, 2012. [30] Z.   Kan,   J.   Klotz,   E.   Pasiliao,   and   W.   E.   Dixon, “Containment   control   for   a   social   network   with   state- dependent connectivity,”   Automatica , 2012, submitted. [31] R.   A.   DeCarlo,   M.   S.   Branicky,   S.   Pettersson,   and B. Lennartson, “Perspectives and results on the stability and stabilizability of hybrid systems,”   Proc. IEEE   , vol. 88, no. 7, pp. 1069–1082, 2000.  9