AIwiki

1. Truth Maintenance Systems (TMS), also called Reason Maintenance Systems, are used within Problem Solving Systems, in conjunction with Inference Engines(IE) such as rule-based inference systems, to manage as a Dependency Network the inference engine's beliefs in given sentences
2. A TMS is intended to satisfy a number of goals:
   1. Provide justifications for conclusions - When a problem solving system gives an answer to a user's query, an explanation of the answer is usually required. An explanation can be constructed by the IE by tracing the justification of the assertion.
   2. Recognise inconsistencies - The IE may tell the TMS that some sentences are contradictory. Then, if on the basis of other IE commands and of inferences we find that all those sentences are believed true, then the TMS reports to the IE that a contradiction has arisen. The IE can eliminate an inconsistency by determining the assumptions used and changing them appropriately.
   3. Support default reasoning - In many situations we want, in the absence of firmer knowledge, to reason from default assumptions. If Tweety is a bird, until told otherwise, we will assume that Tweety flies and use as justification the fact that Tweety is a bird and the assumption that birds fly.
   4. Support dependency driven backtracking - The justification of a sentence, as maintained by the TMS, provides the natural indication of what assumptions need to be changed if we want to invalidate that sentence.
3. TMS maintains a Dependency Network. The network is bipartite, with nodes representing sentences and justifications.
   1. A sentence may correspond to
      • fact, such as „Socrates is a man”
      • rule, such as „if ?x is a man then ?x is mortal”.
   2. We will say that a sentence node
      • is a premise if its sentence is true,
      • is a contradiction if its sentence is false,
      • is an assumption if its sentence is assumed to be true or assumed to be false.
   3. A sentence node receives arcs from justification nodes. Each such justification node provides an argument for believing the given sentence node. In turn a sentence node has arcs to the justification nodes that use it as a premise. A justification node has inputs from sentence nodes, its premises or justifiers, and has output to a sentence node, its conclusion or justificand. A justification node represents the inference of the conclusion from the conjunction of the stated premises
4. Truth Maintenance Systems can have different characteristics:
   1. Justification-Based Truth Maintenance System (JTMS) - It is a simple TMS where one can examine the consequences of the current set of assumptions. The meaning of sentences is not known.
   2. Assumption-Based Truth Maintenance System (ATMS) - It allows to maintain and reason with a number of simultaneous, possibly incompatible, current sets of assumption. Otherwise it is similar to JTMS, i.e. it does not recognise the meaning of sentences.
   3. Logical-Based Truth Maintenance System (LTMS) - Like JTMS in that it reasons with only one set of current assumptions at a time. More powerful than JTMS in that it recognises the propositional semantics of sentences, i.e. understands the relations between p and ~p, p and q and p&q, and so on.

1. CLIPS is equipped with a simple but effective mechanism that enables the programmer to automatically keep track of logical relationships between the facts of the problem. This mechanism is a simple form of TMS and it is based on the idea that each fact in the factual knowledge base (KB) of a program has a logical support that justifies its existence. Consistency of the facts can be done by using keyword logical around the pattern entity in rule definition.
2. Logical Conditional Element (CE) tags those patterns (facts) around it to logically dependent on other facts (its logical support). Once the logical support is retracted the supported facts have no reason to exist in the factual base. In other words, the pattern entities matching the LHS (left-hand side) of the rule using logical condition element provides logical support to the facts created by the RHS (right-hand side) of the rule. So if some facts from LHS of the rule with logical keyword are no longer true, then facts from RHS of this rule are retracted automatically from facts list (KB) - this facts are also no longer true.
3. A pattern entity can be logically supported by more than one group of pattern entities from the same or different rules. If any supporting pattern entities are removed from facts list and there are no other rules that support the pattern, than it is removed from the facts list.
4. A fact created without logical support is said to have unconditional support. It has to be removed explicitly by using the retract action.
5. The logical support of facts can be used:
   • Unordered List Itemto enforce the consistency of the factual knowledge base of the problem
   • to perform an automatic sort of garbage collection, retracting facts that are no longer useful.
