Xi'an Technological University
Subject: Computer Science , Software Engineering
eISSN: 2470-8038
SEARCH WITHIN CONTENT
Yang Sen ^{*} / Xi Leiping
Keywords : Formation Control, Graph Theory, Consistency Theory, Second-order Integrator, Pilot-follow Method
Citation Information : International Journal of Advanced Network, Monitoring and Controls. Volume 3, Issue 2, Pages 54-61, DOI: https://doi.org/10.21307/ijanmc-2018-032
License : (CC-BY-NC-ND-4.0)
Published Online: 07-May-2018
This paper introduces graph and group system consistency theory and puts forward a quadrotor formation control method. The quadrotor is described as a second-order integrator dynamic system, and the relative position deviation of different quadrotors is used to describe formation. According to the communication topology relationship between quadrotors, the formation is modeled by graph theory. The fusion of the pilot-follow and graph theory method is analyzed, and a second-order coherence algorithm with a pilot is presented. With this algorithm, the quadrotors can complete behaviors just as formation rally and formation mobility etc. Finally the paper verifies the availability of the proposed method through simulation tests.
In recent years, quadrotors become more and more popular among scientific researchers because of their small size, light weight, easy manipulation and high efficiency while performing tasks in uncertain and dangerous environment. Due to the shortage of its load and the sensor performance, a single quadrotor is highly restricted in complex tasks. Thus, more and more quadrotors are applied to work together. Multiple quadrotors formation control is a major and basic research subject in the studies of quadrotors cooperative control. It has attracted the interests of many researchers both at home and abroad. The main formation control methods are pilot-followed method, virtual structure method, behavior-based method and graph theory method. Graph theory method means to model the formation to directed graphs or undirected graphs according to the communication network topology relationship and the formation conditions, and then analyze and design the formation information flow and the formation control algorithm through mature graph theory. The method of graph theory has gradually become the mainstream of formation control as it is a fusion of several methods talked before [1].
Consistency theory has been applied in formation control research under a variety of circumstances such as the fixed topology, time-varying topology, communication time delay of ground robots, underwater vehicles and satellite systems etc [2]. Literature [3] proposes a model of multi-robot formation control, which takes a robot as a single integrator dynamics model and analyzes the multi-robot system formation and its stability with consistency theory. As shown in literature [4], in the GRASP laboratory of the Pennsylvania University, a team led by Kumar describes the formation with the relative position and relative direction of the quadrotors. By introducing the error of relative position, they control the formation flight of four quadrotors with consistency algorithm. However, the control structure they describe is a centralized control structure which demands high calculation capability of the central control unit but has poor extensibility. In literature [5], in the study of the automatic quadrotors formation, a communication topology solution is put forward based on the Hamilton loop in the cascade control system.
At present, most of the literature describes intelligence agents as first-order integrator power systems, which is relatively simple. But many complex systems must be described by second-order or higher order system so as to realize accurate and effective control. This article combines graph theory method and pilot-follow method and describes a as s second order integrator system. Through the second-order coherence algorithms, the formation of control method is studied under the topological structure that only one quadrotor is informed of the flight path and all the follower quadrotors can receive information from the pilot.
Graph is a data structure composed by a vertex set and the binary relation between vertexes (i.e., the set of edge), usually referred to as G =(V, E). The collection of vertices and edges are represented as:
In the diagram, if node i and node j has information exchange, the edge (v_{i}, v_{j}) exists; If there is no directional information exchange, then the following exists:
The diagram is called undirected graph. If the information stream is flowing from node i to node j, then the edge is directional and the diagram is a directed graph. Undirected graph can be considered as a special case of directed graph. Directed graph is more practical as it takes the one-way flow of information into consideration.
Adjacency matrix uses algebra matrix to describe the location relationship between the nodes, note adjacency matrix as A = [a_{ij}] ∈ R^{n×n}, thereinto
The neighbor nodes for the node i is the set N_{i} ⊆ V(G), namely
In undirected graph, the degree of any node i is defined as the number of neighbor nodes of node i; in directed graph, the node degree is equal to the sum of the inward degree and the outward degree of node i, namely,
The inward degree and the outward degree of node v_{i} are respectively defined as:
The undirected graph/directed graph Laplacian matrix adopts the following definition:
Assuming that number of flight vehicles in the formation is n, we use $${G}_{n}\triangleq ({v}_{n},{\epsilon}_{n})$$ to indicate the communication topology among various vehicles, in which v_{n} = {1, 2,…,n} is the node set, ε_{n} ⊆ v_{n} × v_{n} is the edge set. The matrix A_{n} = [a_{ij}] ∈ R^{n×n} and L_{n} = [I_{ij}] ∈ R^{n×n} are respectively the adjacency matrix and asymmetric Laplacian of graph G_{n}. Consider a simple single integrator system:
In the equation above, ξ_{i} ∈ R^{m} and u_{i} ∈ R^{m} are respectively the information state and control input of vehile i.
The common continuous time consistency algorithm of first-order integrator system is:
The above two equations are rewritten into matrix form as below:
Theorem 1^{[6]}: Under the condition of fixed time invariant communication topology, if and only if directed communication topology is a bunch of directed spanning tree, the flight vehicles formation can gradually reach agreement; Under the condition of time-varying communication topology, the conditions for flight vehicles formation reaching agreement are the existence of an infinite number of uniformly bounded adjacency periods which enables the set of the directed communication topology of the flight vehicles formation to exist in all these periods and contain a bunch of directed spanning tree.
When considering the maneuver of the flight vehicles formation, we indicate the information equation with a second order integral dynamic system. The second-order dynamic systems integrator algorithm is an extension of the first-order integrator power system consistency algorithm. The existence of a tufted spanning tree in the directed graph is conditions of second-order dynamic systems integrator agreement necessary rather than sufficient conditions.
Taking the following second order integrator power system as an example:
ξ_{i} ∈ R^{m} is the state of system information; ξ_{i} ∈ R^{m} is system information state derivative; u_{i} ∈ R^{m} is the system information input control of member i.
Assuming that the same communication topology about the transfer between ξ_{i} and ζ_{i} exists among different quadrotors, and also uses $${G}_{n}\triangleq ({v}_{n},{\epsilon}_{n})$$ to represent, and A_{n} and L_{n} respectively represent the adjacency matrix and asymmetric Laplace matrix. A basic second-order dynamic systems integrator consistency algorithm is as follows:
i = 1,2,…,n. For any time t is a positive number. If xi_{i} and ζ_{i} respectively signify the position and speed of vehicle i for all ξ_{i}(0) and ζ_{i}(0), through operation type (5), when t → ∞, ||ξ_{i} − ξ_{j}|| → 0 and ||ζ_{i} − ζ_{j}|| → 0, the formation may reach an agreement at this time.
If $$\xi ={[{\xi}_{1}^{T}{\xi}_{2}^{T}\cdots {\xi}_{n}^{T}]}^{T}$$, $$\zeta ={[{\zeta}_{1}^{T}{\zeta}_{2}^{T}\cdots {\zeta}_{n}^{T}]}^{T}$$ the equation above can be rewritten as:
While $$\Theta (t)=\left[\begin{array}{cc}{0}_{n\times n}& {I}_{n}\\ -{L}_{n}(t)& -\gamma (t){L}_{n}(t)\end{array}\right]$$.
Theorem 2: Algorithms (6) asymptotically may reach consistent if and only if there are only two zero eigenvalues in Θ, and other nonzero eigenvalues are all negative real part, Particularly for large enough t,
Thereinto p = [p_{1} p_{2} … p_{n}] ≥ 0, $${1}_{n}^{T}p=1$$, $${L}_{n}^{T}p=0$$. Relevant attests for the Theorem refers to the literature [7].
Quadrotor is a typical underactuated system which has four input and six output. They are usually divided into “X” type and“+ ”type. Quadrotor realizes pitch, yaw and roll motion of the plane by controlling the four motor and the speed of the propeller. The definition of inertia coordinate system ∑_{I}(OXYZ) and body coordinate system ∑_{B}(oxyz), as shown in Fig. 1.
ξ, v ∈ R^{3} is the position and velocity of the quadrotor under the inertial coordinates, and ω ∈ R^{3} is the varying attitude angular velocity of the vehicle under coordinate system. ℛ ∈ R^{3×3} is referred to as the rotation matrix from the coordinate system to the inertial coordinate system,
s = cos(•) and c = cos (•) represent the sine and cosine. Θ = [φ, θ Ψ]^{T} ∈ R^{3} is the euler angle of quadrotor in the vehicle coordinate system. e_{z} = [0 0 1]^{T} is the unit vector of z shaft. n = ℛe_{z} is column 3 of attitude matrix. m is the weight of the quadrotor. J = diag[J^{1} J^{3} J^{3}] ∈ R^{3×3} is the system rotation inertia matrix. g is the acceleration of gravity. T is the total lift of the four propellers that drives the quadrotors’ position change. τ = [τ^{1} τ^{2} τ^{3}]^{T} respectively represent the control matrix of roll, pitch and yaw direction. It is assumed that the center of the aircraft is the origin of the coordinate system. Driving motor has no installation angle error. Excepting the rotor rotation, the rest of a quadrotor is supposed as rigid. Taking the north, east, and the ground coordinate system as the inertial coordinate system, this paper adopts the system model in the literature [8]:
The quadrotor position control comprises the inner and outer loop control structure, in which the inner ring controls posture and the outer one controls position. The controller can be seen in literature [8]. The main concern here is the formation control algorithm. The formation controller receives state information of itself and the other members of the formation through its own sensors and the wireless communication network, puts out the respective expected position and posture to position controller, and drives actuator to perform formation task, as shown in Fig. 2. The key study is the design of formation controller based on second order integrator dynamic model.
If the formation size is N, according to the information interaction relationship between quadrotors, the quadrotors formation can be modeled as a directed graph. i is the node V_{i} in the directed graph, information flowing from i to j is marked as edge e_{ij}, i, j = (1,2,…,N). Number 1 is specified as the pilot and the rest are followers. In formation control layer, we can see each of the quadrotor as a particle in three-dimensional space, and the quadrotors system meet the type (4). ξ_{i}(t) ∈ R^{n} and ζ_{i}(t) ∈ R^{n}(n = 1,2,3) represent position and speed information of quadrotor i. u_{i}(t) ∈ R^{n} is the corresponding input control. Assuming that the pilot only broadcast its own information ξ^{r} and ζ^{r}, the rest followers are able to receive state information from the pilot. The formation topology structure is shown in Fig. 3. Regardless of the pilot, the topological relationship between followers can be arbitrary directed graph.
In the process of formation, communication topology remains unchanged and maintains fixed formation. For the convenience of analysis, we consider the simple case of one dimension, the analysis of the three dimensional space can be obtained through the Kronecker product.
The center of the formation is defined as V_{c}, and its coordinate is R_{c} = (x_{c}, y_{c}, z_{c}). V_{c} is the consistent balance point for consistency algorithm. If there is a leading vehicle, V_{c} is the position of the leader, and when without a leader it is the geometric center. We adopt relative position vector to describe the formation and define the relative position deviation as $${R}_{i}^{*}={({x}_{i}^{*},{y}_{i}^{*},{z}_{i}^{*})}^{T}$$. The spatial location relations are shown in Fig. 4.
For the condition of the existence of a pilot, the following consistency algorithm is shown as:
x_{d} and $${x}_{x}^{d}$$ are respectively the information of the pilot’s position and speed. α is the adjacency relation between followers and the pilot. When a follower i can receive the pilot’s state information, α > 0, otherwise α = 0. Here we take α = 1. In this algorithm, the followers also need to obtain the second order derivative information about the pilot status, namely the pilot input control.
Theorem 3: If μ_{i} is the i characteristic values of −L_{n}, λ_{i} = −α + μ_{i}, $$\overline{\gamma}=0$$. when all of the n − 1 nonzero eigenvalues of −L_{n} are all negative real part if $$\gamma >\overline{\gamma}$$, otherwise,
Therefore in the consistency of the algorithm (9), when t →∞, then $$({x}_{i}-{x}_{i}^{*})\to {x}^{d}$$ and $${v}_{ix}\to {v}_{x}^{d}$$, i = 1, 2,…, n.
When t →∞, algorithm (9) will ensure $$\Vert {x}_{i}-{x}^{d}\Vert \to {x}_{i}^{*}$$ and $$\Vert {v}_{ix}-{v}_{x}^{d}\Vert \to 0$$. At this time the formation reaches consistency and generates the specified array. On the stabilization issue of the formation, each quadrotor must agree on the formation center. The center’s position is changeless and the velocity is zero, which means $${v}_{x}^{d}\equiv 0$$. Through the consistency algorithm, different formation can be designed only by changing the communication topology G and setting up different location deviation $${R}_{i}^{*}$$.
Quadrotor control adopts traditional PID control algorithm. The inner ring control is for posture stability while the outer ring for position control. The experiment assumes that the underlying controller is well performed. On that basis, the formation control module is inserted. The formation number is N = 5, and there are no obstacles in the flight space, the system mass m = 0.6kg, and the moment of inertia are J_{x} = J_{y} = 0.2kg·m^{2}, J_{z} = 0.04kg·m^{2} the communication topological structure is shown in Fig. 5. The Specific parameter is set as α = 1, γ = 2. Quadrotor numbers 1 is the pilot and the remaining four are the followers. The deviation to describe the relative position of the expectation formation is set to
This experiment sets two circumstances: formation rally and formation maneuvers.
Case 1: the pilot hovers in the air waiting for formation in the designated position. At this point, the Setting v^{d} ≡ 0;
Case 2: the pilot make circular motion at fixed height in the air, while the other four quadrotors track the movement of the pilot and ultimately form a set mobile fleet. The trajectory of the pilot is as follows:
The simulation step is 0.001 s, and the simulation time is 15 s.
Case 1: Quadrotors formations are assembled as shown in Fig. 6. At the beginning of the simulation, the pilot waits at a position in the air while the other four take off from the ground. Each quadrotor maneuvers in the pre-selected direction and after a period of time they construct a diamond formation with the pilot as the center. That verifies the effectiveness of algorithm (9) in rallying the formation.
Case 2: Quadrotors formation maneuvers as shown in Fig. 7. At the beginning of the simulation, the pilot do circular motion in the air, the followers in different positions on the ground, take off and receive information about the pilot status. in algorithm (9), each follower will apply the second order derivative of the pilot’s status information, which means the followers know the pilot’s control input at any time. The follower quadrotors do not simply gather towards the pilot, but do circular motion in the plane direction like the pilot. As a result they rise in a spiral and eventually converge to a stabile formation with the pilot as the center.
Fig. 8 and Fig. 9 show more clearly the rule of change in position and speed of each members of the formation from the X direction and Z direction. From Fig. 8 (a), we can see the quadrotors rapidly gather to the pilot (the black curve) after they take off. At t = 4s the followers get close to the specified location and they are able to track the trajectory change of the pilot. From Fig. 8 (b), we can see after t = 5s with consistency algorithm, the following quadrotors is consistent with the pilot’s speed and are able to track speed changes of the pilot. Fig. 9 describes quadrotors’ position and speed change curve in Z direction. The changing rule is roughly the same to that in the X direction, so we do not talk about it in detail. Under the guidance of second order coherence algorithm, quadrotors formation converges at a higher speed and realizes better synchronization.
According to quadrotor aircraft fleet formation problem, the quadrotor is described as a second order integrator dynamics model and a method called distributed formation control method is designed based on graph theory and leading to follow method. The research is mainly focused on the second-order coherence algorithm in the application of the quadrotor aircraft fleet formation. In formation control layer, the quadrotor is regard as a particle in three-dimensional space, and by using the consistent algorithm with leader, the control requirements of marshalling and marshalling maneuver are realized; Finally, the validity of the consistency marshalling algorithm is verified by Matlab simulation.