Cooperative visibility maintenance in SE(3)for multi-robot-networks with limited field-of-view sensors

Hasan A.POONAWALA,Mark W.SPONG

1.Institute for Computational Engineering&Sciences,University of Texas,Austin,TX 78712,U.S.A.;

2.Erik Jonsson School of Engineering&Computer Science,University of Texas at Dallas,Richardson,TX 75080,U.S.A.

Cooperative visibility maintenance in SE(3)for multi-robot-networks with limited field-of-view sensors

Hasan A.POONAWALA1,Mark W.SPONG2?

1.Institute for Computational Engineering&Sciences,University of Texas,Austin,TX 78712,U.S.A.;

2.Erik Jonsson School of Engineering&Computer Science,University of Texas at Dallas,Richardson,TX 75080,U.S.A.

Coordination of motion between multiple robots requires the robots to sense their relative poses.Common sensors depend on maintaining a line-of-sight between the sensor and the object being sensed.When the robots move relative to one another,they must coordinate their motions to ensure that these lines-of-sight are preserved.We propose a control method to preserve desired lines-of-sight in a multi-robot system where each robot has configuration space SE(3).A key feature of the control method is its ability to reject persistent bounded disturbances,enabling its use alongside additional control tasks.We demonstrate the effectiveness of the edge-preserving control in simulations involving additional input velocities that tend to break the edges.

Multi-robot coordination,decentralized control,graph theoretic control

1 Introduction

Multi-robot teams are expected to be a common tool for completion of tasks in large geographic environments.Examples of such tasks include search,surveillance,and object tracking.These teams will need reliable methods to coordinate their motions in order to be autonomous.A considerable amount of research effort has been spent on coordinated behaviors such as location rendezvous[1,2],formation control,and obstacle avoidance.

These multi-robot coordination algorithms rely on the ability of the robots to measure their relative positions.Distributed localization algorithms also require the relative positions between particular sets of robots to be measurable[3].Sensors such as optical cameras,sonar,and LIDAR are commonly used to measure these relative positions.For such sensors,a measurement of the relative position of an object can be made only when the line-of-sight between the sensor and the object is inside the field-of-view of the sensor and not occluded by another object.When this requirement is met,we say that the object is visible to the sensor.

As the robots move relative to one another in order to complete a task,it is possible that relevant lines-of-sight may leave the field-of-view of the associated sensor,or be occluded by an object.Visibility maintenance refers to the problem of preserving these lines-of-sight.The simplest way to preserve the lines-of-sight is to prevent any motion of the robots.This approach is clearly too restrictive,and one would prefer control laws that do not prevent motions compatible with preserving the required lines-of-sight.Moreover,the needs of any multirobot team can be expected to evolve over time,especially when reacting to external situations.This timevarying aspect of the team may result in the need to preserve different lines-of-sights at different times.Therefore,any control we develop must be able to handle these changing requirements.

1.1 Related work

Researchers usually consider two types of visibility maintenance problems.The first type involves an adversarial scenario,where one mobile agent is a target that must be kept within sight at all times by either one or multiple robots.Many approaches use a game-theoretic formulation[4]to study the case of adversarial visibility maintenance.In most cases,the work considers one target and one chaser,especially when providing theoretical guarantees.

The second type of visibility maintenance problem is when the robots must cooperate to preserve multiple lines-of-sight.In this case,it is the existence of multiple simultaneous,and potentially conflicting,constraints on the lines-of-sight that is the root of the problem.This type of problem has been studied in[5–7].These methods usually consider visibility maintenance where the set of lines-of-sight that must be preserved form a directed chain graph.The control law is explicitly developed for planar nonholonomic wheeled mobile robots,that is,agents in SE(2).

In all these methods,the feedback control law is designed for obstacle-free environments,where occlusion is not possible.In order to account for occlusions,the free space available for motion is decomposed into occlusion-free cells[7]or nodes of a graph[8].Using the cells or nodes,a motion planning algorithm coordinates the movement of the robots between these cells in such a way that visibility is maintained.

1.2 Contributions

In this paper,we propose a decentralized control law that preserves multiple lines-of-sight formed by robots equipped with limited field-of-view sensors.This control law possesses a number of properties that distinguishes it from similar contributions in the literature.First,the control law allows robots to preserve multiple edges at the same time,instead of only one as in the case of directed chain graphs.Second,the guarantees of the control law still hold when a bounded external term is present in the input.This property makes the control robust to disturbances and allows its use in conjunction with unknown additive control inputs corresponding to additional tasks.Third,the sensors have configuration in SE(3),making the control useful for aerial robots such as quadrotors.Fourth,the control law uses a hybrid mechanism to enable time-varying preservation of edges,while ensuring that the control is continuous in time.Apreliminary version of this control law for robots with planar kinematics was presented in[9].We represent the orientation of the robot by a rotation matrix here instead of a single scalar value.We develop several non-trivial extensions to define and analyze the control law in this paper to deal with this change,when compared to the work in[9].Furthermore,the focus of this paper is the control law for preserving edges,unlike[9]which focuses on the connectivity properties of directed sensing networks.

2 Preliminaries

In this section we introduce the model of the robot dynamics and concepts from graph theory required to present the problem.

2.1 Robot kinematics

We consider a team of N∈N robots.The center of each robot is a point pi∈R3,where i∈{1,...,N}denotes the index that uniquely identifies each robot.The sensor of robot i is located at pi,and has an orientation Ri∈SO(3).The configuration space for each robot is therefore SE(3).The configuration of the ith robot is qi=(pi,Ri),where pi=[xi,yi,zi]T.

The kinematics of the ith robot are given by

where uci∈ R3and Ωci∈ SO(3)are control terms we design,and uei∈ R3and Ωei∈ R3represent unknown bounded external terms.The symbol q represents the configuration of the entire team.

We assume that the sensor is not rigidly attached to the robot body,but can rotate around it.This assumption allows(1)to be used for wheeled mobile robots,since the orientation of the sensor is not the same as the heading defined by the nonholonomic constraints of the wheels.If the wheeled robot has a large inertia,leading to slow changes in its heading,then(1)would no longer be a valid model for such a robot,and the robot kinematics must be truly holonomic for(1)to apply.

2.2 Field-of-view

The orientation of the sensor of robot i is Ri.The optical axis of this sensor is given by Rie3,where e3=[0,0,1]T.An object is inside the field-of-view of a robot if the line-of-sight from the robot to the object makes a small enough angle with respect to the optical axis of the sensor.Additionally,the object cannot be too far away from the sensor.

Fig.1 depicts the field-of-view of a robot.The figure shows robots in the plane for ease of presentation,it is straightforward to visualize the field-of-view in three dimensions.The field-of-view Fiof robot i is given by

where diand ψmiaxare parameters that define the fieldof-view of the sensor.We assume that ψmiax＜ 1,?i∈V.This assumption ensures that Fiis convex.

Fig.1 The sector illustrates the field-of-view of robot i,defined by ψmi axand di,which contains robot j(but not robot k).The dashed arc denotes points in the field-of-view at unit distance from the focal point of the sensor.The relative distance dijand orientation ψijof robot j in the frame of robot i are also shown.The diagram presents robots in the plane only for ease of presentation.This depiction carries over to the three-dimensional case in a straightforward way.

2.3 Directed graphs

A directed graph G=(V,E)is a tuple consisting of a set of vertices V(also called nodes)and a set of edges E(also called links).If there are N nodes,then we can label them using integers from 1 to N,so that V is identified with the set{1,2,...,N}.An edge e∈E is an ordered pair(i,j)which indicates that a connection exists which starts at node i and ends at node j,where i,j∈V.More precisely,the edge(i,j)is an out-edge for node i and an in-edge for node j.

Given a directed graph G=(V,E),we assign a weight wij∈ R≥0to each edge(i,j)∈ E.Once the edge weights wijare defined,the adjacency matrix Aw(G)={aij}∈ RN×Nis given by

Note that the non-zero entries of the ith row correspond to the edges directed away from node i,which are the out-edges of i.It is also possible to define the ith row based on in-edges,however we do not use that formulation.

The Laplacian Lw(G)∈ RN×Nof the graph is derived from the adjacency matrix Aw(G)and is given by

where Dw(G)is a diagonal matrix whose ith diagonal element isDue to the definition of Aw(G),the matrix Lw(G)is often known as the out-Laplacian,however we do not refer to it as such in the paper.

The eigenvalues of Lw(G)may be complex,and are ordered based on their absolute value.Let the ith smallest eigenvalue of a matrix A be denoted by λi(A).The second smallest eigenvalue of Lw(G)is denoted by λ2(L).In the case of undirected graphs,it is called the Fiedler value of the graph[10].We will henceforth drop the argument G,and the subscript w and from these matrices,with the understanding that a graph matrix with no subscript implies that the edge weights correspond to wijunless otherwise specified.

2.4 Mobile robot networks

We model the visibility of the robots to one another using a graph G=(V,E)where each robot is a node in V.The set E of edges is

The line-of-sight from robot i to j is represented by the edge(i,j).We will refer to lines-of-sight and edges interchangeably.

The distance dijbetween two robots is

and the relative orientation of robot j with respect to robot i is given by

Then,the edge(i,j)∈E if and only if dij＜diandwhere diis the communication radius of robot i,is the half-angle of the field-ofview.Note that ψij∈ [0,2],and is a different measure of relative orientation than what was used in[9].If the optical axis of all robots are coplanar,then the quantity cos?1ψijreduces to the measure of relative orientation in[9].

We can also define the edge set E in terms of diandas

We wish to preserve a subset Ecof edges in E.The set Ecleads naturally to a graph Gc=(V,Ec).For technical reasons,we will restrict ourselves to sets Ecsuch that(i,j)∈Ec(j,i)∈Ec.This means that we will preserve lines-of-sight between robots only when both robots are visible to each other.This restriction also makes the implementation of the control law feasible.

The graph Gcis undirected in terms of the edge set Ec,however any associated graph matrix will not be not symmetric unless the edge weights wijand wjifor all(i,j)∈Ecare equal.An intuitive way to see this is that robot i may be close to the edge of the field-of-view of robot j,while robot j might be in the center of the field-of-view of robot i.If we assign a strength to each edge corresponding to the proximity of the line-of-sight to the center of the field-of-view,then these two edges are unlikely to have the same weight.

3 Problem statement

We consider two problems.

Problem1Consider a team of N mobile robots with configuration q∈(SE(3))N,and let Ecbe the set of edges that must be preserved.Let the kinematics of the robot be given by(1),where uei(t)and Ωei(t)are bounded for all time and all i∈V.Design decentralized controls uci(t)and Ωci(t)that ensure that the edges in Ecare preserved for all t＞t0,assuming that these edges exist at time t0.

Problem2Consider a team of N mobile robots with configuration q∈(SE(3))N,and let Ec(t)be the set of edges that must be preserved for time t∈[t0,tf].Let the kinematics of the robot be given by(1),where uei(t)and Ωei(t)are bounded for all time and all i ∈ V.Design continuous decentralized controls uci(t)and Ωci(t)that ensure that the edges in Ec(t)are preserved for all t∈(t0,tf],assuming that these edges exist at time t0.

Problem2differs from Problem1due to the emphasis on the continuity of the control law.Given that the set Ecmakes discrete changes,one must be careful when designing the control to avoid discontinuous changes which could lead to complicated closed-loop behavior.

4 Visibility control

We now present a control law that is guaranteed to solve Problem 1.The definition of edges in G(and therefore Gc)relies on dijand ψijbeing less than the corresponding bounds for edge(i,j)∈E.This leads to the use of edge tension functions[11]to ensure that dijand ψijnever exceed those bounds.We modify the edge tensions presented in[11]such that the new edge tensions can be zero when dijand ψijare far away from their bounds.This region where the modified edge tensions are zero can be made specific to each edge,using a set of parameters.This modification later allows us to avoid the discontinuities that are faced by the method in[11]whenever new edges are included in the set of preserved edges.A key contribution of this work is to develop a method to analyze the control that does not rely on knowledge of the specific values of the parameters of each edge tension.This property implies that the robots can set these values autonomously,without losing the guarantees for the closed-loop control.

The linear control for the ith robot is given by

and the angular velocity is given by

where αijand βijare the edge tension functions which ensure that dijand|ψij|respectively remain within required bounds,andA projects a matrix A ∈ R3×3to the tangent space of SO(3)at R.We define these functions as follows.First,we define the function ν as

which is a smooth monotonic function such that ν(ρ3,ρ4)(ρ3)=0 and ν(ρ3,ρ4)(ρ4)=1.The numbers ρ3and ρ4are chosen such that 0 ＜ ρ3＜ ρ4.

