[BibTeX] [RIS]
Temporalizing Cardinal Directions: From Constraint Satisfaction to Planning
Type of publication: Inproceedings
Citation: ragwoe06temporalizing
Booktitle: Proceedings of the Tenth International Conference on Principles of Knowledge Representation and Reasoning, Lake District of the United Kingdom, June 2-5, 2006
Year: 2006
Pages: 472-480
Publisher: American Association for Artificial Intelligence; Menlo Park, CA
Abstract: 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.
Userfields: project={R2-BackSpace}, status={Reviewed},
Authors Ragni, Marco
W├Âlfl, Stefan
Editors Doherty, Patrick
Mylopoulos, John
Welty, Christopher A.