Research On Task Allocation Algorithms Of Multi-robot Complete Coverage Problems

Robotic complete coverage problem?CCP?refers to using mobile robots to tra-verse the target environmental area within its physical contact range or within its sensor's sensing range,and to meet the optimization objectives such as the shortest completion time,the least repeated paths or the smallest uncovered areas.CCP appears in military,agriculture,industry,commerce,disaster rescue,urban life,and other aspects,such as automatic demining,crop harvesting,air traffic inspec-tions.In general,the tasks in a CCP have obvious spatial concurrency and can be processed in parallel.Therefore,with the increasing scale of complete coverage missions and the development of multi-robot technologies,multi-robot systems have been introduced into complete coverage missions,and it is expected that the intro-duction will accelerate the completion time of the mission and thus achieve better benefits.In the process of performing a complete coverage mission,the multi-robot sys-tem needs to go through several stages,including the task decomposition stage,the task assignment stage,and the task scheduling stage.The task decomposition stage focuses on breaking down the whole mission into what tasks or breaking down the whole action space into what regions;the task assignment stage focuses on which robot is assigned which task,and the task scheduling stage focuses on the task ex-ecution order of each robot to avoid resource conflicts?such as collisions?.These three stages are collectively referred to as task allocation in this study and task al-location is the key of multi-robot's high performances.A good task allocation plan enables the robots to tackle the speed-up chanllege,the resource conflict chanllege and the stochasticity in robot number or mission environment.Seeking an allocation plan with optimal time balancedness,least collision or no collision,and least robots,the search space may reach O?q^N?as possible,where q and N is the number of robots and tasks,respectively.In general,N can be hundreds or thousands,and it will be the number of cells or the number of atomic regions.In other words,the search space is gigantic,so deterministic algorithms on large-scale problem is almost impossible and designing a feasible and efficient approximate optimal allocation algorithm is one approach.For the three different scenes of multi-robot systems'complete coverage task allocation,where each scene has different combinations of the above-mentioned three challenges,this study designed three types of algorithms.The multi-robot system to which these algorithms are applied is based on a homogeneous robot team with a central computing and communication node for allocation activities.The main work and contributions of this research are as follows:?1?A balanced and collision-free multi-robot task allocation algorithm for known environments and known number of robots.The algorithm defines the latest completion time of the robots as the balancedness measurement,that is,the earlier the latest completion time,the better the balancedness;in order to achieve no colli-sion,the task regions assigned to each robot are non-intersect,and the task regions of a robot are connected,so that each robot does not need to cross the regions of other robots when performing its own tasks,thus avoiding collisions.For this scene,this study proposes an algorithm based on mixed integer linear programming?MILP?for small and medium-scale problems and an approximation algorithm based on span-ning tree division and evolution for large scale problems.Among them,MILP is the first exact algorithm in the literature to solve the balanced connected q-partition,and it can solve the allocation of 100 more regions than the existing MILP on the2-partition(the space is increased by 2¹⁰⁰times).The approximation algorithm is also the first approximation algorithm for the q-partition on general graphs in the literature.It can solve the partition of scale up to 3000 regions,and it can obtain results that are very close to the ideal optimal value by evolving a small number of spanning trees.?2?A task assignment algorithm that optimizes the number of robots when the completion time has a deadline;it optimizes the number of robots and gives the optimal specific allocation plan.Based on the time-limit,the study pre-calculated a tight upper and lower bounds b and a for the number of robots required.Different from the traditional algorithm of enumerating the number of robots and optimizing the?approximate?optimal plans for the corresponding number of robots,this study proposes a multi-objective optimization algorithm based on genetic algorithm,which can obtain the?approximate?minimum number of robots and can give all?approx-imate?optimal allocation plans for the number of robots in the upper and lower bounds range[a,b].The minimum number of robots obtained by the algorithm is0.6 times that of the existing algorithm.The algorithm has excellent generality,so it is also extended to other problems such as robotic topology coverage task allocation.?3?A task allocation algorithm based on reinforcement learning in a non-deterministic environment.Reinforcement learning is modeled by the Markov De-cision Process?MDP?,which can deal with planning problems in deterministic en-vironments and learning problems in non-deterministic environments in complete coverage problems.This research is a step towards the complete coverage in a dy-namic and unknown environment.This study models the multi-robot balanced task allocation(state space up to 2³⁶*36!?10⁵⁰)into an MDP and applies the deep Q-network learning algorithm?DQN algorithm?for task allocation.The experi-mental results show that the DQN algorithm can obtain a better solution than the commonly used heuristic algorithm by training a small amount of sample?sample size is about 10⁷?,and the DQN algorithm can be generalized to optimize un-trained/unseen samples,showing good accuracy and generalization performance.In a non-deterministic environment,the average number of steps of the reinforce-ment learning algorithm for the majority of environment settings is about half of the commonly used heuristic's optimal steps,and the steps of the reinforcement learning algorithm is similar to the commonly used heuristic's results of when the heuristic was told the actual environmental model,showing DQN's good ability to learn about the environment.The above three aspects of work together serve the complete coverage task allocation,but focus on different scenes,so the three aspects have the side-by-side relationship.In each aspect,there are one or two specific research points and thus they form a fair integral technique system.