Temporalizing Cardinal Directions: From Constraint Satisfaction to Planning

Principles of Knowledge Representation and Reasoning: Proceedings of the Tenth International Conference (KR2006)

Volume

Principles of Knowledge Representation and Reasoning: Proceedings of the Tenth International Conference (KR2006)

Contents

Frank's cardinal direction calculus is one of the most prominent spatial constraint formalisms, which allows one to represent, and reason with, the relative position of objects in the Euclidean plane. Typical application fields of this calculus include geographical information systems (GIS), route finding and description systems, and navigation of robots that interact with humans. In this paper we investigate a constraint formalism which temporalizes the cardinal direction calculus with respect to Allen's interval algebra. In this constraint language it is possible to represent objects in the plane which change their absolute position in time. Since such changes entail changes of the relative positions of objects to other objects as well, we are interested in the question of how continuous change of objects is reflected in changes of the respective qualitative relations expressing these relative positions. We will show how continuous changes can be represented as operations to objects in grid-like structures. Based on this representation we finally propose a method for encoding temporalized spatial constraint satisfaction problems as deterministic planning problems.