# Boolean Networks-Based Auction Algorithm for Task Assignment of Multiple UAVs

Authors: Xiaolei Sun; Naiming Qi; Weiran Yao
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

This paper presents an application of Boolean networks-based auction algorithm (BNAA) for task assignment in unmanned aerial vehicles (UAVs) systems. Under reasonable assumptions, the assignment framework consists of mission control system, communication network, and ground control station. As the improved algorithm of consensus-based bundle algorithm (CBBA), the BNAA utilizes a cluster-based combinatorial auction policy to handle multiple tasks. Instead of empirical method based on look-up table about conditional variables, Boolean network is introduced into consensus routine of BNAA for solving the conflict of assignment across the fleet of UAVs. As a new mathematic theory, semitensor product provides the implementation and theoretical proof of Boolean networks. Numerical results demonstrate the effectiveness and efficiency of proposed BNAA method.


---

## Body

## 1. Introduction

In the last decade, the unmanned aerial vehicles (UAVs) are developed into collaborative applications [1], such as search and destroy mission, persistent surveillance, border or perimeter patrol [2], and tracking and rescue mission [3]. These demanding applications call for an increasing level of autonomy for each one of the UAVs fleet, which must adapt to changes in situational awareness at real time [4]. As the number of UAVs and missions grows, the task assignment (TA) algorithms are considered to be NP-hard problem [5]. In recent works, this challenging problem is solved by many approaches, which include three main types of TA algorithms: centralized, decentralized, and auction algorithms [6].Using central planner to communicate the central server that produces the plan for the fleet, centralized algorithm tends to yield a better solution than other approaches. However, in this architecture each UAV must consistently communicate with a fixed station, which greatly limits the scope of tasks that the fleet can execute. Moreover, in the mission, the centralized algorithm is subject to a single point failure [7]. Some decentralized approaches [8, 9] are proposed to eliminate above disadvantages. In order to achieve a conflict-free assignment, each UAV of the fleet must perform the same functionality as the central planner of centralized algorithm. For sharing the information of TA, it is generally assumed that the decentralized methods have the infinite bandwidth of communication. Thus, this approach may lead to an inefficient situation, where the member of the fleet will transfer a number of unnecessary data to each other. If that is not the case, although it can improve this inefficiency by introducing the consensus algorithm, decentralized approaches often require severe latency time to communicate [10]. More recently, auction algorithms based on market mechanism for TA are developed. It is effective for producing near-optimal solutions. After providing bids for match tasks, the UAV with highest value obtains corresponding assignment. To receive these bids and determine the highest value list, the traditional auction method utilizes an auctioneer as the central auction system [11]. Thus, these types of methods suffer the limitations of network topology since the UAV must communicate with the auctioneer for bid on the assignment. Even if the improved method removes the central system, it has been demonstrated that this method still has communication problems.As an improved auction algorithm, the consensus-based bundle algorithm (CBBA) is developed by combining the bundle method with the consensus approach. Many extended algorithms of CBBA demonstrate its advantage in TA field [6, 12–15]. According to the main components, there are two phases of CBBA. The bundle phase is utilized to the situation, where UAV will bid on multiple tasks for the improvement of the assignment efficiency. In addition, the consensus phase is addressed to solve the conflict of assignment between the UAVs. The consensus algorithm of CBBA achieves by look-up table approach. It is essentially empirical method, although the original and extended CBBA methods can achieve the convergence to conflict-free assignment [14–16]. This manner cannot reveal the logical relation between the information vectors and decision actions.Considering the efficiency of the computation and communication, this paper presents a Boolean networks-based auction algorithm (BNAA). As similar structure of CBBA, there are two phases for BNAA: combinatorial auction and Boolean networks-based consensus. In the first phase, the cluster method is utilized to assign the task combination with higher value first. Under this policy, the UAV tends to carry out the tasks in the same area instead of single task with lower value outside this area. As the first phase has dealt with the combinatorial assignment, the second phase of BNAA is in charge to handle the conflicts of assignment. In this process, the Boolean networks method is introduced to model the consensus algorithm of look-up table about conditional variables. As a new way to realize the TA, Boolean networks can transfer conditional statements to mathematical theory based on new matrix product, namely, semitensor product [17]. Then, the Boolean network can be converted into an algebraic function, which is described via transition matrix [18]. Therefore, the consensus becomes the process of identification to the related matrices. In the framework of semitensor product approach, the realization, controllability, observability, and disturbance decoupling of Boolean networks are also investigated in many papers [19–22].The rest of this paper is organized as follows. Section2 gives some preliminaries. Section 3 formulates the problem of TA for UAVs and provides the architecture of proposed method. In Section 4, the BNAA is discussed in detail. In Section 5, general scenarios present the performance of the BNAA through simulations results and Section 6 follows by some concluding remarks.


