CS计算机代考程序代写 Agent-based Systems

Agent-based Systems
Paolo Turrini
↸ www.dcs.warwick.ac.uk/~pturrini p.turrini@warwick.ac.uk

The plan for today
We have seen a way of modelling knowledge using set theory, both in single and multi agent situations.
Today and tomorrow we look at how to model this from a point of view of a reasoning agent
Knowledge Representation:
how to encode the state of the world in a logical language
worlds, actions, goals expressivity versus complexity
We focus on one agent only! (MAS languages: similar pattern)
KR is one of the most active sub-fields of AI, producing many useful results in many areas (e.g., automated medical diagnosis)
Paolo Turrini Knowledge Representation Agent-based Systems

Knowledge Representation An uncertain world
Paolo Turrini Knowledge Representation Agent-based Systems

The main reference
Stuart Russell and Peter Norvig
Artificial Intelligence: a modern approach
Chapters 7-9
Paolo Turrini Knowledge Representation Agent-based Systems

The Wumpus World
Paolo Turrini Knowledge Representation Agent-based Systems

The Wumpus World
Sensors Breeze, Glitter, Smell
Actuators Up, Down, Left, Right, Grab, Release, Shoot, Climb
Rewards 1000 escaping with gold, -1000 dying, -10 using arrow, -1 walking
Environment
Squares adjacent to Wumpus are smelly Squares adjacent to pit are breezy
Glitter i↵ gold is in the same square Shooting kills Wumpus if you are facing it Shooting uses up the only arrow
Grabbing picks up gold if in same square Releasing drops the gold in same square
Paolo Turrini
Knowledge Representation Agent-based Systems

Knowledge base
A set of sentences representing what the agent thinks about the world. ‘I am in [2,1]’
‘I am out of arrows’
‘I smell Wumpus’
‘I’d better not go forward’
We interpret it as what the agent knows,
but it works just fine for what the agent believes.
Paolo Turrini Knowledge Representation Agent-based Systems

Updating the knowledge base
What we TELL the knowledge base
What we ASK the knowledge base
function KB-Agent( percept) returns an action static: KB, a knowledge base
t, a counter, initially 0, indicating time
Tell(KB, Make-Percept-Sentence( percept, t)) action Ask(KB, Make-Action-Query(t)) Tell(KB, Make-Action-Sentence(action, t))
t t+1
return action
Paolo Turrini Knowledge Representation Agent-based Systems

Rational explorations
The starting state…
Paolo Turrini Knowledge Representation Agent-based Systems

Rational explorations
and what we know.
Paolo Turrini Knowledge Representation Agent-based Systems

Rational explorations
B stands for Breeze
Paolo Turrini Knowledge Representation Agent-based Systems

Rational explorations
Where is the pit?
We are ruling out one square!
Paolo Turrini Knowledge Representation Agent-based Systems

Rational explorations
S stands for smell What do we know?
Paolo Turrini Knowledge Representation Agent-based Systems

Rational explorations
Logic is the key!
Paolo Turrini Knowledge Representation Agent-based Systems

Rational explorations
The further we go the more we know
Paolo Turrini Knowledge Representation Agent-based Systems

Rational explorations
Gold!
Paolo Turrini Knowledge Representation Agent-based Systems

Rational explorations
We know the way out Game over
Paolo Turrini Knowledge Representation Agent-based Systems

Representing the Wumpus World
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].
Paolo Turrini Knowledge Representation Agent-based Systems

Representing the Wumpus World
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].
¬P1,1 ¬B1,1 B2,1
Paolo Turrini Knowledge Representation Agent-based Systems

Representing the Wumpus World
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].
¬P1,1 ¬B1,1 B2,1
“Pits cause breezes in adjacent squares”
Paolo Turrini Knowledge Representation Agent-based Systems

Representing the Wumpus World
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].
¬P1,1 ¬B1,1 B2,1
“Pits cause breezes in adjacent squares”
B1,1 , (P1,2 _ P2,1)
B2,1 , (P1,1 _ P2,2 _ P3,1)
“A square is breezy if and only if there is an adjacent pit”
Paolo Turrini Knowledge Representation Agent-based Systems