6. Logical conditional element may be used in conjunction with the and, or and not conditional elements. However, only the first N patterns of the rule can have the logical CE applied to them.
   • Example of legal use of logical CE in rule:

     (defrule good
        (logical (a))
        (logical (b))
     =>
        (assert (z))
     )

   • Examples of illegal use:

     (defrule bad
        (d)
        (logical (a))
        (logical (b))
     =>
        (assert (z))
     )

     (defrule bad
        (logical (a))
        (d)	
        (logical (b))
     =>
       (assert (z))
     )

     (defrule bad
        (or (d) 
            (logical (a)))
            (logical (b))
     =>
        (assert (z))
     )

   • Keep in mind that there is no need to make everything logical.
     • Firstly, it increases the memory and processing time needed - in complex systems there can be many links to check.
     • Secondly, it is not always appropriate - for most applications the standard facts (without logical keyword) are quite sufficient.

1. This simple example classify person to group of cardiac risk based on their weight and if they smokes.
2. Sample code - analyze the content of the file

Code : cardiac_risk.zip

(deftemplate personal-data
   (slot name)
   (slot weight)
   (slot smoker)
)
	
(deffacts people
    (personal-data (name Adam) (weight 60) (smoker no))
    (personal-data (name Brenda) (weight 120) (smoker yes))
    (personal-data (name Charles) (weight 120) (smoker yes))
)

(defrule cardiac-risk
   (logical (personal-data (name ?name) (smoker yes) (weight ?weight)))
   (logical (test (> ?weight 100)))
 =>
   (assert (cardiac_risk ?name))
   (printout t  ?name " is in the group of high cardiac risk" crlf)
)

• deftemplate - used to create structure that assigns names to each field found within the fact. It helps to access fields of the fact by name.
• deffacts - definitions of the facts
• defrule - definition of rule

1. Run the example
   1. First load file
      1. Ordered List Item(load cardiac_risk_simple.clp)
      2. If everything was loaded correctly, you should see TRUE at the end
   2. Display the content of KB
      1. (reset) - removes all facts from the facts list and and asserts all facts listed in deffacts statements into facts list. (Sets all data to their initial values)
      2. (facts) - displays all facts from the facts list
2. Run the inference process
   1. (agenda) - displays rules that are ready to run. You can use this command if you want to know what rules can be run before inference process.
   2. (run) - runs the inference process
3. Display facts
   1. Has the facts list change?
   2. What facts were added?
   3. Why did this happened?
4. Modify the weight of Brenda to 80 kg
   1. (modify 2 (weight 80)) - modify command changes the fact value, in this case number 2 is fact index that corresponds to Brenda
5. Display facts
   1. Has the facts list change?
   2. What happened?
6. Let’s try one last thing
   1. Modify Brenda weight back to 120 kg
      1. What happened?
      2. How many facts are in facts list?
   2. Display facts list
      1. Have you expected the result?
7. When you check what rules are possible to run, you will see that rule of Brenda classification to group of cardiac risk is active and this facts will be asserted only after running the inference process. Consistency of data is maintained only to the current state of the facts - TMS only removes facts that are no longer true after performing some action and do not assert any facts when we do something (this is only done by inference process or directly by the user).
8. Display the process of TMS in CLIPS
   1. The following commands show logical dependencies work:
      1. (watch facts) - shows what happens with facts
         1. if they are retracted (⇐) or asserted (⇒)
   2. (watch activations) - shows what happens with activation of some rule
      1. if activation is possible, asserted (⇒) and when is retracted (⇐)
   3. (watch rules) - shows what rules are fired when we run inference process
      1. Keyword FIRE
   4. After running above commends lets reset our KB to initial values
      1. (reset)
      2. We can see what facts and activations have been retracted and which one has been asserted.
   5. Now let’s check fact list and run the inference process
      1. What happened after running inference process? What rules have been fired? What facts have been asserted?
   6. Let’s again modify Brenda weight to 80 kg
      1. What facts have been retracted/asserted? Why?
   7. This is how inference process and TMS works in CLIPS.

1. Expand the example of cardiac risk to use BMI factor instead of specific weight and age in determining whether a person should belong to a group of cardiac risk.
   1. Create rule that will add fact (obese ?name) when his/her BMI is greater than 30
   2. Modify cardiac risk rule to use information about person obesity and age (person is in the group of high cardiac risk when he/she is obese and is older than 39)
2. Test created system :)

1. J. de Kleer, “An Assumption-Based Truth Maintenance System,”Anificial Intelligence, 1986
2. J. Doyle, “A Truth Maintenance System,” Artificial Intelligence, 1979
3. Cristian Giumale, “Non-Determinacy and Other Interesting Features of CLIPS”, Lecture Notes, http://andrei.clubcisco.ro/cursuri/2pp/13.Clips_advanced.pdf
4. Mladen Stanojevid et al, “Using Truth Maintanance Systems - Tutorial”, IEEE Expert, 1994