Complete coverage path planning for cleaning task using multiple robots

Abstract

This paper proposes a novel path planning method for cleaning task using multiple robots in large environment. To do so, we suggested algorithm which partitions a given region into several smaller regions and plans the covering path which can completely cover these divided areas. The algorithm also allocates the planed areas to cleaning robots sequentially and generates the paths which robots can take, when moving from an area to another area, in the shortest time. For partitioning the given region into several small areas, the Virtual Door Algorithm is used, and for planning the paths, the template-based approach is used. Previously generated look-up table, which uses the Dijkstra algorithm, is used for determining the path from one are to another. The Task Area Allocation Algorithm, which allocates the divided areas to cleaning robots using look-up table, is used for planning paths that cover the area completely. Finally, we evaluated the performance of our algorithms which can completely cover the given region regardless of the number of cleaning robots and verify the effectiveness of our proposed algorithms through computer simulations.