Knowledge Based Reasoning CS101 FALL 2007 Lecture for Chapter 7 Knowledge Based Agent Agent that uses prior or acquired knowledge to achieve its goals Can make more efficient decisions Can make informed decisions Domain independent algorithms ASK Inference engine TELL Knowledge Base Domain specific content Knowledge Base KB contains a set of representations of facts about the Agent s environment Each representation is called a sentence Use some knowledge representation language to TELL it what to know e g temperature 72F ASK agent to query what to do Agent can use inference to deduce new facts from TELLed facts Generic knowledge based agent 1 TELL KB what was perceived Uses a KRL to insert new sentences representations of facts into KB 2 ASK KB what to do Uses logical reasoning to examine actions and select best Logic in general Types of logic Entailment Inference Validity and satisfiability Theorem Propositional logic semantics Propositional inference normal forms product of sums of simple variables or negated simple variables sum of products of simple variables or negated simple variables Proof methods Inference rules Limitations of Propositional Logic 1 It is too weak i e has very limited expressiveness Each rule has to be represented for each situation e g don t go forward if the wumpus is in front of you takes 64 rules 2 It cannot keep track of changes If one needs to track changes e g where the agent has been before then we need a timed version of each rule To track 100 steps we ll then need 6400 rules for the previous example Its hard to write and maintain such a huge rule base Inference becomes intractable First order logic FOL Ontological commitments Objects wheel door body engine seat car passenger driver Relations Inside car passenger Beside driver passenger Functions ColorOf car Properties Color car IsOpen door IsOn engine Functions are relations with single value for each object Universal quantification for all variables sentence Every one in the 561a class is smart x In 561a x Smart x P corresponds to the conjunction of instantiations of P In 561a Manos Smart Manos In 561a Dan Smart Dan In 561a Clinton Smart Mike is a natural connective to use with Common mistake to use in conjunction with e g x In 561a x Smart x means every one is in 561a and everyone is smart Existential quantification there exists variables sentence Someone in the 561a class is smart x In 561a x Smart x P corresponds to the disjunction of instantiations of P In 561a Manos Smart Manos In 561a Dan Smart Dan In 561a Clinton Smart Mike is a natural connective to use with Common mistake to use in conjunction with e g x In 561a x Smart x is true if there is anyone that is not in 561a remember false true is valid Properties of quantifiers Example sentences Brothers are siblings x y Brother x y Sibling x y Sibling is transitive x y z Sibling x y Sibling y z Sibling x z One s mother is one s sibling s mother m c Mother m c Sibling c d Mother m d A first cousin is a child of a parent s sibling c d FirstCousin c d p ps Parent p d Sibling p ps Parent ps c Higher order logic First order logic allows us to quantify over objects the first order entities that exist in the world Higher order logic also allows quantification over relations and functions e g two objects are equal iff all properties applied to them are equivalent x y x y p p x p y Higher order logics are more expressive than first order however so far we have little understanding on how to effectively reason with sentences in higher order logic Using the FOL Knowledge Base Wumpus world FOL Knowledge Base Deducing hidden properties Situation calculus Describing actions Describing actions cont d Planning Generating action sequences Summary on FOL Knowledge Engineer Populates KB with facts and relations Must study and understand domain to pick important objects and relationships Main steps Decide what to talk about Decide on vocabulary of predicates functions constants Encode general knowledge about domain Encode description of specific problem instance Pose queries to inference procedure and get answers Knowledge engineering vs programming Knowledge Engineering 1 2 3 4 Programming Choosing a logic Choosing programming language Building knowledge base Writing program Implementing proof theory Choosing writing compiler Inferring new facts Running program Why knowledge engineering rather than programming Less work just specify objects and relationships known to be true but leave it to the inference engine to figure out how to solve a problem using the known facts Towards a general ontology Develop good representations for categories measures composite objects time space and change events and processes physical objects substances mental objects and beliefs Inference in First Order Logic Proofs extend propositional logic inference to deal with quantifiers Unification Generalized modus ponens Forward and backward chaining inference rules and reasoning program Completeness G del s theorem for FOL any sentence entailed by another set of sentences can be proved from that set Resolution inference procedure that is complete for any set of sentences Logic programming Proofs The three new inference rules for FOL compared to propositional logic are Universal Elimination UE for any sentence variable x and ground term x e g from x Likes x Candy and x Joe x we can infer Likes Joe Candy Existential Elimination EE for any sentence variable x and constant symbol k not in KB x e g from x Kill x Victim we can infer x k Kill Murderer Victim if Murderer new symbol Existential Introduction EI for any sentence variable x not in and ground term g in e g from Likes Joe Candy we can infer x g x x Likes x Candy Generalized Modus Ponens GMP Forward chaining Backward chaining Resolution Resolution inference rule Resolution proof Logical reasoning systems Theorem provers and logic programming languages Production systems Frame systems and semantic networks Description logic systems Logical reasoning systems Theorem provers and logic programming languages Provers use resolution to prove sentences in full FOL Languages use backward chaining on restricted set of FOL constructs Production systems based on implications with consequents interpreted as action e g insertion deletion in KB Based on forward chaining conflict resolution if several possible actions Frame systems and semantic networks objects as nodes in a graph nodes organized as taxonomy links represent binary relations