|Norvig I 460
Truth maintenance/AI research/Norvig/Russell: We have seen that many of the inferences drawn by a knowledge representation system will have only default status, rather than being absolutely certain. Inevitably, some of these inferred facts will turn out to be wrong and will have to be retracted in the face of new information. This process is called belief revision.
Belief revision: is often contrasted with belief update, which occurs when a knowledge base is revised to reflect a change in the world rather than new information about a fixed world. Belief update combines belief revision with reasoning about time and change; it is also related to the process of filtering.
Suppose that a knowledge base KB contains a sentence P - perhaps a default conclusion recorded by a forward-chaining algorithm, or perhaps just an incorrect assertion - and we want to execute TELL(KB, ¬P). To avoid creating a contradiction, we must first execute RETRACT(KB, P).
Norvig I 461
Problem: For example, the implication P ⇒ Q might have been used to add Q. The obvious “solution” - retracting all sentences inferred from P - fails because such sentences may have other justifications besides P. For example, if R and R ⇒ Q are also in the KB, then Q does not have to be removed after all. Truth maintenance systems, or TMSs, are designed to handle exactly these kinds of complications. One simple approach to truth maintenance is to keep track of the order in which sentences are told to the knowledge base by numbering them from P1 to Pn.
A more efficient approach JTMS is the justification-based truth maintenance system, or JTMS. In a JTMS, each sentence in the knowledge base is annotated with a justification consisting of the set of sentences from which it was inferred. The JTMS assumes that sentences that are considered once will probably be considered again, so rather than deleting a sentence from the knowledge base entirely when it loses all justifications, we merely mark the sentence as being out of the knowledge base.
Norvig I 462
An assumption-based truth ATMS maintenance system, or ATMS, makes this type of context switching between hypothetical worlds particularly efficient. An ATMS represents all the states that have ever been considered at the same time. >Truth transfer/Philosophical theories.
Norvig I 472
The study of truth maintenance systems began with the TMS (Doyle, 1979)(1) and RUP (McAllester, 1980)(2) systems, both of which were essentially JTMSs. Forbus and de Kleer (1993)(3) explain in depth how TMSs can be used in AI applications. Nayak and Williams (1997)(4) show how an efficient incremental TMS called an ITMS makes it feasible to plan the operations of a NASA spacecraft in real time.
1. Doyle, J. (1979). A truth maintenance system. AIJ, 12(3), 231–272
2. McAllester,D. A. (1980). An outlook on truth maintenance. Ai memo 551, MIT AI Laboratory
3. Forbus, K. D. and de Kleer, J. (1993). Building Problem Solvers. MIT Press.
4. Nayak, P. and Williams, B. (1997). Fast context switching in real-time propositional reasoning. In
AAAI-97, pp. 50–56_____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010