| Multi-robot task allocation is a common problem in many fields such as warehousing logistics,Unmanned Aerial Vehicle(UAV)cooperative combat,disaster relief,etc,which aims at finding one or more task assignment sequences to guarantee the evaluation index or indexes optimal in multi-robot multi-task environment.In this thesis,In this paper,considering the multiple-robot task allocation problem in postdisaster rescue,reasonable and effective task allocation methods are proposed based on particle swarm optimization(PSO)method,so as to complete the rescue of as many trapped people as possible in a limited time It mainly includes the following three contents:(1)To solve the problem of static single type task allocation,a mathematical model is established and a group task allocation method based on PSO algorithm is proposed.In order to reduce the computational complexity of the task allocation algorithm and improve the rationality of the assignment strategy,based on the problem characteristics,the following strategies are presented: firstly,a reasonable task grouping method is designed according to the tasks' information and time constraint;secondly,the method of generating initial solution of PSO based on clustering is designed,and the inertia weight parameter ? in PSO is improved adaptively.Experimental results show that the proposed method can effectively reduce the computational complexity in the assignment process and improve the effectiveness of the task allocation method.(2)To solve the problem of multi-constraint and multi-type task assignment,a mathematical model is established and a matching degree task assignment method based on PSO algorithm is proposed.With the expansion of rescue scope and the increase complexity of rescue task,it is necessary to consider the diversity type as well as the resource load and energy consumption constraints of robots,the method proposed in content(1)is no longer suitable for solving this problem.In order to further improve the performance of the algorithm,firstly,a single-objective multi-constraint mathematical model is established with the aim of minimum task failure rate and minimum rescue time.Then,matching degree between robots and tasks is proposed based on the above constraints so as to describe the suitability that a task is assigned to a robot.Then,the matching degree is used to improve the particle decoding method and the updating formula,so as to avoid the infeasible solution caused by the constraint and improve the search efficiency of the algorithm.Experiments show that the proposed method can effectively solve many constraints and improve the performance of task allocation strategy.(3)To solve the problem of dynamic multi-type task allocation problem,the mathematical model and local task insertion method are proposed in this paper.The rescue environment after the disaster is complex and secondary disasters occur frequently,the failure rate of rescue robots increases,which leads to dynamic changes in the number of tasks and robots in the rescue process,the methods proposed in content(1)and(2)are no longer suitable for this scenario.Based on this,this thesis proposes a local task allocation method based on PSO algorithm to deal with the dynamic changes in the rescue environment in a timely manner.Firstly,the dynamic factors are analyzed and the task assignment scheme is adjusted accordingly.Secondly,the tasks and robots involved in the local task assignment are determined.The new tasks are inserted into the existing task assignment scheme according to certain strategies based on the particle swarm optimization method.Then,the matching degree between the new task and the robot is established,and the particle decode method based on the matching degree is designed to increase the probability of the particle searching in a better region.Experimental results show that the proposed method can effectively solve dynamic task assignment problem of the above-mentioned scenarios.The thesis includes 26 figures,16 tables and 90 references. |
PDF Full Text Request