Expressivity: at what cost?
OK if we were only dealing with finite objects
But even then we would have to enumerate all the possibilities
Paolo Turrini Knowledge Representation Agent-based Systems

Expressivity: at what cost?
OK if we were only dealing with finite objects
But even then we would have to enumerate all the possibilities
Propositional Logic lacks expressive power
Paolo Turrini Knowledge Representation Agent-based Systems

First order logic
Massive increase of expressivity: we can use existential 9 and universal 8 quantifiers before sentences!
But there are costs, e.g., decidability: we don’t always have a way to establish whether a sentences is true or false.
We will see how to exploit the gains while limiting the costs
Paolo Turrini Knowledge Representation Agent-based Systems

Recall: Universal Instantiation
Every instantiation of a universally quantified sentence is entailed by it:
8v↵ ↵({v /g })
for any variable v and ground term g
Paolo Turrini Knowledge Representation Agent-based Systems

Recall: Universal Instantiation
Every instantiation of a universally quantified sentence is entailed by it:
8v↵ ↵({v /g })
for any variable v and ground term g
E.g., 8 x King(x) ^ Greedy(x) ) Evil(x) yields
King(Jo↵rey)^Greedy(Jo↵rey) ) Evil(Jo↵rey)
King(Aerys) ^ Greedy(Aerys) ) Evil(Aerys) King(Father(Jo↵rey))^Greedy(Father(Jo↵rey)) ) Evil(Father(Jo↵rey))
.
Paolo Turrini Knowledge Representation Agent-based Systems

Recall: Existential instantiation (EI)
For any sentence ↵, variable v, and constant symbol k
that does not appear elsewhere in the knowledge base:
9v↵ ↵({v /g })
Paolo Turrini Knowledge Representation Agent-based Systems

Recall: Existential instantiation (EI)
For any sentence ↵, variable v, and constant symbol k
that does not appear elsewhere in the knowledge base:
9v↵ ↵({v /g })
E.g.,9x Crown(x)^OnHead(x,John)yields
Paolo Turrini Knowledge Representation Agent-based Systems

Recall: Existential instantiation (EI)
For any sentence ↵, variable v, and constant symbol k
that does not appear elsewhere in the knowledge base:
9v↵ ↵({v /g })
E.g.,9x Crown(x)^OnHead(x,John)yields Crown(C1) ^ OnHead(C1, John)
Paolo Turrini Knowledge Representation Agent-based Systems

Recall: Existential instantiation (EI)
For any sentence ↵, variable v, and constant symbol k
that does not appear elsewhere in the knowledge base:
9v↵ ↵({v /g })
E.g.,9x Crown(x)^OnHead(x,John)yields Crown(C1) ^ OnHead(C1, John)
provided C1 is a new constant symbol, called a Skolem constant
Paolo Turrini Knowledge Representation Agent-based Systems

Recall: Existential instantiation contd.
UI can be applied several times to add new sentences; the new KB is logically equivalent to the old
Paolo Turrini Knowledge Representation Agent-based Systems

Recall: Existential instantiation contd.
UI can be applied several times to add new sentences;
the new KB is logically equivalent to the old
EI can be applied once to replace the existential sentence;
Paolo Turrini Knowledge Representation Agent-based Systems

Recall: Existential instantiation contd.
UI can be applied several times to add new sentences;
the new KB is logically equivalent to the old
EI can be applied once to replace the existential sentence; the new KB is not equivalent to the old,
Paolo Turrini Knowledge Representation Agent-based Systems

Recall: Existential instantiation contd.
UI can be applied several times to add new sentences;
the new KB is logically equivalent to the old
EI can be applied once to replace the existential sentence; the new KB is not equivalent to the old,
but is satisfiable i↵ the old KB was satisfiable
Paolo Turrini Knowledge Representation Agent-based Systems

KB with FOL
We can encode the KB at each particular time point using FOL
function KB-Agent( percept) returns an action static: KB, a knowledge base
t, a counter, initially 0, indicating time
Tell(KB, Make-Percept-Sentence( percept, t)) action Ask(KB, Make-Action-Query(t)) Tell(KB, Make-Action-Sentence(action, t))
t t+1
return action
Paolo Turrini Knowledge Representation Agent-based Systems

