A truth maintenance system for supporting constraint-based reasoning

摘要

Many types of choice problems that arise in design, be it architectural/engineering design or the design of economic models, can be formulated as constraint satisfaction problems (CSPs). In general, TMSs are a useful computational mechanism for maintaining consistent beliefs or assumptions in problems characterized by a set of constraints. They also enable a problem solver to explore a search space more efficiently by recording the causes of failed partial solutions, and provide a limited explanation capability since reasons for beliefs are recorded explicitly. In this paper we describe a Truth Maintenance System (TMS) whose architecture has been motivated by the structure of a commonly occurring type of CSP. We show that by exploiting structural features of dependency constraints involved in CSPs and adopting a certain delineation of responsibilities between the TMS and a problem solver, considerable simplicity in the TMS architecture and efficiency in its status assignment algorithms is achieved. We also compare how reasoning systems designed for solving constraint satisfaction problems using our specialized TMS differ from those using other truth maintenance models such as McAllester's RUP and de Kleer's ATMS.