A Divide and Conquer Strategy for Sweeping Coverage Path Planning

Abstract

One of the main challenges faced by floor treatment service robots is to compute optimal paths that completely cover a set of target areas. Short paths are of noticeable importance because their length is directly proportional to the energy used by the robot. Such a problem is known to be NP-hard; therefore, efficient algorithms are needed. In particular, computation efficiency is important for mobile robots with limited onboard computation capability. The general problem is known as coverage path planning (CPP). The CPP has several variants for single regions and for disjoint regions. In this research, we are investigating the solutions for disjoint target regions (rooms) that have fixed connection points (doors). In particular, we have found effective simplifications for the cases of rooms with one and two doors, while the challenging case of an unbounded number of rooms can be solved by approximation. As a result, this work presents a divide and conquer strategy (DnCS) to address the problem of finding a path for a sweeping robot that needs to sweep a set of disjoint rooms that are connected by fixed doors and corridors. The strategy divides the problem into computing the sweeping paths for the target rooms and then merges those paths into one solution by optimising the room visiting order. In this strategy, a geometrical approach for room coverage and an undirected rural postman problem optimisation are strategically combined to solve the coverage of the entire area of interest. The strategy has been tested in several synthetic maps and a real scenario showing short computation times and complete coverage.

Keywords

• sweeping robot
• coverage path planning
• genetic algorithm
• divide and conquer