Coverage Path Planning for Single and Multiple Robots

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:

• N. Agmon, N. Hazon, and G. A. Kaminka. The giving tree: Constructing trees for efficient offline and online multi-robot coverage. Annals of Math and Artificial Intelligence, 52(2–4):143–168, 2008.
• N. Hazon and G. Kaminka. On redundancy, efficiency, and robustness in coverage for multiple robots. Robotics and Autonomous Systems, 56(12):1102–1114, 2008.

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:

• Luca Giuggioli, Idan Arye, Alexandro H. Robles, and Gal A. Kaminka. From Ants to Birds: A Novel Bio-Inspired Approach to Online Area Coverage. In 13th International Symposium on Distributed Autonomous Robotic Systems (DARS-2016), Springer, 2016.
• Ido Ikar. Area Coverage by a Multi-Robot System. Master’s Thesis, Bar Ilan University, 2007.

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:

• Lee-Or Alon, Noa Agmon, and Gal A. Kaminka. Taking Turns in Complete Coverage for Multiple Robots. In 14th International Symposium on Distributed Autonomous Robotic Systems (DARS-2018), Springer, 2018.

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:

• Roi Yehoshua, Noa Agmon, and Gal A. Kaminka. Robotic Adversarial Coverage of Known Environments. International Journal of Robotics Research, 2016.
• Roi Yehoshua, Noa Agmon, and Gal A. Kaminka. Frontier-Based RTDP: A New Approach to Solving the Robotic Adversarial Coverage Problem. In Proceedings of the Fourteenth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-15), 2015.