Next,we define the function κ as

The edge tension functions αijand βijare then

where ρij,δij,∈ij,ζij,and ηijare parameters.These parameters must satisfy 0 ≤ δij＜ ∈ij＜ ρijand 0 ≤ ζij＜respectively,for all(i,j)∈Ec.

Note that in[11],a function similar to κ in(12)is used as the edge tension,and is based on the gradient of a potential function which must be fixed for all time in order to facilitate analysis.We avoid being constrained to a fixed potential function,and instead allow the edge tension to be defined in a flexible manner.

4.1 Analysis

For a graph Gc,we define the set D as

Our control goal of maintaining visibility can now be defined in terms of making the set D invariant,assuming that Ecalways contains edges that must be preserved.We now prove that the controls(9)and(10)indeed preserve all the edges in Ec.

We define edge potential functions as

where we have suppressed the dependence of αijand βijon various parameters.These edge potentials are summed over all edges to obtain the overall potential function

We now rewrite the equations of the robots in such a way that the kth elements of all vectors piare combined.This was also done in[11].We will sometimes denote the kth element of a vector x as[x]k,in order to avoid confusion in subscripts.

We rewrite the kinematics of the position in(1)as

where[x]k=xk,[y]k=yk,[z]k=zk,[ucx]i=[uci]1,[ucy]i=[uci]2,[ucz]i=[uci]3,[uex]i=[uei]1,[uey]i=[uei]2and[ucz]i=[uci]3.We have that

Consider the set D?given by

The set D?is a subset of the boundary of set D in(15).If q(t)reaches D?at some time T,this means that all edges in the graph are lost at the same time instant.In order to prove that D is invariant,we first show that q(t)cannot exit D through D?.

We recall the following result.

Lemma 1(Lemma A.1[12])Let Lσbe a symmetric graph Laplacian for a connected undirected graphwith edge weights σij.Let|V|=p,and x ∈ Rp.Consider the quantity Ω =?Lσx?.If x ≠c1pfor any c∈R,then Ω ＞0.Moreover,if

ProofSee[12].

The result above is useful for analyzing controls of the formwhich is true of(9).Even though each term σijis becoming large,is it possible that all the control terms uicremain small?In other words,does the summation lead to a “cancellation”of the unbounded terms?The result says that this cannot happen.That is,at least one of the terms uicwill become arbitrarily large if all the terms σijbecome arbitrarily large.

This result will be used to show the following.

Lemma 2Consider the connected graph Gc=(V,Ec)with dynamics(1).Let the controls uciand Ωcibe selected according to(9)and(10)respectively.The external control terms uei(t)and Ωei(t)are unknown but bounded for all i∈V.Then,for any solution q(t)of(1)with initial condition q(t0)∈D,if q(t)∈D for all t∈[t0,T)where T ＞t0,then q(T)?D?.

ProofWe prove the Lemma by contradiction.Assume that at t=T,q(T) ∈ D?.This means that for all(i,j)∈Ec,βji(ψji(t))= ∞.

Consider the weighted symmetric Laplacian Lαwith edge weights of the form αij(= αji)corresponding to a graph G′=(V,E′),where E′? Ecand(i,j)∈ E′if andSimilarly,we construct symmetric Laplacians L1β,L2β,and L3βwith edge weights βij+ βjifor a graph G′′=(V,E′′)where E′′? Ecand(i,j)∈ E′′if and only if= ∞.Clearly,E′∪ E′′=Ec.

We then rewrite the control terms ucx,ucy,and uczusing(22)and(23)in(9)to obtain

where the vectors w1,w2,and w3absorb those terms from the control(9)for which＜ ∞ andWe treat these vectors as bounded disturbance terms when analyzing the control.

Since

it can be shown that

The derivative ofV(q)is

where Tr(ATB)=Trace(ATB)represents an inner product over matrices.

We use(29)–(32)to obtain

We bound Δ2as

where MΩis a bound for the last term in(35).We derive this bound using properties of the trace as follows:

where ωci∈SO(3),and Ωci=?ωci,where for ω=[ω1,ω2,ω3]T,

Clearly(ωci)Tωei≤ ?ωci??ωei?.Therefore

The bound above implies that we can boundas

