Truth maintenance system
Encyclopedia
Reason maintenance 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. It encompasses a variety of techniques that share a common architecture: 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. 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 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 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 results the addition of new statements to the KB. This process is called dependency-directed backtracking.
The TMS maintain 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:
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). Multi-context systems allow 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.
Knowledge representation
Knowledge representation is an area of artificial intelligence research aimed at representing knowledge in symbols to facilitate inferencing from those knowledge elements, creating new elements of knowledge...
approach to efficient handling of inferred information that is explicitly stored. Reason maintenance distinguishes between base facts, which can be defeated
Defeasible reasoning
Defeasible reasoning is a kind of reasoning that is based on reasons that are defeasible, as opposed to the indefeasible reasons of deductive logic...
, and derived facts. As such it differs from belief revision
Belief revision
Belief revision is the process of changing beliefs to take into account a new piece of information. The logical formalization of belief revision is researched in philosophy, in databases, and in artificial intelligence for the design of rational agents....
which, in its basic form, assumes that all facts are equally important. Reason maintenance was originally developed as a technique for implementing problem solvers. It encompasses a variety of techniques that share a common architecture: 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
Knowledge representation
Knowledge representation is an area of artificial intelligence research aimed at representing knowledge in symbols to facilitate inferencing from those knowledge elements, creating new elements of knowledge...
method for representing both beliefs and their 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 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 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 results the addition of new statements to the KB. This process is called dependency-directed backtracking.
The TMS maintain 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:
- Support List [SL]
- Conceptual Dependencies(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). Multi-context systems allow 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
Lisp machine
Lisp machines were general-purpose computers designed to efficiently run Lisp as their main software language. In a sense, they were the first commercial single-user workstations...
. 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
- Knowledge representationKnowledge representationKnowledge representation is an area of artificial intelligence research aimed at representing knowledge in symbols to facilitate inferencing from those knowledge elements, creating new elements of knowledge...
- Artificial intelligenceArtificial intelligenceArtificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
- Belief revisionBelief revisionBelief revision is the process of changing beliefs to take into account a new piece of information. The logical formalization of belief revision is researched in philosophy, in databases, and in artificial intelligence for the design of rational agents....
- Knowledge acquisitionKnowledge acquisitionKnowledge acquisition is a method of learning, first proposed by Aristotle in his seminal work "Organon". Aristotle proposed that the mind at birth is a blank slate, or tabula rasa...
Other references
- Bridgeland, D. M. & Huhns, M. N., Distributed Truth Maintenance. Proceedings of. AAAI–90: Eighth National Conference on Artificial Intelligence, 1990.
- J. de Kleer (1986). An assumption-based TMS. Artificial Intelligence, 28:127–162.
- J. Doyle. A Truth Maintenance System. AI. Vol. 12. No 3, pp. 251–272. 1979.
- U. Junker and K. Konolige (1990). Computing the extensions of autoepistemic and default logics with a truth maintenance system. In Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI'90), pages 278–283. MIT PressMIT PressThe MIT Press is a university press affiliated with the Massachusetts Institute of Technology in Cambridge, Massachusetts .-History:...
. - Mason, C. and Johnson, R. DATMS: A Framework for Assumption Based Reasoning, in Distributed Artificial Intelligence, Vol. 2, Morgan Kaufmann PublishersMorgan Kaufmann PublishersMorgan Kaufmann Publishers is a Massachusetts based publisher specializing in computer science and engineering content.Since 1984, Morgan Kaufmann has published content on information technology, computer architecture, data management, computer networking, computer systems, human computer...
, Inc., 1989. - D-A. McAllster. A three valued maintenance system. Massachusetts Institute of TechnologyMassachusetts Institute of TechnologyThe Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
, Artificial Intelligence Laboratory. AI Memo 473. 1978. - G. M. Provan (1988). A complexity analysis of assumption-based truth maintenance systems. In B. Smith and G. Kelleher, editors, Reason Maintenance Systems and their Applications, pages 98–113. Ellis Horwood, New York.
- G. M. Provan (1990). The computational complexity of multiple-context truth maintenance systems. In Proceedings of the Ninth European Conference on Artificial Intelligence (ECAI'90), pages 522–527.
- R. Reiter and J. de Kleer (1987). Foundations of assumption-based truth maintenance systems: Preliminary report. In Proceedings of the Sixth National Conference on Artificial Intelligence (AAAI'87), pages 183–188. PDF
External links
- Google Scholar on TMSs
- Belief Revision and TMSs at Stanford Encyclopedia of PhilosophyStanford Encyclopedia of PhilosophyThe Stanford Encyclopedia of Philosophy is a freely-accessible online encyclopedia of philosophy maintained by Stanford University. Each entry is written and maintained by an expert in the field, including professors from over 65 academic institutions worldwide...