I have a top-end Roomba 980 like the GP is referring to. They don't use random exploration. When you start a cleaning cycle, it begins working in a back and forth cleaning pattern of parallel lines. When it runs out of room to perform the back and forth lines, it moves to a place where there's a "hole" in its map. That may just be a corner behind a chair, or it could be a doorway to a different room. It basically repeats this process until it has filled in all the holes and built a full map of the room, level, or whatever area you're letting it vacuum.

The algorithm definitely isn't perfect. It might clean half of the room where it starts, then wander around and clean most of the house before making its way back to finish that room. Still it seems to work well overall. What really fascinates me is how the algorithm and SLAM mapping gives it very familiar behavioral patterns. For example when it's coming back into a room that it's already visited, it might drive just inside the room, pause, "look" side to side (panning the camera to find landmarks it recognizes), then continue on.