A method of operating a robotic cleaning device over a surface to be cleaned. The method includes: registering roadmap nodes at intervals on the surface during cleaning, the roadmap nodes including positional information; and linking the roadmap nodes to form roadmap links in a roadmap graph, if the robotic cleaning device is driving directly from a previously registered roadmap node to a currently registered roadmap node. The roadmap links in the roadmap graph facilitate navigation of the robotic cleaning device.