Last update: March 4, 2010Logical agentsCMSC 421: Chapter 7CMSC 421: Chapter 7 1Outline♦ Knowledge-based agents♦ Wumpus world♦ Logic in general—models and entailment♦ Propositional (Boolean) logic♦ Equivalence, validity, satisfiability♦ Inference rules and theorem proving– forward chaining– backward chaining– resolutionCMSC 421: Chapter 7 2Knowledge basesInference engineKnowledge base domain−specific contentdomain−independent algorithmsKnowledge base = set of sentences in a formal languageDeclarative approach to building an agent (or other system):Tell it what it needs to knowThen it can Ask itself what to do—answers should follow from the KBAgents can be viewed at the knowledge leveli.e., what they know, regardless of how implementedOr at the implementation leveli.e., data structures in KB and algorithms that manipulate themCMSC 421: Chapter 7 3A simple knowledge-based agentfunction KB-Agent( percept) returns an actionstatic: KB, a knowledge baset, a counter, initially 0, indicating timeTell(KB, Make-Percept-Sentence( percept, t))action ← Ask(KB, Make-Action-Query(t))Tell(KB, Make-Action-Sentence(action, t))t ← t + 1return actionThe agent must be able to:Represent states, actions, etc.Incorporate new perceptsUpdate internal representations of the worldDeduce hidden properties of the worldDeduce appropriate actionsCMSC 421: Chapter 7 4Wumpus World PEAS descriptionEnvironment:One wumpus, one heap of goldP (pit) = 0.2 for each squareSquares next to wumpus are smellyShooting into wumpus’s square kills itShooting uses up the only arrowSquares next to pit are breezyGlitter iff the gold is in your squareGrabbing picks it upReleasing drops itBreeze BreezeBreezeBreezeBreezeStenchStenchBreezePITPITPIT1 2 3 41234STARTGoldStenchPerformance measure:gold +1000, death −1000, −1 per step, −10 for using the arrowActuators: Left turn, Right turn, Forward, Grab, Release, ShootSensors: Breeze, Glitter, SmellCMSC 421: Chapter 7 5Wumpus world characterizationFully observable?CMSC 421: Chapter 7 6Wumpus world characterizationFully observable? No—only local perceptionDeterministic?CMSC 421: Chapter 7 7Wumpus world characterizationFully observable? No—only local perceptionDeterministic? Yes—outcomes exactly specifiedEpisodic?CMSC 421: Chapter 7 8Wumpus world characterizationFully observable? No—only local perceptionDeterministic? Yes—outcomes exactly specifiedEpisodic? No—sequential at the level of actionsStatic?CMSC 421: Chapter 7 9Wumpus world characterizationFully observable? No—only local perceptionDeterministic? Yes—outcomes exactly specifiedEpisodic? No—sequential at the level of actionsStatic? Yes—Wumpus, pits, and gold do not moveDiscrete?CMSC 421: Chapter 7 10Wumpus world characterizationFully observable? No—only local perceptionDeterministic? Yes—outcomes exactly specifiedEpisodic? No—sequential at the level of actionsStatic? Yes—Wumpus, pits, and gold do not moveDiscrete? YesSingle-agent?CMSC 421: Chapter 7 11Wumpus world characterizationFully observable? No—only local perceptionDeterministic? Yes—outcomes exactly specifiedEpisodic? No—sequential at the level of actionsStatic? Yes—Wumpus, pits, and gold do not moveDiscrete? YesSingle-agent? Yes—Wumpus is essentially a natural featureCMSC 421: Chapter 7 12Exploring a wumpus worldAOKOKOKCMSC 421: Chapter 7 13Exploring a wumpus worldOKOK OKAABCMSC 421: Chapter 7 14Exploring a wumpus worldOKOK OKAABP?P?CMSC 421: Chapter 7 15Exploring a wumpus worldOKOK OKAABP?P?ASCMSC 421: Chapter 7 16Exploring a wumpus worldOKOK OKAABP?P?ASOKPWCMSC 421: Chapter 7 17Exploring a wumpus worldOKOK OKAABP?P?ASOKPWACMSC 421: Chapter 7 18Exploring a wumpus worldOKOK OKAABP?P?ASOKPWAOKOKCMSC 421: Chapter 7 19Exploring a wumpus worldOKOK OKAABP?P?ASOKPWAOKOKABGSCMSC 421: Chapter 7 20Other tight spotsAB OKOK OKABAP?P?P?P?Breeze in (1,2) and (2,1)⇒ no safe actionsP(pit in (2,2)) ≈ 0.86P(pits in (1,3) and (3,1)) ≈ 0.31In a later chapter we’ll seehow to compute thisASSmell in (1,1)⇒ cannot move safelyCan use a strategy of coercion:shoot straight aheadwumpus was there ⇒ dead ⇒ safewumpus wasn’t there ⇒ safeCMSC 421: Chapter 7 21Logic in generalLogics are formal languages for representing informationsuch that conclusions can be drawnSyntax defines the sentences in the languageSemantics define the “meaning” of sentences;i.e., define truth of a sentence in a worldE.g., the language of arithmeticx + 2 ≥ y is a sentence; x2 + y > is not a sentencex + 2 ≥ y is true iff the number x + 2 is at least as big as the number yx + 2 ≥ y is true in a world where x = 7, y = 1x + 2 ≥ y is false in a world where x = 0, y = 6CMSC 421: Chapter 7 22EntailmentEntailment means that one thing follows from another:KB |= αKnowledge base KB entails sentence αif and only ifα is true in all worlds where KB is trueE.g., if a KB contains “Maryland won” and “Duke won”,the KB entails “Maryland won or* Duke won”E.g., x + y = 4 entails 4 = x + yEntailment is a relationship between sentences (i.e., syntax)that is based on semanticsNote: brains process syntax (of some sort)*The “or” is inclusive, not exclusive.CMSC 421: Chapter 7 23ModelsA model is a formally structured world in which truth can be evaluatedWe say m is a model of a sentence α if α is true in mM(α) is the set of all models of αThen KB |= α if and only if M(KB) ⊆ M(α)E.g. KB = Maryland won and Duke wonα = Maryland wonM( )M(KB)xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxM(α)M(KB)CMSC 421: Chapter 7 24Entailment in the wumpus worldSituation after detecting nothing in [1,1],moving right, breeze in [2,1]For now, ignore the wumpus and gold.Which of the ?s are pits?For each possible combination of pitlocations, check whether it’s a model.3 Boolean choices ⇒ 8 possible modelsAAB???CMSC 421: Chapter 7 25Wumpus modelsAAB???1 2 312BreezePIT1 2 312BreezePIT1 2 312BreezePIT PITPIT1 2 312BreezePITPIT1 2 312BreezePIT1 2 312BreezePITPIT1 2 312BreezePIT PIT1 2 312BreezeKB = wumpus-world rules + observationsEight possible combinations of pit locations: which ones are models of KB?CMSC 421: Chapter 7 26Wumpus modelsAAB???1 2 312BreezePIT1 2 312BreezePIT1 2 312BreezePIT PITPIT1 2 312BreezePITPIT1 2 312BreezePIT1 2 312BreezePITPIT1 2 312BreezePIT PIT1 2 312BreezeKBKB = wumpus-world rules + observationsThree modelsCMSC 421: Chapter 7 27Wumpus modelsAAB???1 2 312BreezePIT1 2 312BreezePIT1 2 312BreezePIT PITPIT1 2