Cooperative Task Planning Of Multiple Unmanned Aerial Vehicles

Unmanned Aerial vehicles (UAVs) have been fastly developed and widely utilized formilitary applications for decades and attact more and more interest from the public. Inrecent years, as some emerging technology giants participating the UAV game, it is nodoubt that the UAV civilian market will rapidly rise. In order to exploit the operatingmechanisms of UAVs, the task assignment problem of multiple UAVs, concerned with thecooperative decition making and control, has been an emerging issue. Cooperation ofmultiple UAVs as a team to autonomously accomplish missions will enable new operationalparadigms and get higher team performance.However, for the complexity originated from the problem size, UAV performance,mission requirements, uncertainty, imperfect information, computation complexity, etc., theassignment problem is very complicated and extremely challenging.This thesis studies the cooperative task assignment problem of multiple heterogeneousUAVs, which involves UAVs with varieties of kinematic and functional characteristics, andlimited onboad munitions. Three concecutive tasks, including classify, attack and verify, aredemanded to be performed on ground stationary targets. The mathematical tools of graphtheory and combinatorial optimization are used to describe the problem.(1) With the centralized control scheme, the assignment problem is represented as acombinatorial optimization problem, considering the constraints of the heterogeneity ofUAV group and the resource limitation. In order to manage the complexity, a form ofgenetic algorithm (GA) modified with multi-type genes is presented. Genes ofchromosomes are different. They are assorted into several types according to the task thatmust be performed on targets. Different types of genes are processed specifically in theimproved genetic operators including initialization, crossover and mutation. Hence,Feasible chromosomes that vehicles could perform tasks using their limited resources underthe assignment of are created and evolved by genetic operators throughout the whole GAprocess. Finally, a good feasible solution is found.(2) Based on the contract net protocol, a real-time distributed control scheme for thecooperative search and prosecute mission of multiple UAVs is developed. We offer amathematical definition of the local task assignment problem that indeed is the markettrading, and present a decision architecture for distributed decisional nodes as well.Moreover, as tasks being assigned and performed, the workload would not be equal amongthe UAVs. Some of them would work hard, while others would appear to be leisure. That will degrade the system performance. In order to relatively equel the workload amongUAVs, a new reverse contract protocol is presented. Leisure UAVs that have no tasks toproceed will auction their working capability, and buy a new task from other UAVs that donot finish their task sequence yet. And the priority of reverse trading process must be lowerthan the normal one’s, which is called the obverse contract protocol. That means, thereverse trading cannot triggered while any obverse one is announced or in process. With thedouble contract net protocols, the performance of distributed system is obviously improved.(3) Based on the hierarchical cooperative control, the method of UAV coalitionformation is used to solve the market trading of the distributed system. Since twoconsecutive tasks including attack task and verify task are requested to be performed ontargets, and attacking a target might need to decompose the attack task into severalsimultaneous sub-tasks for the munition demand of a target might cannot be satisfied byone vehicle, more than one vehicles may need to be designated to prosecute the target.These UAVs that have a common goal form a temporary sub-team, i.e., coalition. They arecoupled to each other. We use this coalition method to manage the coupling tasks andpresent a procedure to form a suitable UAV coalition. The simulation results validate theeffectiveness.(4) In order to solve the deadlock problem in the consecutive task assignment problem,we present an integrated approach. A combinatorial optimization model is established, ofwhich the non-deadlock condition is specifically analyzed. And a task precedence graph(TPG) and its subgraphs, TESG and TCSG, of solutions are constructed and analyzed fordetecting deadlocks. It is found that the TPG of deadlockd solutions must have non-emptystrongly connected components. Thus a method of transposing operations is posed tounlock solutions involved in deadlocks. In addition, the topological sort of tasks is used inthe path coordinting of vehicles. Finally, deadlock free solutions are obtained and theprocess of path coordination is optimized.