## 2. Preliminaries: Semitensor Product

As a new matrix product tool, semitensor product can convert a logical relation into an algebraic expression. By using this tool, the logical dynamics of a Boolean network can be transformed into discrete-time systems [22].Definition 1.
There areAm×n and Bw×v, where z=Mul(n,w) denotes the least common multiple of n and w. Then the semitensor product of A with B is defined as(1)A⋉B≔A⊗Iz/nB⊗Iz/w,where “⊗” is the Kronecker product. If z=1, then the semitensor product is the regular product of matrix. Thus, “⋉” will be omitted in this paper.First, we introduce some notations [19].(i)
φ:Λn→Λk,Λ={0,1} is called logical function.(ii)
δnk denotes the kth column of the identity matrix In. Particularly, δ0=0,1T, δ1=1,0T.(iii)
Δn={δnk∣k=1,2,…,n},Δ=Δ2.(iv)
IfM=δmk1δmk2⋯δmkp, then M is called a m×p logical matrix. It is briefly denoted as(2)M=δmk1k2⋯kp.Particularly, if m=2, then ki∈Λ, i=1,…,p. The binary number can be converted into a hexadecimal number as follows:(3)M=δk1k2⋯kp=δκ1κ2⋯κphex.To utilize the matrix expression, we identify0~δ0 and 1~δ1. Then the logical variable ak=ak,1-akT∈Δ will be called vector-logical variable. The logical function φ:Λn→Λk can be converted into a mapping φ:Δ2n→Δ2k. There is an important theorem, which is given by Theorem 11 in [20].Theorem 2.
Letf(a1,…,an):Λn→Λk be a logical function, which is converted into vector-logical form f:Δ2n→Δ2k. Then there is a unique 2k×2n logical matrix Mf, which is called the structure matrix of f(a1,…,an), such that(4)fa1,…,an=Mf⋉a=Mf⋉k=1nak,ak∈Δ.


## 3. Task Assignment: Problem Statement

### 3.1. Task Assignment Architecture

In order to illustrate the function of TA, the integrated UAVs system is shown in Figure1. The assignment architecture of UAVs addresses an integrated cooperating platform with the ability to perform the task assignment adhering to a mission control systems (MCS), for running collaborative and assignment algorithm. In this architecture, ground control station (GCS) is in charge of sending the instructions about taking-off and landing, loading the initial information about the mission and receiving the data from the sensors of UAVs. Each UAV’s MCS runs assignment algorithm and achieves the consensus of TA through the wireless communication network.Figure 1
Task assignment architecture of UAVs.


### 3.2. Task Assignment Scenario

