Research On Task Allocation Algorithms For Robots And Vehicles In Complex Environment

With the development of economy and society,people are facing more and more complex task allocation scenarios.Reasonable task allocation can improve work efficiency and reduce operating costs,so it plays an important role in the actual scenario.Based on practical application scenarios,this thesis studies two different kinds of complex task allocation problems.Firstly,the multi-robot cooperative task allocation problem without conflict is studied in this thesis.In practical application scenarios,task assignment and conflict-free path determination for robots are challenging.In this thesis,a special multi-robot task allocation problem is studied,which includes cooperative tasks that require two robots to work at the same time,and also consider the path conflict of robots in the process of moving.In this thesis,multi-graph model and grid network are used to study the multi-robots task allocation problem.VGTA(Vitality-driven genetic task-allocation algorithm)is designed to solve the problem.This algorithm includes several random mutation and greedy sear-ch operators.Vitality selection strategy is used to update the population of genetic algorithm.And it can deal with the path conflict problem.In this thesis,test sets are set up according to the actual environment,and VGTA is compared with MA(memetic algorithm),GVNS(general variable neighborhood search),IPGA(improved partheno genetic algorithms)and FA(fish swarm algorithm).Simulation results show VGTA can reduce calculation time about 50%on average while getting the best search results.Secondly,the task allocation of commodity distribution in urban time-varying road network is studied in this thesis.Commodity distribution task requires that vehicles should plan the order of picking up and delivering goods reasonably,so that the total driving time of all vehicles is minimum.In our commodity distribution model,the corresponding relationship between the pick-up warehouse and the receiving customer is considered,that is,the customer's goods are only stored in the designated warehouse,and the goods will arrive at different times in a day.In addition,this thesis also considers the impact of traffic congestion changes on vehicle speed when goods distribution vehicles travel in urban time-varying road network.This thesis uses the multi-graph model to model the problem,and add the time factor into the multi-graph model.This thesis designs DVNS(dynamic-neighbor-hood-pool variable neighbor-hood search)with dynamic neighborhood pool to solve the problem of commodity distribution.DVNS algorithm has a new neighborhood mutation method,and uses efficient local optimization algorithm and linear programming algorithm as local search algorithm.In addition,local search algorithm can also deal with time-varying congestion.This thesis uses Aliyun's Shanghai commodity distribution data as test set,and compares DVNS with HGA(hybrid genetic algorithm),GVNS(general variable neighborhood search)and VNS(variable neighborhood search).The results show that DVNS can reduce the total vehicle time consumption by about 25%on average while guaranteeing the best search results.In this thesis,two kinds of task allocation problems in complex situations are studied,and the particularities of each problem are discussed.It can provide some reference value for future research on task allocation.