Representing the Wumpus World
You already know how to describe the WW in first order logic
Paolo Turrini Knowledge Representation Agent-based Systems

Representing the Wumpus World
You already know how to describe the WW in first order logic Percept (at given time), e.g., Percept([Stench,Breeze,Glitter],5) or
Percept([None, Breeze, None], 3)
Starting Knowledge Base, e.g., ¬AtGold(0)
Axioms to generate new knowledge from percepts, e.g., 8s,b,t Percept([s,b,Glitter],t) ) AtGold(t) Axioms to generate actions (plans) from KB, e.g.,
8t AtGold(t)^¬Holding(Gold,t) ) Action(Grab,t)
Paolo Turrini Knowledge Representation Agent-based Systems

Representing the Wumpus World
You already know how to describe the WW in first order logic Percept (at given time), e.g., Percept([Stench,Breeze,Glitter],5) or
Percept([None, Breeze, None], 3)
Starting Knowledge Base, e.g., ¬AtGold(0)
Axioms to generate new knowledge from percepts, e.g., 8s,b,t Percept([s,b,Glitter],t) ) AtGold(t)
Axioms to generate actions (plans) from KB, e.g.,
8t AtGold(t)^¬Holding(Gold,t) ) Action(Grab,t) Axioms from knowledge to knowledge, e.g.,
8t AtGold(t)^Action(Grab,t) ) Holding(Gold,t +1)
Paolo Turrini Knowledge Representation Agent-based Systems

Representing the Wumpus World
Perception 8s,b,t Percept([s,b,Glitter],t) ) AtGold(t)
Paolo Turrini Knowledge Representation Agent-based Systems

Representing the Wumpus World
Perception 8s,b,t Percept([s,b,Glitter],t) ) AtGold(t) Location At(Agent,s,t)
Paolo Turrini Knowledge Representation Agent-based Systems

Representing the Wumpus World
Perception 8s,b,t Percept([s,b,Glitter],t) ) AtGold(t) Location At(Agent,s,t)
Decision-making 8t AtGold(t) ) Action(Grab,t)
Paolo Turrini Knowledge Representation Agent-based Systems

Representing the Wumpus World
Perception 8s,b,t Percept([s,b,Glitter],t) ) AtGold(t) Location At(Agent,s,t)
Decision-making 8t AtGold(t) ) Action(Grab,t)
Internal reflection 8t AtGold(t)^¬Holding(Gold,t) ) Action(Grab,t), do we have gold already? (notice we cannot observe if we are holding gold, we need to track it)
Paolo Turrini Knowledge Representation Agent-based Systems

Representing the Wumpus World
Adjacent squares
8 x, y, a, b Adjacent([x, y], [a, b]) ,
(x = a ^ (y = b 1 _ y = b + 1)_ (y = b ^ (x = a 1 _ x = a + 1))
Paolo Turrini Knowledge Representation Agent-based Systems

Representing the Wumpus World
Adjacent squares
8 x, y, a, b Adjacent([x, y], [a, b]) ,
(x = a ^ (y = b 1 _ y = b + 1)_ (y = b ^ (x = a 1 _ x = a + 1))
“A square is breezy if and only if there is an adjacent pit” 8s ,Breezy(s) , 9r(Adjacent(r,s)^Pit(r))
Paolo Turrini Knowledge Representation Agent-based Systems

Representing the Wumpus World
We can go on and describe plans, causal rules, etc. But let’s do some reasoning now
Paolo Turrini Knowledge Representation Agent-based Systems

Facts and knowledge bases
‘Jo↵rey Baratheon is a king’
Paolo Turrini Knowledge Representation Agent-based Systems

Facts and knowledge bases
‘Jon Snow is a person’
Paolo Turrini Knowledge Representation Agent-based Systems

Facts and knowledge bases
‘Jon Snow is a king’
Paolo Turrini Knowledge Representation Agent-based Systems

Telling and Asking
Tell (KB , King (Jo↵rey ))
Paolo Turrini Knowledge Representation Agent-based Systems

Telling and Asking
Tell (KB , King (Jo↵rey )) Tell(KB,Person(Jon))
Paolo Turrini Knowledge Representation Agent-based Systems

Telling and Asking
Tell (KB , King (Jo↵rey )) Tell(KB,Person(Jon))
Tell(KB,8x King(x) ) Person(x))
Paolo Turrini Knowledge Representation Agent-based Systems

Telling and Asking
Tell (KB , King (Jo↵rey )) Tell(KB,Person(Jon))
Tell(KB,8x King(x) ) Person(x)) Ask(KB, 9xPerson(x)) is there a person?
Paolo Turrini Knowledge Representation Agent-based Systems