Figure2 illustrates the scenario of K tasks assignment for N UAVs. Let N={1,…,N} and K={1,…,K} be defined as the index sets for the UAVs and tasks, respectively. In this case, UAVn,n∈N represents the nth UAV and Taskk, k∈K the kth task. The general consideration is that one task is assigned to no more than one UAV, that is, conflict-free assignment. The global objective function [6] of TA is given by(5)max⁡∑n=1N∑k=1KRnk·hnk,s.t.∑k=1Khnk≤Nn,∀n∈N,∑n=1Nhnk≤1,∀k∈K,hnk∈0,1,∀n,k∈N×K,where score Rnk is obtained by UAVn after receiving the assignment of Taskk. hnk∈{0,1} indicates if UAVn is assigned to Taskk; Nn is maximum number of tasks that UAVn can take; and hn=hn1,…,hnK represents a vector of assignment for UAVn. The solution of the TA depends heavily on the high accuracy model of score function. In the BNAA method, score function Rnk consists of a task reward Jk and executing cost Fnk [1]. Rnk is expressed as(6)Rnk=ΘnkJk-Fnk,Jk=gk·e-εk·t,Fnk=ωn·t,where t is execution time; gk denotes a static score of Taskk; εk and ωn are weighting factor. Θnk=βn·ηnk·ξk·ζk is constraint factor, which is defined as(7)βn=1,Drn≥Dn,0,otherwise,ηnk=1,UAVncan  carry  outTaskk,0,otherwise,ξk=1,ck≤t≤dk,0,otherwise,ζk=1,t+τk≤dk,0,otherwise,where βn denotes constraint of fuel level that can be provided to perform the rest distance Dr(n), which must be greater than remaining distance of flight path Dn; ηnk is the constraint about suitability of UAVn to Taskk; ξk denotes the constraint of the execution time, where ck and dk describe the start time and end time of Taskk, respectively; ζk represents the validity of Taskk, where τk is the duration in which the task must be performed.Figure 2
Task assignment scenario of UAVs.


## 3.1. Task Assignment Architecture

In order to illustrate the function of TA, the integrated UAVs system is shown in Figure1. The assignment architecture of UAVs addresses an integrated cooperating platform with the ability to perform the task assignment adhering to a mission control systems (MCS), for running collaborative and assignment algorithm. In this architecture, ground control station (GCS) is in charge of sending the instructions about taking-off and landing, loading the initial information about the mission and receiving the data from the sensors of UAVs. Each UAV’s MCS runs assignment algorithm and achieves the consensus of TA through the wireless communication network.Figure 1
Task assignment architecture of UAVs.


## 3.2. Task Assignment Scenario

Figure2 illustrates the scenario of K tasks assignment for N UAVs. Let N={1,…,N} and K={1,…,K} be defined as the index sets for the UAVs and tasks, respectively. In this case, UAVn,n∈N represents the nth UAV and Taskk, k∈K the kth task. The general consideration is that one task is assigned to no more than one UAV, that is, conflict-free assignment. The global objective function [6] of TA is given by(5)max⁡∑n=1N∑k=1KRnk·hnk,s.t.∑k=1Khnk≤Nn,∀n∈N,∑n=1Nhnk≤1,∀k∈K,hnk∈0,1,∀n,k∈N×K,where score Rnk is obtained by UAVn after receiving the assignment of Taskk. hnk∈{0,1} indicates if UAVn is assigned to Taskk; Nn is maximum number of tasks that UAVn can take; and hn=hn1,…,hnK represents a vector of assignment for UAVn. The solution of the TA depends heavily on the high accuracy model of score function. In the BNAA method, score function Rnk consists of a task reward Jk and executing cost Fnk [1]. Rnk is expressed as(6)Rnk=ΘnkJk-Fnk,Jk=gk·e-εk·t,Fnk=ωn·t,where t is execution time; gk denotes a static score of Taskk; εk and ωn are weighting factor. Θnk=βn·ηnk·ξk·ζk is constraint factor, which is defined as(7)βn=1,Drn≥Dn,0,otherwise,ηnk=1,UAVncan  carry  outTaskk,0,otherwise,ξk=1,ck≤t≤dk,0,otherwise,ζk=1,t+τk≤dk,0,otherwise,where βn denotes constraint of fuel level that can be provided to perform the rest distance Dr(n), which must be greater than remaining distance of flight path Dn; ηnk is the constraint about suitability of UAVn to Taskk; ξk denotes the constraint of the execution time, where ck and dk describe the start time and end time of Taskk, respectively; ζk represents the validity of Taskk, where τk is the duration in which the task must be performed.Figure 2
Task assignment scenario of UAVs.


## 4. BNAA for Task Assignment

