عامل های منطقی

عامل های منطقی

اسلاید 1: 1/29Logical Agents عاملهاي منطقيChapter 7 (Part 1)Modified by Vali Derhami

اسلاید 2: 2/29OutlineKnowledge-based agentsباز نمايي (ارائه) دانش و فرايند هاي استدلال هسته اصلي هوش مصنوعيكار برد در محيط هاي نيمه رويت پذيرانعطاف پذيريWumpus worldLogic in general - models and entailmentعمده ترين ابزار بازنمايي دانش. دانش عاملهاي منطقي Propositional (Boolean) logicEquivalence, validity, satisfiabilityInference rules and theorem provingforward chainingbackward chainingresolution

اسلاید 3: 3/29Knowledge basesKnowledge base = set of sentences in a formal languageDeclarative approach (روش اظهاري)to building an agent (or other system):Tell it what it needs to know(اضافه كردن دانش جديد به عامل)Then 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 them

اسلاید 4: 4/29A simple knowledge-based agentThe agent must be able to:Represent states, actions, etc.Incorporate (بهم پيوستن)new perceptsUpdate internal representations of the worldDeduce (استنباط يا نتيجه گرفتن)hidden properties of the worldDeduce appropriate actions

اسلاید 5: 5/29Wumpus World PEAS descriptionPerformance measuregold +1000, death -1000-1 per step, -10 for using the arrowEnvironmentمكانهاي طلا و ومپوز(بجز مربع شروع) بصورت توزيع احتمال تصادفي يكنواخت انتخاب مي شوند، همچنين هر مربع بجز مربع شروع با احتمال 0.2مي تواند گودال باشد. اژدها بزرگتر از آن است كه در گودال بيفتد.Squares adjacent (مجاور ولي نه قطري)to wumpus are smelly(بد بو) Squares adjacent to pit (چاله) are breezy (نسيم دار)Glitter (درخشندگي) iff gold is in the same squareShooting kills wumpus if you are facing itShooting uses up the only arrowGrabbing (چنگ زدن)picks up gold if in same squareReleasing (رها كردن) drops the gold in same square

اسلاید 6: 6/29Wumpus World PEAS descriptionدر هر لحظه از زمان 5 مورد زير توسط سنسورهاي عامل به آن داده مي شود Sensors: [ Stench(بوي بد) , Breeze (نسيم) , Glitter (درخشش) , Bump(ضربه، وقتيكه عامل به ديوار ميخورد ) , Scream(جيغ، هرگاه تير به اژدها بخورد جيغي ميكشد كه در كل محيط شنيده مي شود) ][S, B, G, P, Sm]Actuators: Left turn, Right turn,Forward اگر ديوار جلوي عامل حركت به جلو بي اثر:Grab برداشتن شي در همان مربعي كه عامل هست:, Release رها كردن شي : Shoot: تير اندازي در خط مستقيم، تير به حركت ادامه تا به ديوار بخورد يا به اژدها عامل تنها يك تير دارد.

اسلاید 7: 7/29Wumpus world characterizationFully Observable No – only local perceptionDeterministic Yes – outcomes exactly specifiedEpisodic No – sequential at the level of actionsStatic Yes – Wumpus and Pits do not moveDiscrete YesSingle-agent? Yes – Wumpus is essentially a natural feature

اسلاید 8: 8/29Exploring a wumpus worldSensors: [S, B, G, P, Sm][ Stench, Breeze , Glitter Bump Scream]Sensors’ input in [1,1] = [ 0 0 0 0 0] شماره اول ستون و شماره دوم سطر است.Sensors’ input in [2,1] = [0 1 0 0 0]

اسلاید 9: 9/29Exploring a wumpus worldSensors: [S, B, G, P, Sm]Sensors’ input in [1,2] = [1 0 0 0 0]

اسلاید 10: 10/29Exploring a wumpus worldSensors: [S, B, G, P, Sm]Sensors’ input in [2,3] = [1 1 1 0 0]

اسلاید 11: 11/29Logic in generalLogics are formal languages for representing information such 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 no less than 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 = 6

اسلاید 12: 12/29Entailment ايجاب Entailment means that one thing follows from another: to mean that the sentence  entails the sentence KB ╞ αKnowledge base KB entails sentence α if and only if α is true in all worlds where KB is trueE.g., the KB containing “the Giants won” and “the Reds won” entails “Either the Giants won or the Reds won”E.g., x+y = 4 entails 4 = x+yEntailment is a relationship between sentences (i.e., syntax) that is based on semantics

اسلاید 13: 13/29ModelsLogicians typically think in terms of models, which are formally structured worlds with respect to 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 ╞ α iff M(KB)  M(α)E.g. KB = Giants won and Reds won α = Giants won

اسلاید 14: 14/29Entailment in the wumpus worldSituation after detecting nothing in [1,1], moving right, breeze in [2,1]Consider possible models for KB assuming only pits3 Boolean choices  8 possible models

اسلاید 15: 15/29Wumpus models

اسلاید 16: 16/29Wumpus modelsKB = wumpus-world rules + observationsتنها سه مدل كه در آن پايگاه دانش درست است.

اسلاید 17: 17/29Wumpus modelsKB = wumpus-world rules + observationsα1 = [1,2] is safe, KB ╞ α1, proved by model checking

اسلاید 18: 18/29Wumpus modelsKB = wumpus-world rules + observations

اسلاید 19: 19/29Wumpus modelsKB = wumpus-world rules + observationsα2 = [2,2] is safe, KB ╞ α2

اسلاید 20: 20/29InferenceKB ├i α = sentence α can be derived from KB by procedure iجمله α مي تواند از KB با الگوريتم استنتاج i بدست بيايد يابعبارت دیگر i ، α را از KB استخراج مي كند.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 α الگوريتم استناجي كامل است كه بتواند هر جمله ايجاب شدني را بدست آورد.Preview: we will define a logic (first-order logic) which is expressive enough to say almost anything of interest, and for which there exists a sound and complete inference procedure.That is, the procedure will answer any question whose answer follows from what is known by the KB.

اسلاید 21: 21/29Propositional logic: SyntaxPropositional logic is the simplest logic – illustrates basic ideasجملات اتمیک: عناصر نحوی غیر قابل تجزیه که با یک نماد گزاره ای نشان داده می شوند مانند PThe proposition symbols P1, P2 etc are sentencesfive connectives:If S is a sentence, S is a sentence (negation نقيض: )If S1 and S2 are sentences, S1  S2 is a sentence (conjunction)If 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)The order of precedence in propositional logic is (from highest to lowest):  , ,  , , and .

اسلاید 22: 22/29Propositional logic: Syntax

اسلاید 23: 23/29Propositional logic: Semanticsمعاني: قواعد تعيين درستي يك جمله نسبت به يك مدل خاص را تعريف ميكند.Each model specifies true/false for each proposition symbolE.g. P1,2 P2,2 P3,1 falsetruefalseWith 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 iffS1 is true andS2 is falseS1  S2is true iffS1S2 is true andS2S1 is trueSimple recursive process evaluates an arbitrary sentence, e.g.,P1,2  (P2,2  P3,1) = true  (true  false) = true  true = true

اسلاید 24: 24/29Truth tables for connectives

اسلاید 25: 25/29Wumpus world sentences یک پایگاه دانش ساده در این دنیاLet Pi,j be true if there is a pit in [i, j].Let Bi,j be true if there is a breeze in [i, j]. R1:  P1,1=True, گودالي در [1،1] وجود نداردR2:B1,1=True , نسیمی در خانه [1،1] وجود نداردR3:B2,1Pits cause breezes in adjacent squares“R4:B1,1  (P1,2  P2,1)R5:B2,1 (P1,1  P2,2  P3,1)

اسلاید 26: 26/29Truth tables for inferenceشرط برقراري KB ╞ α1:1 بايد درست باشد هرگاه KB در ست است. α1 = [1,2] is safe : P1,2=false and W1,2=False

اسلاید 27: 27/29Inference by enumeration استنتاج با بر شمردنDepth-first enumeration of all models is sound and complete For n symbols, time complexity is O(2n), space complexity is O(n)

اسلاید 28: 28/29Logical equivalenceTwo sentences are logically equivalent} iff true in same models: α ≡ ß iff α╞ β and β╞ α

اسلاید 29: 29/29Validity and satisfiability اعتبار و ارضا پذيريA 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 sentence is satisfiable if it is true in some modelse.g., A B, CA sentence is unsatisfiable if it is true in no modelse.g., AASatisfiability is connected to inference via the following:KB ╞ α if and only if (KB α) is unsatisfiable(اثبات با تناقض)