Abstract: As the foundation of many mobile robot applications,complete coverage aims to plan a collision-free path for robot to visit all points in the target area quickly.Using multiple robots for cooperative coverage can significantly reduce coverage time and improve system robustness.However,it increases the algorithm's complexity and makes cooperative robot management more challenging.Therefore,the multi-robot coverage problem in a given environment is studied in this paper,which has been proven to be an NP problem.This work proposes a heuristic multi-robot task assignment based on multi-level graph partitioning(TAMP) method,which consists of a coarse task assignment algorithm and a fine task assignment algorithm.The coarse task assignment algorithm reduces the size of the graph by the strategies of multi-level coarsening and graph maximal matching and then obtains a roughly balanced task assignment by the graph growth strategy.The fine task assignment algorithm proposes a Lazy&Lock strategy to achieve task subdivision,which improves the solution accuracy.Simulations validate the performance of the TAMP approach under different scales of random graphs and real-world policing patrol scenarios.Compared to the conventional task assignment method,TAMP expands the maximum computational scale from thousands to millions.For small-scale graphs(within 3 000),TAMP accelerates computation time by 20 times and outperforms the conventional method in terms of the deviation from the optimal solution for different small-scale graphs.For large-scale graphs(3 000~1 million),TAMP can solve the task assignment problem in 60 s while keeping the deviation of the optimal solution within 0.3%.

Key words: Multi-robot system, Area coverage, Task assignment, Multi-level graph partitioning, Min-max balanced connected q-partition problem