A method of operating a robotic cleaning device over a surface to be cleaned, the method being performed by the robotic cleaning device. The method includes: following a boundary of a first object while registering path markers including positional information at intervals on the surface; tracing previously registered path markers at an offset upon encountering one or more of the previously registered path markers; and switching from tracing the previously registered path markers to following an edge of a second object upon detection of the second object.