StarVars-effective reasoning about relative directions

Relative direction information is very commonly used. Observers typically describe their environment by specifying the relative directions in which they see other objects or other people from their point of view. Or they receive navigation instructions with respect to their point of view, for example, turn left at the next intersection. However, it is surprisingly hard to integrate relative direction information obtained from different observers, and to reconstruct a model of the environment or the locations of the observers based on this information. Despite intensive research, there is currently no algorithm that can effectively integrate this information: this problem is NP-hard, but not known to be in NP, even if we only use left and right relations. In this paper we present a novel qualitative representation, StarVars, that can solve these problems. It is an extension of the STAR calculus [Renz and Mitra, 2004]) by a VARiable interpretation of the orientation of observers. We show that reasoning in StarVars is in NP and present the first algorithm that allows us to effectively integrate relative direction information from different observers.