A multi-robot system includes a first a mobile cleaning robot that has a local storage device to store a persistent map of an environment, at least one sensor to sense the environment, and a control module. The control module is configured to: control the mobile cleaning robot to navigate in the environment using the persistent map and sensing data provided by the at least one sensor, share the persistent map with a second mobile cleaning robot, and coordinate with the second mobile cleaning robot to perform cleaning tasks.