The BNAA method is developed to assignment, in which each UAV will bid on a sequence of multiple tasks by introducing the combinatorial auction algorithm. The Boolean networks-based consensus algorithm is applied for dealing with the conflict of TA in the fleet. Each UAV stores its own information and updates it in continuous loops with these two phases. There are some vectors of information thatUAVn must carry in the BNAA method [13]:(1)
A matrix of tasks informationT={T1,…,TK} with vector Tk=gk,εk,ck,dk,τkT,k∈K, in which all elements belong to [0,∞).(2)
A highest bid listHn={Hn1,…,HnK}, where each element Hnk∈[0,∞) represents the highest bid on Taskk according to the information of UAVn.(3)
A creation time list of highest bidbn={bn1,…,bnK}, where bnk∈[0,∞) is the corresponding creation time of the element in Hn.(4)
A winner listWn={Wn1,…,WnK}, in which element Wnk∈{N∪⌀} is the index of the UAV that wins Taskk according to the information of UAVn.(5)
A combinatorial tasks listZn={Zn1,…,Zn,N(n)}, where Zni∈K for i∈{1,…,N(n)}, N(n)≤Nn represents the number of multiple tasks that UAVn has won. The elements of Zn are ordered according to the adding time of the tasks.(6)
An execution sequence listLn={Ln1,…,Ln,N(n)}, where Lni∈K indicates the order UAVn will perform the task in its combinatorial tasks list, which has the same tasks as Zn.(7)
A time list of executionsn={sn1,…,sn,N(n)}, in which sni∈K is the corresponding time when UAVn will perform the task in Ln.


### 4.1. Combinatorial Auction

As shown in Figure3, combinatorial auction process of BNAA is performed by using cluster algorithm [23], where all tasks are taken into account at each time step. Thus, the task combination with higher score has the priority to be assigned. The cluster algorithm has the following steps.Figure 3
Combinatorial auction process of BNAA.(1) Computation of Distance between Classes. As each task is a class and assuming Dk, k∈K denotes the kth class, and the distance matrix between classes is given by(8)P0=0p210⋮⋮⋱pK1pK2⋯0K×K,where pij represents the distance between Taski and Taskj.(2) Modification of Task Score Function. Given upper limit pmax⁡ of the distance, if the minimum element in P0 besides 0 is pij≤pmax⁡, Di and Dj are merged into a single class. For UAVn, the score of Taski is thereby modified as(9)Rni′t=Rnit+γRnjt+pijV,where γ is weighting factor.(3) Update of Distance Matrix. According to modified information, the matrix is updated to P(1). Steps (1) to (3) are repeated until pij>pmax⁡.The local objective function [6] of UAVn is defined as(10)VnLn=∑k=1KRnk′·hnk,which represents the sum of the rewards that UAVn received by performing the tasks along Ln. The marginal score function about combinatorial tasks Zn [13], that is, the improvement of the objective function when Taskk is added, is given by(11)rnkZn=maxi≤Nn⁡VnLn′-VnLn,k∉Zn,0,k∈Zn,where Ln′=Ln⨄i{k}, the symbol ⨄i is the operator that provides new set {k} after the ith element of the Ln, and ⨄end indicates to add the elements at the end of first list. Zn and Ln update as the following equation:(12)Zn=Zn⨄end⁡k∗,Ln=Ln⨄i∗⁡k∗,where(13)k∗=arg⁡maxk⁡rnkZn·lnk,i∗=arg⁡maxi⁡VnLn′,where lnk=1 if rnk>Hnk and 0 otherwise.


### 4.2. Boolean Networks-Based Consensus