The vectors uex,uey,uez,ωei,w1,w2andw2are bounded by assumption.Let the norm of all terms in(39)consisting of only these vectors be bounded above by M.When the norm of??Lαx ? L3βy+L2βz?,?L3βx ? Lαy ? L1βz?,??L2βx+L1βy ? Lαz?,or?ωci?(for some i∈ V)is larger than M,then the corresponding term in(39)is negative.This implies that we can bound the values of Δ2for which˙V(q)＞0 from above by(3+N)M2.Thus,if one of the negative definite terms in(34)has magnitude greater than(3+N)M2+M,then ˙V(q)＜0,where the additional M comes from Δ1.The final step is to show that this situation indeed happens.

The argument will be to show that at least one of?Lαx?,?Lαy?,and?Lαz?becomes unbounded.Consider the quantity Mddefined as

Since the matrix in(40)is the sum of a block symmetric and a block skew-symmetric,Mdreduces to

Since Ecis connected,we can apply Lemma 1 to Lαand conclude that at least one of?Lαx?,?Lαy?,and?Lαz?approaches∞ as t→ T,since the distance between at least two robots is non-zero.This fact implies that there exists a time τ where 0 ＜ τ ＜ T such that＜0 for all t∈(τ,T].Since V˙(q(t))＜0 for all t∈(τ,T],we have thatV(q(T))remains finite,which contradicts the assumption that q(T) ∈ D?,since for all q?∈D?,V(q?)=∞.This contradiction proves the lemma.

Lemma 2 says that a connected set of edges cannot be broken at the same instant.This statement is a generalization of analysis techniques[13,14]for multi-robot control that show that a single edge cannot be broken when using a control law designed to become large in magnitude as an edge approaches disconnection.

Theorem 1Consider the graph Gc=(V,Ec)with dynamics(1).Let the controls uciand Ωcibe selected according to(9)and(10)respectively.The external control terms uei(t)and Ωei(t)are unknown but bounded for all i∈V.Then,for any solution q(t)to(1)with initial condition q(t0)∈D,

ProofLet there exist some T＞t0such that the solution q(t)of(1)for initial condition q(t0)is such that q(t)∈D?t∈[t0,T)and q(T)?D.Let some set of edges E?be broken at t=T.The edges E?may consist of multiple disconnected components.Each of these disconnected components satisfy the conditions of Theorem 2 independently,since the control terms due to the edges between these components are bounded at t=T,and are therefore considered as bounded disturbance terms.This satisfaction implies that the edges in the components are not broken at t=T,so that the relative distances or orientations do not reach their limits.This statement contradicts the statement that q(T)?D,and so we conclude that q(t)∈ D,?t≥ t0.

5 Hybrid visibility control

We solve Problem 2 using a hybrid control approach.We use a continuous control to preserve lines-of-sight along with a discrete variable that decides which linesof-sight must be preserved.When new edges(i,j)and(j,i)∈E are added to the set of edges that must be preserved,a corresponding control term is added to the controls of nodes i and j,until the decision to stop preserving(i,j)and(j,i)is made.The main task is to ensure that the addition of this control results in a control that is continuous in time.

To each edge(i,j)∈V×V,we assign the time-varying binary statewhich can only take one of two values at any time,namely either 1 or 0.The value of scij(t)determines whether the edge(i,j)∈E(t)is to be preserved,where E(t)is the time-varying set of edges in G(t).The subgraph of G(t)that must be preserved at time t is denoted as Gc(t)=(V,Ec(t)).We define the edge set Ec(t)? E(t)as Ec(t)={(i,j)∈E(t):scij(t)=1}.We then use this edge set in the controls(9)and(10).

We assume that a designer provides two conditions which determine when scijshould be switched to 1 and switched to 0 respectively.We denote these conditions using the logical variables condition1 and condition0 respectively,both of which can have values in{true,false}.We use the conditions to set scijand the parameters in(13)and(14)as follows:

where a←b implies that value b is assigned to variable a.To make the control continuous,we set the parameters ρij,δij,∈ij,ζij,and ηijat the time instant tswwhenswitches from 0 to 1 as follows:

where c∈(0.5,1].The values set by(43)imply that αij(dij(tsw))= βij(ψij(tsw))=0 by design.The state scijswitches from 1 to 0 only when dij＜δij＜diand|ψij|＜ ζij＜(see(42)).Therefore,νij=0 whenand in turn αij(dij)= βij(ψij)=0.Thus,the control uci(t)is never discontinuous in time.

