Multi-Robot Coverage with Reeb Graph Clustering and Optimized Sweeping Patterns - Szklarski, Jacek Tomasz (Computer Assisted Methods in Engineering and Science, 2022)
In order to perform mapping, inspecting, searching, painting, cleaning, and other similar tasks, mobile robots have to act according to a coverage plan. Finding a trajectory that a robot should follow requires an appropriate coverage path planning (CPP) algorithm and is a non-trivial problem, especially if a cooperating group of robots is considered. We propose that the multi-robot CPP can be solved by: decomposing the input occupancy grid map into cells, generating a corresponding Reeb graph, clustering the graph into Nr clusters, and solving the associated equality generalized traveling salesman problem in order to obtain optimal back-and-forth sweeping patterns on the clusters. This last step has been proven to be one of the most efficient ways to find trajectories for a single robot [5]. The discussed approach is motivated by a specific application: industrial cleaning of large warehouses by Nr autonomic mobile cleaners (the cleaning radius of a robot is much smaller than the area to be cleaned). The total time required for cleaning is to be minimized. By means of statistical analysis, using an extensive, realistic set of synthetic maps, it is shown that the proposed algorithm meets the criteria for applying it in the production process.