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. This paper describes a Truth Maintenance System (TMS) whose architecture has been motivated by the structure of a commonly occurring type of CSP. It shows that by exploiting structural features of dependency constrants 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. The paper also compares how reasoning systems designed for solving constraint satisfaction problems using the present specialized TMS differ from those using other truth maintenance models such as McAllester’s RUP and de Kleer’s ATMS.