The definition of Ec(t)and Theorem 1 together lead to the following result.

Proposition 1Consider a multi-robot network where the dynamics of the ith robot is given by(1).The controls uci(t)and Ωci(t)are selected according to(9)and(10).The external control terms uei(t)and Ωei(t)are unknown but bounded for all i∈V.The discrete statesare updated according to(42)and the parameters dij,δij,∈ij,ζij,and ηijare updated according to(43).If=1 for any time t,then(i,j),(j,i)∈E(t).

6 Simulation

We present the results of two types of simulations.Section 6.1 presents simulations in which the set Ecis kept constant throughout the simulation.Section 6.2 presents simulations in which the set Ecis determined based on the task of maintaining strong connectivity of the sensing network.The set Ecin the second type of simulation is time-varying.

6.1 Constant edge set Ec

We simulate three robots with configuration in SE(3)and kinematics(1)in different scenarios.The control uci(t)for each robot is given by(9)and(10).The input terms uei(t)for i∈{1,2,3}are

These terms are designed such that the lines-of-sight between all robots would be lost if uci(t)≡0.We set Ωei(t)to be identically zero for i∈{1,2,3}.

The initial positions for the robots are given by

We obtain the rotation matrix for each robot by rotating the identity matrix around the x-axis by a certain amount.We rotate robot 1 by π/2rad,robot 2 by?π/2rad and robot 3 by ?3π/4rad.Fig.2 shows the resulting configuration.The red line indicates the bodyfixed z-axis which is also the optical axis of the sensor.We change the value of diand ψmiaxin each scenario to demonstrate the effectiveness of the control law.

In the first three scenarios,Ec={(1,2),(1,3)}.In the first scenario,di=2.5m and ψmiax=0.5rad for all i∈{1,2,3}.In the second scenario,di=2.2m and=0.5rad for all i∈{1,2,3}.In the third scenario,=0.4rad for all i∈{1,2,3}.In other words,we tighten the constraints from one scenario to the next.

Figs.3–8 show the results of these three scenarios.In Fig.3 we see that d12and d13remain within the bound of 2.5m,whereas d23(blue line)does not,as expected.In Fig.4 we see that ψ12, ψ21, ψ13,and ψ31remain in the bound 0.5rad,whereas ψ23and ψ32(blue and ochre lines)do not,also as expected.Fig.5 shows that d12remains within the new bound of 2.2m,which it had crossed in the first scenario,demonstrating that the control is effective at preserving desired distances.The difference between the maximum value of dij(t)and the bound ρijdepends on the magnitude of the external terms.

Fig.2 Initial configuration of the three robots in Scenarios 1–3.The body-fixed x,y,and z axes are depicted by the blue,green,and red lines respectively for each sensor frame attached to the robots.

Fig.3 Scenario 1.The distances d12and d13remain within the desired bound 2.5m,whereas d23does not.

Fig.4 Scenario 1.The relative orientations ψijremain within the bound 0.5rad for edges(1,2),(2,1),(1,3)and(3,1).

Fig.5 Scenario 2.The distances d12and d13remain within the new desired bound of 2.2m.This result should be compared with that of Scenario 1 in Fig.3,where d12crosses the value of 2.2m when the bound is 2.5m.

Fig.6 Scenario 2.The relative orientations ψijremain within the bound 0.5rad for edges(1,2),(2,1),(1,3)and(3,1).

Fig.7 Scenario 3.The distances d12and d13remain within the desired bound 2.2m.

Fig.8 shows that ψ12,ψ21,ψ13,and ψ31remain within the bound 0.4rad.The value of ψ31in Scenarios 1 and 2 crossed 0.4rad when ψm3ax=0.5rad,demonstrating the ability of the control to maintain these bounds.

Fig.8 Scenario 3.The relative orientations ψijremain within the bound of 0.4rad for edges(1,2),(2,1),(1,3)and(3,1).This result should be compared with that of Scenarios 1 and 2,where ψ31crosses the value of 0.4rad when ψm3 ax=0.5rad.

In the fourth scenario,we change the amount of rotation for robot 3 to πrad.Fig.9 shows this initial configuration.We add the edges(2,3)and(3,2)to,so that all lines-of-sight must be preserved.The values of diand ψmiaxremain at 2.2m and 0.4rad respectively for all robots.

