StarVars-effective reasoning about relative directions

Jae Hee Lee, Jochen Renz, Diedrich Wolter

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    24 Citations (Scopus)


    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.

    Original languageEnglish
    Title of host publicationIJCAI 2013 - Proceedings of the 23rd International Joint Conference on Artificial Intelligence
    Number of pages7
    Publication statusPublished - 2013
    Event23rd International Joint Conference on Artificial Intelligence, IJCAI 2013 - Beijing, China
    Duration: 3 Aug 20139 Aug 2013

    Publication series

    NameIJCAI International Joint Conference on Artificial Intelligence
    ISSN (Print)1045-0823


    Conference23rd International Joint Conference on Artificial Intelligence, IJCAI 2013


    Dive into the research topics of 'StarVars-effective reasoning about relative directions'. Together they form a unique fingerprint.

    Cite this