A method for traveling down a prescribed arrangement of paths which are connected to one another at nodes with a mobile robot. The robot changes from an initial route, which contains all as yet untraveled paths, to a different replacement route including a loop route which retakes at least one path and at least one further path, and a subsequent remaining route which contains all as yet untraveled paths at that time if a value of a quality function for the replacement route is lower than a value of this quality function for the initial route. The quality function is dependent on a first effort, a second effort, and a variable weighting of the first and second values in relation to one another. The variable weighting weights the second effort lower for a first localization uncertainty of the robot.