Methods and systems for determining the location of an agent within an environment using a hybrid approach are provided. The hybrid approach allows a potentially large physical space to be compressed in the form of a directed graph, in which edges are paths and nodes are locations. An image comparison produces observations for each location and path, which can be used to probabilistically locate the agent in the environment and to select a portion of the 3D point cloud for comparison. The agent can then be localized within the 3D point cloud, or metric-accurate map, using the same features utilized for image matching in the probabilistic location.