A PROBLEM-SOLVER/TMS ARCHITECTURE FOR GENERAL CONSTRAINT SATISFACTION PROBLEMS

Abstract

Constraints, in various forms, are ubiquitous to design problems. In this paper, we provide a formal characterization of a generalized constraint satisfaction problem (CSP) that can be used to model many types of design/planning problems, and the architecture of an imlemented reasoning system for solving this problem. The architecture includes a truth maintenance system (TMS) which is specifically designed to reason about the relationships expressed in the constraints as a problem solution evolves. The CSP consists of two types of data. The first type of datum corresponds to assignments that are handled by the problem solver, and the second type corresponds to constraint terms handled by the TMS. The dependency network, representing the relationships among constraint terms, is static and generally quite small, depending on the number of constraint terms. Also, justifications are never manipulated (only evaluated). This results in an architecture that makes efficient use of both space and time. The need for efficient TMSs, even though these might deal only with certain classes of problems, is underscored by the fact that general purpose TMSs have often been found to be highly inefficient for solving large problems. We also show how certain instances of the generalized CSP can be formulated as an integer programming problem, special cases of which can be solved efficiently using mathematical (integer) programming techniques.