# Maintaining Wireless Connectivity Constraints for Robot Swarms in the Presence of Obstacles

Authors: Joel M. Esposito
Journal: Journal of Robotics
 (2011)

---

## Abstract

The swarm paradigm of multirobot cooperation relies on a distributed architecture, where each robot makes its own decisions based on locally available knowledge. But occasionally the swarm members may need to share information about their environment or actions through some type of ad hoc communication channel, such as a radio modem, infrared communication, or an optical connection. In all of these cases robust operation is best attained when the transmitter/receiver robot pair is (1) separated by less than some maximum distance (range constraint); and (2) not obstructed by large dense objects (line-of-sight constraint). Therefore to maintain a wireless link between two robots, it is desirable to simultaneously comply with these two spatial constraints. Given a swarm of point robots with specified initial and final configurations and a set of desired communication links consistent with the above criteria, we explore the problem of designing inputs to achieve the final configuration while preserving the desired links for the duration of the motion. Some interesting conclusions about the feasibility of the problem are offered. A potential field-based optimization algorithm is provided, along with a novel composition scheme, and its operation is demonstrated through both simulation and experimentation on a group of small robots.


---

## Body

## 1. Introduction

Large teams of mobile robots, referred to asswarms can be more effective in accomplishing certain tasks, as compared with a single, possibly more sophisticated, robot. The advantages of the swarm are especially apparent in applications that benefit from spatially distributed sensing, such as environmental sampling [1], coordinated map making [2], and search [3]. Manipulating and transporting large objects is an application which can benefit from spatially distributed actuation [4–7]. In contrast to centralized control methods, the swarm paradigm of multirobot cooperation relies on a distributed architecture, where each robot makes its own decisions based on locally available knowledge. Advantages of such an approach include improved scalability with respect to swarm size, robustness with respect to the failure of a single swarm member, and the possibility of a human operator controlling swarm wide behavior through a low-dimensional set of input parameters [8, 9].However, in many applications, it is impossible or inefficient to employ truly independent control algorithms on each agent. In order to complete their task the swarm members may need to share information about their intentions or their environment. Indeed, many proposed control laws in the literature require that each member of the swarm is connected to the group through some type of ad hoc, low-power, wireless communication channel, such as a radio or optical links. Power limitations and phenomena such as secondary reflections and shadow effects create a variety constraints on the relative positions of the transmitter and receiver. We abstract these more complex electromagnetic phenomena and work with a simpler two-component communication constraint. The first is a limitation on the maximum distance between the transmitter and receiver, referred to here, and in other works, as theRange Constraint. Considerably less attention has been given to Line-of-Sight Constraints—necessitated by the difficulty of reliably transmitting wireless messages through large dense obstacles. Together we term these two spatial constraints Communication Constraints. If a pair of robots meet these constraints, we assume they can establish a wireless link. While this treatment is idealized, it is a significant improvement over the “range only" constraints considered in most of the connectivity control literature. Of course in addition to these constraints the robots may have some overall motion objectives (either individually or as a group), such as moving toward a goal and avoiding obstacles.In this paper we address the problem of navigating the swarm, in the plane, from an initial configuration to a specified final configuration, while maintaining a pre-specified list of wireless links between certain robots (range plus line-of-sight). After a review of related work below, we provide a formal problem statement in Section3. We consider existence of solutions in Section 4 and necessary properties of solution trajectories. In Section 5 we introduce potential fields for the goal/obstacle avoidance, range and line-of-sight objectives. Section 6 discusses how to compose these sometimes disparate objectives and provides a computational algorithm for assigning motion directions. Simulation and hardware-based experimental demonstrations of the algorithm’s operation are included in Section 7 followed by concluding remarks in Section 8.


## 2. Related Work

In this section we review some common notions of robot swarm connectivity and their role in flocking behavior and formation control. We then narrow the scope of the discussion to related work on explicit control of swarm connectivity, and the relationship to the approach presented here. We end with a discussion of the line-of-sight constraint.


### 2.1. Notions of Connectivity

Most discussions on connectivity within robot swarms employ a neighbor or proximity graph modeling paradigm [10], where each vertex in the graph represents a robot and each graph edge represents a wireless communication link. The criteria to establish a link is almost always based on the physical distance (i.e., range) between the robots [11, 12]. We adopt both the graph theoretic modeling paradigm and the range constraint in this paper. As an extension, some works [13, 14] consider multihop connectivity, still using interrobot range as the underlying criteria. If an edge joins two vertices, the corresponding robots are considered locally connected. The swarm as a whole is considered globally connected if an edgepath of finite length exists between any two vertices in the graph. Global connectivity can be verified algebraically by determining if the second smallest Eigenvalue of the graph’s LaPlacian matrix is greater than zero. Larger values indicate a more strongly connected configuration.


### 2.2. Role of Connectivity in Consensus and Stability

All works on flocking and formation control rely on some underlying notion of swarm connectivity to prove stability and convergence. In general the primary objective offlocking can be thought of as establishing a consensus on individual robot velocity vectors [15]. The work by Reynolds [16] is considered to be the inspiration for many works on flocking. While that work did not formally describe the notion of global connectivity in terms of graphs, the control law stipulated certain informational dependencies—namely, that each robot should know the position and velocity of the other agents in its neighborhood. These assumption are now considered standard, and we make similar ones in this paper. Efforts to formally prove that the swarm reaches a consensus regarding their velocity vectors ultimately employed a neighbor graph to reflect these dependencies, showed that global connectivity is a necessary condition for consensus, and proved that the convergence rate is determined by the second smallest Eigenvalue of the graph’s LaPlacian matrix [10–12]. In these works the relative pose of the robots is not specified and the connection topology is entirely range based, and therefore dynamic, so the control laws must include a potential function that maintains interrobot ranges within a certain tolerance, similar to [17].Formation control involves moving a group of robots while maintaining a fixed relative pose between them. In these works some type of graph theoretic framework is also used [18]. Typically the connection topology is static, where certain robots are designated as leaders, and others follow maintaining specific edges in the graph. Here the connectivity properties of the graph can be used to prove stability [19–23]. In both formation and flocking works, while there is a acknowledged relationship between stable flocking and connectivity, the primary objective is the former and the later is a necessary condition.


### 2.3. Connectivity as a Primary Control Objective

There are several works that explicitly treat connectivity as the primary control objective. They can be loosely divided intooptimization-based (or open loop) approaches and feedback approaches. In [24] the authors synthesize configurations and paths that maximize swarm’s global connectivity, as measured by the second smallest Eigenvalue of the graph’s LaPlacian matrix using a Semidefinite Programming formulation. The work in [13] more closely resembles the problem considered here. A desired graph is specified and must be maintained for all time. Two hop, range-based edges are considered, and they show the set of all such connected configurations is a star-shaped set. As a result, the initial path supplied to the receding horizon optimizer consists of contracting the swarm to a point, following a straight line trajectory to the goal, and expanding the swarm again. An optimization criteria called connectivity robustness is used to refine the result. In both cases numerical techniques are used off-line to compute an open loop path. In our work, numerical methods are employed in real time as part of a closed loop feedback control law.An example of a feedback-based method is in [25]. The problem of maintaining specific edges in the neighbor graph is phrased as controlling the dynamics of the adjacency matrix through a set of inequalities [14]. A potential field-based controller is used in [26]. A potential function is defined on the Cartesian product of swarm member poses, and loss of global connectivity is modeled as a virtual obstacle in that space. Locally optimal configurations are achieved. Unlike [13] or [27], this approach does not specify individual edges to be maintained.Like the works discussed above, the work presented here and our earlier work [27] explicitly treat connectivity as a control objective.


### 2.4. Line of Sight

