Spatial problem solving for diagrammatic reasoning

Diagrammatic reasoning (DR) is pervasive in human problem solving as a powerful adjunct to symbolic reasoning based on language-like representations. However, Artificial Intelligence is overwhelmingly based on symbolic representations, with proportionately scant attention to diagrams. This dissertation is a contribution to building artificial agents that can create and use diagrams as part of their problem solving. The work is in a framework in which DR is modeled as a process in which subtasks are solved, as appropriate, either by inference from symbolic representations or by information perceived from a diagram, and subtasks may also act on the diagram, i.e., create or modify objects in the diagram. The perceptions and actions are in fact domain- and task-specific 2D spatial problems defined in terms of properties and relations involving diagrammatic objects. Most DR systems built so far are task-specific, and their developers as a rule have hand-crafted the required perceptions and actions. Our goal is the development of a general, i.e., domain- and task-independent, capability that takes specifications of perceptions and actions and automatically executes them. Thus, this dissertation investigates: 1. A language for a human problem solver to communicate a wide variety of 2D spatial problems relevant to DR, and 2. A general domain-independent framework of underlying representations and reasoning strategies suitable for efficiently solving spatial problems without human intervention. This dissertation will present a high-level language that is extensible, human-usable, and expressive enough to describe a wide variety of spatial problems 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. Two general and independent strategies – constraint satisfaction and spatial search – are developed for automatically solving the spatial problems specified in that language. Several ideas about how to make these strategies computationally efficient are proposed and illustrated by examples. A traditional AI problem solver is augmented with this spatial problem solver for reasoning with diagrams in different domains for real-world applications. The utility of the framework is judged by the expressiveness of the language, and generality and efficiency of the two strategies.