Qualitative Spatial Reasoning in Euclidean Spaces
Ian Pratt-Hartmann & Michael Zakharyaschev
Logic & Computation
Week Two - 14.00-15.30 - Level: A
Spatial reasoning in everyday life possesses two distinctive - and related - characteristics: it is primarily concerned with extended (as opposed to point-like) entities, and it typically invokes qualitative (as opposed to quantitative) concepts. This observation has prompted consideration, within the Artificial Intelligence community, of representation languages whose variables range over some specified collection of extended spatial objects, and whose non-logical primitives are interpreted as qualitative spatial properties and relations involving those objects. Several such `spatial logics' have been widely discussed in the AI literature, and their fundamental properties are by now well-understood. In recent years, however, attention has turned to languages able to express the key properties of `connectedness' and `convexity', which were relatively neglected in earlier work. As is now becoming clear, such spatial logics typically exhibit a surprising degree of expressive power - and commensurate computational complexity. This course will provide a comprehensive overview of classical results in qualitative spatial reasoning, and outline the more advanced techniques required to establish the latest developments.