Several authors in the wireless networking community have studied the adverse impact of transmitter/receiver occlusions from an electromagnetic field strength perspective and the modeling implications of this for mobile robotics have been discussed in detail [28]. Practitioners have long observed the effect. Applications in multirobot coverage [29] and map making [30], for example, assume that information exchanges only occur when line of sight is established. Also, the pervasive use of computer vision for robotics tasks such as cooperative localization [31], or search and pursuit [32] has also necessitated the consideration of line-of-sight constraints.In some of these cases, loss of line of sight is considered an unfortunate “fact of life” [30]; in other cases it is exploited to determine the connectivity properties of the environment [29, 31]. But none of these works explicitly includes a motion controller that actively prevents such losses from occurring.The principle difference between the connectivity work discussed in the previous section and the work presented in this paper, is that we modify the local connection/edge formation criteria to explicitly maintain line-of-sight constraints as well as the widely used single-hop, range constraint. To our knowledge this issue has only been considered in a few previous works. A behavior-based approach is described in [33]; while the performance cannot be proven it was illustrated through simulation. In [34] a planetary rover application was considered and six heuristics for maintaining line of sight were introduced. The approach was largely successful but could not solve all the presented test scenarios. The authors speculated that some of the unsolved scenarios were simply infeasible.


## 2.1. Notions of Connectivity

Most discussions on connectivity within robot swarms employ a neighbor or proximity graph modeling paradigm [10], where each vertex in the graph represents a robot and each graph edge represents a wireless communication link. The criteria to establish a link is almost always based on the physical distance (i.e., range) between the robots [11, 12]. We adopt both the graph theoretic modeling paradigm and the range constraint in this paper. As an extension, some works [13, 14] consider multihop connectivity, still using interrobot range as the underlying criteria. If an edge joins two vertices, the corresponding robots are considered locally connected. The swarm as a whole is considered globally connected if an edgepath of finite length exists between any two vertices in the graph. Global connectivity can be verified algebraically by determining if the second smallest Eigenvalue of the graph’s LaPlacian matrix is greater than zero. Larger values indicate a more strongly connected configuration.


## 2.2. Role of Connectivity in Consensus and Stability

All works on flocking and formation control rely on some underlying notion of swarm connectivity to prove stability and convergence. In general the primary objective offlocking can be thought of as establishing a consensus on individual robot velocity vectors [15]. The work by Reynolds [16] is considered to be the inspiration for many works on flocking. While that work did not formally describe the notion of global connectivity in terms of graphs, the control law stipulated certain informational dependencies—namely, that each robot should know the position and velocity of the other agents in its neighborhood. These assumption are now considered standard, and we make similar ones in this paper. Efforts to formally prove that the swarm reaches a consensus regarding their velocity vectors ultimately employed a neighbor graph to reflect these dependencies, showed that global connectivity is a necessary condition for consensus, and proved that the convergence rate is determined by the second smallest Eigenvalue of the graph’s LaPlacian matrix [10–12]. In these works the relative pose of the robots is not specified and the connection topology is entirely range based, and therefore dynamic, so the control laws must include a potential function that maintains interrobot ranges within a certain tolerance, similar to [17].Formation control involves moving a group of robots while maintaining a fixed relative pose between them. In these works some type of graph theoretic framework is also used [18]. Typically the connection topology is static, where certain robots are designated as leaders, and others follow maintaining specific edges in the graph. Here the connectivity properties of the graph can be used to prove stability [19–23]. In both formation and flocking works, while there is a acknowledged relationship between stable flocking and connectivity, the primary objective is the former and the later is a necessary condition.


## 2.3. Connectivity as a Primary Control Objective

There are several works that explicitly treat connectivity as the primary control objective. They can be loosely divided intooptimization-based (or open loop) approaches and feedback approaches. In [24] the authors synthesize configurations and paths that maximize swarm’s global connectivity, as measured by the second smallest Eigenvalue of the graph’s LaPlacian matrix using a Semidefinite Programming formulation. The work in [13] more closely resembles the problem considered here. A desired graph is specified and must be maintained for all time. Two hop, range-based edges are considered, and they show the set of all such connected configurations is a star-shaped set. As a result, the initial path supplied to the receding horizon optimizer consists of contracting the swarm to a point, following a straight line trajectory to the goal, and expanding the swarm again. An optimization criteria called connectivity robustness is used to refine the result. In both cases numerical techniques are used off-line to compute an open loop path. In our work, numerical methods are employed in real time as part of a closed loop feedback control law.An example of a feedback-based method is in [25]. The problem of maintaining specific edges in the neighbor graph is phrased as controlling the dynamics of the adjacency matrix through a set of inequalities [14]. A potential field-based controller is used in [26]. A potential function is defined on the Cartesian product of swarm member poses, and loss of global connectivity is modeled as a virtual obstacle in that space. Locally optimal configurations are achieved. Unlike [13] or [27], this approach does not specify individual edges to be maintained.Like the works discussed above, the work presented here and our earlier work [27] explicitly treat connectivity as a control objective.


## 2.4. Line of Sight

Several authors in the wireless networking community have studied the adverse impact of transmitter/receiver occlusions from an electromagnetic field strength perspective and the modeling implications of this for mobile robotics have been discussed in detail [28]. Practitioners have long observed the effect. Applications in multirobot coverage [29] and map making [30], for example, assume that information exchanges only occur when line of sight is established. Also, the pervasive use of computer vision for robotics tasks such as cooperative localization [31], or search and pursuit [32] has also necessitated the consideration of line-of-sight constraints.In some of these cases, loss of line of sight is considered an unfortunate “fact of life” [30]; in other cases it is exploited to determine the connectivity properties of the environment [29, 31]. But none of these works explicitly includes a motion controller that actively prevents such losses from occurring.The principle difference between the connectivity work discussed in the previous section and the work presented in this paper, is that we modify the local connection/edge formation criteria to explicitly maintain line-of-sight constraints as well as the widely used single-hop, range constraint. To our knowledge this issue has only been considered in a few previous works. A behavior-based approach is described in [33]; while the performance cannot be proven it was illustrated through simulation. In [34] a planetary rover application was considered and six heuristics for maintaining line of sight were introduced. The approach was largely successful but could not solve all the presented test scenarios. The authors speculated that some of the unsolved scenarios were simply infeasible.


## 3. Problem Statement

Givenn point robots, let qi∈ℝ2 be the state vector of robot i. The robots operate in a subset of the plane C⊂ℝ2 which is populated with obstacles defined by compact sets Oj, j=1,…,m. Motion is generated according to the dynamics (1)q̇i=ui,
where the velocity input is ui∈U⊂ℝ2; qi is only permitted to evolve in the free space Cfree=C-⋃j=1mOj. Occasionally we will use q∈ℝ2n to denote the swarm state—the concatenation of states q1⋯qn; u to represent the concatenation of the input vectors; q̇=u to represent the collective swarm dynamics.Any given swarm stateq induces a communication graph G(q)=(V,E). Each vertex in the graph, vi∈V represents a robot and each edge eij∈E represents a wireless communication link between robots i and j. The edge eij is added to the graph if both of the following conditions are met.(1)
Range: d(qi,qj)≤ρmax where ρmax is some positive constant indicating the maximum effective range of the transmitter.(2)
Line of Sight: ∃x(s)∈Cfree, for all s∈[0,1], such that x(s)=sqi+(1-s)qj.Note thatd indicates distance as measured by the Euclidian metric. Both constraints model the power limitations of small wireless transmitters discussed in Section 1. A configuration q is said to be connected if the induced communication graph G is connected (i.e., if for any node pair i,j there exists an edge path of arbitrary length between them).We are concerned with the following problem (see Figure1), which requires the entire swarm to move to a desired position while maintaining certain communication links, G*.Figure 1
The basic problem considered in this paper. Design a control law to guide the swarm from the initial position,qo, to the desired final position, qf, while maintaining desired communication links (range plus line of sight).Problem 1.
Given an initial connected configurationqo=q(to), a desired final connected configuration qf and a graph G* such that G(qo)⊇G* andG(qf)⊇G*, determine a function 𝒰:[to,tf]→U such that(1)
q(tf)=qf (i.e., Goal-directed motion);(2)
G(q(t))⊇G*, for all t∈[to,tf] (Line of Sight and Range).


