Area coverage is an important task for mobile robots, with many real-world applications. In many cases, the coverage has to be completed without the use of a map or any a priori knowledge about the area, a process referred-to as on-line coverage. Previous investigations of multi-robot on-line coverage focused on the improved efficiency gained from the use of multiple robots, but did not formally addressed the potential for greater robustness. We present a novel multi-robot on-line coverage algorithm, based on approximate cell decomposition. We analytically show that the algorithm is complete and robust, in that as long as a single robot is able to move, the coverage would be completed. We analyze the assumptions underlying the algorithm requirements and present a number of techniques for executing it in real robots. We show empirical coverage-time results of running the algorithm in two different environments and several group sizes