New Scientist has an article about a robot that had to find its way through a city without a map.
The robot, called ACE for Autonomous City Explorer, lacks an inbuilt map of Munich or a GPS system. Like a lost human in a similar situation, all it could do was ask for directions.
The beauty of this approach is its ability to deal with changing environments, construction, hazards, etc. It trades the temporal instability of hard coded maps for the risk that it will get wrong directions in the field. I imagine a system that could dynamically weigh the viability of data from various sources could bring a lot of value to the navigation industry.