A Modified Brain Storm Optimization Based Distributed Model Predictive Control Method for Formation Control of Multiple UAVs

Abstract

In this paper, a distributed Model Predictive Control (MPC) method based on modified Brain Storm Optimization (BSO) algorithm is proposed to solve the control problem of multiple Unmanned Aerial Vehicles (UAVs). The modified BSO algorithm considers all cluster centers, and the chaos mechanism is introduced into the solution replacement mechanism. Based on the distributed model predictive control framework, the cost functions and trigger mechanism are designed for formation control. Simulation results show that the designed trigger mechanism can reduce the amount of calculation, and verifies the feasibility and effectiveness of the proposed method.

1 Introduction

In an increasingly complex combat environment, a single small Unmanned Aerial Vehicle (UAV) is gradually unable to meet mission requirements. UAV swarm has attracted more attention. When performing complex tasks such as reconnaissance, offense, and defense, different formation shapes such as horizontal, column, echelon, and V formation shape can be used. A reasonable formation can improve aerodynamic efficiency, reduce energy consumption, and extend flight distance [1].

The typical control methods of formation control include leader-follower strategy, behavior-based method, virtual structure, Model Predictive Control (MPC), consensus theory, etc. SASKA [2] realized formation flying with the leader-follower control method based on the on-board visual perception equipment. Duan [3, 4] proposed an improved multi-objective pigeon-inspired optimization algorithm to design a multi-UAV obstacle avoidance control algorithm. Based on the back-stepping design, they proposed a consensus control algorithm for multi-rotor formation control. Research on MPC includes strategies to reduce the amount of calculation, nonlinear predictive control theory, and so on. Compared with the centralized model predictive control to solve the multi-constraint optimization problem as a whole, the distributed model predictive control can decompose the complexity of the overall optimization. A trigger mechanism can be combined into the MPC scheme to decrease the update frequency of control inputs and reduce the computational burden.

Brain Storming Optimization (BSO) algorithm is inspired by the brain storm conference [5]. The algorithms for improving BSO can be divided into two types. One is to change the cluster method and replace the k-means cluster with other clustering methods. The other is to change the update formula of the solution. The predator and prey mechanism can be introduced, and then perform a chaotic search on each updated solution [6]. Chaotic theory can be used to change the random one-dimensional solution in a randomly selected cluster. Multi-branch chaotic mutation can be used to generate a chaotic mutation operator [7, 8]. These methods mainly focus on the cluster method and the update method of the solution, and pay less attention to the replacement mechanism of the solution and the generation mechanism of the auxiliary solution in BSO algorithm.

2 Modified BSO Based Distributed MPC Method

2.1 Model

Assuming that there is a UAV i in a certain height horizontal plane, it can regarded as a mass point, and its state $z_{i} = [x_{i} ,y_{i} ,\theta_{i} ,v_{i} ]^{T}$ is

$$ \left\{ {\begin{array}{*{20}l} {\dot{x}_{i} = v_{i} \cos \theta_{i} } \hfill \\ {\dot{y}_{i} = v_{i} \sin \theta_{i} } \hfill \\ {\dot{\theta }_{i} = \omega_{i} } \hfill \\ {\dot{v}_{i} = a_{i} } \hfill \\ \end{array} } \right.i = 1,2,...,N_{uav} $$

(1)

where the $x_{i} ,y_{i}$ is the position of UAV i, $v_{i}$ indicates the linear velocity and $a_{i}$ is the acceleration. $\theta_{i}$ indicates the yaw angle and $\omega_{i}$ is the angular velocity.

2.2 Distributed MPC

Compared with centralized model predictive control, distributed model predictive control has stronger ability to deal with multi-input and multi-output systems with state and control constraints. It transforms the control problem into a group of control problems of subsystems, and constructs multiple distributed predictive platforms with information interaction to solve the optimization problem. Establish a distributed model predictive control framework for the UAV formation system, the UAV system $i \in V = \{ 1,2,...,N_{{{\text{uav}}}} \}$ can be expressed as

$$ \dot{z}_{i} \left( t \right) = f_{i} \left( {z_{i} \left( t \right),u_{i} \left( t \right)} \right),{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} t \ge t_{0} ,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} z_{i} (t_{0} ) = z_{i0} $$

(2)

