Knowledge Based ReasoningKnowledge-Based AgentGeneric knowledge-based agentLogic in generalTypes of logicEntailmentInferenceValidity and satisfiabilityPropositional logic: semanticsPropositional inference: normal formsProof methodsInference rulesLimitations of Propositional LogicFirst-order logic (FOL)Universal quantification (for all): Existential quantification (there exists): Properties of quantifiersExample sentencesHigher-order logic?Using the FOL Knowledge BaseWumpus world, FOL Knowledge BaseDeducing hidden propertiesSituation calculusDescribing actionsDescribing actions (cont’d)PlanningGenerating action sequencesSummary on FOLKnowledge EngineerKnowledge engineering vs. programmingTowards a general ontologyInference in First-Order LogicProofsGeneralized Modus Ponens (GMP)Forward chainingBackward chainingResolutionResolution inference ruleResolution proofLogical reasoning systemsSlide 41Fuzzy set operatorsWhat we have so farSearch vs. planningTypes of plannersA Simple Planning AgentSTRIPS operatorsPartially ordered plansPlanPOP algorithm sketchPOP algorithm (cont.)Warren McCulloch and Walter Pitts (1943)Multi-layer Perceptron ClassifierBayes’ ruleExampleKnowledge Based ReasoningCS101FALL 2007Lecture for Chapter 7Knowledge-Based Agent•Agent that uses prior or acquired knowledge to achieve its goals–Can make more efficient decisions–Can make informed decisions•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 factsKnowledge BaseInference engineDomain independent algorithmsDomain specific contentTELLASKGeneric knowledge-based agent1. TELL KB what was perceivedUses a KRL to insert new sentences, representations of facts, into KB2. ASK KB what to do.Uses logical reasoning to examine actions and select best.Logic in generalTypes of logicEntailmentInferenceValidity and satisfiability TheoremPropositional logic: semanticsPropositional inference: normal forms“sum of products of simple variables ornegated simple variables”“product of sums of simple variables ornegated simple variables”Proof methodsInference rulesLimitations of Propositional Logic1. 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 rules2. 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-baseInference becomes intractableFirst-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 objectUniversal 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 PIn(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 PIn(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 quantifiersExample 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 BaseWumpus world, FOL Knowledge BaseDeducing hidden propertiesSituation calculusDescribing actionsDescribing actions (cont’d)PlanningGenerating action sequencesSummary on FOLKnowledge Engineer•Populates KB with facts and relations•Must study and understand domain to pick important objects and relationships•Main steps:Decide what to talk aboutDecide on vocabulary of predicates, functions & constantsEncode general knowledge about domainEncode description of specific problem instancePose queries to inference procedure and get answersKnowledge engineering vs. programmingKnowledge Engineering Programming1. Choosing a logic Choosing programming language2. Building knowledge base Writing program3. Implementing proof theory Choosing/writing compiler4. Inferring new facts Running programWhy 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