Reason maintenance

Reason maintenance[1][2] is a knowledge representation approach to efficient handling of inferred information that is explicitly stored. Reason maintenance distinguishes between base facts, which can be defeated, and derived facts. As such it differs from belief revision which, in its basic form, assumes that all facts are equally important. Reason maintenance was originally developed as a technique for implementing problem solvers.[2] It encompasses a variety of techniques that share a common architecture:[3] two components - a reasoner and a reason maintenance system - communicate with each other via an interface. The reasoner uses the reason maintenance system to record its inferences and justifications of ("reasons" for) the inferences. The reasoner also informs the reason maintenance system which are the currently valid base facts (assumptions). The reason maintenance system uses the information to compute the truth value of the stored derived facts and to restore consistency if an inconsistency is derived.

A truth maintenance system, or TMS, is a knowledge representation method for representing both beliefs and their dependencies and an algorithm called the "truth maintenance algorithm" that manipulates and maintains the dependencies. The name truth maintenance is due to the ability of these systems to restore consistency.

It is also termed as a belief revision system, a truth maintenance system maintains consistency between old believed knowledge and current believed knowledge in the knowledge base (KB) through revision. If the current believed statements contradict the knowledge in the KB, then the KB is updated with the new knowledge. It may happen that the same data will again come into existence, and the previous knowledge will be required in the KB. If the previous data is not present, it is required for new inference. But if the previous knowledge was in the KB, then no retracing of the same knowledge was needed. Hence the use of TMS to avoid such retracing; it keeps track of the contradictory data with the help of a dependency record. This record reflects the retractions and additions which makes the inference engine (IE) aware of its current belief set.

Each statement having at least one valid justification is made a part of the current belief set. When a contradiction is found, the statement(s) responsible for the contradiction are identified and an appropriate is retraced. This process is called dependency-directed backtracking.

The TMS algorithm maintains the records in the form of a dependency network. The nodes in the network are one of the entries in the KB (a premise, antecedent, or inference rule etc.) Each arc of the network represent the inference steps from which the node was derived.

A premise is a fundamental belief which is assumed to be always true. They do not need justifications. Considering premises are base from which justifications for all other nodes will be stated.

There are two types of justification for each node. They are:

  1. Support List [SL]
  2. Conditional Proof (CP)

Many kinds of truth maintenance systems exist. Two major types are single-context and multi-context truth maintenance. In single context systems, consistency is maintained among all facts in memory (database) and relates to the notion of consistency found in classical logic. Multi-context systems support paraconsistency by allowing consistency to be relevant to a subset of facts in memory (a context) according to the history of logical inference. This is achieved by tagging each fact or deduction with its logical history. Multi-agent truth maintenance systems perform truth maintenance across multiple memories, often located on different machines. de Kleer's assumption-based truth maintenance system (ATMS, 1986) was utilized in systems based upon KEE on the Lisp Machine. The first multi-agent TMS was created by Mason and Johnson. It was a multi-context system. Bridgeland and Huhns created the first single-context multi-agent system.

See also

References

  1. ↑ Doyle, J.: The ins and outs of reason maintenance.
  2. 1 2 Doyle, J.: Truth maintenance systems for problem solving. Tech. Rep. AI-TR-419, Dep. of Electrical Engineering and Computer Science of MIT (1978)
  3. ↑ McAllester, D.A.: Truth maintenance. AAAI90 (1990)

Other references

External links

This article is issued from Wikipedia - version of the Monday, August 24, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.