7 Comparisons with other approaches

7.2 Truth maintenance systems

Assumption resolution is a form of truth maintenance. A traditional truth maintenance system (TMS) [5] represents every fact or deduction as a node in a network. At any point in time, each node is assumed to be in (true) or out (false). Each node has a justification representing nodes that must be in and nodes that must be out for that node to be in. Making a new deduction can cause the status of a node to change from in to out, changing the status of other nodes, and so on. However, propagating such changes throughout a network, and refiring rules to take them into account, can be very inefficient.

An assumption-based truth maintenance system (ATMS) [3] is designed to overcome some of these inefficiencies. An ATMS follows through the consequences of every assumption being true, and is therefore similar to the basic assumptions mechanism in SDML. Such systems are particularly efficient when many solutions need to be found or when it is difficult to find a solution due to multiple conflicting assumptions. However, when using SDML for simulation tasks, one solution is normally sufficient and complex conflicting relationships between assumptions rarely arise.

SDML uses a different approach to overcome the inefficiency problems of truth maintenance. Assumptions are only generated where necessary, corresponding to fewer nodes in a TMS network. Partitioning is used to divide the truth maintenance task into subtasks. The observation that most assumptions end up being true is used to limit the search space. These optimisations, described in Section 5.4, usually entail that assumption resolution is trivial.

Efficient Forward Chaining for Declarative Rules in a Multi-Agent Modelling Language - 16 FEB 95

[Next] [Previous] [Up] [Top] [Contents]

Generated with CERN WebMaker