Guest Speaker CS 416 Artificial Intelligence Topics in Optimal Control Minimax Control and Game Theory March 28th 2 p m OLS 005 Onesimo Hernandez Lerma Department of Mathematics CINVESTAV IPN Mexico City Lecture 13 First Order Logic Chapter 8 This is a nontechnical introduction mainly thru examples to some recent topics in control and game theory including adaptive control minimax control a k a worst case control or games against nature partially observable systems a k a controlled hidden Markov models cooperative and noncooperative game equilibria etc First order logic Diagnostic Rules Rules leading from observed effects to hidden causes We saw how propositional logic can create intelligent behavior After you ve observed something this rule offers an explanation These rules explain what happened in the past Breezy implies pits But propositional logic is a poor representation for complex environments Not breezy implies no pits Combining First order logic is a more expressive and powerful representation Causal Rules Causal Rules Some hidden property causes percepts to be generated The causal rules formulate a model Knowledge of how the environment operates Model can be very useful and important and replace straightforward diagnostic approaches These are predictions of perceptions you expect to have in the future given current conditions A pit causes adjacent squares to be breezy If all squares adjacent to a square a pitless it will not be breezy Page 1 Conclusion Discussion of models If the axioms correctly and completely describe the way the world works and the way percepts are produced then any complete logical inference procedure will infer the strongest possible description of the world state given the available percepts The agent designer can focus on getting the knowledge right without worrying about the processes of deduction Let s think about how we use models every day Daily stock prices Seasonal stock prices Seasonal temperatures Annual temperatures Knowledge Engineering Identify the task Understand a particular domain What is the range of inputs and outputs How does stock trading work Will the stock trading system have to answer questions about the weather Learn what concepts are important in the domain features Perhaps if you re buying wheat futures Must the agent store daily temperatures or can it use another agent Buyer confidence strength of the dollar company earnings interest rate Create a formal representation of the objects and relations in the domain Forall stocks price low confidence high profitability high Assemble the relevant knowledge Formalize the knowledge You know what information is relevant How can you accumulate the information Decide on vocabulary of predicates functions and constants Not formal description of knowledge at this point Just principled understanding of where information resides Beginning to map domain into a programmatic structure You re selecting an ontology A particular theory of how the domain can be simplified and represented at its basic elements Mistakes here cause big problems Page 2 Encode general knowledge Map to this particular instance Write down axioms for all vocabulary terms Encode a description of the specific problem instance Define the meaning of terms Should be an easy step Write simple atomic sentences Errors will be discovered and knowledge assembly and formalization steps repeated Derived from sensors percepts Derived from external data Use the knowledge base Debug the knowledge base Pose queries and get answers There will most likely be bugs Use inference procedure Derive new facts If inference engine works bugs will be in knowledge base Missing axioms Axioms that are too weak Conflicting axioms Enough talk let s get to the meat Propositional Inference Chapter 9 Inference in First Order Logic We already know how to perform inference in propositional logic Transform first order logic to propositional logic First order logic makes powerful use of variables We want to use inference to answer any answerable question stated in first order logic Universal quantification for all x Existential quantification there exists an x Page 3 Converting universal quantifiers Converting existential quantifiers Universal Instantiation Example after substitution x John x Richard x Father John becomes Existential Instantiation Example There is some thing that is a crown and is on John s head Let s call it C1 becomes You can replace the variable with a constant symbol that does not appear elsewhere in the knowledge base The constant symbol is a Skolem constant We ve replaced the variable with all possible ground terms terms without variables Existential Instantiation Complete reduction Convert existentially quantified sentences Only perform substitution once Creates one instantiation There exists an x s t Kill x Victim Convert universally quantified sentences Someone killed the victim Maybe more than once person killed the victim Existential quantifier says at least one person was killer Creates all possible instantiations Use propositional logic to resolve Replacement is Every first order knowledge base and query can be propositionalized in such a way that entailment is preserved Kill Murderer Victim Trouble ahead A theorem of completeness Universal quantification with functions if a sentence is entailed by the original first order knowledge base then there is a proof involving just a finite subset of the propositional knowledge base What about Father Father Father John Isn t it possible to have infinite number of substitutions How well will the propositional algorithms work with infinite number of sentences We want to find that finite subset Page 4 First try proving the sentence with constant symbols Then add all terms of depth 1 Father Richard Then add all terms of depth 2 Father Father Richard Still more trouble The Halting Problem Alan Turing and Alonzo Church proved Completeness says that if statement is true in first order logic it will also be true in propositions You can write an algorithm that says yes to every entailed sentence but You no algorithm exists that says no to every nonentailed sentence But what happens if you ve been waiting for your proposition based algorithm to return an answer and it has been a while So if your entailment checking algorithm hasn t returned yes yet you cannot know if that s because the sentence is not entailed Entailment for first order logic is semi decidable Is the statement not true Is the