ITCS 3153 Artificial IntelligenceLogical AgentsWhy study knowledge-based agentsComponents of knowledge-based agentKnowledge RepresentationLogical ReasoningLogical inferenceInference AlgorithmsPropositional (Boolean) LogicComplex sentencesBackus-Naur Form (BNF)Slide 12Truth tableConcepts related to entailmentSomething to work onITCS 3153Artificial IntelligenceLecture 10Lecture 10Logical AgentsLogical AgentsChapter 7Chapter 7Lecture 10Lecture 10Logical AgentsLogical AgentsChapter 7Chapter 7Logical AgentsWhat are we talking about, “logical?”What are we talking about, “logical?”•Aren’t search-based chess programs logicalAren’t search-based chess programs logical–Yes, but knowledge is used in a very specific wayYes, but knowledge is used in a very specific wayWin the gameWin the gameNot useful for extracting strategies or understanding Not useful for extracting strategies or understanding other aspects of chessother aspects of chess•We want to develop more general-purpose knowledge We want to develop more general-purpose knowledge systems that support a variety of logical analysessystems that support a variety of logical analysesWhat are we talking about, “logical?”What are we talking about, “logical?”•Aren’t search-based chess programs logicalAren’t search-based chess programs logical–Yes, but knowledge is used in a very specific wayYes, but knowledge is used in a very specific wayWin the gameWin the gameNot useful for extracting strategies or understanding Not useful for extracting strategies or understanding other aspects of chessother aspects of chess•We want to develop more general-purpose knowledge We want to develop more general-purpose knowledge systems that support a variety of logical analysessystems that support a variety of logical analysesWhy study knowledge-based agentsPartially observable environmentsPartially observable environments•combine available information (percepts) with general knowledge to combine available information (percepts) with general knowledge to select actionsselect actionsNatural LanguageNatural Language•Language is too complex and ambiguous. Problem-solving agents are Language is too complex and ambiguous. Problem-solving agents are impeded by high branching factor.impeded by high branching factor.FlexibilityFlexibility•Knowledge can be reused for novel tasks. New knowledge can be Knowledge can be reused for novel tasks. New knowledge can be added to improve future performance.added to improve future performance.Partially observable environmentsPartially observable environments•combine available information (percepts) with general knowledge to combine available information (percepts) with general knowledge to select actionsselect actionsNatural LanguageNatural Language•Language is too complex and ambiguous. Problem-solving agents are Language is too complex and ambiguous. Problem-solving agents are impeded by high branching factor.impeded by high branching factor.FlexibilityFlexibility•Knowledge can be reused for novel tasks. New knowledge can be Knowledge can be reused for novel tasks. New knowledge can be added to improve future performance.added to improve future performance.Components of knowledge-based agentKnowledge BaseKnowledge Base•Store informationStore information–knowledge knowledge representationrepresentation language language•Add information (Add information (TellTell))•Retrieve information (Retrieve information (AskAsk))•Perform Perform inferenceinference–derive new derive new sentencessentences (knowledge) from existing (knowledge) from existing sentencessentencesKnowledge BaseKnowledge Base•Store informationStore information–knowledge knowledge representationrepresentation language language•Add information (Add information (TellTell))•Retrieve information (Retrieve information (AskAsk))•Perform Perform inferenceinference–derive new derive new sentencessentences (knowledge) from existing (knowledge) from existing sentencessentencesKnowledge RepresentationMust be syntactically and semantically correctMust be syntactically and semantically correctSyntaxSyntax•the formal specification of how information is storedthe formal specification of how information is stored–a + 2 = c (typical mathematical syntax)a + 2 = c (typical mathematical syntax)–a2y += (not legal syntax)a2y += (not legal syntax)SemanticsSemantics•the meaning of the informationthe meaning of the information–a + 2 = c (c must be 2 more than a)a + 2 = c (c must be 2 more than a)Must be syntactically and semantically correctMust be syntactically and semantically correctSyntaxSyntax•the formal specification of how information is storedthe formal specification of how information is stored–a + 2 = c (typical mathematical syntax)a + 2 = c (typical mathematical syntax)–a2y += (not legal syntax)a2y += (not legal syntax)SemanticsSemantics•the meaning of the informationthe meaning of the information–a + 2 = c (c must be 2 more than a)a + 2 = c (c must be 2 more than a)Logical ReasoningEntailmentEntailment•one sentence follows logically from anotherone sentence follows logically from another–a->ba->b–the sentence a entails the sentence bthe sentence a entails the sentence b•a->b if and only ifa->b if and only if–every model in which a is true, b is also trueevery model in which a is true, b is also trueEntailmentEntailment•one sentence follows logically from anotherone sentence follows logically from another–a->ba->b–the sentence a entails the sentence bthe sentence a entails the sentence b•a->b if and only ifa->b if and only if–every model in which a is true, b is also trueevery model in which a is true, b is also trueLogical inferenceEntailment permitted logicEntailment permitted logic•we inferred new knowledge from entailmentswe inferred new knowledge from entailmentsModel CheckingModel Checking•We enumerated all possibilities to ensure inference was We enumerated all possibilities to ensure inference was completecompleteEntailment permitted logicEntailment permitted logic•we inferred new knowledge from entailmentswe inferred new knowledge from entailmentsModel CheckingModel Checking•We enumerated all possibilities to ensure inference was We enumerated all possibilities to ensure inference was completecompleteInference AlgorithmsSoundSound•only entailed sentences are inferredonly entailed sentences are