The consensus algorithm of look-up table about conditional variables is an effective approach to perform the consistent TA, however, this algorithm is an empirical method, which is hard to demonstrate by theoretical proof. In this work, the conditional variables are transferred to Boolean logic variables, which are the elements of the Boolean network. Using the semitensor product theory, the Boolean network can be converted into an algebraic function.The BNAA consensus is shown in Table1, which lists the decision rules of UAVn according to received information from UAVm. There are three actions the UAV can choose from:(1)
Update: The UAVn updates its information about highest bid list Hn and winner list Wn.(2)
Reset: The UAVn will reset its Hnk=0 and Wnk=⌀.(3)
Drop (default action): When UAVn receives the useless data its information will remain the same.Table 1
BNAA decision rules.
W
m
k of the sender UAVm
W
n
k of the receiver UAVn
Decision condition
Action
b
m
k
>
b
n
k
H
m
k
>
H
n
k
m
n
√
Update
m or ⌀
Update
i
∉
n
,
m
√
Update
n
n or ⌀
Drop
m
Reset
i
∉
n
,
m
Drop
i
∉
n
,
m
n
√
Update
m or ⌀
Update
j
∉
n
,
m
,
i
√
√
Update
⌀
n or ⌀
Drop
m
Reset
i
∉
n
,
m
DropThe Boolean network is the core of the consensus algorithm for BNAA. As shown in Table2, after the conversion of the conditional variables into logical relation, the Boolean network that can be controlled and analyzed by semitensor product approach is established. According to its own information {Wnk,bnk,Hnk} and received information {Wmk,bmk,Hmk} from UAVm about Taskk, UAVn chooses one action from the decision set {Update,Reset,Drop}. The conversion process of variables is shown in Figure 4.Table 2
The conversion of the conditional variables into logical relation.
(a)
S
1
S
2
W
n
k
1
1
m
1
0
n
0
0
⌀
0
1
Otherwise
(b)
S
1
′
S
1
′
W
m
k
1
1
m
1
0
n
0
0
⌀
0
1
Otherwise
(c)
S
b
Condition
1
b
m
k
>
b
n
k
0
Otherwise
(d)
S
H
Condition
1
H
m
k
>
H
n
k
0
Otherwise
(e)
Q
U
Action
1
Update
0
Otherwise
(f)
Q
D
Action
1
Drop
0
Otherwise
(g)
Q
R
Action
1
Reset
0
OtherwiseFigure 4
Conversion process of variables.The dynamics of a Boolean control network is expressed as follows [22]:(14)x1t+1=φ1x1t,…,xwt,u1t,…,uvt,x2t+1=φ2x1t,…,xwt,u1t,…,uvt,⋮xwt+1=φwx1t,…,xwt,u1t,…,uvt,yjt=fjx1t,…,xwt,u1t,…,uvt,j=1,…,p,where xi(t)∈Λ denotes logical variables; φi, i=1,…,w and fj, j=1,…,p are the logical functions; uq(t)∈Λ, q=1,…,v means the controls; yj(t)∈Λ indicates the outputs.A Boolean network can be briefly defined by the five-tuple as(15)Ω=x,y,u,φ,f,where x∈R2wdenotes the state variable vector, y∈R2p is the output vector, u∈R2v denotes the control input vector, φ:x×u→x is the state transition logical function, and f:x×u→y is the output logical function. The dynamics of Boolean network can be formulated as(16)xt+1=φxt,ut,yt=fxt,ut.By the argument as for Theorem2, if x=⋉q=1wxq, u=⋉q=1vuq, and y=⋉q=1pyq, then these equations can be converted into the vector-logical expression, which is given by(17)xt+1=Mφutxt,yt=Mfutxt.According to the logical relation of the variables in this work, the vector variables can be described as follows:(18)u1t=S1′,1-S1′T,u2t=S2′,1-S2′T,u3t=Sb,1-SbT,u4t=SH,1-SHT,x1t=S1,1-S1T,x2t=S2,1-S2T,yt=QU,1-QU,QD,1-QD,QR,1-QRT.Solving (17), the structure matrixes can be received as(19)Mφ=F9F9000000000000040444440404444402022222FBFB22220000999900009999hex,Mf=δF9F90000F9D90000hexδ0606777706267777hexδ0000888800008888hex.In many decision systems, the conditional statements can get very complicated, which makes the algorithm difficult to achieve and maintain. On the other hand, the consensus algorithm based on Boolean network by semitensor product theory has important theoretical significance.


## 4.1. Combinatorial Auction

