Coverage Path Planning for Single and Multiple Robots

Multi-robot coverage algorithm of the MSTC family, working in simulation.

Coverage is a canonical task for robots, where one or more robots are required to pass over a target work area, and visit every point in the area at least once. Typically, the objective is to minimize the time it takes to complete the task. In offline coverage, the map of the work area is given. In online coverage, the map of the work area is initially unknown.

Over the years, we have tackled several distinct types of coverage algorithms.

Multi-robot Spanning Tree Coverage (MSTC)

MSTC algorithms divide the continuous work area into a grid, and then build an efficient continuous path over the grid such that every cell is covered as the robots move along the path. The algorithms divide the path between the robots, to shorten the time until the last robot finishes.

All the MSTC algorithms share an important trait: they are guaranteed to complete the coverage even if robots fail, as long as one robot remains.

One important lesson from this line of research was the following: In general, robots can minimize coverage time, or minimize coverage redundancy, but cannot minimize both.

To learn more about MSTC algorithms, see:

Multi-robot Coverage without Global localization

Many coverage path-planning algorithms require the robots to know where they are in the work area, and to communicate with each other. Realistically, this is not always possible, and when it is possible, it is not cheap. We therefore explore bio-mimetic robot coverage approaches which make lesser requirements of the communication and localization capabilities of the robots:

Other Robot Coverage Work

Exact work-area decomposition

A weakness of the MSTC approach is that it approximates the work area using a grid, and can therefore miss coverage of some points. An alternative algorithm divides up the work area into connected obstacle-free regions, and then decides on a sequence of visiting these regions for each robot. It also optimizes the coverage motion in each region, while maintaining the robustness guarantee above:

Adversarial Coverage

Prof. Noa Agmon and I collaborated on a variant of the coverage problem, where the robot is to cover the entire area, knowing that there are traps in some locations. The path planning problem is then not only to minimize coverage time, but also to consider survival of the robot. Some relevant publications listed here; see Prof. Noa Agmon’s Publications for more: