展开查看详情
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
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.
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
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.
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.
热门城市
