Int'l J. of Communications, Network and System Sciences
Vol.3 No.6(2010), Article ID:2009,9 pages DOI:10.4236/ijcns.2010.36076
Flocking Control of a Group of Agents Using a Fuzzy-Logic-Based Attractive/Repulsive Function
Institute of Nonlinear and Complex Systems, China Three Gorges University, Yichang, China
E-mail: {yuhui, jiguijian, Shenyj}@ctgu.edu.cn
Received March 5, 2010; revised April 7, 2010; accepted May 17, 2010
Keywords: Flocking, Cooperative Control, Multi-Agent System, Fuzzy Logic
Abstract
In this study, a novel procedure is presented for control and analysis of a group of autonomous agents with point mass dynamics achieving flocking motion by using a fuzzy-logic-based attractive/repulsive function. Two cooperative control laws are proposed for a group of autonomous agents to achieve flocking formations related to two different centers (mass center and geometric center) of the flock. The first one is designed for flocking motion guided at mass center and the other for geometric center. A virtual agent is introduced to represent a group objective for tracking purposes. Smooth graph Laplacian is introduced to overcome the difficulties in theoretical analysis. A new fuzzy-logic-based attractive/repulsive function is proposed for separation and cohesion control among agents. The theoretical results are presented to indicate the stability (separation, collision avoidance and velocity matching) of the control systems. Finally, simulation example is demonstrated to validate the theoretical results.
1. Introduction
A special behavior of large number of interacting dynamic agents called “flocking” has attracted many researchers from diverse fields of scientific and engineering disciplines. Examples of this behavior in the nature include flocks of birds, schools of fish, herds of animals, and colonies of bacteria.
In 1986, Reynolds introduced three heuristic rules that leads to the creation of the first computer animation model of flocking [1]. It should be noticed that these rules are also known as cohesion, separation, and alignment rules respectively in the literature. Similar problems have become a major thrust in systems and control theory, in the context of cooperative control, distributed control of multiple vehicles and formation control. A research field which is tightly related to the theme of this paper is that of consensus seeking of autonomous multi-agent. In this case, multi-agent achieve consensus if their associated state variables converge to a common value [2-5]. In the meantime, an important progression has been achieved on synchronous and/or asynchronous swarm stability analysis [6-8]. Pioneering works [9-11] on flocking motion of particle systems have properly explained the heuristic rules embedded in Reynolds model. One of the important works in [9-11] is the design of attractive/repulsive potential function. In [12], Gu and Hu proposed a flocking control algorithm for fixed and switching network of multi-agent respectively, in which the attractive/repulsive potential was designed using fuzzy logic. Stability is analyzed using the classical Lyapunov theory in fixed network and non-smooth analysis in dynamical network, respectively.
In this study, the flocking behaviors of multi-agent systems with point mass dynamics and dynamical network topology are investigated. The major difference or contribution compared with previous works, for example [9-12], can be outlined as follows. First of all, the new results are based on more general particle model and the flocking motion is centered at different centers, e.g., mass center and geometric center. Secondly, two new cooperative control laws are proposed such that desired collective behaviors (separation, collision avoidance and velocity matching) can be achieved. Finally, smooth graph Laplacian and smooth attractive/repulsive potential based on fuzzy logic are proposed to overcome the difficulties in theoretical analysis and for separation and cohesion control between agents, respectively. In contrast to [12], owing to the design of smooth attractive/repulsive potential based on fuzzy logic and application of smooth graph Laplacian, stability analysis both in fixed and dynamical networks can easily conducted using classical Lyapunov theory.
The rest of the paper is organized as follows. In Section 2, the problems are formulated based on algebraic graph theory, preliminaries about smooth collective potential function and fuzzy control function are provided. In Section 3, two flocking control laws based on fuzzy logic are proposed. Stability analysis is given in Section 4. Simulation results are provided in Section 5. Finally, concluding remarks are made in Section 6.
2. Problem Formulation and Preliminaries
2.1. System Dynamics
Consider a group of agents (or particles) moving in an -dimensional Euclidean space, each has point mass dynamics described by
(1)
where is the position vector of agent, is its velocity vector, is its mass, is the control input acting on agent, is the velocity damping gain, and is the velocity damping term.
For flocking motion of a group of agents, the control objectives are to design flocking control laws such that:
a) The distances between any two neighbor agents are asymptotically convergent to a desired constant value;
b) The velocity vectors reach consensus, i.e., , where is the velocity vector of the center of a group of agents and is the velocity vector of a virtual agent;
c) No collision between agents occurs during the flocking.
The theoretical framework presented in this paper for creation of flocking behavior relies on a number of fundamental concepts in algebraic graph theory [13] that are described below.
A weighted undirected graph will be used to model the interaction topology among agents. An undirected graph consists of a set of vertices and a set of edges, where an edge is an unordered pair of distinct vertices in. In graph, the th node represents agent and a edge denoted as or represents an information exchange link between agentand. The adjacency matrix of a graph is a matrix with nonzero elements satisfying the property. Throughout the paper, for simplicity of notation, we assume for all (or the graphs have no loops). The graph is called weighted whenever the elements of its adjacency matrix are other than just elements. Here, weighted undirected graph is used in this paper. The degree matrix of is a diagonal matrix with diagonal elements that are row-sums of. The graph Laplacian is defined as. The Laplacian matrix always has a right eigenvector associated with eigenvalue. A graph is called undirected if and only if the adjacency matrix is symmetric. The set of neighbors of node is defined by
(2)
In fixed network topology, agent can range or communication with a fixed set of neighbors. Therefore, the set is time invariant. However, in dynamical or switching network topology, the set of neighbors of agent is time-varying due to limited communication.
2.2. Smooth Collective Potential Function
Smooth collective potential function is originally proposed in [11]. The following is a brief introduction about it. For more detailed information, the reader is referred to [11].
In order to construct smooth collective potential function, a map is defined as
with a parameter. Note that is differentiable everywhere, but is not differentiable at.
Smooth adjacency matrix elements are constructed by using a scalar function that smoothly varies between and. One possible choice is as follows:
(3)
where. Using this function, a position-dependent adjacency matrix can be defined as with
(4)
and position-dependent Laplacian matrix as , where, , denote the interaction range between two agents.
The set of neighbors of agent is defined by
.
By the definition of, the control objective (1) can be expressed as following algebraic constraint:
(5)
where.
Given a interaction range, a neighboring graph can be specified by and the set of edges, that clearly depends on.
A smooth collective potential function has the form:
where is a smooth pairwise attractive/repulsive potential with a finite cut-off at and a global minimum at. In order to construct a smooth potential function, denote and define this function as:
(6)
where is some function to be designed. Obviously, function should vanish for all.
In the next section, the function is implemented using fuzzy logic.
2.3. Preliminaries of Fuzzy Control Function
To the best of our knowledge, for flocking control, [12] is the first paper in which attractive/repulsive function is designed using fuzzy logic. In this section, we provide a brief introduction about fuzzy control function [12].
A set of fuzzy logic rules performs a mapping from an input to a deterministic control, i.e., fuzzy control function. For the kth dimension state, agent uses states to build a P-dimension vector as fuzzy input. The corresponding fuzzy input set is. A fuzzy rule between agent and agent can be expressed as:
where, is the number of fuzzy rules.
Use the Gaussian function to define the membership function of fuzzy set:, where are the mean and variance, respectively. The activation degree of rule is calculated by product operation:
The crisp output is calculated by center of area method:
3. Flocking Motion Guided at Mass Center and/or Geometric Center
In this section, two cooperative control algorithms are developed for flocking guided at mass center and geometric center respectively. In flocking motion, each agent applies a control input that consists of four terms:
(7)
where is a gradient-based term and will be designed using fuzzy logic, is a velocity consensus/alignment term, is a navigation term due to a group objective and is the velocity damping term.
Similar to [9-11], the velocity consensus/alignment term is in the form
(8)
and
(9)
for flocking motion guided at mass center and geometric center, respectively. The navigation term is designed in the following form
(10)
The pair is the desired state vector of the group center (mass center or geometric center). The desired state of the group center can be described by
(11)
3.1. Fuzzy Attractive/Repulsive Control
For state vector, the fuzzy input consists of and, where, i.e., and . The fuzzy output is defined as
which implies. A fuzzy rule is then defined as:
Therefore,
The fuzzy output vector between agent and is
where
Denote the gradient of the attractive/repulsive potential as:
and denote, we have
(12)
Therefore, gradient-based control term can be designed as
(13)
3.2. Flocking Control guided at Group Centers
Consider the multi-agent motion relative to the group center (the mass centeror geometric center). The position and velocity vectors of agent relative tois denoted byand, the collective state vectors of all agents relative toby and, whereor, , is kronecker product.
The mass center of all agents is defined as
(14)
Note that
(15)
and due to, , , we have
Then, the dynamic of mass center is given by
(16)
Denote, the relative dynamic of center of mass is given by
(17)
where
We can choose proper control parameters and such that matrix is Hurwitz stable, and from Lyapunov theory, for given positive matrix, there exists a positive definite matrix, such that:
(18)
For creation of flocking motion relative to mass center, we propose following control laws:
(19)
where.
The geometric center of all agents is defined as
(20)
Similarly, for geometric center, we propose following control law:
(21)
4. Analysis of Stability
In this section, we present our main results for flocking in multi-agent networks with dynamical topology, and conduct stability analysis based on classical Lyapunov theory and LaSalle's invariance principle. In [12], owing to the discontinuity of collective potential function in the case of dynamical topology, stability analysis is done using classical Lyapunov theory in fixed networks and nonsmooth analysis theory, which is difficult to understand for engineers in real applications, in dynamical networks, respectively. In our paper, due to the design of smooth collective potential function, in both cases of fixed network and dynamical network, stability analysis can be conducted based on classical Lyapunov theory and LaSalle's invariance principle.
For the collective motion relative to mass center, define energy function
(22)
where,
is the parameter of the navigation term.
Applying control law (19) to system (1), following theorem is held to explain the emergence of flocking behaviors of agents guided at center of mass.
Theorem 1 Consider a group of agents applying control law (19) with proper selected parameters satisfying (18) to system (1). Assume that the initial value is finite. Then, the following statements hold.
(i) The solution of system (1) asymptotically converges to an equilibrium point where a local minima of is.
(ii) The velocities of all agents asymptotically converge to the velocity of mass center, and the velocity of mass center asymptotically converge to the desired velocity, i.e.,.
(iii) No collision between agents occurs during the flocking.
Proof: First of all, we explain the fact that the energy function is positive definite.
Obviously, and is positive. Therefore, the positive definiteness of energy function is equivalent to that of. By similar analysis to theorem 1 of [12], can be designed positive definite by using proper fuzzy rules, i.e., can be designed positive definite.
Secondly, the derivative of the energy function is seminegative definite.
(23)
(24)
Due to, we have
From (15) and note that
We have
Then,
(25)
where.
From (17), we have
(26)
From (23) to (26), we have
(27)
Part (i) and part (ii) follow from LaSalle's invariance principle. As is seminegative definite, given, is an invariant set. From, we have. Therefore, both and are bounded. Given the desired state is bounded and from the definition of and, we know is bounded.
From LaSalle's invariance principle, all states starting inconverge to the largest invariant set. Hence, all states converge to the largest invariant set asymptotically, i.e., all agent velocities converge to the velocity of center of mass, , and the position and velocity vectors of center of mass, , converge to the desired states, , asymptotically.
Furthermore, in stable state,. There is a equilibrium point at where is a local minima of.
Finally, we prove part (iii) by contradiction. Assume there exists a time when two distinct agents collide, i.e.,. For all, we have
At, defining larger than leads to, which is in contradiction with the invariant set. Therefore, no two agents collide at any time.
Remark: From theorem 1, control objective a) and b) are achieved, but the geometric characterization of local minima of is not possible satisfying the algebraic constraint (5). In [11], the authors pose two conjectures that establish the close relationship between geometric and graph theoretic properties of any local minima of and features of flocks. Based on the conjectures in [11], we can conclude that the local minima of is a so-called quasi--lattice [11], i.e.,. Obviously, it is very close to the conformation satisfying algebraic constraint (5).
When control laws (21) applied to system (1), similar theorem is established to explain the emergence of flocking behavior of agents guided at geometric center.
For the collective motion relative to geometric center, define energy function
Where
, is the parameter of the navigation term,.
We have following theorem.
Theorem 2 Consider a group of agents applying control law (21) with proper selected parameters satisfying (18) to system (1). Assume that the initial value is finite. Then, the following statements hold.
1) The solution of system (1) asymptotically converges to an equilibrium point where a local minima of is.
2) The velocities of all agents asymptotically converge to the velocity of geometric center, and the velocity of geometric center asymptotically converge to the desired velocity, i.e.,.
3) No collision between agents occurs during the flocking.
Proof: The proof of this theorem is similar to that of theorem 1.
5. Simulation
In this section, mass center guided flocking motion is simulated in 2-dimentional space. The following parameters were fixed throughout the simulation:, and for. Eight fuzzy sets are designed for the fuzzy control input. They are LN, N, SN, Z, SP, P, LP, and PP as shown in Figure 1. Eight fuzzy rules are designed as follows:
IF is LN THEN
;
IF is N THEN
;
IF is SN THEN
;
IF is Z THEN;
IF is SP THEN
;
IF is P THEN
;
IF is LP THEN
;
IF is PP THEN
.
Control parameters are selected to be. The two eigenvalues of matrix are and. Therefore, matrix is Hurwitzstable. Let, using Matlab command lyap(K,Q), we obtain positive definite matrix.
Figure 1. Fuzzy membership function.
Simulation is calculated within 20 seconds time by using Matlab Simulink. In addition, the position of each agent is marked with a right triangle sign.
Figures 2 to 5 show the simulation results within 2-D flocking using control law (19) for 50 agents. Figures 2 to 4 show snapshots of 2-D flocking at time, and (sec). The initial position and initial velocity coordinates were uniformly chosen in the random domain of and, respectively. The mass of each agent was also uniformly chosen in a random domain of [0.5, 1.5]. A steady configuration was formed
Figure 2. Initial positions of 50 agents.
Figure 3. Configuration of 50 agents at t = 4.3495 (sec).
Figure 4. Final configuration of 50 agents at t = 20 (sec).
Figure 5. Position-dependent neighboring graph at t = 20 (sec).
Figure 6. Velocities of 50 agents along x-axis and y-axis respectively.
Figure 7. Trajectories of all agents within 20 (sec) time.
as shown in Figure 4 and maintained thereafter. A virtual agent
was used for this example. For highly disconnected neighboring graph in initial state, Figure 5 shows the connected neighboring graph corresponding to the final configuration. Figure 6 shows velocity matching is achieved along x-axis and y-axis respectively. Figure 7 shows the trajectories of all agents within 20(sec) simulation time and the cohesive behaviors. The simulation demonstration with control law (21) was similar to that conducted by control laws (19), and therefore is not necessarily repeated here.
6. Conclusions
This paper establishes a theoretical framework for design and analysis of flocking control algorithms using a fuzzy-logic-based attractive/repulsive potential function for multiple agent networks with dynamical topology. Two cooperative control laws have been proposed for a group of autonomous agents to achieve flocking motion relative to different centers (mass center and geometric center). A virtual agent is introduced to represent a group objective for tracking purposes. Smooth Laplacian and smooth fuzzy-logic-based attractive/repulsive potential are proposed to overcome the difficulties in stability analysis. Simulation results validated the theoretical results.
7. Acknowledgements
This paper is supported in part by Hubei Provincial Natural Science Foundation under the grant 2008CDB316, Natural Science Research Project of Hubei Provincial Department of Education under the grant D20101201, and Scientific Innovation Team Project of Hubei Provincial College under the grant T200809.
8. References
[1] C. W. Reynolds, “Flocks, Herds, and Schools: A Distributed Behavioral Model,” Computer Graphics (ACM SIGGRAPH '87 Conference Proceedings), Vol. 21, No. 4, 1987, pp. 25-34.
[2] R. Olfati-Saber and R. M. Murray, “Consensus Problems in Networks of Agents with Switching Topology and Time-Delays,” IEEE Transactions on Automatic Control, Vol. 49, No. 9, September 2004, pp. 101-115.
[3] A. Jadbabaie, J. Lin and S. A. Morse, “Coordination of Groups of Mobile Agents Using Nearest Neighbor Rules,” IEEE Transactions on Automatic Control, Vol. 48, No. 6, June 2003, pp. 988-1001.
[4] W. Ren and R. Beard, “Consensus Seeking in MultiAgent Systems Using Dynamically Changing Interaction Topologies,” IEEE Transactions on Automatic Control, Vol. 50, No. 5, May 2005, pp. 655-661.
[5] L. Moreau, “Stability of Multiagent Systems with Time-Dependent Communication Links,” IEEE Transactions On Automatic Control, Vol. 50, No. 2, February 2005, pp. 169-182.
[6] Y. Liu, K. M. Passino and M. M. Polycarpou, “Stability analysis of M-dimensional Asynchronous Swarms with a Fixed Communication Topology,” IEEE Transactions on Automatic Control, Vol. 48, No. 1, Juanary 2003, pp.76- 95.
[7] Y. Liu, K. M. Passino and M. M. Polycarpou, “Stability Analysis of One-Dimensional Asynchronous Swarms,” IEEE Transactions on Automatic Control, Vol. 48, No. 10, October 2003, pp. 1848-1854.
[8] V. Gazi and K. M. Passino, “Stability Analysis of Swarms,” IEEE Transactions on Automatic Control, Vol. 48, No. 4, April 2003, pp. 692-697.
[9] H. G. Tanner, A. Jadbabaie and G. J. Pappas, “Stable Flocking of Mobile Agents, Part I: Fixed Topology,” The 42nd IEEE Conference on Decision and Control, Maui, December 2003, pp. 2010-2015.
[10] H. G. Tanner, A. Jadbabaie and G. J. Pappas, “Stable Flocking of Mobile Agents, Part II: Dynamic Topology,” The 42nd IEEE Conference on Decision and Control, Maui, December 2003, pp. 2016-2021.
[11] R. Olfati-Saber, “Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory,” IEEE Transactions on Automatic Control, Vol. 51, No. 3, March 2006, pp. 401-420.
[12] D. Gu and H. Hu, “Using Fuzzy Logic to Design Separation Function in Flocking Algorithms,” IEEE Transactions on Fuzzy Systems, Vol. 16, No. 4, August 2008, pp. 826-838.
[13] C. Godsil and G. Royle, “Algebraic Graph Theory,” Springer, New York, 2001.