where $z_{i} (t) \in {\mathcal{R}}^{n}$ is the state of UAV $i$ at time $t$, and $u_{i} (t) \in {\mathcal{R}}^{m}$ is the control input of the UAV $i$. $z_{i0}$ is the initial state, $t_{0}$ is the initial time, and $N_{{{\text{uav}}}}$ is the number of UAVs.

The neighbors of the UAV $i$ in the set ${\mathcal{N}}_{i}$ can be expressed as

$$ \dot{z}_{ - i} (t) = f_{ - i} (z_{ - i} (t),u_{ - i} (t)),t \ge t_{0} $$

(3)

where $u_{ - i} (t) = \{ u_{j} (t)\} ,z_{ - i} (t) = \{ z_{j} (t)\} ,j \in {\mathcal{N}}_{i}$. And the optimal predictive control input and cost function of the UAV $i$ are

$$ u_{i}^{*} (s;t_{c} ) = \arg \mathop {\min }\limits_{{u_{i}^{*} (s;t_{c} )}} J_{i} \left( {z_{i} (s;t_{c} ),z_{ - i} (s;t_{c} ),u_{i} (s;t_{c} )} \right) $$

(4)

$$ J_{i} = \int_{{t_{c} }}^{{t_{c} + T_{p} }} {F_{i} \left( {z_{i}^{p} (s;t_{c} ),\hat{z}_{ - i} (s;t_{c} ),u_{i}^{p} (s;t_{c} )} \right)ds} $$

(5)

where the prediction horizon $T_{p} \in (0,\infty )$ is a constant, and the control update period $\delta_{T} \in (0,T_{p} ]$ is selected based on requirements. The update time is defined as $t_{c} = t_{0} + \delta_{T} c,c \in \left\{ {0,1,2,...} \right\}$. At each update instant, $J_{i}$ is a distributed cost function, $F_{i}$ is a function determined by task requirements, $z_{i}^{p} (s;t_{c} )$ is the predictive state of the UAV $i$ and $\hat{z}_{ - i} (s;t_{c} )$ is the estimated state of its neighbors. The estimated state is composed of two parts, the optimal prediction state ${\text{ z}}_{j}^{*} (s;t_{c - 1} )$ in $s \in [t_{c} ,t_{c - 1} + T_{p} )$ and the optimal prediction state $z_{j}^{*} (t_{c - 1} + T_{p} ;t_{c - 1} )$ in $s \in [t_{c - 1} + T_{p} ,t_{c} + T_{p} ]$.

2.3 Modified BSO

Firstly, an initial solution is randomly generated in the solution space, and each solution can be expressed as $X_{i} = \left\{ {X_{i}^{1} ,X_{i}^{2} ,...,X_{i}^{D} } \right\},i \in \left\{ {1,2,3,...,N} \right\}$,$D$ is the dimension of solution space, $X_{i}^{1} ,X_{i}^{2} ,...,X_{i}^{D}$ are coordinates of the solution in each dimension of the solution space. The range of the solution is limited by the solution space $X_{i} \in \left[ {X_{\min } ,X_{\max } } \right]$, where $X_{\min }$ is the lower limit of the solution space and $X_{\max }$ is the upper limit of the solution space.

K-means cluster is used to divide $N$ individuals into $m$ clusters. In each cluster $C_{j} ,j \in \left\{ {1,2,3,...,m} \right\}$, individuals are sorted according to the value of cost function, and the optimal individual is the cluster center $X_{Cj}$.

Replace the solution with probability $p_{r}$, and randomly generate a random number $p_{r0}$ between [0, 1]. If $p_{r0} < p_{r}$, select a cluster center $X_{{Cj_{r} }}$ randomly and replace it with chaotic solution, where $j_{r} \in \left\{ {1,2,3,...,m} \right\}$ is the randomly selected. A D-dimension vector $cr(0)$ is randomly generated as the seed of the sequence. A chaotic map $f_{rmap}$ is selected for $n_{r}$ times mapping, and the chaotic sequence $\left\{ {cr(1),cr(2),...,cr(n_{r} )} \right\}$ is generated by formula

$$ cr(i_{r} ) = f_{rmap} (cr(i_{r} - 1)),i_{r} = 1,2,...,n_{r} $$

(6)

The corresponding chaotic solution sequence $\left\{ {cx(1),cx(2),...,cx(n_{r} )} \right\}$ is obtained by formula