Telling and Asking
Tell (KB , King (Jo↵rey )) Tell(KB,Person(Jon))
Tell(KB,8x King(x) ) Person(x)) Ask(KB, 9xPerson(x)) is there a person? Askvar(KB,Person(x)) who is a person?
Paolo Turrini Knowledge Representation Agent-based Systems

Telling and Asking
Tell (KB , King (Jo↵rey ))
Tell(KB,Person(Jon))
Tell(KB,8x King(x) ) Person(x))
Ask(KB, 9xPerson(x)) is there a person? Askvar(KB,Person(x)) who is a person?
Askvar returns a list of substitutions: {x/Jo↵rey},{x/Jon}
Paolo Turrini Knowledge Representation Agent-based Systems

Substitutions
Definition
Given a sentence S and a substitution ,
Paolo Turrini Knowledge Representation Agent-based Systems

Substitutions
Definition
Given a sentence S and a substitution ,
S denotes the result of plugging into S; e.g.,
Paolo Turrini Knowledge Representation Agent-based Systems

Substitutions
Definition
Given a sentence S and a substitution ,
S denotes the result of plugging into S; e.g., S = Smarter(x,y)
Paolo Turrini Knowledge Representation Agent-based Systems

Substitutions
Definition
Given a sentence S and a substitution ,
S denotes the result of plugging into S; e.g., S = Smarter(x,y)
= {x/Tyrion,y/Jo↵rey}
Paolo Turrini Knowledge Representation Agent-based Systems

Substitutions
Definition
Given a sentence S and a substitution ,
S denotes the result of plugging into S; e.g., S = Smarter(x,y)
= {x/Tyrion,y/Jo↵rey}
S = Smarter(Tyrion,Jo↵rey)
Paolo Turrini Knowledge Representation Agent-based Systems

Substitutions
Definition
Given a sentence S and a substitution ,
S denotes the result of plugging into S; e.g., S = Smarter(x,y)
= {x/Tyrion,y/Jo↵rey}
S = Smarter(Tyrion,Jo↵rey)
Askvar(KB,S) returns some/all such that KB |= S
Paolo Turrini Knowledge Representation Agent-based Systems

Unification
8x King(x)^Greedy(x) ) Evil(x) King (Jo↵rey )
8y Greedy(y)
Paolo Turrini Knowledge Representation Agent-based Systems

Unification
8x King(x)^Greedy(x) ) Evil(x) King (Jo↵rey )
8y Greedy(y)
We can get the inference immediately if we can find a substitution matching the premises of the implication to the known facts.
Paolo Turrini Knowledge Representation Agent-based Systems

Unification
8x King(x)^Greedy(x) ) Evil(x) King (Jo↵rey )
8y Greedy(y)
We can get the inference immediately if we can find a substitution matching the premises of the implication to the known facts.
✓ = {x/Jo↵rey,y/Jo↵rey} works
Paolo Turrini Knowledge Representation Agent-based Systems

Unification
Unify(↵, ) returns ✓ if ↵✓ = ✓
Paolo Turrini Knowledge Representation Agent-based Systems

Unification
Unify(↵, ) returns ✓ if ↵✓ = ✓ pq✓
Knows (Jo↵rey , x ) Knows (Jo↵rey , x ) Knows (Jo↵rey , x ) Knows (Jon, x )
Knows (Jo↵rey , Sansa) Knows (y , Sansa)
Knows (y , Mother (Jo↵rey )) Knows (x , Mother (Jon))
Paolo Turrini
Knowledge Representation
Agent-based Systems

