11Logical AgentsBurr H. SettlesCS-540, UW-Madisonwww.cs.wisc.edu/~cs540-1Summer 20032AnnouncementsHomework #1 is due today– You have up to 3 “late days”– Weekends only count as 1 late dayRead Chapter 8 in AI: A Modern Approachfor MondayProject proposals are due Monday, too3Review of Agent ArchitectureReal WorldAgentSensorsEffectorsReasoningModel of WorldActionsKnowledgeGoals/Utility4Recap of Agent PropertiesThe agent must be able to:– Represent states, actions, etc.– Incorporate new percepts– Update internal representation of world– Deduce possibly unobservable properties of world– Decide on appropriate actions, etc…One of the core issues in developing intelligent agents is that of knowledge:– How to represent knowledge– How to reason using that knowledge5Knowledge BasesA knowledge base is:– The domain-specific content for an agent– A set of representations of facts about the world– A set of sentences in a formal languageBuilding a knowledge base:– Learning: agent discovers what it knows– Telling: agent is given what it knows (declarative)6Knowledge-Based AgentsMain actions of knowledge-based agents:– Tell information to the KB in the form of percept– Ask the KB what to do in the form of actionAn inference engine is composed of domain-independent algorithms that are used to determine what follows from the knowledge baseAnswers should follow from KB… the Agent shouldn’t just make things up!27Knowledge-Based AgentsViews of a knowledge-based agent:– Knowledge level:what agent knows at high level– Logic level:level of sentence encoding– Implementation level:level that runs on the architecture,detail of data structures and algorithmsWhat we’ll bediscussing today8General LogicLogics are formal languages for representingknowledge from which conclusions can be drawnSyntax specifies symbols and how they are combined to form sentences in the languagee.g. arithmetic: 2 ×××× x < y is a sentence, 2××××<xy is notSemantics specifies what world facts a sentence refers to, and how to assign truth value to sentencee.g. 2 ×××× x < y means:• Is true if & only if the number 2 × x is less than the number y• Is true in a world where x = 11, y = 33• Is false in a world where x = 3, y = 49General LogicLogics are characterized by what they consider to be “primitives”degree of belief 0…1degree of truthFuzzydegree of belief 0…1factsProbability Theorytrue/false/unknownfacts, objects, relations, timesTemporaltrue/false/unknownfacts, objects, relationsFirst-Ordertrue/false/unknownfacts (propositions)PropositionalAvailable KnowledgePrimitivesLogic10General LogicRecall that the agent internally represents its world/environment in its knowledge baseSentencesFactsrepresentation in agentworld/environmentSentences are representations in some languageFacts are claims about the world that are true/false11General LogicSentences represent facts in the worldSentencesFactsrepresentation in agentworld/environmentSemanticsSemantics connect sentences with factsA sentence is true if what it represents is actually the case in the real world12General LogicIn human reasoning, we try to take known facts and deduce new facts from them, to arrive at logical conclusions that are also factsThe agent, however, only knows sentences, which are representations of facts… so it must generate new sentences from old onesWe must be careful that the sentences generated by the agent actually follow from the KB!313General Logicrepr.worldKnowledgeSentencesConclusionSentenceinferfollowsFacts FactProper reasoning ensures that conclusions inferred from the KB are consistent with reality– That is, conclusions represent facts that actually follow from the facts in the KB14General LogicComputers don’t know the semantics (meaning)!So we need a mechanical inference procedure that derives conclusion sentences without needing to know the meanings of sentencesrepr.worldKnowledge ConclusioninferfollowsFacts Factentails15EntailmentKB The knowledge base KB is said to entailif and only if is true in all worlds where KB is true is true no matter what KB’s interpretation is: meaning is now meaningless!For example:– KB: “sky is blue,” “grass is green”– Entails: “sky is blue and grass is green”16Interpretations and ModelsAn interpretation is a formally structured world from which a sentence’s truth can be determined– Assign truth values to symbols in sentenceA model for a sentence is any world under a particular interpretation where that sentence is true– m is a model of sentence if is true in m– M() is the set of all models of – Then KB if and only if M(KB)are also M()17Logical InferenceAn inference procedure can:– Generate new sentences entailed by KB– Determine whether or not a given sentence is entailed by KB (i.e. “prove” )KBiSentence can be derived from KB bysome inference procedure i18Logical InferenceSoundness:Inference procedure i is sound ifwhenever KBi, it is also true that KB An inference procedure that derives only entailed sentences is called sound or truth-preservingInference produces only real entailments,i.e. any sentence that follows deductivelyfrom true premises is itself true419Logical InferenceCompleteness:Inference procedure i is complete ifwhenever KB , it is also true thatKBiInference should produce all entailments, i.e. all true sentences can be derived from the true premises20Our GoalWe want to define a simple logic that is expressive enough to say anything of interest, but also has a sound and complete inference procedureThis will allow an agent to answer questions whose answers follow from the KBThe fundamental problem of designing logical languages is the tradeoff between their expressiveness (power) and its tractability(efficiency) for knowledge and reasoning21Propositional Logic (PL)A very simple but useful logicSyntax of PL:– Proposition symbols P1, P2, etc. are sentences– If S is a sentence ¬¬¬¬S is a sentence– If S1and S2are sentences, S1∧∧∧∧S2is a sentence– If S1and S2are sentences, S1∨∨∨∨S2is a sentence– If S1and S2are sentences, S1S2is a sentence– If S1and S2are sentences, S1⇔⇔⇔⇔S2is a sentence22Propositional Logic (PL)Models specify truth value for