$$ cx(i_{r} ) = cr(i_{r} )(X_{\max } - X_{\min } ) + X_{\min } $$

(7)

The cost function value of each chaotic solution is calculated. The chaotic solution $cx_{best}$ with the optimal cost function value is to replace the selected cluster center $X_{{Cj_{r} }} = cx_{best}$.

Generate an auxiliary solution $X_{ih}$ for each solution $X_{i}$. In the generation of auxiliary solution $\left\{ {X_{{C_{1} }} ,X_{{C_{2} }} ,...,X_{{C_{m} }} } \right\}$ all cluster centers are considered. A m-dimension vector $ch(0) = \left[ {ch_{1} (0),ch_{2} (0),...,ch_{m} (0)} \right]$ is randomly generated as the seed of the sequence, and a chaotic map $f_{hmap}$ is selected for secondary mapping. The chaotic weight coefficient sequence $\left\{ {ch(1),ch(2),...,ch(n_{h} )} \right\}$ is generated by

$$ ch(i_{h} ) = f_{hmap} (cr(i_{h} - 1)),i_{h} = 1,2,...,n_{h} $$

(8)

Use $ch(n_{h} ) = \left[ {ch_{1} (n_{h} ),ch_{2} (n_{h} ),...,ch_{m} (n_{h} )} \right]$ and cluster centers to generate auxiliary solutions

$$ X_{ih} = \sum\limits_{j = 1}^{m} {(ch_{j} (n_{h} ) \times X_{{C_{j} }} )} $$

(9)

A new solution $X_{inew}$ is generated based on each auxiliary solution $X_{ih}$. The update formula is

$$ X_{inew} = X_{ih} + {\text{logsig}}({{(0.5 \times T_{\max } - T_{now} )} \mathord{\left/ {\vphantom {{(0.5 \times T_{\max } - T_{now} )} k}} \right. \kern-\nulldelimiterspace} k}) \times X_{rand} \times norm(0,1,D) $$

(10)

${\text{logsig()}}$ is the sigmoid function, and the output of it is between $(0,1)$. $k$ is the parameter that affects the slope of the function. $T_{\max }$ is the maximum number of iterations, $T_{now}$ is the current number of iterations. $norm(0,1,D)$ generates a normal distribution of random numbers to form a D-dimensional vector. If the value of cost function of $X_{inew}$ is better than that of $X_{i}$, update the solution $X_{i} = X_{inew}$.

It is checked whether the maximum number of iterations is reached, and if reached, the optimal solution is output as the optimization result, otherwise, iterative optimization is performed until the maximum number of iterations is reached. The flow chart of the modified BSO algorithm is shown in Fig. 1.

Fig. 1.

The flow chart of the modified BSO algorithm

2.4 Cost Functions and Trigger Mechanism

Cost Functions

The cost function for multiple UAVs to maintain the desired formation according to the desired trajectory are

$$ F_{i} (z_{i} (t),u_{i} (t)) = w_{idst} F_{idst} (z_{i} (t),u_{i} (t)) + w_{itrj} F_{itrj} (z_{i} (t),u_{i} (t)) $$

(11)

$$ F_{idst} (z_{i} (t),u_{i} (t)) = \sum\limits_{{j \in {\mathcal{N}}_{i} }} {\left\| {p_{ij} (t) - p_{ij}^{d} (t)} \right\|^{2} } $$

(12)

$$ F_{itrj} (z_{i} (t),u_{i} (t)) = \left\| {p_{c} (t) - p_{c}^{d} (t)} \right\|^{2} $$

(13)

where $F_{idst}$ is the formation distance cost function of UAVs. $p_{ij}$ is the distance between UAV $i,j$, and $p_{ij}^{d}$ is the desired distance between UAV $i,j$. $F_{idst}$ is the cost function of tracking the reference trajectory. $p_{c} { = }{{\sum\limits_{i \in V} {p_{i} } } \mathord{\left/ {\vphantom {{\sum\limits_{i \in V} {p_{i} } } {N_{uav} }}} \right. \kern-\nulldelimiterspace} {N_{uav} }}$ is the center position of the formation. $p_{i}$ is the position of the drone, and $p_{c}^{d}$ is the desired position of the formation center. $w_{idst} ,w_{itrj}$ are the weight constants. The distributed cost function of UAV $i$ in $s \in [t_{c} ,t_{c} + T_{p} ]$ is

