A method of navigating an autonomous robot within an area at least partially enclosed by walls (305a-l), the method comprising: maneuvering the robot in a following mode in which the robot is controlled to travel along path segments adjacent an obstacle, while recording data indicative of the path segments as signatures (420a-e); maneuvering the robot in a coverage mode in which the robot is controlled to traverse the area while performing a function, while generating data (400a, 400b, 400c) indicative of a physical layout of the area, including area boundaries (305a-l) and obstacle perimeters detected while performing the function, updating data indicative of a calculated robot pose, the calculated robot pose comprising a calculated location and orientation of the robot within the area, based at least on robot odometry data, and calculating a robot pose confidence level; and in response to the robot pose confidence level being below a predetermined confidence limit: selecting a signature from the plurality of signatures (420a-e) based on a relative uncertainty of the robot in a given direction; maneuvering the robot to a suspected location of a path segment corresponding to the selected signature, based on the calculated robot pose and the data (400a, 400b, 400c) indicative of the physical layout of the area; and then, in response to detecting the path segment adjacent the obstacle within a predetermined distance from the suspected location of the path segment, updating at least one of the data indicative of the calculated robot pose and the data indicative of the physical layout of the area, thereby updating a relative pose of the robot within the area. maneuvering the robot in a following mode in which the robot is controlled to travel along path segments adjacent an obstacle, while recording data indicative of the path segments as signatures (420a-e); maneuvering the robot in a coverage mode in which the robot is controlled to traverse the area while performing a function, while generating data (400a, 400b, 400c) indicative of a physical layout of the area, including area boundaries (305a-l) and obstacle perimeters detected while performing the function, updating data indicative of a calculated robot pose, the calculated robot pose comprising a calculated location and orientation of the robot within the area, based at least on robot odometry data, and calculating a robot pose confidence level; and in response to the robot pose confidence level being below a predetermined confidence limit: selecting a signature from the plurality of signatures (420a-e) based on a relative uncertainty of the robot in a given direction; maneuvering the robot to a suspected location of a path segment corresponding to the selected signature, based on the calculated robot pose and the data (400a, 400b, 400c) indicative of the physical layout of the area; and then, in response to detecting the path segment adjacent the obstacle within a predetermined distance from the suspected location of the path segment, updating at least one of the data indicative of the calculated robot pose and the data indicative of the physical layout of the area, thereby updating a relative pose of the robot within the area. generating data (400a, 400b, 400c) indicative of a physical layout of the area, including area boundaries (305a-l) and obstacle perimeters detected while performing the function, updating data indicative of a calculated robot pose, the calculated robot pose comprising a calculated location and orientation of the robot within the area, based at least on robot odometry data, and calculating a robot pose confidence level; and in response to the robot pose confidence level being below a predetermined confidence limit: selecting a signature from the plurality of signatures (420a-e) based on a relative uncertainty of the robot in a given direction; maneuvering the robot to a suspected location of a path segment corresponding to the selected signature, based on the calculated robot pose and the data (400a, 400b, 400c) indicative of the physical layout of the area; and then, in response to detecting the path segment adjacent the obstacle within a predetermined distance from the suspected location of the path segment, updating at least one of the data indicative of the calculated robot pose and the data indicative of the physical layout of the area, thereby updating a relative pose of the robot within the area. selecting a signature from the plurality of signatures (420a-e) based on a relative uncertainty of the robot in a given direction; maneuvering the robot to a suspected location of a path segment corresponding to the selected signature, based on the calculated robot pose and the data (400a, 400b, 400c) indicative of the physical layout of the area; and then, in response to detecting the path segment adjacent the obstacle within a predetermined distance from the suspected location of the path segment, updating at least one of the data indicative of the calculated robot pose and the data indicative of the physical layout of the area, thereby updating a relative pose of the robot within the area.