9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # Vision-based Distributed Coordination and Flocking of Multi-agent Systems_图文

Vision-based Distributed Coordination and Flocking of Multi-agent Systems

Nima Moshtagh, Ali Jadbabaie, Kostas Daniilidis

GRASP Laboratory University of Pennsylvania Philadelphia, Pennsylvania 19104 Email: {nima, jadbabai, kostas}@grasp.upenn.edu

Abstract— We propose a biologically inspired, distributed coordination scheme based on nearest-neighbor interactions for a set of mobile kinematic agents equipped with vision sensors. It is assumed that each agent is only capable of measuring the following three quantities relative to each of its nearest neighbors (as de?ned by a proximity graph): time-to-collision, a single optical ?ow vector and relative bearing. We prove that the proposed distributed control law results in alignment of headings and ?ocking, even when the topology of the proximity graph representing the interconnection changes with time. It is shown that when the proximity graph is ”jointly connected” over time, ?ocking and velocity alignment will occur. Furthermore, the distributed control law can be extended to the case where the agents follow a leader. Under similar connectivity assumptions, we prove that the headings converge to that of the leader. Simulations are presented to demonstrate the effectiveness of this approach.

I. I NTRODUCTION Over the past few years a considerable amount of attention has been focused on the problem of coordinated motion and cooperative control of multiple autonomous agents. From ecology and evolutionary biology to social sciences, and from systems and control theory to complexity theory, statistical physics, and computer graphics, researchers have been trying to develop an understanding of how a group of moving objects such as ?ocks of birds, schools of ?sh, crowds of people can perform collective tasks such as reaching a consensus or moving in a formation without centralized coordination. Such problems have been studied in ecology and theoretical biology, in the context of animal aggregation and social cohesion in animal groups. There is evidence that individuals within such groups often only have access to local information about the behavior of near-neighbors. Nevertheless this is suf?cient as an organizing principle for the entire group to perform collective locomotion, yet remain cohesive even when moving around obstacles or when avoiding predators [28]. Furthermore, there has been a large body of research focused on mimicking the observed social aggregation phenomena in different animal species using computer simulation. The pioneering work in this area was done by Reynolds [29]. More recently, several researchers in the area of statistical physics and complexity theory have addressed ?ocking and schooling behavior in the context of non-equilibrium phenomena in many-degree-of-freedom dynamical systems and

self organization in systems of self-propelled particles, starting from the work of Vicsek et al. [34]. In robotics and control theory, these problems have been studied in the context of cooperative control of autonomous robots, unmanned vehicles, and general multiagent systems. A nonexhaustive list of references include [5], [8], [10], [12], [15], [17], [25], [26], [32]. A simple but compelling model of ?ocking and coordination is the model proposed by Vicsek et al. in [34] and analyzed in [15]. The model describes a set of agents moving with constant speed v , whose heading direction is updated by a simple alignment rule. The heading of each agent is updated in discrete time as the average of the heading of itself and those who fall within a disc of a pre-speci?ed radius centered around each agent. As the agents move, the set of nearest neighbors change, resulting in a discontinuous change or switching in the control law. The neighborhood relationship between any two agents can be described conveniently with a graph whose nodes represent the agents and the edges represent the neighborhood relation. It was shown in [15] that if the neighborhood graph stays connected in time, then the headings of all agents converge to a common value. As a result all agents align, and the pairwise distances stabilize. Furthermore, it was shown that when one agent acts as a leader, the headings converge to that of the leader under similar conditions. Over the past 2 years, a plethora of similar results have appeared in the control literature. Also, extensions to dynamic point-mass models have also appeared [26], [32]. These results assume that each agent is capable of measuring the heading of its nearest neighbors (in discrete time models), or difference between headings of itself and its neighbors (in continuoustime models), effectively requiring communication on top of sensing. While the nearest neighbor interactions have been shown to be biologically plausible and have been observed in schools of ?sh and ?ocks of birds, the assumptions about knowledge of relative headings and distances is not biologically plausible. Even if some species might use ultrasound to estimate distances or binocular vision to estimate positions and motions of others, such sensing mechanisms do not perform well for ?ocking where simultaneous measurements in multiple directions are needed. The simplest assumption we can make is that such systems have only monocular vision and that they