$$ \begin{gathered} F_{i} \left( {z_{i}^{p} (s;t_{c} ),\hat{z}_{ - i} (s;t_{c} ),u_{i}^{p} (s;t_{c} )} \right) \hfill \\ = w_{idst} \sum\limits_{{j \in {\mathcal{N}}_{i} }} {\left\| {p_{i}^{p} (s;t_{c} ) - \hat{p}_{j} (s;t_{c - 1} ) - p_{ij}^{d} (s;t_{c} )} \right\|^{2} } \hfill \\ + \,w_{itrj} \left\| {\frac{1}{{N_{uav} }}\left( {p_{i}^{p} (s;t_{c} ) + \sum\limits_{{j \in {\mathcal{N}}_{i} }} {\hat{p}_{j} (s;t_{c - 1} )} } \right) - p_{c}^{d} (s;t_{c} )} \right\|^{2} , \hfill \\ s \in [t_{c} ,t_{c} + T_{p} ] \hfill \\ \end{gathered} $$

(14)

where $p_{i}^{p} (s;t_{c} )$ is the predictive position of the UAV, and $\hat{p}_{j} (s;t_{c - 1} )$ is the estimated position of the UAV $j$. $p_{ij}^{d} (s;t_{c} )$ represents the desired distance between the UAV $i$ and $j$,and $p_{c}^{d} (s;t_{c} )$ is the desired position of the formation center, determined by the reference trajectory.

Trigger Mechanism

In order to reduce the burden of calculation, a trigger mechanism is introduced. The control inputs are solved and updated when the trigger condition is met. The mechanism of triggering the solution and update is mainly determined by the error of formation distance, the error of trajectory tracking, control input and prediction horizon.

$$ \, \Delta p_{ij} (t_{c} ){ = }\left\| {p_{i}^{p} (t_{c} ) - \hat{p}_{j} (t_{c - 1} ) - p_{ij}^{d} (t_{c} )} \right\| - \varepsilon_{p} , \, j \in {\mathcal{N}}_{i} $$

(15)

$$ \Delta p_{O} (t) = \left\| {\frac{1}{N}\left( {p_{i}^{p} (t) + \sum\limits_{{j \in {\mathcal{N}}_{i} }} {\hat{p}_{j} (t)} } \right) - p_{c}^{d} (t)} \right\| - \varepsilon_{O} $$

(16)

$$ \Delta u_{i} (t_{c} ) = u_{i}^{p} (t_{c} ) - \eta u_{\max } , \, u_{\max } = \left[ {a_{\max } ,\omega_{\max } } \right]^{T} $$

(17)

$$ \Delta T_{i} (t_{c} ) = t_{c} - (t_{trg}^{i} + T_{p} ) $$

(18)

where $\varepsilon_{p}$ is the threshold of predictive formation distance error, and $\varepsilon_{O}$ is the threshold of formation tracking error. $u_{\max } = \left[ {a_{\max } ,\omega_{\max } } \right]^{T}$ is the limitation of the control input. $u_{i}^{p} (t_{c} )$ is the predictive control input of the UAV $i$, and the range of $\eta$ is from 0 to 1. $t_{trg}^{i}$ is the last update instant of the UAV $i$. $\Delta p_{ij} (t_{c} )$ is the difference between the formation distance error and the corresponding threshold. $\Delta p_{O} (t)$ is the difference between the trajectory tracking error and the corresponding threshold. $\Delta u_{i} (t_{c} )$ is the difference between the control input and the corresponding threshold. $\Delta T_{i} (t_{c} )$ is the difference between $t_{c}$ and the prediction horizon $t_{trg}^{i} + T_{p}$ at the last update instant $t_{trg}^{i}$. The update condition can be described as

$$ \left. { \, \Delta p_{ij} (t_{c} ) \ge 0} \right\|\left. {\Delta p_{O} (t) \ge 0} \right\|\left. {\Delta u_{i} (t_{c} ) \ge 0} \right\|\Delta T_{i} (t_{c} ) \ge 0 $$

(19)

When the condition is met, the solution is updated. otherwise the last optimal control input is used. The flow chart of modified BSO based distributed MPC method is shown in Fig. 2.

Fig. 2.

The framework of modified BSO based distributed MPC method

3 Numerical Simulations

In this section, numerical simulations are used to verify the performance of the designed method. The formation control of three UAVs are considered in the simulation scenario. The initial states of UAVs are shown in Table 1.