Figs.10 and 11 show the results of the simulation of Scenario 4.We see that d23, ψ23and ψ32also satisfy their respective bounds.This is in contrast to Scenarios 1–3 where these quantities crossed the bounds since no control was employed to prevent that from occurring.This simulation again demonstrates the effectiveness of the control law.

Fig.9 Initial configuration of the three robots for Scenario 4.The body-fixed x,y,and z axes are depicted by the blue,green,and red lines respectively for each sensor frame attached to the robots.

Fig.10 Scenario 4.All inter-robot distances dijare within the bound 2.2m.

Fig.11 Scenario 4.All relative orientations ψijare within the bound 0.4rad.

6.2 Time-varying edge set Ec

As mentioned earlier,some distributed localization algorithms[3]rely on the visibility graph remaining strongly connected.We use the conditions presented in[9]to choose which edges must be preserved.Briefly,we construct a graph with edge weights wijthat are smooth monotonically decreasing functions of dijand ψij.This graph is strongly connected if and only if|λ2(L)| ＞ 0 and γ ＞ 0,where γ ∈ RNis the unique left eigenvector corresponding to the zero eigenvalue of L.The values|λ2(L)|and the elements of γ determine which edges must be preserved.

The initial conditions,bounds on dijand ψij,and additional inputs are the same as that of the simulation for Scenario 1 in Section 6.1.Figs.12 and 13 show the results of this simulation.In Fig.12,we see that the quantities ψ23and ψ31initially exceed the value=0.5rad,since the associated edges are not included in Ec.Once these edges are included in Ec,their value does not exceed 0.5rad.Fig.13 shows that the strong connectivity property of the graph is alwayspreserved,sinceremainnon-zero throughout the simulation.

Fig.12 Simulation results for the hybrid visibility controller.The quantities ψ23and ψ31initially exceed the value 0.5rad when these edges are not included in Ec.Once they are included in Ec,they remain within the bound.Note that the control is always continuous in time.

Fig.13 Simulation results for the hybrid visibility controller.The strong connectivity property of the graph is always preserved,since＞ 0 and|λ2L(t)|＞ 0 for all t∈ [0,40].

7 Conclusions

In this paper,we proposed a control method to maintain the visibility of robots to each other when they are equipped with limited field-of-view sensors.The effectiveness of this controllaw was established through both analysis and simulation.The control method is shown to guarantee preservation of visibility even in the presence of bounded disturbance inputs.Note that the ex-ternal control terms can also be interpreted as additional control objectives such as tracking a leader or reaching positions in a formation.Therefore,the edge-preserving control law presented in this paper can be used alongside other control tasks.

An avenue for future work is to understand the effect of delayed measurements on the stability of the system.Errors in the distance measurement may also complicate the implementation of the edge-preserving control law.It may be necessary to develop methods to overcome these errors during implementation.

[1]R.Olfati-Saber,J.A.Fax,R.M.Murray.Consensus and cooperation in networked multi-agent systems.Proceedings of the IEEE,2007,95(1):215–233.

[2]W.Ren,R.W.Beard.Consensus seeking in multiagent systems under dynamically changing interaction topologies.IEEE Transactions on Automatic Control,2005,50(5):655–661.

[3]S.S.Kia,S.F.Rounds,S.Martinez.A centralized-equivalent decentralized implementation of extended Kalman filters for cooperative localization.IEEE/RSJ International Conference on Intelligent Robots and Systems,Chicago:IEEE,2014:3761–3766.

[4]D.Panagou,V.Kumar.Maintaining visibility for leaderfollower formations in obstacle environments.IEEE International Conference on Robotics and Automation,St Paul:IEEE,2012:1811–1816.

[5]M.A.Dehghani,M.B.Menhaj,M.Azimi.A supervisory control strategy for visibility maintenance in the leader-follower formation.Proceedings of the 2nd International Conference on Knowledge-Based Engineering and Innovation,Tehran,Iran:IEEE,2015:124–129.

[6]R.Maeda,T.Endo,F.Matsuno.Decentralized navigation for heterogeneous swarm robots with limited field of view.IEEE Robotics and Automation Letters,2017,2(2):904–911.

[7]D.Panagou,V.Kumar.Cooperative visibility maintenance for leader-follower formations in obstacle environments.IEEE Transactions on Robotics,2014,30(4):831–844.