have basic visual capabilities like the estimation of optical ?ow and time to collision. Experimental evidence suggest that several animal species, including pigeons, are capable of estimating time to collision [20], [36]. Computationally, time to collision can be estimated from the ratio of area change to area or from the divergence of the optical ?ow [4], [19]. Regarding optical ?ow, we refer the reader to the survey [3]. Many of the existing vision-based distributed control strategies assume that the robots are capable of communicating to their neighbors an estimation of their position [30], [38], [39] and are based on distributed computation [1]. Other cooperative systems are based on local computation work in the con?guration space [11], [24]. From the vision point of view, our paper is mostly related to the formation control systems in [6], [7], [35]. However, these approaches assume that a speci?c vertical pose of an omnidirectional camera allows the computation of both bearing and distance, while we use only the optical ?ow (bearing derivative) and time-tocollision. Our goal in this paper is to develop a provably correct coordination and ?ocking scheme that is also biologically plausible. We will show that coordination and ?ocking is possible based on measuring time-to-collision and optical ?ow, even if the neighborhood graph topology changes, so long as a weak notion of connectivity denoted as ”connectivity in time” is preserved (same as in [15]). We will also show that the above problem is directly related to the Kuramoto model of coupled nonlinear oscillators, a famous problem in mathematical physics [16], [31]. II. G RAPH T HEORY P RELIMINARIES In this section we introduce some standard graph theoretic notation and terminology. For more information, the interested reader is referred to [13]. An (undirected) graph G consists of a vertex set, V , and an edge set E , where an edge is an unordered pair of distinct vertices in G. If x, y ∈ V , and (x, y ) ∈ E , then x and y are said to be adjacent, or neighbors and we denote this by writing x ? y . The number of neighbors of each vertex is its valence. A path of length r from vertex x to vertex y is a sequence of r + 1 distinct vertices starting with x and ending with y such that consecutive vertices are adjacent. If there is a path between any two vertices of a graph G, then G is said to be connected. If there is such a path on a directed graph ignoring the direction of the edges, then the graph is weakly connected. The adjacency matrix A(G) = [aij ] of an (undirected) graph G is a symmetric matrix with rows and columns indexed by the vertices of G, such that aij = 1 if vertex i and vertex j are neighbors and aij = 0, otherwise. The valence matrix D(G) of a graph G is a diagonal matrix with rows and columns indexed by V , in which the (i, i)-entry is the valence of vertex i. The (un)directed graph of a (symmetric) matrix is a graph whose adjacency matrix is constructed by replacing all nonzero entries of the matrix with 1. The symmetric singular matrix de?ned as: L(G) = D(G) ? A(G)

is called the Laplacian of G. The Laplacian matrix captures many topological properties of the graph. The Laplacian L is a positive semide?nite M-matrix (a matrix whose off-diagonal entries are all nonpositive) and the algebraic multiplicity of its zero eigenvalue (i.e., the dimension of its kernel) is equal to the number of connected components in the graph. The ndimensional eigenvector associated with the zero eigenvalue is the vector of ones, 1. Given an orientation of the edges of a graph, we can de?ne the edge-vertex incidence matrix of the graph to be a matrix B with rows indexed by vertices and columns indexed by edges with entries of 1 representing the source of a directed edge and -1 representing a sink. The Laplacian matrix of a graph can be also represented in terms of its incidence matrix as L = BB T independent of the orientation of the edges. III. D ISTRIBUTED C OORDINATION AND F LOCKING WITH K INEMATIC M ODELS A. System Model Consider a group of N agents on a plane. Each agent is equipped with a vision sensor that is capable of sensing some information from its neighbors as de?ned by: . Ni = {j |i ? j } ? {1, . . . , N }\{i}. The neighborhood set of agent i, Ni , is a set of agents that can be “seen” by agent i. The exact de?nition of “sensing” will be discussed shortly. The characteristics of the vision sensor limits the size of the neighborhood. We therefore assume that there is a predetermined radius R which determines the neighborhood relationship. The location of agent i, (i = 1, . . . , N ) in the world coordinates is given by (xi , yi ) and it’s velocity is vi = (x ˙ i, y ˙ i )T . The heading or orientation of agent i is θi and is given by: θi = atan2(y ˙i , x ˙ i ). It is assumed that all agents move with constance speed v . We assume a unicycle kinematic model for each agent: x ˙i y ˙i ˙i θ = v cos θi = v sin θi = ωi

i = 1, . . . , N

(1)

The goal is to design a control input ωi so that the group of mobile agents ?ock in the sense of following de?nition: De?nition 3.1: (Flocking) A group of mobile agents is said to (asymptotically) ?ock, when all agents attain the same velocity vector and distances between the agents are stabilized. In order to make the model biologically plausible, we impose constraints on what each agent can measure. Let βij (bearing) be the relative angle between agents i and j as measured in the local coordinate of agent i. To formally de?ne the sensing, we assume that each agent i can measure: ? βij or the relative bearing in agent i’s reference frame ˙ ij or ”optical ?ow”: the rate of change of bearing ? β ? τij or ”time-to-collision”

How can we generate a distributed control law based on measured quantities? A simple calculation indicates that when two agents are aligned, the resulting optical ?ow is zero. This suggests that perhaps the sum of optical ?ows between each agent and its neighbors is a plausible choice. Unfortunately, having the sum of optical ?ows between each node and its nearest neighbors equal to zero is necessary for alignment, but is not suf?cient. This is where the knowledge of time to collision becomes useful. Consider any pair of agents i and any of its neighbors j . By differentiating (2) we get l˙ij 2v θi ? θj θi ? θj 1 = = sin( ) cos(βij + ) τij lij lij 2 2

