Representations and strategies for solving spatial problems with diagrams

Spatial problems (SP) are inevitable in reasoning with diagrams. In this paper, we investigate general representations and computational strategies for a SP-solver such that it can accept problems from a human in a high-level language and output the solution without human intervention. We propose a language in which a variety of domain-independent 2D SPs can be specified in terms of constraints. The constraints are specified in first-order logic over the real domain using a vocabulary of objects, properties, relations and actions. We also propose two general and independent computational strategies - constraint satisfaction and spatial search -for autonomously solving the SPs. Ideas about how to make these strategies computationally efficient are discussed and illustrated by examples. © 2007 IEEE