As shown in Figure3, combinatorial auction process of BNAA is performed by using cluster algorithm [23], where all tasks are taken into account at each time step. Thus, the task combination with higher score has the priority to be assigned. The cluster algorithm has the following steps.Figure 3
Combinatorial auction process of BNAA.(1) Computation of Distance between Classes. As each task is a class and assuming Dk, k∈K denotes the kth class, and the distance matrix between classes is given by(8)P0=0p210⋮⋮⋱pK1pK2⋯0K×K,where pij represents the distance between Taski and Taskj.(2) Modification of Task Score Function. Given upper limit pmax⁡ of the distance, if the minimum element in P0 besides 0 is pij≤pmax⁡, Di and Dj are merged into a single class. For UAVn, the score of Taski is thereby modified as(9)Rni′t=Rnit+γRnjt+pijV,where γ is weighting factor.(3) Update of Distance Matrix. According to modified information, the matrix is updated to P(1). Steps (1) to (3) are repeated until pij>pmax⁡.The local objective function [6] of UAVn is defined as(10)VnLn=∑k=1KRnk′·hnk,which represents the sum of the rewards that UAVn received by performing the tasks along Ln. The marginal score function about combinatorial tasks Zn [13], that is, the improvement of the objective function when Taskk is added, is given by(11)rnkZn=maxi≤Nn⁡VnLn′-VnLn,k∉Zn,0,k∈Zn,where Ln′=Ln⨄i{k}, the symbol ⨄i is the operator that provides new set {k} after the ith element of the Ln, and ⨄end indicates to add the elements at the end of first list. Zn and Ln update as the following equation:(12)Zn=Zn⨄end⁡k∗,Ln=Ln⨄i∗⁡k∗,where(13)k∗=arg⁡maxk⁡rnkZn·lnk,i∗=arg⁡maxi⁡VnLn′,where lnk=1 if rnk>Hnk and 0 otherwise.


## 4.2. Boolean Networks-Based Consensus

The consensus algorithm of look-up table about conditional variables is an effective approach to perform the consistent TA, however, this algorithm is an empirical method, which is hard to demonstrate by theoretical proof. In this work, the conditional variables are transferred to Boolean logic variables, which are the elements of the Boolean network. Using the semitensor product theory, the Boolean network can be converted into an algebraic function.The BNAA consensus is shown in Table1, which lists the decision rules of UAVn according to received information from UAVm. There are three actions the UAV can choose from:(1)
Update: The UAVn updates its information about highest bid list Hn and winner list Wn.(2)
Reset: The UAVn will reset its Hnk=0 and Wnk=⌀.(3)
Drop (default action): When UAVn receives the useless data its information will remain the same.Table 1
BNAA decision rules.
W
m
k of the sender UAVm
W
n
k of the receiver UAVn
Decision condition
Action
b
m
k
>
b
n
k
H
m
k
>
H
n
k
m
n
√
Update
m or ⌀
Update
i
∉
n
,
m
√
Update
n
n or ⌀
Drop
m
Reset
i
∉
n
,
m
Drop
i
∉
n
,
m
n
√
Update
m or ⌀
Update
j
∉
n
,
m
,
i
√
√
Update
⌀
n or ⌀
Drop
m
Reset
i
∉
n
,
m
DropThe Boolean network is the core of the consensus algorithm for BNAA. As shown in Table2, after the conversion of the conditional variables into logical relation, the Boolean network that can be controlled and analyzed by semitensor product approach is established. According to its own information {Wnk,bnk,Hnk} and received information {Wmk,bmk,Hmk} from UAVm about Taskk, UAVn chooses one action from the decision set {Update,Reset,Drop}. The conversion process of variables is shown in Figure 4.Table 2
The conversion of the conditional variables into logical relation.
(a)
S
1
S
2
W
n
k
1
1
m
1
0
n
0
0
⌀
0
1
Otherwise
(b)
S
1
′
S
1
′
W
m
k
1
1
m
1
0
n
0
0
⌀
0
1
Otherwise
(c)
S
b
Condition
1
b
m
k
>
b
n
k
0
Otherwise
(d)
S
H
Condition
1
H
m
k
>
H
n
k
0
Otherwise
(e)
Q
U
Action
1
Update
0
Otherwise
(f)
Q
D
Action
1
Drop
0
Otherwise
(g)
Q
R
Action
1
Reset
0
OtherwiseFigure 4
Conversion process of variables.The dynamics of a Boolean control network is expressed as follows [22]:(14)x1t+1=φ1x1t,…,xwt,u1t,…,uvt,x2t+1=φ2x1t,…,xwt,u1t,…,uvt,⋮xwt+1=φwx1t,…,xwt,u1t,…,uvt,yjt=fjx1t,…,xwt,u1t,…,uvt,j=1,…,p,where xi(t)∈Λ denotes logical variables; φi, i=1,…,w and fj, j=1,…,p are the logical functions; uq(t)∈Λ, q=1,…,v means the controls; yj(t)∈Λ indicates the outputs.A Boolean network can be briefly defined by the five-tuple as(15)Ω=x,y,u,φ,f,where x∈R2wdenotes the state variable vector, y∈R2p is the output vector, u∈R2v denotes the control input vector, φ:x×u→x is the state transition logical function, and f:x×u→y is the output logical function. The dynamics of Boolean network can be formulated as(16)xt+1=φxt,ut,yt=fxt,ut.By the argument as for Theorem2, if x=⋉q=1wxq, u=⋉q=1vuq, and y=⋉q=1pyq, then these equations can be converted into the vector-logical expression, which is given by(17)xt+1=Mφutxt,yt=Mfutxt.According to the logical relation of the variables in this work, the vector variables can be described as follows:(18)u1t=S1′,1-S1′T,u2t=S2′,1-S2′T,u3t=Sb,1-SbT,u4t=SH,1-SHT,x1t=S1,1-S1T,x2t=S2,1-S2T,yt=QU,1-QU,QD,1-QD,QR,1-QRT.Solving (17), the structure matrixes can be received as(19)Mφ=F9F9000000000000040444440404444402022222FBFB22220000999900009999hex,Mf=δF9F90000F9D90000hexδ0606777706267777hexδ0000888800008888hex.In many decision systems, the conditional statements can get very complicated, which makes the algorithm difficult to achieve and maintain. On the other hand, the consensus algorithm based on Boolean network by semitensor product theory has important theoretical significance.