## 4. Existence of Solutions

Clearly there are certain combinations of the free spaceCfree and the desired connectivity graph G* for which the problem may not have a solution. Furthermore, even when a solution exists, there are certain classes of algorithms incapable of solving the problem. The concept of homotopy [35] is intimately related to these existence questions.


### 4.1. Homotopy Definitions

Ifq1,q2:[to,tf]→Cfree are continuous maps (paths), we say that q1(t) and q2(t) are homotopic if there exists a continuous map T:[to,tf]×[0,1]→Cfree such that (2)T(t,0)=q1(t),T(t,1)=q2(t),∀t.
If such a function exists, we say T is a homotopy. This homotopy defines an equivalence relation on paths. Note that unlike path homotopy [35], the endpoints of q1 and q2 do not coincide.Of particular interest in this paper is thestraight-line homotopy, illustrated in Figure 3 (right), (3)T(t,s)=(1-s)q1(t)+sq2(t),
due to its obvious connection to the line-of-sight constraint. If two paths q1(t), q2(t) have a straight line homotopy then the line-of-sight constraint is preserved for all t. If the range constraint is violated at any point on the trajectory, the straight-line homotopy can be used to correct the condition.


### 4.2. Intrinsic Lack of Solution

Obviously, whenCfree is not path connected, and q0 and qf lie in different connected components, there is no solution to the motion planning problem.Furthermore, ifCfree is multiply connected and G* contains cycles, solutions do not exist for all choices of qo or qf. To capture this we apply the concept of loop homotopy.A pathq, is considered a loop, λ, if q(to)=q(tf). Note that the trivial loop is the constant loop λ(t)=λ(to), for all t. We can apply the homotopy equivalence relation to loops as well. Similar to general homotopy, if one loop can be continuously deformed into a second loop, the two loops are loop-homotopic equivalent.For a given cycleGc⊆G*, one can connect the points qio corresponding to the vertices in the cycle to form a loop λo using straight-line segments; likewise a corresponding loop λf, using qf, can be constructed using the same vertices. See Figure 2 for an example. If these two loops are not in the same homotopic equivalence class, it implies that the loops wrap around the obstacles in such a way that is impossible to go from q0 to qf without disconnecting some edges, then no solution to the problem exists.Figure 2
Geometry of the line-of-sight problem, required to computeϕijlos.Figure 3
Frames depict an example of a combination ofG*, qo, and qf which are not feasible. Loops in left and right frames are not in the same homotopic equivalence class.Remark 1.
To ensure the existence of solutions in this paper we only consider path-connected free spaces; andq0,qf such that loops corresponding to any cycles of G* are homotopic to the constant loop.


### 4.3. Attribute of Complete Solution Algorithms

As remarked earlier, in order to maintain an edgeeij, for all t∈[to,tf], there must exist a straight-line homotopy between qi(t) and qj(t). Intuitively a necessary (not sufficient) condition for such a solution is that paths qi(t) and qj(t) must pass around the same “side" of an obstacle. See Figure 3. Therefore, if G* is connected, all robots, in some loose sense, must collectively pass around the same “side" of every obstacle—that is, the swarm cannot “split".This notion is difficult to formalize however. The traditional path-homotopy equivalence relation does not apply because the endpoints ofqi(t) and qj(t) do not coincide. Also, general homotopy does not preserve the line-of-sight constraint; and the straight-line homotopy does not induce an equivalence relation (it lacks transitivity). Instead we introduce the following definition which formalizes the concept of the paths “passing around the same side of the obstacle".Definition 2 (Path-Loop Homotopic Equivalence).
Given two pathsqi(t) and qj(t), consider the loop resulting from the concatenation λij=[qi(t)]·[qi(tf)→qj(tf)]·[qj(t)]-1·[qj(to)→qi(to)] (see Figure 3). We call qi(t) and qj(t) path loop homotopic if and only if λij is homotopic to the constant loop.Remark 3.
Later we will explore some connections between the definitions in this section and our control laws. Namely,(1)
our range potential produces motions equivilent to the straight line homotopy;(2)
the line-of-sight potential preserves path-loop homotopic equivalence;(3)
the pathloop homotopic equivalence condition suggests that a truly distributed controller is incapable of solving the problem for arbitrary initial conditions—either some “lead" robot must select a path class for the entire swarm or some type of bidirectional messaging must be used to reach a dynamic consensus on path-class selection.


## 4.1. Homotopy Definitions

Ifq1,q2:[to,tf]→Cfree are continuous maps (paths), we say that q1(t) and q2(t) are homotopic if there exists a continuous map T:[to,tf]×[0,1]→Cfree such that (2)T(t,0)=q1(t),T(t,1)=q2(t),∀t.
If such a function exists, we say T is a homotopy. This homotopy defines an equivalence relation on paths. Note that unlike path homotopy [35], the endpoints of q1 and q2 do not coincide.Of particular interest in this paper is thestraight-line homotopy, illustrated in Figure 3 (right), (3)T(t,s)=(1-s)q1(t)+sq2(t),
due to its obvious connection to the line-of-sight constraint. If two paths q1(t), q2(t) have a straight line homotopy then the line-of-sight constraint is preserved for all t. If the range constraint is violated at any point on the trajectory, the straight-line homotopy can be used to correct the condition.


## 4.2. Intrinsic Lack of Solution

Obviously, whenCfree is not path connected, and q0 and qf lie in different connected components, there is no solution to the motion planning problem.Furthermore, ifCfree is multiply connected and G* contains cycles, solutions do not exist for all choices of qo or qf. To capture this we apply the concept of loop homotopy.A pathq, is considered a loop, λ, if q(to)=q(tf). Note that the trivial loop is the constant loop λ(t)=λ(to), for all t. We can apply the homotopy equivalence relation to loops as well. Similar to general homotopy, if one loop can be continuously deformed into a second loop, the two loops are loop-homotopic equivalent.For a given cycleGc⊆G*, one can connect the points qio corresponding to the vertices in the cycle to form a loop λo using straight-line segments; likewise a corresponding loop λf, using qf, can be constructed using the same vertices. See Figure 2 for an example. If these two loops are not in the same homotopic equivalence class, it implies that the loops wrap around the obstacles in such a way that is impossible to go from q0 to qf without disconnecting some edges, then no solution to the problem exists.Figure 2
Geometry of the line-of-sight problem, required to computeϕijlos.Figure 3
Frames depict an example of a combination ofG*, qo, and qf which are not feasible. Loops in left and right frames are not in the same homotopic equivalence class.Remark 1.
To ensure the existence of solutions in this paper we only consider path-connected free spaces; andq0,qf such that loops corresponding to any cycles of G* are homotopic to the constant loop.


## 4.3. Attribute of Complete Solution Algorithms