[8]J.-B.Hayet,H.Carlos,C.Esteves,et al.Motion planning for maintaining landmarks visibility with a differential drive robot.Robotics and Autonomous Systems,2014,62(4):456–473.

[9]H.A.Poonawala,M.W.Spong.On maintaining visibility in multirobot-networks with limited field-of-view sensors.Proceedins of the American Control Conference,Seattle:IEEE,2017:4983–4988.

[10]M.Fiedler.Algebraic connectivity of graphs.Czechoslovak Mathematical Journal,1973,23(2):298–305.

[11]M.Ji,M.Egerstedt.Distributed coordination control of multiagent systems while preserving connectedness.IEEE Transactions on Robotics,2007,23(4):693–703.

[12]H.A.Poonawala,M.W.Spong.Preserving strong connectivity in directed proximity graphs.IEEE Transactions on Automatic Control,2017,62(9):4392–4404.

[13]H.A.Poonawala,A.C.Satici,M.W.Spong.Collision-free formation control with decentralized connectivity preservation for nonholonomic-wheeled mobile robots.IEEE Transactions on Control of Network Systems,2015,2(2):122–130.

[14]J.Wagenpfeil,A.Trachte,T.Hatanaka,et al.A distributed minimum restrictive connectivity maintenance algorithm.IFAC Proceedings Volumes,2009,42(16):365–370.

5 September 2017;revised 12 October 2017;accepted 12 October 2017

DOIhttps://doi.org/10.1007/s11768-017-7096-8

?Corresponding author.

E-mail:hasanp@utexas.edu Tel.:+1-903-495-4776.

This paper is dedicated to Professor T.J.Tarn on the occasion of his 80th birthday.

?2017 South China University of Technology,Academy of Mathematics and Systems Science,CAS,and Springer-Verlag GmbH Germany

HasanA.POONAWALAreceivedthe B.Tech.degree in Mechanical Engineering from the National Institute of Technology,Surathkal,India,in 2007,the M.Sc.degree in Mechanical Engineering from the University of Michigan,Ann Arbor,MI,U.S.A.,in 2009,and the Ph.D.degree in Electrical Engineering from the University of Texas,Dallas,TX,U.S.A.,in 2014.He is currently a postdoctoral researcher at the Institute for Computational Engineering&Sciences in the University of Texas at Austin.His current research interests include nonlinear control theory,machine learning,networks,hybrid systems and robotics.E-mail:hasanp@utexas.edu.

Mark W.SPONGreceived the B.A.degree(magna cum laude and Phi Beta Kappa)in Mathematics and Physics from Hiram College,Hiram,OH,U.S.A.,in 1975,the M.Sc.degree in Mathematics from New Mexico State University,Las Cruces,NM,U.S.A.,in 1977,and the M.Sc.and D.Sc.degrees in Systems Science and Mathematics from Washington University in St.Louis,MO,U.S.A.,in 1979 and 1981,respectively.

He was with the University of Illinois at Urbana-Champaign,Urbana,IL,U.S.A.,from 1984 to 2008.He is currently a Professor of electrical engineering in the Erik Jonsson School of Engineering and Computer Science,University of Texas at Dallas,TX,U.S.A.,where holds both the Lars Magnus Ericsson Chair and the Excellence in Education Chair.He has authored or co-authored more than 250 technical papers in control and robotics and four books,and holds one patent.His current research interests include robotics,mechatronics,and nonlinear control theory.

Dr.Spong was the President of the IEEE Control Systems Society and was both the Editor-in-Chief and an Associate Editor of the IEEE Transactions on Control Systems Technology and an Associate Editor of the IEEE Transactions on Robotics and Automation,the IEEE Control Systems Magazine,and the IEEE Transactions on Automatic Control.He was the Vice President for Publication Activities from2000to2002.He was the recipient of several awards,including the first Intelligent Robots and Systems Fumio Harashima Award for Innovative Technologies,the IEEE Transactions on Control Systems Technology Outstanding Paper Award,the Senior Scientist Research Award from the Alexander von Humboldt Foundation,the Distinguished Member Award from the IEEE Control Systems Society,the John R.Ragazzini and O.Hugo Schuck Awards from the American Automatic Control Council,and the IEEE Third Millennium Medal.E-mail:mspong@utdallas.edu.