Autonomous navigation through complex dynamic real-world scenarios is a demanding challenge for today’s mobile robots. Even for humans without map knowledge or GPS this constitutes an ambitious task in unknown environments. Present-day cognitive robotics research is still far away from enabling robots to accomplish even a basic task like navigating to designated goal locations only given symbolic identification labels of the locations. Humans have the compelling ability to consult other humans regarding required but missing directional information in order to fill such identified knowledge gaps, such as the way to a particular location “X”. Particularly, in unknown environments there will always be knowledge gaps for the robot as not everything can be pre-programmed and online learning on its own is not always a feasible or efficient solution. The ability to assess gaps in its own knowledge and to retrieve missing information from other agents like humans whenever possible is, thus, a highly desirable, yet, missing feature of today’s robots. Information exchange between humans and robots must not only be limited to robots serving information to humans, but also extended to humans supporting robots by providing specific missing information.