Table 1. Initial states of UAVs

The prediction horizon is set as $T_{p} = 4\,{\text{s}}$, and the update period is $\delta_{T} = 0.2\,{\text{s}}$. The acceleration range is $[ - 7\,{{\text{m}} \mathord{\left/ {\vphantom {{\text{m}} {{\text{s}}^{2} }}} \right. \kern-\nulldelimiterspace} {{\text{s}}^{2} }}, + 7\,{{\text{m}} \mathord{\left/ {\vphantom {{\text{m}} {{\text{s}}^{2} }}} \right. \kern-\nulldelimiterspace} {{\text{s}}^{2} }}]$, and the angular velocity range is $[ - 0.25\,{{{\text{rad}}} \mathord{\left/ {\vphantom {{{\text{rad}}} {\text{s}}}} \right. \kern-\nulldelimiterspace} {\text{s}}}, + 0.25\,{{{\text{rad}}} \mathord{\left/ {\vphantom {{{\text{rad}}} {\text{s}}}} \right. \kern-\nulldelimiterspace} {\text{s}}}]$. The desired formation shape is an isosceles right triangle and the length of its hypotenuse is $20\,{\text{m}}$.

The numerical simulation is carried out without trigger mechanism. The trajectory of formation is shown in Fig. 3. It can be seen that the UAV can form the desired formation, and the formation center can track the reference trajectory. The states of each UAV and the distances of formation are shown in Fig. 4. As the formation is formed, the velocity and yaw angle of each UAV gradually converge, and the acceleration and angular velocity also tend to be the same. The formation center moves to the reference trajectory quickly in the early stage. The trajectory tracking error is greatly reduced, and then fluctuated around 0. The maximum error is within 1.25 m. After the formation is formed, the distance $d_{31}$ between UAV 1 and UAV 3 is kept near 20 m, and the distance $d_{12} ,d_{23}$ are kept near 14.14 m. These errors are within 0.2 m.

Fig. 3.

The trajectory of formation

Fig. 4.

States and distances of formation

The numerical simulation is carried out with trigger mechanism, and the thresholds are set as $\varepsilon_{p} = 2\;{\text{m}},\;\varepsilon_{O} = 2\;{\text{m}},\;\eta = 1$. The trajectory of formation with trigger mechanism is shown in Fig. 5. It can be seen that the UAV can form the desired formation, and the formation center can track the reference trajectory. The states of each UAV and the distances of formation with trigger mechanism are shown in Fig. 6. As the formation is formed, the velocity and yaw angle of each UAV gradually converge, and the acceleration and angular velocity also tend to be the same. The formation center moves to the reference trajectory quickly in the early stage. The trajectory tracking error is greatly reduced, and then fluctuated around 0. The maximum error is within 1.4 m. After the formation is formed, the distance is kept near 20 m, and the error is within 0.25 m. The distance $d_{12} ,d_{23}$ are kept near 14.14 m. These errors are within 0.3 m. The trigger instants of each UAV are shown in Fig. 7. It can be seen that the control inputs of each UAV is solved asynchronously. When the formation shape has not been formed in the early stage, the control inputs are solved and updated frequently, and then the numbers of triggering times are reduced. There are 240 update instants, and UAV 1, UAV 2 and UAV 3 trigger 157, 155 and 160 rimes respectively, reducing the number of solving the control problem by more than 33.3%, which lessens the computational burden.

Fig. 5.

The trajectory of formation with trigger mechanism

Fig. 6.

The states of each UAV and the distances of formation with trigger mechanism

Fig. 7.

The trigger instants of each UAV

4 Conclusions

This paper proposes a modified BSO algorithm, which introduces the chaos theory to the replacement mechanism of the solution and considers all cluster centers in the update mechanism of the solution. Based on the distributed MPC, the cost function and trigger mechanism are designed, and the proposed algorithm is used to solve the control inputs of each UAV, forming a distributed MPC method based on the modified BSO. The cost function and trigger mechanism are designed, and the proposed method is used to solve the control problem of UAV formation. Numerical simulation results show the feasibility and effectiveness of the method. The designed trigger mechanism reduces the number of update times to less than two-thirds, and reduces the amount of calculation. Further research will improve the trigger mechanism and carry out simulation analysis on control problems of distributed heterogeneous UAVs.