As remarked earlier, in order to maintain an edgeeij, for all t∈[to,tf], there must exist a straight-line homotopy between qi(t) and qj(t). Intuitively a necessary (not sufficient) condition for such a solution is that paths qi(t) and qj(t) must pass around the same “side" of an obstacle. See Figure 3. Therefore, if G* is connected, all robots, in some loose sense, must collectively pass around the same “side" of every obstacle—that is, the swarm cannot “split".This notion is difficult to formalize however. The traditional path-homotopy equivalence relation does not apply because the endpoints ofqi(t) and qj(t) do not coincide. Also, general homotopy does not preserve the line-of-sight constraint; and the straight-line homotopy does not induce an equivalence relation (it lacks transitivity). Instead we introduce the following definition which formalizes the concept of the paths “passing around the same side of the obstacle".Definition 2 (Path-Loop Homotopic Equivalence).
Given two pathsqi(t) and qj(t), consider the loop resulting from the concatenation λij=[qi(t)]·[qi(tf)→qj(tf)]·[qj(t)]-1·[qj(to)→qi(to)] (see Figure 3). We call qi(t) and qj(t) path loop homotopic if and only if λij is homotopic to the constant loop.Remark 3.
Later we will explore some connections between the definitions in this section and our control laws. Namely,(1)
our range potential produces motions equivilent to the straight line homotopy;(2)
the line-of-sight potential preserves path-loop homotopic equivalence;(3)
the pathloop homotopic equivalence condition suggests that a truly distributed controller is incapable of solving the problem for arbitrary initial conditions—either some “lead" robot must select a path class for the entire swarm or some type of bidirectional messaging must be used to reach a dynamic consensus on path-class selection.


## 5. Potential Functions

### 5.1. Range