Unification
Unify(↵, ) returns ✓ if ↵✓ = ✓ pq✓
Knows (Jo↵rey , x ) Knows (Jo↵rey , x ) Knows (Jo↵rey , x ) Knows (Jon, x )
Knows (Jo↵rey , Sansa) {x /Sansa} Knows (y , Sansa)
Knows (y , Mother (Jo↵rey ))
Knows (x , Mother (Jon))
Paolo Turrini
Knowledge Representation
Agent-based Systems

Unification
Unify(↵, ) returns ✓ if ↵✓ = ✓ pq✓
Knows (Jo↵rey , x ) Knows (Jo↵rey , x ) Knows (Jo↵rey , x ) Knows (Jon, x )
Knows (Jo↵rey , Sansa) {x /Sansa}
Knows (y , Sansa) {x /Sansa, y /Jo↵rey } Knows (y , Mother (Jo↵rey ))
Knows (x , Mother (Jon))
Paolo Turrini
Knowledge Representation Agent-based Systems

Unification
Unify(↵, ) returns ✓ if ↵✓ = ✓ pq✓
Knows (Jo↵rey , x ) Knows (Jo↵rey , x ) Knows (Jo↵rey , x ) Knows (Jon, x )
Knows (Jo↵rey , Sansa) Knows (y , Sansa)
Knows (y , Mother (Jo↵rey )) Knows (x , Mother (Jon))
{x /Sansa}
{x /Sansa, y /Jo↵rey }
{y /Jo↵rey , x /Mother (Jo↵rey )}
Paolo Turrini
Knowledge Representation Agent-based Systems

Unification
Unify(↵, ) returns ✓ if ↵✓ = ✓ pq✓
Knows (Jo↵rey , x ) Knows (Jo↵rey , x ) Knows (Jo↵rey , x ) Knows (Jon, x )
Knows (Jo↵rey , Sansa) Knows (y , Sansa)
Knows (y , Mother (Jo↵rey )) Knows (x , Mother (Jon))
{x /Sansa}
{x /Sansa, y /Jo↵rey }
{y /Jo↵rey , x /Mother (Jo↵rey )} fail
Paolo Turrini
Knowledge Representation Agent-based Systems

Standardising apart
Knows(Jon,x) & Knows(x,Mother(Jon)) fails
Paolo Turrini Knowledge Representation Agent-based Systems

Standardising apart
Knows(Jon,x) & Knows(x,Mother(Jon)) fails Standardising apart eliminates overlap of variables, e.g.,
Knows(z17, Mother(Jon))
Paolo Turrini Knowledge Representation Agent-based Systems

Generalized Modus Ponens (GMP)
Definite clause:
disjunction of literals, exactly one of which positive
Paolo Turrini Knowledge Representation Agent-based Systems

Generalized Modus Ponens (GMP)
Definite clause:
disjunction of literals, exactly one of which positive e.g., (p1 ^ p2 ^ . . . ^ pn ) q)
Paolo Turrini Knowledge Representation Agent-based Systems

Generalized Modus Ponens (GMP)
Definite clause:
disjunction of literals, exactly one of which positive e.g., (p1 ^ p2 ^ . . . ^ pn ) q)
p10, p20, …, pn0, (p1^p2^…^pn )q) wherepi0✓=pi✓foralli q✓
Assuming all variables are universally quantified…
p10 is King(Jo↵rey)
p20 is Greedy(y)
✓ is {x/Jo↵rey, y/Jo↵rey} q✓ is Evil(Jo↵rey)
p1 is King(x) p2 is Greedy(x) q is Evil(x)
Paolo Turrini
Knowledge Representation
Agent-based Systems

Soundness of GMP
Need to show that
p10, …, pn0, (p1 ^…^pn )q)|=q✓ provided that pi0✓=pi✓ for all i
Lemma: If ‘ is definite clause, then ‘ |= ‘✓ by Universal Instantiation.
1 (p1^…^pn )q)|=(p1^…^pn )q)✓=(p1✓^…^pn✓)q✓)
2 p10, …, pn0 |=p10 ^…^pn0 |=p10✓^…^pn0✓
3 From 1 and 2, q✓ follows by ordinary Modus Ponens
Paolo Turrini Knowledge Representation Agent-based Systems

In this lecture
How to describe the world in logic Moving as a way to gather new facts Generalised modus ponens
Paolo Turrini Knowledge Representation Agent-based Systems

Related Posts