003-agents that reason logiclly

This chapter is mainly about agents that reason logiclly, which mainly includes knowledge-based agents;propositional logic;wumpus world example;representation, reasoning, and logic and so on.
展开查看详情

1.

2. Presentation Outline 1 A Knowledge-Based Agent 2 Representation, Reasoning, and Logic 3 Propositional Logic 4 Wumpus World Example

3. Knowledge-Based Agents • Hold information about the world in a Knowledge Base (KB) • KB is built up of sentences. • KB contains background knowledge

4. Knowledge-Based Agents (2) Three levels we can describe them at: – Knowledge Level: What the agent actually knows. – Logical Level: A list of the sentences in the KB. – Implementation Level: The actual way the information is held in a data structure.

5. Presentation Outline 1 A Knowledge-Based Agent 2 Representation, Reasoning, and Logic 3 Propositional Logic 4 Wumpus World Example

6. Representation, Reasoning and Logic • Syntax: Describes the symbols in a language and how they can be used together. • Semantics: Gives meaning to the syntax. Defines how the symbols in the syntax relate to in the real world.

7. Representation, Reasoning, and Logic • Entailment: If x entails y, then if x is true y is true. • Proof Theory: The way in which the entailments work for a set of sentences.

8. Inference • Valid: A sentence that’s true in all situations. • Satisfiability: A sentence that is true in at least one situation. • Unsatisfiability: A sentence that isn’t satisfiable.

9. Inference in Computers • Computer programs can use valid or unsatisfiable sentences to create new sentences. • This is the basis of learning in logically reasoning agents. agents

10. Presentation Outline 1 A Knowledge-Based Agent 2 Representation, Reasoning, and Logic 3 Propositional Logic 4 Wumpus World Example

11. Propositional Logic (we covered) • Syntax • Sematics • Validity & Inference • Rules of Inference • Complexity of propositional Inference

12. Semantics • In BNF

13. Validity • A sentence is valid if it is true in all the cases. • The validity of a sentence can be tested in a truth table.

14. Inference • A sentence (Q) is inferred by a set of sentences {p1, p2, ... } if whenever Q is true, then {p1, p2, …} are all true.

15. Rules of Inference • Modus Ponens if α ⇒ β, α then β • And-Elimination if α1∧α2∧...∧αn then αi

16. Rules of Inference • And-Introduction if α1, α2, α3, …, αn then α1∧ α2∧ α3∧... ∧ αn • Or-Introduction if αi then α1∨ α2∨ α3∨... ∨ αn

17. Rules of Inference • Double Negation Elimination if ¬ ¬ α then α • Unit Resolution if α ∨ β, ¬β then α

18. Rules of Inference • Resolution if α ∨ β, ¬β ∨ γ then α ∨ γ

19. Complexity of Propositional inference • It was mentioned by Cook in 1971 that the complexity of propositional inference is NP-complete. – More precisely, it’s 2n. • Basically, we have to try all the combinations of the truth values of symbols in a sentence.

20.Inference

21. Presentation Outline 1 A Knowledge-Based Agent 2 Representation, Reasoning, and Logic 3 Propositional Logic 4 Wumpus World Example

22. Wumpus World Example • The Wumpus World Environment • Simple Logic • The agent acting in the wumpus world

23.Wumpus World

24. Wumpus World • In the squares directly adjacent to the Wumpus, the agent will perceive a stench. • In the square directly adjacent to a pit, the agent will perceive a breeze. • In the square where the gold is, the agent will perceive a glitter. • The agent dies a miserable death if it enters a square containing a pit or a live wumpus. • The agent can kill the wumpus if it shoots the only arrow into the square it is facing when the Wumpus is in that square.

25. Wumpus World • If the agent enters a square which has no pit or wumpus but has a wumpus next to it, a pit next to it and the gold in it, it will receive the percept[None, Stench, Breeze, Glitter]. • The agent’s goal is to find the gold and bring it back. • The agent uses logic, the percepts it receives and it’s current KB to learn about the world around it. • The agent adds to it’s KB this new information it learns and can now use it.

26. Simple logic • If the agent senses a stench, then it knows the WUMPUS must be in the front or left or right square. • If the agent feels a breeze, then it knows the PIT must be in the front or left or right square. • If the agent perceives a glitter, then it is in the square with the gold. • If the agent receives none, all directly adjacent squares are safe.

27. Logic in Wumpus World • The agent has sentences in it’s KB that correspond to the basic inferences it should be able to make. • For example in the KB it will have a sentence that if an agent in 1,1 senses a stench then 1,2 or 2,1 has a wumpus in it. • If in 1,1 the agent sense nothing then it will know that 1,2 2,1 and 1,1 all have neither a wumpus nor a pit in them.

28.Wumpus World

29. Logic Example in Wumpus World • Our agent starts in 1,1 and feels no stench. By the rule Modus Ponens and the built in knowledge in it’s KB, it can conclude that 1,2 and 2,1 do not have a wumpus. • Now by the rule And-Elimination we can see that 1,2 doesn’t contain a wumpus and neither does 2,1. • If our agent now moves to 2,1 it receives a percept telling it there is a breeze but no percept of a stench. Using Modus Ponens and And- Elimination we can conclude that 2,2 does not contain a wumpus, 1,1 does not contain a wumpus and 3,1 does not contain a wumpus. • If our agent now backtracks because it’s unsure of where a pit may be and moves to square 1,2. It senses a stench. By Modus Ponens this means that 1,1 1,3 or 2,2 contain a wumpus.