Distributed Algorithm Research For Multi-UAV Task Assignment Problem

Compared with a large multi-functional and expensive UAV,multiple heterogeneous cost-effective UAV have potential advantages in operational reliability and adaptability to complex environments.UAV in the cluster select reasonable task through optimization computation of task allocation,so as to maximize the benefits or minimize the costs of multi-UAV's task execution.Efficient and real-time task allocation is one of the most important means to ensure the maximum operational efficiency of multi-UAV.In recent years,distributed cooperative task assignment(without a central network node)has attracted much attention from academia and industry.However,most of the related researches are still stay in phase of theoretical analysis of algorithm convergence and digital simulation verification.In terms of performance verification,there is a lack of support from the semi-physical platform with the computing chip-loop.About these two aspects,this paper has carried on the following research.Firstly,the target model and constraint model of the assignment algorithm,as well as the solution method based on distributed auction algorithm are studied for the multi-UAV single-assignment problem.The convergence of the algorithm is analyzed,and the simulation verification and analysis are carried out.Aiming at the scenario that multiple UAVs are required to perform the same task together,the solution method based on Contract Network Protocol is studied.The core thought of this method is to locally execute the process of "bid inviting-bidding-winning" within the multiple UAVs,and the contract network protocol is simulated and analyzed.Aiming at the multi-assignment scenario,the solution flow based on Consensus-Based Bundle Algorithm is studied and simulated.The task list is dynamically stored by UAV.Information is exchanged between UAVs to adjust the current task list and avoid task conflict.This strategy ensure that the UAV can execute the next task immediately after the current task is done,and then local optimal assignment is realized.A low-cost distributed semi-physical experiment platform is designed and built.The platform consists of four TMS320C6748 DSP chips.The UART serial communication protocol is used for the data exchange between PC and development board.Low-cost XBee wireless communication module is used in real-time communication between development boards.Under the framework of this platform,the dynamic characteristics of the UAV are simulated on the computer.Wireless and wired communication protocols and distributed assignment algorithms run on the development board in real time.On the semi-physical simulation platform,the transplant and performance evaluation of distributed auction algorithm were carried out in the distribution problem settings including 6 targets 4 UAVs with the linear communication topological.Based on the measured data,the communication capability of the wireless module and the performance of the distributed auction algorithm are evaluated.