A method for navigating a robot from a current pose to a goal pose, comprising receiving a map representing obstacles and free space within an area for robot navigation; constructing, based on the received map , a matching map pyramid comprising a highest resolution matching map and a set of decimated matching maps at successively lower resolutions; constructing, based on the received map , an exclusion map pyramid comprising a highest resolution exclusion map and a set of decimated exclusion maps at successively lower resolutions; receiving a goal pose for navigating a robot from its present location to the goal pose along a goal path; receiving a laser-radar scan comprising a point cloud representing obstacles in proximity to the robot at its present location; finding the current pose of the robot ; and moving the robot to a next pose on the goal path in the direction of the goal pose; wherein finding the current pose of the robot comprises: determining a search area within the received map ; creating a search heap comprising search tasks representing candidate poses at one or more resolutions of the matching map pyramid ; scoring the search tasks on the search heap to determine a best candidate pose, wherein if the best candidate pose is at the highest resolution matching map , the pose is selected as the current pose; wherein if the best candidate pose is not at the highest resolution matching map the search heap is expanded based on the best candidate pose at a next highest resolution matching map; and characterized in that the search heap is not expanded with search tasks with candidate poses that would localize the robot in an exclusion zone of an exclusion map at the next highest resolution exclusion map. receiving a map representing obstacles and free space within an area for robot navigation; constructing, based on the received map , a matching map pyramid comprising a highest resolution matching map and a set of decimated matching maps at successively lower resolutions; constructing, based on the received map , an exclusion map pyramid comprising a highest resolution exclusion map and a set of decimated exclusion maps at successively lower resolutions; receiving a goal pose for navigating a robot from its present location to the goal pose along a goal path; receiving a laser-radar scan comprising a point cloud representing obstacles in proximity to the robot at its present location; finding the current pose of the robot ; and moving the robot to a next pose on the goal path in the direction of the goal pose; wherein finding the current pose of the robot comprises: determining a search area within the received map ; creating a search heap comprising search tasks representing candidate poses at one or more resolutions of the matching map pyramid ; scoring the search tasks on the search heap to determine a best candidate pose, wherein if the best candidate pose is at the highest resolution matching map , the pose is selected as the current pose; wherein if the best candidate pose is not at the highest resolution matching map the search heap is expanded based on the best candidate pose at a next highest resolution matching map; and determining a search area within the received map ; creating a search heap comprising search tasks representing candidate poses at one or more resolutions of the matching map pyramid ; scoring the search tasks on the search heap to determine a best candidate pose, wherein if the best candidate pose is at the highest resolution matching map , the pose is selected as the current pose; wherein if the best candidate pose is not at the highest resolution matching map the search heap is expanded based on the best candidate pose at a next highest resolution matching map; and characterized in that the search heap is not expanded with search tasks with candidate poses that would localize the robot in an exclusion zone of an exclusion map at the next highest resolution exclusion map. <EOS>