Qualitative place maps for landmark-based localization and navigation in GPS-denied environments

GPS-based services (e.g. Google Maps) are very popular in our daily life, while there are still many GPS-denied environments (e.g. indoor and underground scenarios) in which they cannot be used. In these situations, localization and navigation are still important, for example in emergency evacuation or indoor navigation. In this paper we aim to solve the problem of localizing and navigating humans or robots in GPS-denied environments based on landmarks. Our work is inspired by human daily communications about localization and navigation, for example someone who has been to a shopping mall many times can localize and guide another person to get to a certain shop via conversations over the cellphone. Our goal is to build a system with the same capability. We propose a system that relies on qualitative information of places (e.g. the direction relations between landmarks involved in route descriptions), where localization can be achieved in an interactive manner and by analyzing observations provided by users. Our system decides the "best" route from one place to another by three factors: the number of landmarks; the number of ambiguous turns; and the qualitative distance (e.g. near and far). According to the experimental results, the number of requeries in the interactive localization process is acceptable and our route planning algorithm outperforms previous methods in several cases.