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
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
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)
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)
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)
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✓
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…
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
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
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
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