Hierarchical Task Network Planning
The hierarchical task network planning, also called hierarchical planning, is employed in complex decision making systems. It generates a relatively abstract ordering of steps to realize the goal and then each abstract step is realized with simpler plans. A hierarchical planning scheme looks somewhat like a tree structure, where the steps at the higher level of the tree represent more abstract and complex tasks. Let us, for example, consider the plan for 'writing a book'. We, following the...
Iterative Deepening A Algorithm
The iterative deepening search algorithm, discussed earlier, searches the goal node in a depth first manner at limited depth. In each pass the depth is increased by one level to test the presence of the goal node in that level. The A algorithm, on the other hand, in each pass, selects the least cost f node for expansion. The iterative deepening A or IDA algorithm presented below attempts to combine the partial features of iterative deepening and A algorithms together. Here, the heuristic...
The Logic of Propositions and Predicates
The chapter presents various tools and techniques for representation of knowledge by propositions and predicates and demonstrates the scope of reasoning under the proposed framework of knowledge representation. It begins with the syntax and semantics of the logic of propositions, and then extends them for reasoning with the logic of predicates. Both the logic of propositions and predicates require the formulation of a problem in the form of a logical theorem and aim at proving it by the...
Soundness and Completeness 1
The issues of soundness and completeness of the resolution principle for propositional logic have already been discussed in a previous section. This section discusses these issues for predicate logic. To prove the completeness of the resolution theorem of predicate logic, the following definitions and theorems are presented in order. Definition 5.15 The Herbrand Universe Hs for a given set of clauses S is defined as the set of all possible ground terms, constructed by replacing the variables in...
Alphabets of FOL
The alphabets of FOL are of the following types 4. Operators A, v , i , Definition 5.11 A term is defined recursively as being a constant, variable or the result of application of a function to a term. e.g., a, x, t x , t g x are all terms. To illustrate the difference between functions and predicates, we give their formal definitions with examples. Definition 5.12 Function denotes relations defined on a domain D. They map n elements n gt 0 to a single element of the domain. father-of, age-of...
Circumscription
Circumscription 7 is the third main type of non-monotonic reasoning following NMLs and default logic. Developed by John McCarthy, circumscription attempts to minimize the interpretation of specific predicates, thus reducing the scope of non-monotonicity. For instance, suppose that a child knows only two kinds of birds parrot and sparrow. Formally, we can write this as Bird parrot v Bird sparrow . So, he defines a rule V X Bird X Bird parrot v Bird sparrow . The expression of the form X parrot v...
Exercises 1
1. Prove that for the atomic propositions p, q, r and s b p, q r, s p, q, r s Could you remember the use of the above tautologies in Wang's algorithm If yes, in which steps did you use them 2. Verify the following theorems by Wang's algorithm. c p q A q p p A q V p A q Note For b and c , prove the theorems first from left to right and then from right to left. 3. Apply resolution theorem to prove the following theorem Hints Here, goal is r so resolve r with the CNF form of premise clauses to...
Fuzzy Modus Tollens and Duality
In classical modus tollens 15 , for predicates A and B, given the rule A B and the observed evidence - B, then the derived inference is A. Thus the contrapositive rule A B B A follows. It is known that in fuzzy logic the sum of the belief of an evidence and its contradiction is greater than or equal to one 22 . So, if the belief of an evidence is known, the belief of its contradiction cannot be easily ascertained. However, in many real world problems, the belief of non-occurrence of an evidence...
Defeasible Reasoning in Semantic Nets
The last example demonstrates whenever we have inconsistent inferences like Fly X and Fly X , we resolve it by giving favour to the more restrictive rules. But how to determine which rule is more restrictive This section presents a principle, by which one will be able to select a better inference, even when the reasoning is constrained with contradictions. Rules em ploying -- gt type of im plications are called defeasible rules 7 - 8 . Rules using are called absolute monotonie. Rules using - --...
Info Khq
Suppose, we are interested to compute Bel BT lt 98 F and Bel BT gt 100 F . Now, with reference to Pearl's nomenclature, we thus assume the following items in fig. 9.8 Here, A.y body-temp 1.0 and Az body-temp 1.0 Since body-temp C is a terminal node in fig, 9.8. the A values incoming to it should be unity. Thus by expression 9.19 , we find nBT high-GM x nBT high-CP x P BT lt 98 F high-GM, high-CP nBT high-GM x nBT low-CP x P BT lt 98 F high-GM, low-CP nBT low-GM x nBT high-CP x P BT lt 98 F...
Acknowledgment
The author gratefully acknowledges the contributions of many people, who helped him in different ways to complete the book. First and foremost, he wishes to thank his graduate students attending the course entitled AI and Pattern Recognition in ETCE department, Jadavpur University during the 1993-1999 sessions. Next, he would like to thank the scholars working for their Ph.D. degree under his supervision. In this regard, the author acknowledges the contribution of Ms. Jaya Sil, a recipient of...
Exercises Oja
1. Represent the following sentences by default logic. Also mention the sets D a Typically molluscs are shell-bearers 2 . c Cephalopods are not shell-bearers. Hints W Cephalopod X Molluscs X and 2. Represent the following sentences by default logic. a John is a high school leaver. b Generally, high school leavers are adults. c Generally, adults are employed. Now, determine the extension of the default theory. Do you think that the extension is logically rational 3. Replace rule c in the last...
The SLD Resolution
We start this section with a few definitions and then illustrate the SLD resolution with examples. Definition 6.3 A definite program clause 1 is a clause of the form A Bl, B2, , Bn which contains precisely one atom viz. A in its consequent head and a null, one or more literals in its body viz. B1 or B2 or or Bn . Definition 6.4 A definite program is a finite set of definite program clauses. Definition 6.5 A definite goal is a clause of the form B1, B2, , Bn i.e., a clause with an empty...
The Closed World Assumption
The readers by this time can understand that non-monotonicity mainly creeps into a reasoning system because of incompleteness of information. Thus for reasoning in a non-monotonic domain, one has to presume either a closed world assumption or add new facts and knowledge to continue reasoning. The phrase closed world assumption means that the ground predicates not given to be true are assumed to be false. For instance, consider the following clauses. Bird X a Abnormal X Fly X Bird parrot ....
Semantic Method for Theorem Proving
The following notation will be used to represent a symbolic theorem, stating that conclusion c follows from a set of premises pi ,p2 , , pn pi, P2 , , Pn c or pi, P2 , , Pn C In this technique, we first construct a truth table representing the relationship of p1 through pn with c. Then we test the validity of the theorem by checking whether both the forward and backward chaining methods, to be presented shortly, hold good. The concept can be best illustrated with an example. Example 5.1 Let us...
Syntactic Methods for Theorem Proving
Before presenting the syntactic methods for theorem proving in propositional logic, we state a few well-known theorems 4 , which will be referred to in the rest of the chapter. Standard theorems in propositional logic Assuming p, q and r to be propositions, the list of the standard theorems is presented below. 4. q, p q p Modus Tollens 6. p q, q r p r Chaining 7. p, p q, q r r Modus Ponens amp Chaining 13. p Oq p A q V p A q 15. p q q p contraposition theorem The syntactic approach for theorem...
Chapter 6 Principles in Logic Programming
6.1 Introduction to PROLOG Programming 6.2 Logic Programs - A Formal Definition 6.3 A Scene Interpretation Program 6.4 Illustrating Backtracking by Flow of Satisfaction Diagrams 6.6 Controlling Backtracking by CUT 6.8 Negation as a Failure in Extended Logic Programs 6.9 Fixed Points in Non-Horn Clause Based Programs 6.10 Constraint Logic Programming 6.11 Conclusions Exercises References
Chapter 5 The Logic of Propositions and Predicates
5.3 Tautologies in Propositional Logic 5.4 Theorem Proving by Propositional Logic 5.4.1 Semantic Method for Theorem Proving 5.4.2 Syntactic Methods for Theorem Proving 5.4.2.2 Theorem Proving by Using Wang's Algorithm 5.5 Resolution in Propositional Logic 5.6 Soundness and Completeness of Propositional Logic 5.8 Writing a Sentence into Clause Forms 5.10.1 Theorem Proving in FOL with Resolution Principle 5.11 Different Types of Resolution 5.11.1 Unit Resulting Resolution 5.11.3 Double Resolution...