Fig. 1. Con?guration of 2 agents.

(4)

and by differentiating (3) we obtain ˙ ij + ωi = ? 2v sin( θi ? θj ) sin(βij + θi ? θj ) β lij 2 2 (5)

for any agent j in the set of its neighbors Ni . Note that measurement of time-to-collision τij is not equivalent to measurement of the relative distance between agents as is usually the case in visual motion problems. This is due to the fact that time-to-collision can only recover the distance up to an unknown factor which in our case is different for every agent. The reader should also note that only one optical ?ow vector per rigid body is observed. Thus, making it impossible to rely on structure from motion algorithms. Simple calculation reveals that bearing and relative distance between agents i and j are given by (see Figure 1):

2 Distance : lij

A straightforward computation, using trigonometry identities, shows that the following relation between (4) and (5) holds: 1 ˙ ij ) sin βij = v sin(θi ? θj ). cos βij ? (ωi + β (6) τij lij This provides us with an odd function of θi ? θj . Since this equation holds for any agent i and any of its neighbors j ∈ Ni , we can sum (6) over all its neighbors to get 1 v ˙ ij ) sin βij = cos βij ? sin(θi ?θj ). (ωi +β τij lij j ∈Ni j ∈Ni j ∈Ni (7) We will show in section IV that a control law of the form v ωi = ? sin(θi ? θj ) (8) lij

j ∈Ni

= (xj ? xi )2 + (yj ? yi )2 =

Bearing : βij

(2) π atan2(yj ? yi , xj ? xi ) ? θi + (3) 2

It can be shown that the time-to-collision between agents i and j can be measured as the rate of growth of the image area [20], i.e. the relative change in the area Aij of projection of agent j on the image plane of agent i. In other words τij = Aj lij = . ˙j A l˙ij

will result in ?ocking according to de?nition 3.1. Equation (7) reveals that the above control law can be exactly computed using the measured quantities from nearest neighbors. By plugging (8) in (7), we get: ˙ ij sin βij ? 1 cos βij . β 1 ? j ∈Ni sin βij τij j ∈Ni (9) In the next section, we will show that the above distributed control strategy will result in ?ocking even when the set of nearest neighbors change in time. ωi = IV. S TABILITY A NALYSIS We now prove that the above chosen control law results in ?ocking of all agents ?rst when the proximity graph is ?xed and connected, and then when the graph changes with time but a weaker notion of connectivity is preserved. Note that the heading equation is now exactly the well-known Kuramoto model of coupled nonlinear oscillators, which has been studied extensively in the mathematical physics literature [31], and its stability properties was analyzed recently in [16], [22], [26]. The particular case of all-to-all connected graphs was also analyzed in [18]. 1

B. The Distributed Control Law In order to have a successful distributed control law which results in heading alignment and ?ocking, we need to have a measure of misalignment appear as a term in the controller. One way for the control input of any agent i to be spatially ˙i = distributed and result in alignment, is to have the form θ ? j wij (θi ? θj ), where weights wij are positive when agent i is a neighbor of agent j , and zero otherwise. Such a distributed control law is effectively the negative of the weighted Laplacian of the proximity graph, and has been analyzed in [2], [15], [21], [22], [26]. However, as we said before, since there is no communication between nearest neighbors, the relative heading information is not available. It turns out however, that we do not need to have θi ? θj explicitly in the controller. Instead, it suf?ces to have an odd function of θi ? θj .

A. Fixed Graphs We ?rst consider the case where the neighboring relations among agents are represented by a ?xed, weighted graph. De?nition 4.1: The neighboring graph G = {V , E , W } is a weighted graph consisting of: ? a set of vertices V indexed by the set of mobile agents; ? a set of pairs E = {eij = (νi , νj ) | νi , νj ∈ V , and i neighbor of j }; ? a set of positive edge weights wij , for each edge eij . Assume an arbitrary orientation for the edges of G. Consider the N × e incidence matrix B of this oriented graph, G with N vertices and e edges. Then, we can write (8) as: ˙ = ω = ?BW sin(B T θ) θ (10)

From (12) and the fact that sin(·) is a bounded function we get: ˙ij = 0. Thus, the inter-agent distances stabilizes limθi ,θj →θ ?l eventually and the group of mobile agents reaches a formation. We have therefore proven the following theorem: Theorem 4.2: Consider a set of kinematic mobile agents described by (1). Assume that each agent i is capable of ˙ ij , as measuring the bearing angle βij , the optical ?ow β well as the time-to-collision τij . If the graph G representing the neighborhood relationship is ?xed and connected, then (9) will result in ?ocking and the consensus state is locally asymptotically stable, i.e., all headings will eventually align and all pair-wise distances will stabilize. Note that for all initial conditions that the connectivity condition holds the result is valid. B. Switching Graphs In practice, the motion of individual agents will result in change in topology. This change in topology could be taken into account by using smooth “bump functions” [26], or by resorting to nonsmooth analysis [32]. To avoid complications that occur because of discontinuous change in the set of nearest neighbors, we will assume that there is always a minimum time, called a dwell time over which the graph does not change. This simplifying assumption will avoid in?nite switches over a ?nite period of time, and can be relaxed by using nonsmooth analysis [9]. What this means in the present context is that each agent is constrained to change its control law only at discrete time instances. Each agent i would use a control law similar to (8) (which is now hybrid, since the set of neighbors Ni changes discontinuously). By assuming a minimum dwell time, the controller would be of the form: v ωi (t) = ? sin(θi (t) ? θj (t)) lij (t)

j ∈Ni (tik )

where θ = [θ1 , . . . , θN ]T , and W is the diagonal matrix whose entries are the edge weights for G. The equation (10) can be written in a more compact form as: ˙ = ω = ?BW B T θ, θ diag{ lv sinc(θi ij (11)

where W = ? θj ) | (i, j ) ∈ E}. The quantities v and lij are positive and sinc(?θ) = sin(?θ) is positive when the heading vector θ is in the cube ?θ (?π/2, π/2)N . Therefore W is a valid weight matrix. Now T consider the quadratic Lyapunov function U = 1 2 θ θ . Then, ˙ = ?θT BW B T θ = ?θT Lw θ ≤ 0 ˙ = θT θ U where Lw = BW B T is the Laplacian of the graph G. Because U is a non-increasing function along the trajectories of the ˙ ≤ 0), the set system (U ≥ 0 and U ?c = {θi , i = 1, . . . , N | U ≤ c} is positively invariant for the largest value of c such that ?c ? (?π/2, π/2)N . It is also compact (closed and bounded) because θ’s are bounded and vary continuously. Hence, according to LaSalle’s invariance principle any solution starting in ?c converges to the largest invariant set, Sθ , contained in ˙ = 0} E = {θi , i = 1, . . . , N | U as t → ∞. This largest invariant set, Sθ , is a set of states that are solutions of Lw θ = 0. Therefore, vector θ is in the null space of the weighted Laplacian. If graph G is connected, null space of Lw is the span of . the vector 1 = [1, . . . , 1]T . Thus, ?} Sθ = {(θ1 , . . . , θN ) | θ1 = . . . = θN = θ (12)

t ∈ [tik , tik + ?i ) where ?i is a pre-speci?ed positive number called a dwell time and {t0 , t1 , . . . } is an in?nite time sequence such that ti(k+1) ? tik = ?i , k ≥ 0. In the sequel we will analyze controls of this form subject to two simplifying assumptions. First we will assume that all N agents use the same dwell time which we henceforth denote by ?D . Second we assume the agents are synchronized in the sense that tik = tjk for all i, j ∈ {1, 2, . . . , N } and all k ≥ 0. De?nition 4.3: A collection of graphs {Gp1 , Gp2 , . . . , Gpm }, each with vertex set V is called jointly connected, if the graph G with vertex set V and edge set equaling the union of the edge sets of all of the graphs in the collection is connected. It is natural to say that the N agents under consideration are linked together across a time interval [t, τ ] if the collection of graphs {Gσ(t) , Gσ(t+1) , . . . , Gσ(τ ) } encountered along the interval, is jointly connected. In [15] it was shown that the proposed nearest neighbor law results in heading alignment and ?ocking if there is an in?nite sequence of non-consecutive, bounded, non-overlapping time intervals over which the agents are linked together.

which suggests that all agents reach the same heading as t → ∞. Now we can show that eventually the relative distances between agents stabilizes. In order to have lij equal to a constant, we just need to show that limt→∞ l˙ij = 0. From (4) we can show that:

t→∞

θi ? θj θi ? θj ) cos( + βij ) lim l˙ij = lim 2v sin( t→∞ 2 2

This result was further extended in [21], [22] to the case where the agents are linked together over in?nite time intervals. This means that for any time t0 , the collection of graphs over [t0 , ∞) has to be jointly connected. If the uniformity requirement is removed, only asymptotic convergence of all headings is achieved, as opposed to exponential convergence. It turns out that the existence of uniformly bounded time intervals is necessary for exponential alignment of all headings. In trying to extend the previous theorem to graphs with the above mentioned switching regime, we need the following lemma, which was proven in [15]. Lemma 4.4: If {Gp1 , Gp2 , . . . , Gpm } is a jointly connected collection of graphs with Laplacians Lp1 , Lp2 , . . . , Lpm , then

m

decays to zero exponentially fast and therefore all agents align. Once the agents’ headings are aligned, the velocity vectors become the same, and as before, l˙ij goes to zero and all pairwise distances stabilize to a constant value. Remark 4.6: It is shown in [27] that if the measurements of the headings from neighboring agents is delayed by ti , then linear stability still holds. V. L EADER F OLLOWING In many ?ocking instances observed in the nature, such as ?ocking of birds, one of the ?ock-mates acts as the leader of the group and others follow the leader while staying in a formation. Similarly, here we consider the case that one additional agent, labeled 0, acts as the group’s leader. Agent 0 moves with the constant velocity v (same as others) and a ?xed heading θ0 . Other agents in the group may or may not have the leader as a neighbor. Here we ?nd a control law that results in a stable formation of the group while following the leader, so that in the end all agents reach the desired heading θ0 . Consider the input of each agent in the leaderless case that is given by (8). We can separate the leader from other agents and write: v v ˙i = ? θ sin(θi ? θj ) ? ci sin(θi ? θ0 ), (15) lij li0

j ∈Ni

kernel Lpi = span {1}.

i=1

(13)

The above lemma states that the intersection of the null space of the Laplacian of a set of jointly connected graphs is only the vector of ones. In other words, even though the graphs might be disconnected, and as a result their Laplacian have a larger kernel, the intersection is only the vector of ones. We can now state the following theorem: Theorem 4.5: Let the initial heading vector θ0 be ?xed and let σ : {0, 1, 2, . . .} → P be a switching signal mapping the integers to a ?nite set of indices corresponding to all graphs over N vertices for which there exists an in?nite sequence of contiguous, non-empty, bounded, time-intervals [ti , ti+1 ), i ≥ 0, starting at t0 = 0, with the property that across each such interval, the N -agent group is linked together. Then

t→∞

lim θ(t) = θss 1

(14)

where ci = 1 if agent i and the leader are neighbors and ci = 0 otherwise. To show that all the headings become equal to θ0 , we ˙i , we can consider the error term ei = θi ? θ0 . Since e ˙i = θ write (15) as follows: v v e ˙i = ? sin(ei ? ej ) ? ci sin ei . lij li0

j ∈Ni

for some value θss , i.e., all agents will asymptotically ?ock. T Proof: We use the same Lyapunov function U := 1 2θ θ as before. Using the same notation, we now have ˙ = ?θT Bσ(t) Wσ(t) (θ)B T θ = ?θT Lw θ ≤ 0 ˙ = θT θ U σ σ (t) where σ is the switching signal, and for each p ∈ P , Lwp is the weighted Laplacian matrix of the corresponding graph. Again, we note that since the headings are in the cube (?π/2, π/2)N , the weights are positive, and Lwσ is a positive semide?nite matrix. By LaSalle’s invariance principle, over the compact set ?c = {θ | U ≤ c} (for the largest value of c such that ?c ? (π/2, π/2)N ), the trajectories converge to the largest ˙ = 0. Because σ (·) is such that there is invariant set in the set U an in?nite sequence of jointly connected collection of graphs, and because of the previous lemma, the largest invariant set ˙ = 0 is only the span of vector 1. Therefore, in over the set U the region (?π/2, π/2)N there is an exponential decrease in the value of the Lyapunov function for the component of the heading along 1⊥ . In other words, we can decompose the vector θ as the direct sum of two components along 1 and its orthogonal complement in the subspace 1⊥ . Since there is no other ˙ = 0, the component of θ along 1⊥ direction in the set U

Similar to calculations of section IV, the error dynamics becomes: e ˙ = = = ?BW B T e ? Wl e ? Lw + Wl e ?Hl e

(16)

? θj ) | (i, j ) ∈ E} and Wl = where W = diag{ci lv sinc ( θ ? θ ) | ( i, 0) ∈ E}. Both W and Wl are i 0 i0 weight matrices with positive entries, because sinc(θi ? θ0 ) is positive for θi ∈ (?π/2, π/2), and v, lij and ci are all positive coef?cients. In order to show that the error is asymptotically stable, T consider the Lyapunov function U = 1 2 e e. The derivative of this along the trajectory of the error system ˙ = ?eT Hl e, where Hl = Lw + Wl . can be written as U Next, we will prove that Hl is positive de?nite, and the error will asymptotically decay to zero. Note that both Lw and Wl are positive semi-de?nite matrices and so is Hl . We need to show that Hl is indeed positive de?nite. To do this, we make the following observations: ? Hl is an irreducible matrix (because if we replace nonzero elements of Lw with 1 we obtain the adjacency matrix of

sinc(θi diag{ lv ij

Fig. 2.

The sphere and its tangent plane.

Fig. 3.

The polar angle βij and the azimuth ψij for two agents in 3D.

the neighboring graph that is strictly connected. Adding the diagonal matrix Wl doesn’t change the neighboring graph, thus Hl is irreducible); ? Lw is diagonally dominant; ? For at least one of the rows of Hl the diagonal entry is strictly greater than the sum of off-diagonal entries (because Wl ia a diagonal matrix with nonnegative entries). According to Taussky theorem [14] Hl is an irreducibly diagonally dominant matrix and is invertible (hence, no zero eigenvalues). Thus, Hl is a positive de?nite matrix. ˙ < 0 and the error vector asymptotically As a result, U decays to zero; consequently θi = θ0 for every i = 1, . . . , N , as t → ∞. In the case of changing topology, given that conditions of Theorem 4.5 hold, and by using Lemma 4.4 we can show that leader following is achieved (the analysis is dropped due to lack of space). VI. E XTENSIONS TO FLOCKING IN 3 DIMENSIONS Consider a group of N agents in the 3 dimensional space. Our goal in this section is to extend the ?ocking results we obtained for planar motion in section IV to ?ocking in three dimensions. Similar assumptions on the local interactions among agents hold. Without loss of generality, it is assumed that all agents move with a constant speed 1. The velocity of agent i in 3 dimensions is given by: ? ? cos θi sin φi vi = ? sin θi sin φi ? (17) cos φi where φi and θi are the attitude and heading angles of agent i. The dynamics equation of agent i then becomes v ˙ i = Uiθ Xiθ + Uiφ Xiφ where the orthonormal vectors Xiθ and Xiφ are ? ? ? ? ? sin θi cos θi cos φi Xiθ = ? cos θi ? , Xiφ = ? sin θi cos φi ? 0 ? sin φi and Uiθ and Uiφ are the control inputs for agent i. Figure 2 shows the tangent space containing the vectors Xiθ , Xiφ and the geodesic direction Yij . (18)

The notion of a geodesic control law was ?rst introduced in [23], and the inputs Uθi = ?

j ∈Ni

sin φj sin(θi ? θj )

(19)

Uφi = ?

j ∈Ni

sin φi cos φj ? sin φj cos φi cos(θi ? θj ) (20)

were derived for the alignment of the velocity vectors of a group of kinematics agent. We state the following theorem without proof and refer the reader to [23] for more details. Theorem 6.1: Consider the system of N agents with dynamics given by (18). If the proximity graph of the agents is ?xed and connected, then the control laws (19) and (20) result in ?ocking (at least locally) in the sense of de?nition (3.1), i.e., the consensus state is locally asymptotically stable. We now use the geodesic control laws to design control inputs that are only functions of the measurable quantities of bearing, optical ?ow and time-to-collision. Note that in 3D the bearing is expressed by two projection angles βij , ψij (Figure 3), and consequently the optical ?ow of a neighboring agent ˙ ij , ψ ˙ ij , which are the speeds of projections. is represented by β Let lij denote the distance between two agents i and j . Then Qij = lij qij is a vector in R3 connecting i to j , and ? ? lij sin ψij cos βij Qij = ? lij sin ψij sin βij ? . (21) lij cos ψij The optical ?ow equation for agent i is now given by ˙ ij = ? Q

j ∈Ni j ∈Ni

ωi × Qij +

j ∈Ni

(vj ? vi )

(22)

where ωi ∈ R3 is the angular velocity vector of agent i. vi and vj are the velocity vectors of agents i and j given in the body frame of agent i. The summation is over the set of neighbors Ni of agent i. The angular velocity ωi in terms of the desired inputs (19) and (20) becomes ? ? ?Uiθ ωi = vi × vj = ? Uiφ ? . (23) 0 j ∈Ni

20

20

15

10

15

5

position [m]

position [m]

0

10

?5

?10

5

?15

0

?20

0

5

10 position [m]

15

20

?25

?10

?5

0

5

10 15 position [m]

20

25

30

35

40

Fig. 4.

At T = 0 (sec) agents form a connected graph.

Fig. 5. At T = 100 (sec) group reaches a stable formation - (Leaderless case)

20

position [m]

After plugging in (21) and (23) in the optical ?ow equation (22), we can solve for the control input Uiθ and Uiφ in terms of ˙ ij , ψ ˙ ij and τij . It is shown the measured quantities βij , ψij , β in the next section that the geodesic control laws can result in the alignment of the velocities vectors of a multi-agent system. VII. S IMULATIONS In this section we numerically show that the distributed control law (9) can force a group of agents to ?ock according to de?nition (3.1). In our simulations the group consists of 10 agents with dynamics described by (1). The initial position and heading of all agents are generated randomly within a pre-speci?ed area. The initial location of agents are shown by ( ), and the ?nal location by (?). The neighboring radius is chosen large enough so that agents form a connected graph. The initial states of 10 agents are shown in Figure 4. Figure 5 shows that agents smoothly adjust their headings and after a reasonable amount of time they converge to a formation, and their relative distances stabilizes. The effect of a leader in the group is shown in Figures 6 and 7. In the simulations, one of the agents is randomly chosen to be the leader of the group, and its heading is constant. Without knowing which one of them is the leader, all other agent adjust their headings to follow him so that the formation remains stable. Even if the leader’s motion has dynamics, agents in the group will follow him, as it is shown in Figure 7. Figure 8 shows how the geodesic control laws (19) and (20) result in ?ocking of agents in three dimensions. VIII. C ONCLUSIONS AND F UTURE W ORK We provided a coordination scheme which resulted in ?ocking of a collection of kinematic agents. The control law was based on nearest neighbor sensing, without the need for explicit communication between agents. The coordination scheme was based on measurement of relative bearing, optical ?ow and time-to-collision between each agent and its nearest neighbors. It was shown that it possible to develop a distributed control law similar to that of the Kuramoto model of coupled nonlinear oscillators [16].

15

10

5

0

?5

?10

?15

?20

?5

0

5

10

15 20 position [m]

25

30

35

40

Fig. 6.

All agents are forced to follow the leader.

It was shown that ?ocking is possible despite possible changes in the topology of the proximity graph representing the neighborhood relationship. Furthermore, we showed that similar results extend to leader-follower formations. A generalization of the current analysis would be to develop results similar to [32], [33] for dynamic models, by using arti?cial potential functions similar to [10] while avoiding explicit use of relative headings. An important question that we need to answer is how to enforce the connectivity condition of the proximity graph. This idea is known as topology control in the mathematics and networking community. A starting point could be to follow the work of [37] as a primary result in topology control for planar graphs. R EFERENCES

[1] M. Batalin, G.S. Sukhatme, and M. Hattig. Mobile robot navigation using a sensor network. In IEEE International Conference on Robotics and Automation, pages 636–642, 2004. [2] R. W. Beard and V. Stepanyan. Synchronization of information in distributed multiple vehicle coordinated control. In Proceedings of IEEE Conference on Decision and Control, December 2003. [3] S.S. Beauchemin and J.L. Barron. The computation of optical ?ow. ACM Computing Surveys, 27:433–467, 1995. [4] R. Cipolla and A. Blake. Surface orientation and time to contact from image divergence and deformation. In Proc. Second European Conference on Computer Vision, pages 187–202, 1992.

35

30

[17] [18] [19] [20] [21]

25 position [y]

20

15

10

?5

0

5

10 position [x]

15

20

25

[22] [23]

Fig. 7.

Agents follow a leader with dymanic motion.

40

[24]

35

30

25 position [m]

[25] [26] [27]

20

15

10

5 40 0 20 15 10 5 0 ?5 ?10 position [m] ?15 ?20 0 ?25 position [m] 20

[28] [29] [30]

Fig. 8.

The velocity vectors converge to a common direction in 3D

[5] J. Cortes, S. Martinez, T. Karatas, and F. Bullo. Coverage control for mobile sensing networks. IEEE Transactions on Robotics and Automation, 20(2):243–255, February 2004. [6] N. Cowan, O. Shakernia, and R. Vidaland S. Sastry. Formation control of nonholonomic mobile robots with omnidirectional visual servoing and motion segmentation. In IEEE Conference on Intelligent Robotic Systems, 2003. [7] A. Das, R. Fierro, V. Kumarand J. Ostrowski, J. Spletzer, and C. J. Taylor. Vision based formation control of multiple robots. IEEE Trans. Robotics and Automation, 19:813–825, 2002. [8] J. P. Desai, J. P. Ostrowski, and V. Kumar. Modeling and control of formations of nonholonomic mobile robots. IEEE Transactions on Robotics and Automation, 17(6):905–908, 2001. [9] A. F. Filippov. Differential equations with discontinuous right-hand side. Mathematics and Its Applications (Soviet Series). Kluwer Academic Publishers, The Netherlands, 1988. [10] P. Ogren E. Fiorelli and N. E. Leonard. Cooperative control of mobile sensing networks:adaptive gradient climbing in a distributed environment. IEEE Transactions on Automatic Control, 49(8):1292– 1302, August 2004. [11] J. Fredslund and M.J. Mataric. A general algorithm for robot formations using local sensing and minimal communication. IEEE Trans. Robotics and Automation, pages 837– 846, 2002. [12] V. Gazi and K. M. Passino. Stability analysis of swarms. IEEE Transactions on Automatic Control, 48(4):692–696, April 2003. [13] C. Godsil and G. Royle. Algebraic Graph Theory. Springer Graduate Texts in Mathematics # 207, New York, 2001. [14] R. Horn and C. Johnson. Matrix Analysis. Cambridge University Press, 1999. [15] A. Jadbabaie, J. Lin, and A. S. Morse. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control, 48(6):988–1001, June 2003. [16] A. Jadbabaie, N. Motee, and M Barahona. On the stability of Kuramoto

[31] [32] [33]

[34] [35]

[36] [37] [38] [39]

model of coupled nonlinear oscillators. In Proceedings of the American Control Conference, June 2004. E.W. Justh and P.S. Krishnaprasad. A simple control law for UAV formation ?ying. Technical Report 2002-38, Institute for Systems Research, 2002. E. Klavins and D. E. Koditschek. Phase regulation of decentralized cyclic robotic systems. International Journal of Robotics Research, 21(3):257–276, 2002. J. J. Koenderink and A. J. van Doorn. How an ambulant observer can construct a model of the enviornment from the geometrical structure of the visual in?ow. Kybernetik, 1977. D. N. Lee and P. E. Reddish. Plummeting gannets - a paradigm of ecological optics. Nature, 5830:293–294, 1981. Z. Lin, M. Brouke, and B. Francis. Local control strategies for groups of mobile autonomous agents. 49(4):622–629, April 2004. L. Mureau. Leaderless coordination via bidirectional and unidirectional time-dependent communication. In Proceedings of IEEE Conference on Decision and Control, December 2003. K. Daniilidis N. Moshtagh, A. Jadbabaie. Distributed geodesic control laws for ?ocking of nonholonomic agents. In IEEE Conference on Decision and Control, 2005. (submitted). D.J. Naf?n, G.S. Sukhatme, and M. Akar. Lateral and longitudinal stability for decentralized formation control. In Proceedings of the International Symposium on Distributed Autonomous Robotic Systems, 2004. ¨ P. Ogren, M. Egerstedt, and X. Hu. A control Lyapunov function approach to multi-agent coordination. IEEE Transactions on Robotics and Automation, 18, October 2002. R. Olfati-Saber and R. M. Murray. Consensus problems in networks of agents with switching topology and time-delays. IEEE Transactions on Automatic Control, 49(9):1520–1533, September 2004. A. Papachristodoulou and A. Jadbabaie. Synchronization in oscillator networks: Switching topologies and presence of nonhomogeneous delays. In IEEE Conference on Decision and Control, 2005. (submitted). J. K. Parrish and L Edelstein-Keshet. Complexity, pattern, and evolutionary trade-offs in animal aggregation. Science, 284:99–101, 1999. C. Reynolds. Flocks, birds, and schools: a distributed behavioral model. Computer Graphics, 21:25–34, 1987. P.E. Rybski, S.A. Stoeter, M. Gini, D.F. Hougen, and N.P. Papanikolopoulos. Performance of a distributed robotic system using shared communications channels. IEEE Trans. Robotics and Automation, 19:847–855, 2002. S. H. Strogatz. From Kuramoto to Crawford: exploring the onset of synchronization in population sof coupled nonlinear oscillators. Physica D, 143:1–20, 2000. H. Tanner, A. Jadbabaie, and G. Pappas. Flocking in ?xed and switching newtorks. Automatica, July 2003, submitted. H. Tanner, A. Jadbabaie, and G Pappas. Flocking in teams of nonholonomic agents. In V. Kumar, A. S. Morse, and N. E. Leonard, editors, Proceedings of the Block Island Workshop on Cooperative Control, Springer Series in Control and Informations Science, to appear. 2004. T. Vicsek, A. Czirok, E. Ben Jacob, I. Cohen, and O. Schochet. Novel type of phase transitions in a system of self-driven particles. Physical Review Letters, 75:1226–1229, 1995. R. Vidal, O. Shakernia, and S. Sastry. Formation control of nonholonomic mobile robots with omnidirectional visual servoing and motion segmentation. In IEEE International Conference on Robotics and Automation, 2003. Y. Wang and B. J. Frost. Time to collision is signalled by neurons in the nucleus rotundus of pigeons. Nature, 356(6366):236–238, 1992. Roger Wattenhofer, Li Li, Paramvir Bahl, and Yi-Min Wang. Distributed topology control for wireless multihop ad-hoc networks. In INFOCOM, pages 1388–1397, 2001. T. Weigel, J.-S. Gutmann, M. Dietl, A. Kleiner, and B. Nebel. Cs freiburg: coordinating robots for successful soccer playing. IEEE Trans. Robotics and Automation, 19:685– 699, 2002. Z. Zhu, K. Rajasekar, E. Riseman, and A. Hanson. Panoramic virtual stereo vision of cooperative mobile robots for localizing 3d moving objects. In IEEE Workshop on Omnidirectional Vision, pages 29–36, 2000.

- Flocking for multi-agent dynamic systems Algorithms and theory
- Real world multi-agent systems information sharing, coordination and planning
- Behavior-Based Coordination in Multi-Robot Systems
- distributed coordination of multi-agent systems with quantizaed-observer based encoding-decoding
- Distributed Consensus for Multi-agent Systems with Communication Delays and Limited Data Rate
- Distributed coordination in multi-agent systems
- Distributed multi-criteria coordination in multi-agent systems
- A UML-Based Conversion Tool for Monitoring and Testing Multi-Agent Systems
- An algorithm for distributed reinforcement learning in cooperative multi-agent systems
- Division of Water Supply Systems into District Metered Areas Using a Multi-agent Based Approach
- 学霸百科
- 新词新语