Researches On Multi-Robot Cooperative Task Allocation For Search And Rescue Scenarios Under Dynamic Environments

With the development of national industrialization and intelligence,intelligent robots are widely used in various search and rescue,reconnaissance and strike scenarios,and daily surveil-lance areas with their high performance,high flexibility,re-usability,low cost,and causing no casualties in dangerous areas.As a vital part of robot systems,autonomous decision-making and cooperative task allocation have attracting many researchers to carry out researches on.Two of the most important types of tasks in post-disaster relief operations are search tasks and rescue tasks.Execution of these two types of tasks requires different types of resources,which are usually completed by different emergency teams.However,the allocation and exe-cution of rescue tasks depend on the execution of search tasks.First,the overall objective of search and rescue is to improve the rescue efficiency.The key is to carry out overall optimiza-tion of the allocation of these two types of tasks,which requires modeling the two according to the same goal,and designing a task allocation mode that can optimize the whole work.This article considers the scenario of multi-robot performing search and rescue missions after a disaster,and focuses on the mathematical modeling,architecture construction and algo-rithm design of task allocation problems involved.The main contributions are as follows:1)The mission mode of the post-disaster multi-robot search and rescue are analyzed.A mathematical model,a task allocation mode and a distributed architecture of multi-robot coop-erative search and rescue task allocation are presented.In view of the problem that most of the existing researches on multi-robot task allocation for search and rescue scenarios consider search tasks or rescue tasks separately.Analysis and modeling for the mulri-robot search and rescue task allocation problem are based on the goal of saving more survivors.Based on the analysis and modeling,a task allocation mode of multi-robot cooperative search and rescue operations is designed,which adopts a centralized multi-robot search task allocation method,a distributed online search task allocation method and a distributed online rescue task allocation method for search and rescue task allocation.Finally,according to the task allocation mode,an distributed architecture for multi-robot cooperative search and rescue task allocation is established.2)Research on centralized multi-robot search task allocation and proposed a new algorithm:the bi-ovjective multi-ACO based memetic algorithm.In view of the problems that most of the existing research on centralized multi-robot task allocation consider a single objective(total traveling distance or maximum traveling distance of robots),and most of the existing research on multi-objective optimization have low solu-tion efficiency due to high computational complexity.The proposed algorithm simplifies the multi-ACO algorithm to reduce its computational complexity? integrates a sequence variable neighborhood descent process with the multi-ACO to improve the solution quality of the algo-rithm? designs a novel local optimization method with restricted neighborhood to improve the computational efficiency of the local search process.Simulation results show that the proposed method has high solving efficiency and can achieve high quality solutions.Compared with the state-of-the-art algorithms,the optimization effect is improved by up to 20%,and the calculation time is reduced by up to 60%.3)Research on distributed multi-robot search task allocation problem under dynamic envi-ronments and propose a new strategy: the dynamic partition-based Bayesian learning strategy.For most of the existing distributed multi-robot searching task allocation algorithms,it is easy to fall into local optimum,or difficult to adapt to dynamic environment changes and un-stable communication environments.A novel distributed dynamic graph partitioning method is proposed to solve the problems.The proposed method constrains the robots' decision-making ranges by graph partitioning,which overcomes the problems of low global optimization capabil-ities and high requirements for the communication stability of online algorithms? adjusts graph partitioning dynamically by reward-based learning methods,which overcomes the disability for the partition-based methods to adapt to dynamic environment changes? optimize the specific searching routes of the robots by an improved Bayesian model,which improves the continuous optimization ability of the algorithm.The simulation results show that the proposed method can achieve stable and effective searching plans for the robots under dynamic environments.Com-pared with the state-of-the-art online algorithms,the convergence speed of the proposed method is improved by about 30%,the conflict between robots is significantly reduced under different communication packet loss rates,and the solution quality is improved.4)Research on distributed multi-robot rescue task allocation problem under dynamic en-vironments and propose a new method: the dynamic grouping task allocation method based on cluster-first strategy.The existing distributed task allocation methods are prone to fall into the local optimum,and unable to quickly respond to the dynamic changes of task information,robot status and communication network status.As a result,high-quality solutions cannot be obtained in time.Aiming at the above problems,improvements have been made to a type of algorithms that are currently commonly used for solving distributed task allocation problems: the consensus-based auction algorithm.To improve the task selection phase of the algorithms,a cluster-first strat-egy is designed to divide tasks into clusters.The strategy distinguishes the priority of tasks for different robots.By reducing the conflict between robots,the convergence efficiency of the algorithms is improved.Based on the strategy,a task selection method based on probability selection is designed to prevent the algorithms from easily falling into local optimums.To im-prove the consensus phase,a dynamic grouping method for robots is designed.The method solves the problem that the algorithms cannot quickly respond to dynamic changes and avoid conflict between robots when communication environment is unstable.Simulation results show that the proposed improved methods has excellent performance in solving task allocation prob-lems with deadlines.Compared with state-of-the-art algorithms,the convergence speed of the improve algorithms is increased by aoubt 50%,and the number of tasks assigned is increased by about 20%.The proposed method can meet dynamic environment changes,such as frequent addition of new tasks,robot damage,and robot addition capabilities.5)According to the designed task allocation mode and the established distributed archi-tecture for multi-robot cooperative search and rescue,a prototype system for mutli-robot search and rescue task allocation based on UAVs is built.The task allocation mode and algorithms studied in this paper are actually tested in a real environment.Experimental results verify the feasiblity and correctness of the system designed,and show that the researches in this paper meet the requirements of non-deterministic and dy-namic environments of actual search and rescue scenarios,and has certain application value.