## 5. Simulation

The CBBA and the extended algorithms have demonstrated its advantage in TA and achieved the convergence to conflict-free assignment [12–16]. In addition, the demonstration for mathematical features of Boolean network using semitensor product theory is addressed in many papers [17, 19–22]. Over the mathematical proof, this paper presents a typical scenario and simulation results.To verify the efficiency of proposed method, the simulation is tested in MATLAB environment on a PC with Intel Pentium Dual-Core CPU E5800 3.2 GHz and 4 GB RAM. In the 10 km × 10 km mission scenario, there are 5 UAVs to perform tasks. All UAVs fly at constant velocity of 200 m/s. Experiments are carried out by randomly setting the locations of tasks. Figure5 compares the performance of CBBA and BNAA. The x-axis shows the number of tasks, while the y-axis highlights the objective function of each method. The comparison result demonstrates that BNAA can achieve better assignment than CBBA does. Furthermore, Figure 6 gives a simulation result of BNAA in a specific scenario with 10 tasks.Figure 5
Comparison result of objective function between BNAA and CBBA.Figure 6
Simulation result with 5 UAVs and 10 tasks using BNAA.For a given 5 UAVs, the performance in terms of the time that one-step communication consumed in simulation by varying the number of tasks is shown in Figure7. Since the Boolean network only involves logical operations, the average time of a communication of BNAA is reduced by 23% compared to CBBA, which utilizes the look-up table to make decision.Figure 7
Average time taken to each communication of BNAA and CBBA.


## 6. Conclusion

This paper presents a new way to implement the consensus algorithm of TA for UAVs, which improves theoretical significance and practical value to the development of decision system based on conditional statements. The vector logical expression, transferred from Boolean network by semitensor product theory, is a connection between conditional statements and mathematical theory. The reason to extend our work based on CBBA is because it is the original algorithm of this series. To strengthen the theoretical effectiveness of consensus algorithm in TA, the BNAA begins with the typically valuable reference for broaching this subject.



---

*Source: 425356-2015-08-11.xml*