The range constraint dictates that ifeij∈G* then d(qi,qj)≤ρmax. This is enforced by a potential
(4)ϕijrange(qi,qj)={0,d(qi,qj)<ρmax⁡,(d(qi,qj)-ρmax⁡)2,d(qi,qj)≥ρmax⁡.
We point out several observations. (1)
The potential only possesses minima at configurations where the range constraint is satisfied.(2)
The partial derivatives are antisymmetric:∂ϕijrange/∂qi=-∂ϕijrange/∂qj.(3)
ϕrange is smooth and the partial derivatives are defined everywhere.(4)
The motion induced byq̇i=-∂ϕijrange/∂qi is essentially the straight-line homotopy and therefore preserves line of sight.


### 5.2. Line of Sight

If two robotsqi, qj such that eij∈E, are in danger of losing line of sight, it means one of them is occluded from the other's view by an obstacle as seen in Figure 4. Consider the straight line connecting them. We call the closest parallel that does not intersect the obstacle, the occlusion line, OL. The line-of-sight constraint is enforced by a potential: (5)ϕijlos(qi,qj)={0ifL.O.S.d2(qi,OL)else,
where d(qj,OL) denotes the distance from qi to the occlusion line defined in the usual way.Figure 4
The left frame illustrates a situation where line of sight is not maintained (no straight-line homotopy between paths; loop is not homotopic to constant loop). The right frame shows two paths that maintain line of sight (straight-line homotopy between paths; loop is homotopic to the constant loop).We point out several observations.(1)
The potential only possesses minima at configurations where the line-of-sight constraint is satisfied.(2)
The partial derivatives are symmetric∂ϕijlos/∂qi=∂ϕijlos/∂qj.(3)
The motion induced byui=uj=-∂ϕijlos/∂qi preserves path-loop homotopic equivalence.(4)
ϕlos is continuous and its partial derivatives are defined almost everywhere (see Figure 4).(5)
The set of measure zero, along whichϕlos is non-smooth, is not in the basin of attraction of the induced motion.To see why the third property holds, consider two paths that possess path-loop equivalence, such as in Figure3 (right). Deforming the path-loop in such a way as to make it no longer equivalent to the constant loop requires forcing one of the lines connecting qi and qj to cross through the center of the obstacle (Figure 4) which requires increasingϕlos.


### 5.3. Goal Attainment and Obstacle Avoidance

In this paper we use Navigation Functions as the basis for ensuring the goal completion portion of the problem (q→qf). Navigation Functions are artificial potential fields that simultaneously provide obstacle avoidance and almost everywhere convergence to a goal configuration [36].Definition 4 (Navigation Function).
For roboti, a scalar map ϕigoal:Cfree→[0,1] is aNavigation  Function if it is(1)
polar atqif (i.e., has a unique minimum on the path connected component of Cfree containing qif);(2)
admissible onCfree (i.e., it is uniformly maximal on the boundary of Cfree);(3)
a Morse function (i.e., its Hessian is nonsingular at the critical points);(4)
smooth onCfree (i.e., at least C2).As an example consider that in the simplest case of circular obstacles in a circular workspace, a navigation function for roboti can be defined as (6)ϕigoal⁡(qi)=d2(qi,qif)[dk(qi,qif)+∏j=0Md(qi,Oj)]1/k,
where Oj is obstacle j, O0 is the boundary of the workspace, and the parameter k must be selected high enough that all local minima, except at qif, disappear.Remark 5.
A fundamental result from topology (the Morse Index Theorem [35]) states that it is impossible to derive a smooth potential function that has only one critical point (at the goal) when the workspace is multiply connected. Therefore, any potential defined on a workspace with M obstacles will inevitably possess M saddle points. Emerging from each saddle point is a stable manifold connecting the saddle to other extrema. Initial positions on different sides of these manifolds evolve in different path loop homotopic equivalence classes around the obstacle associated with the saddle point. Therefore, if eij∈G(q0) but the line segment connecting qi(t0) and qj(t0) crosses the stable manifold, the necessary condition in Section 4 will not hold.


## 5.1. Range

The range constraint dictates that ifeij∈G* then d(qi,qj)≤ρmax. This is enforced by a potential
(4)ϕijrange(qi,qj)={0,d(qi,qj)<ρmax⁡,(d(qi,qj)-ρmax⁡)2,d(qi,qj)≥ρmax⁡.
We point out several observations. (1)
The potential only possesses minima at configurations where the range constraint is satisfied.(2)
The partial derivatives are antisymmetric:∂ϕijrange/∂qi=-∂ϕijrange/∂qj.(3)
ϕrange is smooth and the partial derivatives are defined everywhere.(4)
The motion induced byq̇i=-∂ϕijrange/∂qi is essentially the straight-line homotopy and therefore preserves line of sight.


## 5.2. Line of Sight

If two robotsqi, qj such that eij∈E, are in danger of losing line of sight, it means one of them is occluded from the other's view by an obstacle as seen in Figure 4. Consider the straight line connecting them. We call the closest parallel that does not intersect the obstacle, the occlusion line, OL. The line-of-sight constraint is enforced by a potential: (5)ϕijlos(qi,qj)={0ifL.O.S.d2(qi,OL)else,
where d(qj,OL) denotes the distance from qi to the occlusion line defined in the usual way.Figure 4
The left frame illustrates a situation where line of sight is not maintained (no straight-line homotopy between paths; loop is not homotopic to constant loop). The right frame shows two paths that maintain line of sight (straight-line homotopy between paths; loop is homotopic to the constant loop).We point out several observations.(1)
The potential only possesses minima at configurations where the line-of-sight constraint is satisfied.(2)
The partial derivatives are symmetric∂ϕijlos/∂qi=∂ϕijlos/∂qj.(3)
The motion induced byui=uj=-∂ϕijlos/∂qi preserves path-loop homotopic equivalence.(4)
ϕlos is continuous and its partial derivatives are defined almost everywhere (see Figure 4).(5)
The set of measure zero, along whichϕlos is non-smooth, is not in the basin of attraction of the induced motion.To see why the third property holds, consider two paths that possess path-loop equivalence, such as in Figure3 (right). Deforming the path-loop in such a way as to make it no longer equivalent to the constant loop requires forcing one of the lines connecting qi and qj to cross through the center of the obstacle (Figure 4) which requires increasingϕlos.


## 5.3. Goal Attainment and Obstacle Avoidance

In this paper we use Navigation Functions as the basis for ensuring the goal completion portion of the problem (q→qf). Navigation Functions are artificial potential fields that simultaneously provide obstacle avoidance and almost everywhere convergence to a goal configuration [36].Definition 4 (Navigation Function).
For roboti, a scalar map ϕigoal:Cfree→[0,1] is aNavigation  Function if it is(1)
polar atqif (i.e., has a unique minimum on the path connected component of Cfree containing qif);(2)
admissible onCfree (i.e., it is uniformly maximal on the boundary of Cfree);(3)
a Morse function (i.e., its Hessian is nonsingular at the critical points);(4)
smooth onCfree (i.e., at least C2).As an example consider that in the simplest case of circular obstacles in a circular workspace, a navigation function for roboti can be defined as (6)ϕigoal⁡(qi)=d2(qi,qif)[dk(qi,qif)+∏j=0Md(qi,Oj)]1/k,
where Oj is obstacle j, O0 is the boundary of the workspace, and the parameter k must be selected high enough that all local minima, except at qif, disappear.Remark 5.
A fundamental result from topology (the Morse Index Theorem [35]) states that it is impossible to derive a smooth potential function that has only one critical point (at the goal) when the workspace is multiply connected. Therefore, any potential defined on a workspace with M obstacles will inevitably possess M saddle points. Emerging from each saddle point is a stable manifold connecting the saddle to other extrema. Initial positions on different sides of these manifolds evolve in different path loop homotopic equivalence classes around the obstacle associated with the saddle point. Therefore, if eij∈G(q0) but the line segment connecting qi(t0) and qj(t0) crosses the stable manifold, the necessary condition in Section 4 will not hold.


## 6. Parallel Composition

At any time, roboti must select a direction to move, which goes toward its goal position and avoid obstacles (ideally, q̇i=-∂ϕigoal/∂qi), and for each corresponding edge eij in G*, it must maintain range (ideally q̇i=-∂ϕijrange/∂qi) and line of sight (ideally q̇i=-∂ϕijlos/∂qi). Simply adding the three underlying potential functions does not guarantee that their underlying behavior is retained and may introduce local minima. In this section we explain how this disparate objectives are composed in parallel.


### 6.1. Theory

Consider a single roboti and a single associated scalar navigation function ϕigoal. Typically, goal attainment and obstacle collision avoidance is achieved by the unique choice of input u=-∇∂ϕigoal. However, we will see that there are an uncountable set of possible inputs that meet these objectives.Theorem 6.
Given a Navigation functionϕigoal, define a vector field [∇ϕigoal]⊥ such that ∇ϕi·[∇ϕigoal]⊥=0, for all q, with [∇ϕigoal]⊥=0 where ∇ϕigoal=0. Then the control law
(7)uiα=-α1(t)∇ϕigoal⁡+α2(t)[∇ϕigoal⁡]⊥,
also results in goal attainment and obstacle avoidance, for any function α:ℝ+→ℝ+×ℝ.The proof [37] proceeds in two parts. First we address goal attainment.Proof.
Observe thatϕigoal satisfies all the criteria of a candidate Lyapunov function since it is continuous and positive definite. Next note that any given constant value of α̅ can be used to define a dynamic system that for which ϕigoal is a Lyapunov function and qf is an equilibrium, since it is strictly decreasing along system trajectories except at qf(8)ϕ̇igoal⁡=∇ϕigoal⁡⋅uiα=∇ϕigoal⁡⋅(-α1(t)∇ϕigoal⁡+α2(t)[∇ϕigoal⁡]⊥)=∇ϕigoal⁡⋅(-α1∇ϕigoal⁡)≤0.
Therefore, the equilibrium point, qf must be asymptotically stable. This family of differential equations, parameterized by α̅, shares ϕigoal as a common Lyapunov Function. It is known (see [38] or [39]) that a dynamic system whose derivative switches between such a family will be stabilized to the common equilibrium, regardless of the nature of the switching sequence.Next we show the obstacle avoidance property is preserved.Proof.
For any point on the boundary of the free spaceq∈∂O let n̂(q) be the unit normal pointing toward the interior of the free space. Then proving that the robot does not hit the obstacles is equivalent to proving q̇i·n̂(qi)≥0, for all qi∈∂O. Using q̇i=uiα we have
(9)(-α1∇ϕigoal⁡+α2[∇ϕigoal⁡]⊥)⋅n̂.
Recall that navigation functions are uniformly maximal on the boundary of the free space, so -∇ϕigoal(q) is parallel to n̂(q) for all q∈∂O, so -∇ϕigoal(q)·n̂(q)>0 and [∇ϕigoal(q)]⊥·n̂(q)=0. Therefore (9) reduces to
(10)(-α1∇ϕgoal⁡⋅n̂)≥0.This proof suggests that we are able to select values ofα online to satisfy other objectives, in a possibly discontinuous fashion, without destroying the goal attainment or obstacle avoidance behavior of the navigation function.Remark 7.
This fact that many vector fields can decrease the value of the potential was observed in [40, 41]; the set of all input vectors which decrease some cost-to-go function is termed the “cone of progress”. However in both of these contexts the fact is used passively to address sensor uncertainty—rather than to explicitly construct a motion control law.We now turn our attention toϕijrange and ϕijlos.Theorem 8.
Assume at timet=0, that ϕijrange=0 and ϕijlos=0. Any control law ui which satisfies both
(11)∂∂qiϕijrange⋅(ui-uj)≤0,(12)∂∂qiϕijlos⋅(ui+uj)≤0,
preserves the range and line of sight constraints for all t.Proof.
Thus(13)ϕ̇ijrange=∂∂qiϕijrange⋅q̇i+∂∂qjϕijrange⋅q̇j.
However, q̇i=ui and the partial derivatives are antisymmetric, leading to the result above. The derivation of the second equation is analogous—except that the partial derivatives of the line-of-sight constraint are symmetric.


### 6.2. Algorithm

Problem 2.
Assume roboti knows ∂ϕigoal/∂qi, ∂ϕijlos/∂qi, ∂ϕijrange/∂qi, and uj. Compute α to
(14)min⁡(-(α1)2+(α2)2),
such that
(15)∂∂qiϕijrange⋅(uiα-uj)≤0,∂∂qiϕijlos⋅(uiα+uj)≤0,
with 0≤α1≤α1max and -α2max≤α2≤α2max.We call such auiα, if it exists, a feasible direction. The concept of a feasible direction bears some relation to, and is named after, a numerical optimization method [42]; it is also loosely related to so-called null-space control methods [9].Consider Figure5. Geometric insight into the problem can be gained from recognizing that the range and line-of-sight constraints each define a cone in the velocity space. While the set of all uiα defines a half plane of possible velocity vectors.Figure 5
An illustration of the velocity selection problem for roboti. uα is the set of all vectors in the same half plane as -∂ϕigoal/∂qi (labeled as Goal). Similarly, the range and line of sight constraints define cones in the tangent space. The set of feasible directions lies at the intersection of these sets.If the intersection of the two cones and half plane is empty, no solution exists; and one of the constraints must be relaxed. If the intersection is not empty the formulation of the objective function reflects a preference toward rapid goal attainment (largeα1 and small α2).Computationally, this is a essentially a semidefinite programming problem, which can be solved in polynomial-time [43]. We use the CVX package, implemented in Matlab [44].One attractive feature of the semidefinite programming approach used inCVX is that if the set of feasible direction, depicted in Figure 5 is not empty, the algorithm is guaranteed to find a solution in polynomial time. Because the problem is very small (2 dimensions and 2 constraints) numerical solution can be computed extremely rapidly.In cases where the set of feasible directions is empty, simultaneously satisfying the three objectives is impossible.CVX will recognize this and report failure.This approach is summarized in Algorithm1.Algorithm 1:Algorithm for generating a feasible motion direction for Robot i, using time steps Δt.
Lett=0.while  qi≠qifdofor  j such that there exists eij∈G*doDetermineqj and ujCompute∂ϕijlos/∂qi and ∂ϕijrange/∂qiend  forCompute∂ϕigoal/∂qiComputeuα via numerical optimizationif Feasible thenMove.t=t+ΔtelseInfeasible. Drop a constraint or terminate.end  ifend  while


### 6.3. Problem Structure and Completeness

So far we have show that alluα satisfy the goal objective; and at each time step, if there is exists a value of α that meets the constraints, the numerical optimization algorithm is guaranteed to find it. Still the question remains: are there situations in which there is no value of α that will solve the problem? The answer is yes. As discussed in Remark 5, given any eij∈G* if the line connecting qio and qjo, or qif and qjf intersects a stable manifold of the Navigation Function’s saddle points the problem is infeasible. Figure 6 graphically illustrates one such scenario, both robots are selecting infeasible directions as the Navigation function tries to force them into different path classes around the obstacle. When this occurs we drop one of the constraints until a feasible solution exists. This is discussed more in Section 7.Figure 6
A generic pair of robots, with active line of sight and range constraints. Figure indicates possible directions of-(∂/∂q)ϕgoal that could result in no feasible direction for simultaneously satisfying three objectives.


## 6.1. Theory

Consider a single roboti and a single associated scalar navigation function ϕigoal. Typically, goal attainment and obstacle collision avoidance is achieved by the unique choice of input u=-∇∂ϕigoal. However, we will see that there are an uncountable set of possible inputs that meet these objectives.Theorem 6.
Given a Navigation functionϕigoal, define a vector field [∇ϕigoal]⊥ such that ∇ϕi·[∇ϕigoal]⊥=0, for all q, with [∇ϕigoal]⊥=0 where ∇ϕigoal=0. Then the control law
(7)uiα=-α1(t)∇ϕigoal⁡+α2(t)[∇ϕigoal⁡]⊥,
also results in goal attainment and obstacle avoidance, for any function α:ℝ+→ℝ+×ℝ.The proof [37] proceeds in two parts. First we address goal attainment.Proof.
Observe thatϕigoal satisfies all the criteria of a candidate Lyapunov function since it is continuous and positive definite. Next note that any given constant value of α̅ can be used to define a dynamic system that for which ϕigoal is a Lyapunov function and qf is an equilibrium, since it is strictly decreasing along system trajectories except at qf(8)ϕ̇igoal⁡=∇ϕigoal⁡⋅uiα=∇ϕigoal⁡⋅(-α1(t)∇ϕigoal⁡+α2(t)[∇ϕigoal⁡]⊥)=∇ϕigoal⁡⋅(-α1∇ϕigoal⁡)≤0.
Therefore, the equilibrium point, qf must be asymptotically stable. This family of differential equations, parameterized by α̅, shares ϕigoal as a common Lyapunov Function. It is known (see [38] or [39]) that a dynamic system whose derivative switches between such a family will be stabilized to the common equilibrium, regardless of the nature of the switching sequence.Next we show the obstacle avoidance property is preserved.Proof.
For any point on the boundary of the free spaceq∈∂O let n̂(q) be the unit normal pointing toward the interior of the free space. Then proving that the robot does not hit the obstacles is equivalent to proving q̇i·n̂(qi)≥0, for all qi∈∂O. Using q̇i=uiα we have
(9)(-α1∇ϕigoal⁡+α2[∇ϕigoal⁡]⊥)⋅n̂.
Recall that navigation functions are uniformly maximal on the boundary of the free space, so -∇ϕigoal(q) is parallel to n̂(q) for all q∈∂O, so -∇ϕigoal(q)·n̂(q)>0 and [∇ϕigoal(q)]⊥·n̂(q)=0. Therefore (9) reduces to
(10)(-α1∇ϕgoal⁡⋅n̂)≥0.This proof suggests that we are able to select values ofα online to satisfy other objectives, in a possibly discontinuous fashion, without destroying the goal attainment or obstacle avoidance behavior of the navigation function.Remark 7.
This fact that many vector fields can decrease the value of the potential was observed in [40, 41]; the set of all input vectors which decrease some cost-to-go function is termed the “cone of progress”. However in both of these contexts the fact is used passively to address sensor uncertainty—rather than to explicitly construct a motion control law.We now turn our attention toϕijrange and ϕijlos.Theorem 8.
Assume at timet=0, that ϕijrange=0 and ϕijlos=0. Any control law ui which satisfies both
(11)∂∂qiϕijrange⋅(ui-uj)≤0,(12)∂∂qiϕijlos⋅(ui+uj)≤0,
preserves the range and line of sight constraints for all t.Proof.
Thus(13)ϕ̇ijrange=∂∂qiϕijrange⋅q̇i+∂∂qjϕijrange⋅q̇j.
However, q̇i=ui and the partial derivatives are antisymmetric, leading to the result above. The derivation of the second equation is analogous—except that the partial derivatives of the line-of-sight constraint are symmetric.


## 6.2. Algorithm

Problem 2.
Assume roboti knows ∂ϕigoal/∂qi, ∂ϕijlos/∂qi, ∂ϕijrange/∂qi, and uj. Compute α to
(14)min⁡(-(α1)2+(α2)2),
such that
(15)∂∂qiϕijrange⋅(uiα-uj)≤0,∂∂qiϕijlos⋅(uiα+uj)≤0,
with 0≤α1≤α1max and -α2max≤α2≤α2max.We call such auiα, if it exists, a feasible direction. The concept of a feasible direction bears some relation to, and is named after, a numerical optimization method [42]; it is also loosely related to so-called null-space control methods [9].Consider Figure5. Geometric insight into the problem can be gained from recognizing that the range and line-of-sight constraints each define a cone in the velocity space. While the set of all uiα defines a half plane of possible velocity vectors.Figure 5
An illustration of the velocity selection problem for roboti. uα is the set of all vectors in the same half plane as -∂ϕigoal/∂qi (labeled as Goal). Similarly, the range and line of sight constraints define cones in the tangent space. The set of feasible directions lies at the intersection of these sets.If the intersection of the two cones and half plane is empty, no solution exists; and one of the constraints must be relaxed. If the intersection is not empty the formulation of the objective function reflects a preference toward rapid goal attainment (largeα1 and small α2).Computationally, this is a essentially a semidefinite programming problem, which can be solved in polynomial-time [43]. We use the CVX package, implemented in Matlab [44].One attractive feature of the semidefinite programming approach used inCVX is that if the set of feasible direction, depicted in Figure 5 is not empty, the algorithm is guaranteed to find a solution in polynomial time. Because the problem is very small (2 dimensions and 2 constraints) numerical solution can be computed extremely rapidly.In cases where the set of feasible directions is empty, simultaneously satisfying the three objectives is impossible.CVX will recognize this and report failure.This approach is summarized in Algorithm1.Algorithm 1:Algorithm for generating a feasible motion direction for Robot i, using time steps Δt.
Lett=0.while  qi≠qifdofor  j such that there exists eij∈G*doDetermineqj and ujCompute∂ϕijlos/∂qi and ∂ϕijrange/∂qiend  forCompute∂ϕigoal/∂qiComputeuα via numerical optimizationif Feasible thenMove.t=t+ΔtelseInfeasible. Drop a constraint or terminate.end  ifend  while


## 6.3. Problem Structure and Completeness

So far we have show that alluα satisfy the goal objective; and at each time step, if there is exists a value of α that meets the constraints, the numerical optimization algorithm is guaranteed to find it. Still the question remains: are there situations in which there is no value of α that will solve the problem? The answer is yes. As discussed in Remark 5, given any eij∈G* if the line connecting qio and qjo, or qif and qjf intersects a stable manifold of the Navigation Function’s saddle points the problem is infeasible. Figure 6 graphically illustrates one such scenario, both robots are selecting infeasible directions as the Navigation function tries to force them into different path classes around the obstacle. When this occurs we drop one of the constraints until a feasible solution exists. This is discussed more in Section 7.Figure 6
A generic pair of robots, with active line of sight and range constraints. Figure indicates possible directions of-(∂/∂q)ϕgoal that could result in no feasible direction for simultaneously satisfying three objectives.


## 7. Experiments

The method is tested both in simulation and on a group of mobile robots.


### 7.1. Simulation

First, the method was simulated using Matlab (version 2010A) on a desktop PC. We created a 300 by 300 unit workspace, populated with random triangular obstacles, as seen in Figure8. Red circles represent robots; green lines indicate wireless links; and blue stars are goal configurations.For the first set of experiments 5 robots are required to maintain a “P-" shaped connectivity graph. For example see the configuration labeled “frame 1" in the lower left quadrant of Figure8. The P shape was chosen because it includes both leaf vertices as well as a cycle. The maximum acceptable range ρmax was chosen to be 50 units.The robots are placed in randomly generated initial scenarios using a uniform distribution. In order to generate acceptable scenarios, each initial condition was tested for two criteria.(1)
Is the desired P-shaped connectivity graph a subset of the connectivity graph induced by the range and line of sight conditions?(2)
Are all of the robots inside the free space?If the answer to either of these questions was “no", the condition was rejected and a new set of random positions was generated. This methodology is identical to the one used to generate samples for Monte-Carlo integration over nonrectangular domains.Even though the simulation is done on a single PC, we try to replicate the typical information dependencies that would arise on a distributed multirobot system. Specifically, roboti was assumed to know: (1)
its own positionqi;(2)
the geometry of the obstacles and the workspace;(3)
the position and velocity,qj and uj, of any robots for which the range and line-of-sight criteria are met.Regarding the first two assumptions, they are difficult to guarantee for physical implementation, but are none the less standard simulation assumptions in the literature. Regarding the third, recall that the motivation for designing this motion controller is to maintain communication links. Therefore, it is reasonable that those links could be used for peer-to-peer communication that is helpful for that purpose. Finally, we point out that the robots donot require all-to-all information exchanges of their position and velocity—the only global variable is time.In the context of the simulation, the robots exchange the required information as permitted and recompute their velocities via numerical optimization every time step (0.1 second). Their top speed is 10 units/sec. Because there are no higher order dynamics, we use a forward Euler numerical integration method. To numerically solve the velocity selection problem at each time step, we usedCVX Version 1.21, with the default SeDuMi solver and the precision option set to “low" (machine precision1/4). The computation time for the optimization method was on average 0.032 sec per robot per time step, with a standard deviation of 0.008 sec. The computer we used ran Windows XP (32-bit), 1 GB RAM, and an AMD Athlon64 processor running at 2.2 GHz.We selected one typical example scenario for illustration shown in Figure8. As the robots move from frame 1 to frame 2, the leaf vertex’s range to its neighbor is ρmax and the range constraint is active. There is also an extra link that forms dynamically as two of the robots come with range. Between frames 2 and 3 and again from 3-4 the leaf node’s line of sight constraint becomes active to prevent it from being occluded by the obstacle vertices. After frame 4, the robots proceed straight to the goal configuration at t≈39 sec. The goal configuration was selected to comply with the range and line-of-sight constraints dictated by the desired connectivity graph.A second scenario illustrates this with a larger group of 12 robots and 15 desired links and is shown in Figure9. Beginning in the upper right corner, the swarm constricts to fit through the gap between the two obstacles. The configuration snapshot in the middle of the figure shows an example of the many line-of-sight constraints that were activated as the robots negotiated the lower vertex of the left obstacle.The table in Figure7 summarizes the experiments. For each swarm size (n=5, 12, and 20) we randomly generated 50 initial scenarios. The third column lists the number of scenarios that had active range or line-of-sight constraints. Many random scenarios do not exercise the constraints. For example, initial conditions that are very close to the goal may not require negotiating any obstacles. In other cases, the natural behavior of the navigation function generates motions that respect the range constraint.Figure 7
Simulation results for connectivity algorithm.Figure 8
A swarm of 5 robots maintaining a specified communication graph, beginning in the lower left corner and moving toward the upper right corner.Figure 9
A swarm of 12 robots maintaining a specified communication graph. Beginning in the upper right corner and moving toward the lower left corner.The next column lists how many scenarios resulted in a minor constraint violation. We define a minor violation as a short duration (2 or fewer time steps), small magnitude < (0.1 sec × 10 m/s)2 violations of (12) or (11). An illustration of a minor violation is included in Figure 10. The leaf vertex briefly violated the line-of-sight constraint. The primary reason this occurs is that velocity sharing effectively induces a delay, meaning that robot i uses robot j's velocity from the previous time step to compute its new velocity. This can lead to small violations of the constraints. As the time step gets smaller, or the maximum velocity decreases, the magnitude of these violations decreases. In practice, such a small constraint violation is unlikely to cause a wireless link to fail. However, the effect can be mitigated by including a small constant “buffer" in (12) or (11).Figure 10
An illustration of a minor constraint violation.The final column lists the number of scenarios deemed infeasible byCVX. An illustration of an infeasible situation is included in Figure 11. One can see that robots 1, 4, and 5 start on the opposite side of the saddle point emanating from the left obstacle (depicted as the dotted red line) as compared with robots 2 and 3. Such scenarios, eventually lead to a situation in which the optimization routine determines the problem is infeasible. In such cases, we drop the offending constraints until a solution exists. They are later added back once the problem becomes feasible again and the robots are no longer separated by a saddle point. This is an unfortunate limitation of the approach proposed here.Figure 11
An illustration of an infeasible problem.The algorithm was implemented on 6 iRobot Creates, shown in Figure12. Each robot is controlled with an onboard netbook, using the Matlab Tool Box for the iRobot Create (MTIC) [45]. Their forward speed is limited to 0.2 meter/sec and use a time step of 0.5 seconds. They are given a manually made metric map of the environment, which is a 3 by 5 meter carpeted region. The obstacles are a 0.38 by 0.39 meter chair and a 0.6 by 0.6 meter cardboard box. We exploit their zero turn radius and use a backstepping controller (see our previous work [37] for details) to simulate the holonomic motions produced by the algorithm. The Minkowski sum of the robot’s footprint and the obstacles is used to account for the size of the robots [36]. The robots were tagged with retro-reflective fiducials and each robot obtained their positions from a 6 camera Vicon Motion Capture System, set up to broadcast simulated GPS NMEA messages. Each robot is also equipped with a Xbee radio modem to allow it to receive simulated GPS information as well as to exchange position and velocity with other robots. Due to the high power of the Xbee modules, and the small spatial scale of the experiment, signal strength tends to be high regardless of range or line of sight. Therefore, each robot's communication program is set to simulate these constraints, by only passing the exchanged information to the main program if they are met. Figures 12 and 13 show six snap shots of a feasible scenario where the range and line-of-sight constraints are active.Three sequential snapshots of the 6 iRobot Creates executing the motion planner presented in this paper. The first frame show the connectivity ring and the goal positions.Three sequential snapshots of the 6 iRobot Creates executing the motion planner presented in this paper. Frame 6 is the goal position.


## 7.1. Simulation

First, the method was simulated using Matlab (version 2010A) on a desktop PC. We created a 300 by 300 unit workspace, populated with random triangular obstacles, as seen in Figure8. Red circles represent robots; green lines indicate wireless links; and blue stars are goal configurations.For the first set of experiments 5 robots are required to maintain a “P-" shaped connectivity graph. For example see the configuration labeled “frame 1" in the lower left quadrant of Figure8. The P shape was chosen because it includes both leaf vertices as well as a cycle. The maximum acceptable range ρmax was chosen to be 50 units.The robots are placed in randomly generated initial scenarios using a uniform distribution. In order to generate acceptable scenarios, each initial condition was tested for two criteria.(1)
Is the desired P-shaped connectivity graph a subset of the connectivity graph induced by the range and line of sight conditions?(2)
Are all of the robots inside the free space?If the answer to either of these questions was “no", the condition was rejected and a new set of random positions was generated. This methodology is identical to the one used to generate samples for Monte-Carlo integration over nonrectangular domains.Even though the simulation is done on a single PC, we try to replicate the typical information dependencies that would arise on a distributed multirobot system. Specifically, roboti was assumed to know: (1)
its own positionqi;(2)
the geometry of the obstacles and the workspace;(3)
the position and velocity,qj and uj, of any robots for which the range and line-of-sight criteria are met.Regarding the first two assumptions, they are difficult to guarantee for physical implementation, but are none the less standard simulation assumptions in the literature. Regarding the third, recall that the motivation for designing this motion controller is to maintain communication links. Therefore, it is reasonable that those links could be used for peer-to-peer communication that is helpful for that purpose. Finally, we point out that the robots donot require all-to-all information exchanges of their position and velocity—the only global variable is time.In the context of the simulation, the robots exchange the required information as permitted and recompute their velocities via numerical optimization every time step (0.1 second). Their top speed is 10 units/sec. Because there are no higher order dynamics, we use a forward Euler numerical integration method. To numerically solve the velocity selection problem at each time step, we usedCVX Version 1.21, with the default SeDuMi solver and the precision option set to “low" (machine precision1/4). The computation time for the optimization method was on average 0.032 sec per robot per time step, with a standard deviation of 0.008 sec. The computer we used ran Windows XP (32-bit), 1 GB RAM, and an AMD Athlon64 processor running at 2.2 GHz.We selected one typical example scenario for illustration shown in Figure8. As the robots move from frame 1 to frame 2, the leaf vertex’s range to its neighbor is ρmax and the range constraint is active. There is also an extra link that forms dynamically as two of the robots come with range. Between frames 2 and 3 and again from 3-4 the leaf node’s line of sight constraint becomes active to prevent it from being occluded by the obstacle vertices. After frame 4, the robots proceed straight to the goal configuration at t≈39 sec. The goal configuration was selected to comply with the range and line-of-sight constraints dictated by the desired connectivity graph.A second scenario illustrates this with a larger group of 12 robots and 15 desired links and is shown in Figure9. Beginning in the upper right corner, the swarm constricts to fit through the gap between the two obstacles. The configuration snapshot in the middle of the figure shows an example of the many line-of-sight constraints that were activated as the robots negotiated the lower vertex of the left obstacle.The table in Figure7 summarizes the experiments. For each swarm size (n=5, 12, and 20) we randomly generated 50 initial scenarios. The third column lists the number of scenarios that had active range or line-of-sight constraints. Many random scenarios do not exercise the constraints. For example, initial conditions that are very close to the goal may not require negotiating any obstacles. In other cases, the natural behavior of the navigation function generates motions that respect the range constraint.Figure 7
Simulation results for connectivity algorithm.Figure 8
A swarm of 5 robots maintaining a specified communication graph, beginning in the lower left corner and moving toward the upper right corner.Figure 9
A swarm of 12 robots maintaining a specified communication graph. Beginning in the upper right corner and moving toward the lower left corner.The next column lists how many scenarios resulted in a minor constraint violation. We define a minor violation as a short duration (2 or fewer time steps), small magnitude < (0.1 sec × 10 m/s)2 violations of (12) or (11). An illustration of a minor violation is included in Figure 10. The leaf vertex briefly violated the line-of-sight constraint. The primary reason this occurs is that velocity sharing effectively induces a delay, meaning that robot i uses robot j's velocity from the previous time step to compute its new velocity. This can lead to small violations of the constraints. As the time step gets smaller, or the maximum velocity decreases, the magnitude of these violations decreases. In practice, such a small constraint violation is unlikely to cause a wireless link to fail. However, the effect can be mitigated by including a small constant “buffer" in (12) or (11).Figure 10
An illustration of a minor constraint violation.The final column lists the number of scenarios deemed infeasible byCVX. An illustration of an infeasible situation is included in Figure 11. One can see that robots 1, 4, and 5 start on the opposite side of the saddle point emanating from the left obstacle (depicted as the dotted red line) as compared with robots 2 and 3. Such scenarios, eventually lead to a situation in which the optimization routine determines the problem is infeasible. In such cases, we drop the offending constraints until a solution exists. They are later added back once the problem becomes feasible again and the robots are no longer separated by a saddle point. This is an unfortunate limitation of the approach proposed here.Figure 11
An illustration of an infeasible problem.The algorithm was implemented on 6 iRobot Creates, shown in Figure12. Each robot is controlled with an onboard netbook, using the Matlab Tool Box for the iRobot Create (MTIC) [45]. Their forward speed is limited to 0.2 meter/sec and use a time step of 0.5 seconds. They are given a manually made metric map of the environment, which is a 3 by 5 meter carpeted region. The obstacles are a 0.38 by 0.39 meter chair and a 0.6 by 0.6 meter cardboard box. We exploit their zero turn radius and use a backstepping controller (see our previous work [37] for details) to simulate the holonomic motions produced by the algorithm. The Minkowski sum of the robot’s footprint and the obstacles is used to account for the size of the robots [36]. The robots were tagged with retro-reflective fiducials and each robot obtained their positions from a 6 camera Vicon Motion Capture System, set up to broadcast simulated GPS NMEA messages. Each robot is also equipped with a Xbee radio modem to allow it to receive simulated GPS information as well as to exchange position and velocity with other robots. Due to the high power of the Xbee modules, and the small spatial scale of the experiment, signal strength tends to be high regardless of range or line of sight. Therefore, each robot's communication program is set to simulate these constraints, by only passing the exchanged information to the main program if they are met. Figures 12 and 13 show six snap shots of a feasible scenario where the range and line-of-sight constraints are active.Three sequential snapshots of the 6 iRobot Creates executing the motion planner presented in this paper. The first frame show the connectivity ring and the goal positions.Three sequential snapshots of the 6 iRobot Creates executing the motion planner presented in this paper. Frame 6 is the goal position.


## 8. Conclusion

Motivated by the use of wireless communication among swarm members, in this paper we consider the problem of steeringn robots to n goals, while maintaining some range and line-of-sight constraints in the presence of obstacles. Range and line of sight are two conditions which improve the reliability of wireless transmission. To the author's knowledge this is the first work to consider the effect of line-of-sight constraints for swarms. After establishing some basic conditions on the existence of solutions, we show that one rather profound condition is that all robots must pass on the same side of an obstacle (same path-class) for the swarm to remain connected. An implication of this is that, in order to remain connected, the swarm must either have a leader or some online method for achieving consensus on the path class. A further consequence of this is that navigation functions do not offer a global solution to this problem because the existence of saddle points makes it impossible to guarantee all robots select the same path class for arbitrary initial conditions. Basic potentials for Range and Line-of-Sight Constraints were introduced and a method for composing multiple potential functions into a single feasible motion direction was presented. An efficient computational algorithm to compute this direction is proposed. Simulations and hardware-based demonstrations of the algorithm’s operation are provided and show promising results.



---

*Source: 571485-2011-08-28.xml*