1、智能计算研究中心 Artificial intelligence part 3 Knowledge and reasoning Autumn 2012Instructor: Wang XiaolongHarbin Institute of Technology, Shenzhen Graduate SchoolIntelligent Computation Research Center(HITSGS ICRC)智能计算研究中心VII. Logical AgentsAutumn 2012Instructor: Wang XiaolongHarbin Institute of Technolog
2、y, Shenzhen Graduate SchoolIntelligent Computation Research Center(HITSGS ICRC)3Outline 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 chain
3、ing resolution4Knowledge-Based AgentAgent that uses prior or acquired knowledge to achieve its goalsCan make more efficient decisionsCan make informed decisionsKnowledge Base (KB): contains a set of representations of facts about the Agents environmentEach representation is called a sentence Use som
4、e knowledge representation language, to TELL it what to know e.g., (temperature 72F)Then it can Ask itself what to do - answers should follow from the KBAgent can use inference to deduce new facts from TELLed factsKnowledge BaseInference engineDomain independent algorithmsDomain specific contentTELL
5、ASK5Generic 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.6Wumpus World PEAS descriptionPerformance measure gold +1000, death -1000 -1 per step, -10 f
6、or using the arrowEnvironment Squares adjacent to wumpus are smelly Squares adjacent to pit are breezy Glitter iff gold is in the same square Shooting kills wumpus if you are facing it Shooting uses up the only arrow Grabbing picks up gold if in same square Releasing drops the gold in same squareSen
7、sors: Stench, Breeze, Glitter, Bump, ScreamActuators: Left turn, Right turn, Forward, Grab, Release, Shoot7Wumpus world characterizationFully Observable? No only local perceptionDeterministic? Yes outcomes exactly specified Episodic? No sequential at the level of actionsStatic? Yes Wumpus and Pits d
8、o not moveDiscrete? YesSingle-agent? Yes Wumpus is essentially a natural feature8Exploring a Wumpus worldA= AgentB= BreezeS= SmellP= PitW= WumpusOK = SafeV = VisitedG = Glitter9Exploring a Wumpus worldA= AgentB= BreezeS= SmellP= PitW= WumpusOK = SafeV = VisitedG = Glitter10Exploring a Wumpus worldA=
9、 AgentB= BreezeS= SmellP= PitW= WumpusOK = SafeV = VisitedG = Glitter11Exploring a Wumpus worldA= AgentB= BreezeS= SmellP= PitW= WumpusOK = SafeV = VisitedG = Glitter12Exploring a Wumpus worldA= AgentB= BreezeS= SmellP= PitW= WumpusOK = SafeV = VisitedG = Glitter13Exploring a Wumpus worldA= AgentB=
10、BreezeS= SmellP= PitW= WumpusOK = SafeV = VisitedG = Glitter14Exploring a Wumpus worldA= AgentB= BreezeS= SmellP= PitW= WumpusOK = SafeV = VisitedG = Glitter15Exploring a Wumpus worldA= AgentB= BreezeS= SmellP= PitW= WumpusOK = SafeV = VisitedG = Glitter16Other tight spots17Another example solutionN
11、o perception 1,2 and 2,1 OKMove to 2,1B in 2,1 2,2 or 3,1 P?1,1 V no P in 1,1Move to 1,2 (only option) 18Example solutionS and No S when in 2,1 1,3 or 1,2 has W1,2 OK 1,3 WNo B in 1,2 2,2 OK & 3,1 P19Logic in generalLogics are formal languages for representing information such that conclusions can b
12、e 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 arithmetic x+2 y is a sentence; x2+y is not a sentence x+2 y is true iff the number x+2 is no less than the number y x+2 y is true in a world
13、 where x = 7, y = 1 x+2 y is false in a world where x = 0, y = 620Entailment Entailment 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 true E.g., the KB containing “the Giants won” and “the Reds won” entails “Either th
14、e Giants won or the Reds won” E.g., x+y = 4 entails 4 = x+y Entailment is a relationship between sentences (i.e., syntax) that is based on semantics21ModelsLogicians typically think in terms of models, which are formally structured worlds with respect to which truth can be evaluatedWe say m is a mod
15、el of a sentence if is true in mM() is the set of all models of Then KB iff M(KB) M() E.g. KB = Giants won and Redswon , = Giants won22Entailment in the wumpus world Situation after detecting nothing in 1,1, moving right, breeze in 2,1 Consider possible models for KB assuming only pits 3 Boolean cho
16、ices 8 possible models23Wumpus models24Wumpus modelsKB = wumpus-world rules + observations25Wumpus modelsKB = wumpus-world rules + observations 1 = 1,2 is safe, KB 1, proved by model checking26Wumpus modelsKB = wumpus-world rules + observations27Wumpus modelsKB = wumpus-world rules + observations 2
17、= 2,2 is safe, KB 228InferenceKB i = sentence can be derived from KB by procedure i Soundness: i is sound if whenever KB i , it is also true that KB Completeness: i is complete if whenever KB , it is also true that KB i 29Logic as a representation of the WorldSentencesSentencesEntailsFactsFactsFollo
18、wsSemanticsSemanticsRepresentationWorld Sentence are physical configurations of the agent, and reasoning is a process of constructing new physical configurations from old ones. Logical reasoning should ensure that the new configurations represent aspects of the world that actually follow from the as
19、pects that the old configurations represent.30Propositional logic: Syntax Propositional logic is the simplest logic illustrates basic ideas The proposition symbols P1, P2 etc are sentences If S is a sentence, S is a sentence (negation) If S1 and S2 are sentences, S1 S2 is a sentence (conjunction) If
20、 S1 and S2 are sentences, S1 S2 is a sentence (disjunction) If S1 and S2 are sentences, S1 S2 is a sentence (implication) If S1 and S2 are sentences, S1 S2 is a sentence (biconditional)31Propositional logic: SemanticsEach model specifies true/false for each proposition symbolE.g. P1,2 P2,2 P3,1 fals
21、etruefalseWith these symbols, 8 possible models, can be enumerated automatically.Rules for evaluating truth with respect to a model m:Sis true iff S is false S1 S2 is true iff S1 is true and S2 is trueS1 S2 is true iff S1is true or S2 is trueS1 S2 is true iffS1 is false orS2 is true i.e., is false i
22、ff S1 is true andS2 is falseS1 S2is true iffS1S2 is true andS2S1 is trueSimple recursive process evaluates an arbitrary sentence, e.g.,P1,2 (P2,2 P3,1) = true (true false) = true true = true32Truth tables for connectives33Wumpus world sentencesLet Pi,j be true if there is a pit in i, j.Let Bi,j be t
23、rue if there is a breeze in i, j. P1,1B1,1B2,1 Pits cause breezes in adjacent squaresB1,1 (P1,2 P2,1)B2,1 (P1,1 P2,2 P3,1)34Truth tables for inference35Inference by enumeration Depth-first enumeration of all models is sound and complete For n symbols, time complexity is O(2n), space complexity is O(
24、n)36Logical equivalence Two sentences are logically equivalent iff true in same models: iff and 37Validity and satisfiabilityA sentence is valid if it is true in all models,e.g., True,A A, A A, (A (A B) BValidity is connected to inference via the Deduction Theorem:KB if and only if (KB ) is validA s
25、entence is satisfiable if it is true in some modele.g., A B, CA sentence is unsatisfiable if it is true in no modelse.g., AASatisfiability is connected to inference via the following:KB if and only if (KB ) is unsatisfiable - refutation38Proof methods Proof methods divide into (roughly) two kinds: A
26、pplication of inference rules Legitimate (sound) generation of new sentences from old Proof = a sequence of inference rule applicationsCan use inference rules as operators in a standard search algorithm Typically require transformation of sentences into a normal form Model checking truth table enume
27、ration (always exponential in n) improved backtracking, e.g., Davis-Putnam-Logemann-Loveland (DPLL) heuristic search in model space (sound but incomplete)e.g., min-conflicts-like hill-climbing algorithms39Inference Rules40Inference Rules41ResolutionConjunctive Normal Form (CNF) conjunction of disjun
28、ctions of literalsclausesE.g., (A B) (B C D)Resolution inference rule (for CNF):li lk, m1 mnli li-1 li+1 lk m1 mj-1 mj+1 . mn where li and mj are complementary literals. E.g., P1,3 P2,2, P2,2 P1,3Resolution is sound and complete for propositional logic42ResolutionSoundness of resolution inference ru
29、le: (li li-1 li+1 lk) li mj (m1 mj-1 mj+1 . mn)(li li-1 li+1 lk) (m1 mj-1 mj+1 . mn)43Conversion to CNFB1,1 (P1,2 P2,1)1.Eliminate , replacing with ( )( ).(B1,1 (P1,2 P2,1) (P1,2 P2,1) B1,1)2. Eliminate , replacing with .(B1,1 P1,2 P2,1) (P1,2 P2,1) B1,1)3. Move inwards using de Morgans rules and do
30、uble-negation:(B1,1 P1,2 P2,1) (P1,2 P2,1) B1,1)4. Apply distributivity law ( over ) and flatten:(B1,1 P1,2 P2,1) (P1,2 B1,1) (P2,1 B1,1)44Resolution algorithm Proof by contradiction, i.e., show KB unsatisfiable45Resolution exampleKB = (B1,1 (P1,2 P2,1) B1,1 = P1,246Forward and backward chainingHorn
31、 Form (restricted)KB = conjunction of Horn clauses (clauses with 1 positive literal) Horn clause = proposition symbol; or (conjunction of symbols) symbol E.g., C (B A) (C D B)Modus Ponens (for Horn Form): complete for Horn KBs1, ,n,1 n Can be used with forward chaining or backward chaining.These alg
32、orithms are very natural and run in linear time47Forward chaining Idea: find any rule whose premises are satisfied in the KB, add its conclusion to the KB, until query is found48Forward chaining algorithm Forward chaining is sound and complete for Horn KB49Forward chaining example50Forward chaining
33、example51Forward chaining example52Forward chaining example53Forward chaining example54Forward chaining example55Forward chaining example56Forward chaining example57Proof of completeness FC derives every atomic sentence that is entailed by KB1.FC reaches a fixed point where no new atomic sentences a
34、re derived2.Consider the final state as a model m, assigning true/false to symbols3.Every clause in the original KB is true in m a1 ak b4.Hence m is a model of KB5.If KB q, q is true in every model of KB, including m58Backward chainingIdea: work backwards from the query q:to prove q by BC,check if q
35、 is known already, orprove by BC all premises of some rule concluding qAvoid loops: check if new subgoal is already on the goal stackAvoid repeated work: check if new subgoal1. has already been proved true, or2. has already failed59Backward chaining example60Backward chaining example61Backward chain
36、ing example62Backward chaining example63Backward chaining example64Backward chaining example65Backward chaining example66Backward chaining example67Backward chaining example68Backward chaining example69Forward vs. backward chaining FC is data-driven, automatic, unconscious processing, e.g., object r
37、ecognition, routine decisions May do lots of work that is irrelevant to the goal BC is goal-driven, appropriate for problem-solving, e.g., Where are my keys? How do I get into a PhD program? Complexity of BC can be much less than linear in size of KB70Efficient propositional inferenceTwo families of
38、 efficient algorithms for propositional inference: Based on backtracking search Based on hillclimbing searchComplete backtracking search algorithms DPLL algorithm (Davis, Putnam, Logemann, Loveland)Incomplete local search algorithms WalkSAT algorithm71The DPLL algorithmDetermine if an input proposit
39、ional logic sentence (in CNF) is satisfiable.A recursive depth-first enumeration of possible models.Improvements over truth table enumeration:1.Early terminationA clause is true if any literal is true.A sentence is false if any clause is false.2.Pure symbol heuristicPure symbol: always appears with
40、the same sign in all clauses. e.g., In the three clauses (A B), (B C), (C A), A and B are pure, C is impure. Make a pure symbol literal true.3.Unit clause heuristicUnit clause: only one literal in the clauseThe only literal in a unit clause must be true.72The DPLL algorithm73The WalkSAT algorithm In
41、complete, local search algorithm Evaluation function: The min-conflict heuristic of minimizing the number of unsatisfied clauses Balance between greediness and randomness74The WalkSAT algorithm75Hard satisfiability problems Consider random 3-CNF sentences. e.g.,(D B C) (B A C) (C B E) (E D B) (B E C
42、)m = number of clauses n = number of symbols Hard problems seem to cluster near m/n = 4.3 (critical point)76Hard satisfiability problems77Hard satisfiability problems Median runtime for 100 satisfiable random 3-CNF sentences, n = 5078Inference-based agents in the wumpus worldA wumpus-world agent usi
43、ng propositional logic:P1,1 W1,1 Bx,y (Px,y+1 Px,y-1 Px+1,y Px-1,y) Sx,y (Wx,y+1 Wx,y-1 Wx+1,y Wx-1,y)W1,1 W1,2 W4,4 W1,1 W1,2 W1,1 W1,3 64 distinct proposition symbols, 155 sentences7980Expressiveness limitation of propositional logic KB contains physics sentences for every single square For every
44、time t and every location x,y,Lx,y FacingRight t Forward t Lx+1,y Rapid proliferation of clausest81SummaryLogical agents apply inference to a knowledge base to derive new information and make decisionsBasic concepts of logic: syntax: formal structure of sentences semantics: truth of sentences wrt mo
45、dels entailment: necessary truth of one sentence given another inference: deriving sentences from other sentences soundness: derivations produce only entailed sentences completeness: derivations can produce all entailed sentencesWumpus world requires the ability to represent partial and negated information, reason by cases, etc.Resolution is complete for propositional logicForward, backward chaining are linear-time, complete for Horn clausesPropositional logic lacks expressive power82Assignments Ex 7.4,7.12, 7.17.
