1) (FOL and situation calculus)
We need to represent and reason within the scenario defined by assignment 1.
For simplicity, we will assume that the amount of any specific
resource at a node cannot be more than 1, i.e. a node either contains
the resource or it does not.
a) Write down the axioms for the behavior of the world using FOL and
situation calculus. Assume only one agent.
Use the predicates:
Edge(e, v1, v2) ; e is an edge in the graph between v1 and v2.
Goal(v) ; The agent's goal is vertex v.
Also use the fluents (situation-dependent predicates)
Salt(v, s) ; Vertex v has salt in situation s.
Ice(e, s) ; Edge e has ice in situation s.
Water(v, s) ; Vertex v has water in situation s.
Fire(e, s) ; Edge e has fire in situation s.
Carrying(r, s) ; Agent is carrying resource type r in situation s.
Loc(v,s) ; Agent is at vertex v in situation s
Constants: as needed, including constants for the resource types:
Sa "salt", Wa for "water"
Functions: not needed here, except to denote actions:
move(e) ; Denotes a move action across edge e (may be ineffective).
load(r) ; Denotes loading (a single unit of) resource r.
and of course the "Result" function:
Result(a,s) ; Denotes the situation resulting from doing action a in
; situation s.
Add the facts representing the following scenario in situation S0.
Edge(E1, Vstart, Vmid)
Edge(E2, Vmid, Vend)
Edge(E3, Vmid, Vend)
Goal(Vmid)
; Situation S0
Water(Vstart, S0)
Salt(Vstart, S0)
Fire(E1, S0)
Ice(E2, S0)
not Carrying(Sa, S0)
not Carrying(Wa, S0)
Loc(Vstart, S0)
ANSWER: One way to do this is through successor-state axioms for
all fluents.
For Salt, Water, Ice, and Fire these can only become false, so
this is a special case.
Resources are there just when they have been there before, and have not been
picked up successfully (load can fail if agent not on location or carrying something).
1. forall v, a Salt(v, Result(a,s)) iff
Salt(v, s) and
(not a=load(Sa) or not Loc(v, s) or exists r Carrying(r,s))
2. forall v, a Water(v, Result(a,s)) iff
Water(v, s) and
(not a=load(Wa) or not Loc(v, s) or exists r Carrying(r,s))
Blockages are there just when they have been there before, and have not been
remove by an agent traversing the edge with an appropriate resource.
3. forall e, a Ice(e, Result(a,s)) iff
Ice(e, s) and
(not a=move(e) or not Carrying(Sa, s) or
not (exists u, v Edge(e, u, v) and (Loc(u, s) or Loc(v, s))))
4. forall e, a Fire(e, Result(a,s)) iff
Ice(e, s) and
(not a=move(e) or not Carrying(Wa, s) or
not (exists u, v Edge(e, u, v) and (Loc(u, s) or Loc(v, s))))
Note that we could save some duplication above if we define auxiliary predicates
such as:
AtEdge(e, s) <===> (exists u, v Edge(e, u, v) and (Loc(u, s) or Loc(v, s))
Now a successor-state axiom for the Carrying fluent: a resource is
being carried if it was carried before and we did not successfully
traverse an edge that uses it, or if we are at a location
that has the resource, and we are loading the resource successfully.
5. forall a, s, Carrying(Sa, Result(a,s)) iff
(Carrying(Sa, s) and
not (exists e, u, v Edge(e, u, v) and (Loc(u, s) or Loc(v, s)) and
a = move(e) and Ice(e,s))) or
(exists v Loc(v,s) and a=load(Sa) and Salt(v,s) and not Carrying(Wa,s))
6. forall a, s, Carrying(Wa, Result(a,s)) iff
(Carrying(Wa, s) and
not (exists e, u, v Edge(e, u, v) and (Loc(u, s) or Loc(v, s)) and
a = move(e) and Fire(e,s))) or
(exists v Loc(v,s) and a=load(Wa) and Water(v,s) and not Carrying(Sa,s))
Finally, as successor-state axiom for the Loc fluent: we are at v
if we were there and did not successfully move elsewhere, or if
we were elsewhere (u) and successfully moved to v.
7. forall v, s, a, Loc(v, Result(a,s)) iff
(Loc(v,s) and
(not exists e,u, a=move(e) and (Edge(e,u,v) or Edge(e,v,u))
and (Fire(e,s) => Carrying(Wa,s)) and (Ice(e,s) => Carrying(Wa,s))))
or (exists u, e a=move(e) and (Edge(e,u,v) or Edge(e,v,u)) and Loc(u,s)
and (Fire(e,s) => Carrying(Wa,s)) and (Ice(e,s) => Carrying(Sa,s))))
In some cases we will need to handle equality. For now assume
we add axioms:
Move actions are not equal to load actions (already in CNF):
NEQ1: forall x,y not load(x) = move(y)
A move action on e is equal to a move action on e:
EQ1: forall e move(e) = move(e)
A load action on r is equal to a load action on r:
EQ2: forall r load(r) = load(r)
Must also assume that only at most one of fire and ice are possible, i.e. (in CNF)
FNX: forall e, s not Fire(e,s) or not Ice(e,s)
For COMPLETE axiomatization of the domain need many additional
axioms, such as inequality of vertices:
NEQxx: not Vstart = Vmid
(many such "not equal" axioms)
Cannot be in more than one location in the same situation:
NLoc: forall s, v, u Loc(v,s) and Loc(u,s) => v=u
And also must state all the clear edges at S0! (Although in this particular
case we can get away without it).
b) Now, we need to find a sequence of actions that will result in reaching Vmid,
and prove a theorem that it will do so. Do the following steps:
A) Convert the knowledge base to conjunctive normal form.
Answer: the good thing about successor-state axioms is that they seem to
solve the frame problem. Unfortunately, they look bad when converting to CNF.
We will thus do only some of them.
For example, we will not need Axiom 1, but will show it for exercise.
To convert the Salt axiom 1 into CNF, first separate into 2, removing the iff:
1A: forall v, a not Salt(v, Result(a,s)) or
(Salt(v, s) and
(not a=load(Sa) or not Loc(v, s) or exists r Carrying(r,s)))
1B: forall v, a Salt(v, Result(a,s)) or not
(Salt(v, s) and
(not a=load(Sa) or not Loc(v, s) or exists r Carrying(r,s)))
In part A, we need to move the "exists r" and Skolemize, and remove the qantifiers:
1A: not Salt(v, Result(a,s)) or
(Salt(v, s) and
(not a=load(Sa) or not Loc(v, s) or Carrying(R-of(a,s),s)))
Which then gets split using distribtion, into:
1A1: not Salt(v, Result(a,s)) or Salt(v, s)
1A2: not Salt(v, Result(a,s)) or not a=load(Sa) or not Loc(v, s) or Carrying(R-of(a,s),s)
In part B, moving negation in we get:
1B: forall v, a Salt(v, Result(a,s)) or
(not Salt(v, s) or
(a=load(Sa) and Loc(v, s) and forall r not Carrying(r,s)))
We can now remove the quantifiers (note that r is now universally quantified,
so no Skolem function), and apply distribution to get the sentences:
1B1: Water(v, Result(a,s)) or not Water(v, s) or a=load(Wa)
1B2: Water(v, Result(a,s)) or not Water(v, s) or Loc(v, s)
1B3: Water(v, Result(a,s)) or not Water(v, s) or not Carrying(r,s)
Axiom 2 is exactly the same, so will not be shown, except for the final results:
2A1: not Water(v, Result(a,s)) or Water(v, s)
2A2: not Water(v, Result(a,s)) or not a=load(Wa) or not Loc(v, s) or Carrying(R1-of(a,s),s)
2B1: Water(v, Result(a,s)) or not Water(v, s) or a=load(Wa)
2B2: Water(v, Result(a,s)) or not Water(v, s) or Loc(v, s)
2B3: Water(v, Result(a,s)) or not Water(v, s) or not Carrying(r,s)
Note that when generating the Skolem function here for "exists r",
we need a NEW Skolem function with a differemt name from the previous one.
The axiom for Ice (3) is also split to get:
A: forall e, a not Ice(e, Result(a,s)) or
(Ice(e, s) and
(not a=move(e) or not Carrying(Sa, s) or
not (exists u, v Edge(e, u, v) and (Loc(u, s) or Loc(v, s)))))
B: forall e, a Ice(e, Result(a,s)) or
not (Ice(e, s) and
(not a=move(e) or not Carrying(Sa, s) or
not (exists u, v Edge(e, u, v) and (Loc(u, s) or Loc(v, s)))))
Processing A, moving negation in we get:
A: forall e, a not Ice(e, Result(a,s)) or
(Ice(e, s) and
(not a=move(e) or not Carrying(Sa, s) or
(forall u, v not Edge(e, u, v) or (not Loc(u, s) and not Loc(v, s)))))
As there are only universal quantifiers and no re-naming needed, we can drop
the quantifiers and do the last distributive step, to get:
3A1: not Ice(e, Result(a,s)) or Ice(e, s)
3A2: not Ice(e, Result(a,s)) or not a=move(e) or not Carrying(Sa, s) or
not Edge(e, u, v) or not Loc(u, s)
3A3: not Ice(e, Result(a,s)) or not a=move(e) or not Carrying(Sa, s) or
not Edge(e, u, v) or not Loc(v, s)
Processing B, we move negation in to get:
B: forall e, a Ice(e, Result(a,s)) or
(not Ice(e, s) or
(a=move(e) and Carrying(Sa, s) and
(exists u, v Edge(e, u, v) and (Loc(u, s) or Loc(v, s)))))
So we have existentially quantified u, v inside the scope of e, a and need
Skolem functions, call them U1-of(e,a) and V1-of(e,a), and now can remove quantifiers:
B: Ice(e, Result(a,s)) or
(not Ice(e, s) or
(a=move(e) and Carrying(Sa, s) and
(Edge(e, U1-of(e,a), V1-of(e,a)) and
(Loc(U1-of(e,a), s) or Loc(V1-of(e,a), s)))))
Applying distribution, we get the following sentences:
3B1: Ice(e, Result(a,s)) or not Ice(e, s) or a=move(e)
3B2: Ice(e, Result(a,s)) or not Ice(e, s) or Carrying(Sa, s)
3B3: Ice(e, Result(a,s)) or not Ice(e, s) or Edge(e, U1-of(e,a), V1-of(e,a))
3B4: Ice(e, Result(a,s)) or not Ice(e, s) or Loc(U1-of(e,a),s) or Loc(V1-of(e,a),s)
Axiom 4 looks exactly the same as 3, so will not be done here.
We will need the carrying Water axiom 6, and
begin by separating it into two, one in each direction of implication.
Will also convert the implication as we go:
forall a, s, Carrying(Wa, Result(a,s)) or
not ((Carrying(Wa, s) and
not (exists e, u, v Edge(e, u, v) and (Loc(u, s) or Loc(v, s)) and
a = move(e) and Fire(e,s))) or
(exists v Loc(v,s) and a=load(Wa) and Water(v,s) and not Carrying(Sa,s)))
and:
forall a, s, not Carrying(Wa, Result(a,s)) or
((Carrying(Wa, s) and
not (exists e, u, v Edge(e, u, v) and (Loc(u, s) or Loc(v, s)) and
a = move(e) and Fire(e,s))) or
(exists v Loc(v,s) and a=load(Wa) and Water(v,s) and not Carrying(Sa,s)))
Since we only need the first one, we will only do that. Moving negation in we get:
forall a, s, Carrying(Wa, Result(a,s)) or
((not Carrying(Wa, s) or
(exists e, u, v Edge(e, u, v) and (Loc(u, s) or Loc(v, s)) and
a = move(e) and Fire(e,s))) and
(forall v not Loc(v,s) or not a=load(Wa) or not Water(v,s) or Carrying(Sa,s)))
We can split this into 2 as well, for convenience:
A: forall a, s, Carrying(Wa, Result(a,s)) or
((not Carrying(Wa, s) or
(exists e, u, v Edge(e, u, v) and (Loc(u, s) or Loc(v, s)) and
a = move(e) and Fire(e,s)))
B: forall a, s, Carrying(Wa, Result(a,s)) or
(forall v not Loc(v,s) or not a=load(Wa) or not Water(v,s) or Carrying(Sa,s)))
Now do not need variable re-naming in each part, so move quantifiers left:
A: forall a, s, exists e, u, v
(Carrying(Wa, Result(a,s)) or
((not Carrying(Wa, s) or
(Edge(e, u, v) and (Loc(u, s) or Loc(v, s)) and
a = move(e) and Fire(e,s)))
B: forall a, s, v Carrying(Wa, Result(a,s)) or
(not Loc(v,s) or not a=load(Wa) or not Water(v,s) or Carrying(Sa,s)))
For A, we need skolem functions for e,u,v being in the scope of a,s,
so introduce E-of(a,s), U-of(a,s) V-of(a,s), and can now remove
the quantifiers:
A: Carrying(Wa, Result(a,s)) or ((not Carrying(Wa, s) or
(Edge(E-of(a,s), U-of(a,s), V-of(a,s)) and
(Loc(U-of(a,s), s) or Loc(V-of(a,s), s)) and
a = move(E-of(a,s)) and Fire(E-of(a,s),s)))
Now we need to apply distribution and get several CNF clauses:
6A1: Carrying(Wa,Result(a,s)) or not Carrying(Wa,s) or Edge(E-of(a,s),U-of(a,s),V-of(a,s))
6A2: Carrying(Wa,Result(a,s)) or not Carrying(Wa,s) or Loc(U-of(a,s),s) or Loc(V-of(a,s),s)
6A3: Carrying(Wa,Result(a,s)) or not Carrying(Wa,s) or a = move(E-of(a,s))
6A4: Carrying(Wa,Result(a,s)) or not Carrying(Wa,s) or Fire(E-of(a,s),s)
For B, just removing the quantifiers we get a single CNF clause:
6B: Carrying(Wa, Result(a,s)) or not Loc(v,s) or not a=load(Wa) or not Water(v,s)
or Carrying(Sa,s))
The carrying axiom for water (5) looks exactly the same, so is not repeated.
Finally, the location axiom (7) has 2 parts after removing the iff:
A. forall v, s, a, not Loc(v, Result(a,s)) or
((Loc(v,s) and
(not exists e,u, a=move(e) and (Edge(e,u,v) or Edge(e,v,u))
and (Fire(e,s) => Carrying(Wa,s)) and (Ice(e,s) => Carrying(Sa,s))))
or (exists u, e a=move(e) and (Edge(e,u,v) or Edge(e,v,u)) and Loc(u,s)
and (Fire(e,s) => Carrying(Wa,s)) and (Ice(e,s) => Carrying(Sa,s)))))
B. forall v, s, a, Loc(v, Result(a,s)) or not
((Loc(v,s) and
(not exists e,u, a=move(e) and (Edge(e,u,v) or Edge(e,v,u))
and (Fire(e,s) => Carrying(Wa,s)) and (Ice(e,s) => Carrying(Sa,s))))
or (exists u, e a=move(e) and (Edge(e,u,v) or Edge(e,v,u)) and Loc(u,s)
and (Fire(e,s) => Carrying(Wa,s)) and (Ice(e,s) => Carrying(Sa,s)))))
We will be using only B, and will separate that into 2 first:
B1. forall v, s, a, Loc(v, Result(a,s)) or not
((Loc(v,s) and
(not exists e,u, a=move(e) and (Edge(e,u,v) or Edge(e,v,u))
and (not Fire(e,s) or Carrying(Wa,s)) and (not Ice(e,s) or Carrying(Sa,s))))
B2. forall v, s, a, Loc(v, Result(a,s)) or not
(exists u, e a=move(e) and (Edge(e,u,v) or Edge(e,v,u)) and Loc(u,s)
and (not Fire(e,s) or Carrying(Wa,s)) and (not Ice(e,s) or Carrying(Sa,s))))
Starting with B1, moving negation in we get:
B1. forall v, s, a, Loc(v, Result(a,s)) or
((not Loc(v,s) or
(exists e,u, a=move(e) and (Edge(e,u,v) or Edge(e,v,u))
and (not Fire(e,s) or Carrying(Wa,s)) and (not Ice(e,s) or Carrying(Sa,s))))
We have existentials e, u, within scope of v,s,a so need new Skolem functions
E2-of(v,s,a), U2-of(v,s,a). After processing quantifiers and removing them,
we get:
B1. Loc(v, Result(a,s)) or
((not Loc(v,s) or
(a=move(E2-of(v,s,a)) and
(Edge(E2-of(v,s,a),U2-of(v,s,a),v) or Edge(E2-of(v,s,a),v,U2-of(v,s,a)))
and (not Fire(E2-of(v,s,a),s) or Carrying(Wa,s))
and (not Ice(E2-of(v,s,a),s) or Carrying(Sa,s))))
We can now distribute and get the sentences:
7B1: Loc(v, Result(a,s)) or not Loc(v,s) or a=move(E2-of(v,s,a))
7B2: Loc(v, Result(a,s)) or not Loc(v,s) or
Edge(E2-of(v,s,a),U2-of(v,s,a),v) or Edge(E2-of(v,s,a),v,U2-of(v,s,a))
7B3: Loc(v, Result(a,s)) or not Loc(v,s) or not Fire(E2-of(v,s,a),s) or Carrying(Wa,s)
7B4: Loc(v, Result(a,s)) or not Loc(v,s) or not Ice(E2-of(v,s,a),s) or Carrying(Sa,s)
Processing B2, move negation in to get:
B2. forall v, s, a, Loc(v, Result(a,s)) or
(forall u, e not a=move(e) or (not Edge(e,u,v) and not Edge(e,v,u)) or not Loc(u,s)
or (Fire(e,s) and not Carrying(Wa,s)) or (Ice(e,s) and not Carrying(Sa,s))))
We now have only universal quantifiers, with non-euqal variable names, so can remove them
and distribute, to get (these are all the cases where an agent moves
successfully across an edge!).
7B10: Loc(v, Result(a,s)) or not a=move(e) or not Loc(u,s) or
not Edge(e,u,v) or Fire(e,s) or Ice(e,s)
7B11: Loc(v, Result(a,s)) or not a=move(e) or not Loc(u,s) or
not Edge(e,u,v) Fire(e,s) or not Carrying(Sa,s)
7B12: Loc(v, Result(a,s)) or not a=move(e) or not Loc(u,s) or
not Edge(e,u,v) or not Carrying(Wa,s) or Ice(e,s)
7B13: Loc(v, Result(a,s)) or not a=move(e) or not Loc(u,s) or
not Edge(e,u,v) or not Carrying(Wa,s) or not Carrying(Sa,s)
7B14: Loc(v, Result(a,s)) or not a=move(e) or not Loc(u,s) or
not Edge(e,v,u) or Fire(e,s) or Ice(e,s)
7B15: Loc(v, Result(a,s)) or not a=move(e) or not Loc(u,s) or
not Edge(e,v,u) or Fire(e,s) or not Carrying(Sa,s)
7B16: Loc(v, Result(a,s)) or not a=move(e) or not Loc(u,s) or
not Edge(e,v,u) or not Carrying(Wa,s) or Ice(e,s)
7B17: Loc(v, Result(a,s)) or not a=move(e) or not Loc(u,s) or
not Edge(e,v,u) or not Carrying(Wa,s) or not Carrying(Sa,s)
B) Formally list what we need to prove, and state its negation.
Answer: we see that 2 actions are needed: load(Wa) and move(E1).
We need to show that in a stuation resulting from this action, the
agent will be at a goal location. Note that as stated, the "goal"
predicate is a red herring. That is, we need to prove:
Q: exists v Goal(v) and Loc(v,Result(move(E1),Result(load(Wa), S0)))
Its negation is:
Q': not exists v Goal(v) and Loc(v,Result(move(E1),Result(load(Wa), S0)))
Convering it to CNF, we get:
Q'': not Goal(v) or not Loc(v,Result(move(E1),Result(load(Wa), S0)))
C) Use resolution to reach a contradiction, thus proving the theorem.
Answer:
Resolve Q'' with "Goal(Vmid)", unifier {v|Vmid} to get:
100: not Loc(Vmid,Result(move(E1),Result(load(Wa), S0)))
Resolve 100 with 7B12 (why? because we will be able to prove that there
is no ice and we are carrying water, and thus be able to apply 7B12),
unifier {v|Vmid, a|move(E1), s|Result(load(Wa), S0)} to get:
101: not move(E1)=move(e) or not Loc(u,Result(load(Sa), S0)) or
not Edge(e,u,Vmid) or not Carrying(Wa,Result(load(Wa), S0)) or
Ice(e,Result(load(Wa), S0))
Resolving 101 with EQ1, unifier {e|E1} we get:
102: not Loc(u,Result(load(Wa), S0)) or
not Edge(E1,u,Vmid) or not Carrying(Wa,Result(load(Wa), S0)) or
Ice(E1,Result(load(Wa), S0))
Resolving 102 with the fact "Edge(E1,Vstart,Vmid)" with unifier {u|Vstart} we get:
103: not Loc(Vstart,Result(load(Wa), S0)) or
not Carrying(Wa,Result(load(Wa), S0)) or
Ice(E1,Result(load(Wa), S0))
We now aim to get rid of these 2 disjuncts. First, using 7B1 to show that
we have nor moved from Vstart, in 2 steps.
Resolving 103 with 7B1, (resolven is first clause in each)
unifier {v|Vstart, a|load(Wa), s|S0} we get:
104: not Loc(Vstart,S0) or load(Wa)=move(E2-of(Vstart,S0,load(Wa))) or
not Carrying(Wa,Result(load(Wa), S0)) or
Ice(E1,Result(load(Wa), S0))
Resolving 104 with NEQ1 on the equality, unifier {x|Sa, y|E2-of(Vstart,S0,load(Wa))},
105: not Loc(Vstart,S0) or
not Carrying(Wa,Result(load(Wa), S0)) or
Ice(E1,Result(load(Wa), S0))
Resolving 105 with the given situation S0 datum "Loc(Vstart, S0)", we get:
106: not Carrying(Wa,Result(load(Wa), S0)) or Ice(E1,Result(load(Wa), S0))
Not to show that we are carrying water as a result of loading it.
Resolve 106 with 6B, on the Carrying predicate, unifier {a|load(Wa),s|S0}:
107: not Loc(v,S0) or not load(Wa)=load(Wa) or not Water(v,S0) or Carrying(Sa,S0))
or Ice(E1,Result(load(Wa), S0))
Resolving 107 with "Loc(Vstart,S0)", unifier {v|Vstart} we get:
108: not load(Wa)=load(Wa) or not Water(Vstart,S0) or Carrying(Sa,S0))
or Ice(E1,Result(load(Wa), S0))
Resolving 108 with EQ2, unifier {r|Wa} we get:
109: not Water(Vstart,S0) or Carrying(Sa,S0))
or Ice(E1,Result(load(Wa), S0))
Resolving 109 with S0 data "not Carrying(Sa, S0)" we get:
110: not Water(Vstart,S0) or Ice(E1,Result(load(Wa), S0))
Resolving 110 with S0 data "Water(Vstart, S0)" we get:
111: Ice(E1,Result(load(Wa), S0))
No to disprove the appearance of ice on E1. Resolving 111 with 3A1,
unifier {e|E1, a|load(Wa), s|S0} we get:
112: Ice(E1,S0)
Resolve 112 with FNX, unifier {e|E1, s|S0} we get:
113: not Fire(E1,S0)
Finally, resolving 113 with the given S0 datum "Fire(E1,S0)"
we get the empty clause, a contradiction.
This completes the proof.
c) What would be a potential problem in the proof if we did not
have "frame axioms" in our representation (i.e. stating what
did not change)?
Answer: We would not be able to show that we are at Vstart in Result(load(Sa), S0),
because it must be stated that the location does NOT change as a result
of "load" actions, and failing that we
would not be able to show that move(E1) brings us to Vmid.
d) Would we be able to do the proof using only backward chaining?
Answer: as is, this would not work with generalized modus
ponens, either for forward or backward chaining, because the proof MUST use 6B,
which is not in Horn form (it has 2 positive literals).
A different axiomatization of the domain migh allow it, e.g.
if we added a fluent "HandsFree(s)" we might have
"not Handsfree(s)" instead of "Carrying(Sa,s)", and then
with the data "Handsfree(S0)" the proof may be able to succees using
Generalized modus ponens.
2) (agents and environment simulators)
For each of the following domains, which type of agent is appropriate
(table lookup, reflex, goal based, or utility based). Also, indicate the
type of environment:
a) An agent that plays Bridge.
ANSWER: Utility based. Environment is non-deterministic, inaccessible,
non-episodic, discrete, static, and multi-agent (only semi-static
in competitions, because there are time limits).
b) An agent that plays checkers.
ANSWER: Utility or goal based. Environment is deterministic, accessible,
non-episodic, discrete, static, and multi-agent.
c) An agent that can play Klondike solitaire
ANSWER: Utility or goal based. Environment is non-deterministic, inaccessible,
episodic, discrete, static, and single-agent.
d) An autonomous robot that can win the DARPA challenge (driving in
a city).
ANSWER: Utility based. Environment is non-deterministic, inaccessible,
non-episodic, continuous, dynamic, and multi-agent.
e) An internet coordination agent (sets meetings between humans).
ANSWER: Utility based. Environment is non-deterministic, inaccessible,
non-episodic, continuous, dynamic, and multi-agent.
f) An agent that can solve peg-and-hole solitaire.
ANSWER: Goal based, possibly even reflex or table lookup ("only" 3^33 states).
Environment is deterministic, accessible,
episodic, discrete, static, and single-agent.
3) (Propositional logic)
For each of the following sentences, determine whether they are
satisfiable, unsatisfiable, and/or valid. For each sentence that
is satisfiable, determine the number of models (over the propositional
variables in the sentence).
a) (A or B or C) and D
ANSWER: Satisfiable, 7 models
b) (not (((not A) or B) and ((not B) or C))) or C
ANSWER: Satisfiable, 7 models
c) (A and (not A)) or (B and not B)
ANSWER: Unsatisfiable
d) (not A or B) and (C or not D)
ANSWER: Satisfiable, 9 models
e) A -> not A
ANSWER: Satisfiable, 1 model (A false)
f) (A -> not A) and (not A -> A)
ANSWER: Unsatisfiable
4) (Search):
Show the run of the following algorithms on the setting of question 1
above, where the agent needs to reach Vend. Assume that h(n) uses
simple Dijsktra in the graph (assuming no blockages). Edges E1 and E2 cost 1,
and E3 costs 10.
ANSWER: We will assume that no state repetitions are generated along
a path, but not checked across different seacrh-tree parts.
Needed in order to avoid infinite loops. We assume only operators that
succeed are tried.
a) Greedy search (f(n) = h(n)), breaking ties in favor of states where the
agent is not carrying anything.
ANSWER: Start at S0, h=2. Not a goal, so generate:
S1: load(Sa), h=2.
S2: load(Wa), h=2.
States now: S1, S2.
Here we have 2 states with equal h, and no obvious tie breaking, so
assume arbitrarily that S2 is expanded first. Only one action is possible:
S3: move(E1), h=1.
States now: S1, S3. Expanding S3, to get:
S4: move(E3), h=0.
S5: move(E1), h=1.
States now: S1, S4, S5. Select S4, which is a goal, and return it.
Resulting path is: load(Wa), move(E1), move(E3), with a total cost of 1*3+10=13.
b) A* search, (f(n) = g(n)+h(n)), breaking ties in favor of states where the
agent is not carrying anything.
ANSWER: Start at S0, f=h=2. Not a goal, so generate:
S1: load(Sa), f=h=2.
S2: load(Wa), f=h=2.
States now: S1, S2.
Here we have 2 states with equal f, and no obvious tie breaking, so
assume arbitrarily that S2 is expanded first. Only one action is possible:
S3: move(E1), h=1, g=3, so f=4.
States now: S1, S3. Expanding S1 from which no moves are possible.
So we are left with S3, expanded next.
S4: move(E3), h=0, g=13, f = 13.
S5: move(E1), h=2, g=4, f = 6.
States now are S4, S5. Expanding S5. move(E1) is possible, but reaches
a state equal to S3, so discarded. This leaves:
S6: load(Sa), h=2, g=4, f=6.
States now are S4, S6. Expanding S6.
S7: move(E1), h = 1, g=6, f=7.
States now are S4, S7. Expanding S7. move(E1) is possible, but reaches
a state equal to S6, so discarded. This leaves:
S8: move(E2), h=0, g=8, f=8.
S9: move(E3), h=0, g=28, f=28.
States now are S4, S8, S9. Selecting S8, which is a goal, return
(path is load(Wa), move(E1), move(E1), load(Sa), move(E1), move(E2), cost is 8).
c) A* search, (f(n) = g(n)+h(n)), breaking ties in favor of states where the
agent IS carrying a resource.
ANSWER: same as b.
d) Repeat a-c but using h'(n) = 3*h(n) as the heuristic. Is h'(n) admissible?
ANSWER:
a) no change, as multiplying by 3 is a positive linear
transformation of h, and sorting is only by h.
b) Start at S0, f=h=6. Not a goal, so generate:
S1: load(Sa), f=h=6.
S2: load(Wa), f=h=6.
States now: S1, S2.
Here we have 2 states with equal f, and no obvious tie breaking, so
assume arbitrarily that S2 is expanded first. Only one action is possible:
S3: move(E1), h=3, g=3, so f=6.
States now: S1, S3. Expanding S1 from which no moves are possible.
So we are left with S3, expanded next.
S4: move(E3), h=0, g=13, f = 13.
S5: move(E1), h=6, g=4, f = 10.
States now are S4, S5. Expanding S5. move(E1) is possible, but reaches
a state equal to S3, so discarded. This leaves:
S6: load(Sa), h=6, g=4, f=10.
States now are S4, S6. Expanding S6.
S7: move(E1), h = 3, g=6, f=9.
States now are S4, S7. Expanding S7. move(E1) is possible, but reaches
a state equal to S6, so discarded. This leaves:
S8: move(E2), h=0, g=8, f=8.
S9: move(E3), h=0, g=28, f=28.
States now are S4, S8, S9. Selecting S8, which is a goal, return
(path is load(Wa), move(E1), move(E1), load(Sa), move(E1), move(E2), cost is 8).
Same behavior as before. But if we had h''(n)=5*h(n), we would have f''(S4)= 14
so would pick S4 with f''(S4) = 13, and return this goal state, for a suboptimal
answer.
c) Same as the latter b.
5) (Game trees and Search):
Consider a 4-person game with complete information, where the score is
computed for PAIRS that are defined in advance. That is, the players are
A, B, C, D, and AC are a pair, BD are the other pair. The score for
each member a pair are the same, and is NEGATIVE of the scores for the
other pair. For example, if A scores 100, C also scores 100, B scores -100
and D scores -100. Assume that players take turns in the order A, B, C, D,
repeatedly, until the game ends.
a) Write an algorithm for optimal play by player A.
ANSWER: a simple generalization of MiniMax, changed so as to maximize
over moves of A and C, and minimize over moves of B and D.
Basically it looks like:
MaxMinMaxMin(player, position) {
position is terminal then return its value;
if move is by A then return maximum of MaxMinMaxMin(B,position(move)) over moves;
if move is by B then return minimum of MaxMinMaxMin(C,position(move)) over moves;
if move is by C then return maximum of MaxMinMaxMin(D,position(move)) over moves;
if move is by D then return minimum of MaxMinMaxMin(A,position(move)) over moves;
}
Note that this only works assuming that C also plays perfectly.
(B and D can play imprefectly, if so this may only increase A's
score. But C playing imperfectly can ruin everything!)
b) If A cannot communicate with C, and vice-versa, is your algorithm
still optimal? In what cases, if any, can you run into problems?
ANSWER: The game is compelete information, and strict turn based,
so despite lack of communication all agent see all moves. So the algorithm
above is still "perfect play" with the above assumptions.
Lacking any of these properties, the algorithm would run into problems
in attempting "perfect play".
c) Modify your algorithm so that it is optimal for A, but where B
makes moves randomly with uniform probability.
ANSWER: as above, but averaging over B moves.
MaxExpectiMaxMin(player, position) {
position is terminal then return its value;
if move is by A then return maximum of MaxExpectiMinMaxMin(B,position(move)) over moves;
(But if top level, return the best move rather than the score)
if move is by B then return average of MaxExpectiMaxMin(C,position(move)) over moves;
if move is by C then return maximum of MaxExpectiMaxMin(D,position(move)) over moves;
if move is by D then return minimum of MaxExpectiMaxMin(A,position(move)) over moves;
}
d) Show an example 4-ply game tree with branching factor 2, and show
the values computed in this tree for all three of the above algorithms.
We will call moves by A: A1 and A2, etc.
MIN MAX MIN
A1 10--- B1 10---- C1 0 ----- D1 100
\ \ ----- D2 0
\ --- C2 10 ----- D1 10
\ ----- D2 20
- B2 15---- C1 -1 ----- D1 -1
\ ----- D2 0
--- C2 15 ----- D1 100
----- D2 15
A2 1--- B1 1---- C1 1 ----- D1 1
\ \ ----- D2 15
\ --- C2 -9 ----- D1 -9
\ ----- D2 0
B2 90---- C1 90 ----- D1 100
\ ----- D2 90
--- C2 -3 ----- D1 10
----- D2 -3
Here A will select A1 which guarantees 10 for A and C. Same result for case b.
For a random move by B, we get:
AVG MAX MIN
A1 12.5- B1 10---- C1 0 ----- D1 100
\ \ ----- D2 0
\ --- C2 10 ----- D1 10
\ ----- D2 20
- B2 15---- C1 -1 ----- D1 -1
\ ----- D2 0
--- C2 15 ----- D1 100
----- D2 15
A2 45.5-- B1 1---- C1 1 ----- D1 1
\ \ ----- D2 15
\ --- C2 -9 ----- D1 -9
\ ----- D2 0
B2 90---- C1 10 ----- D1 100
\ ----- D2 10
--- C2 -3 ----- D1 10
----- D2 -3
In this case A will prefer A2, with an expected value of 45.5 for A and C.
6) (Game-tree search - alpha-beta pruning)
a) Give an example of a 3-ply game tree (branching factor 2 for MAX and 3 for MIN)
where alpha-beta pruning saves NOTHING, and another where the savings
is maximal. How many nodes are pruned in each case?
ANSWER: using the same scheme as before to designate moves:
MIN MAX
A1 2 --- B1 20---- A1 10
\ ---- A2 20
\ - B2 10---- A1 5
\ ---- A2 10
- B3 2 ---- A1 1
---- A2 2
A2 22--- B1 35---- A1 30
\ ---- A2 35
\ - B2 27---- A1 25
\ ---- A2 27
- B3 22---- A1 22
---- A2 21
In this case, performing the search in the order indicated by the ordering of lines,
nothing is saved. The value is determined only on the last branch in each
case, and nothing is pruned. At the end, A will pick A2 for a value of 22.
Reversing the ordering at each level, we get:
MIN MAX
A1 22--- B1 22---- A1 21
\ ---- A2 22
\ - B2 >=27-- A1 27
\ ---- A2 25 (but pruned, no need to check, as B will never pick B2)
- B3 >=30-- A1 30
---- A2 30 (but pruned, no need to check, as B will never pick B3)
A2 <=2 - B1 2 ---- A1 2
\ ---- A2 1
\ - B2 X ---- A1 10 (pruned, as well as everyhing beyond this point
\ ---- A2 5 since B is assured a move that results in
- B3 X ---- A1 20 no more than 2, so A will never pick A2 anyway).
---- A2 10
Here A can pick A1 and be assured a value of 22, pruning (i.e. not looking at)
A1B2A2, A1B3A2, and also A2B2 and A2B3.
b) Provide an example of a 2-ply + 1 chance node level game tree where
alpha-beta saves as much search as the maximum possible in a deterministic game,
and a similar example where changing the distribution on the chance node
edges results in no savings for pruning.
ANSWER: assume that scores are limited by 10 in absolute value.
We will let the chance be biased. Let the deterministic case be:
CHANCE MIN
A1 7.1-- .9 9---- B1 9
\ ---- B2 10
- .1 -10---- B1 -10
A2 <=1-- .9 <=0--- B1 0
\ ---- B2 5 (pruned, as well as anything below. A will not pick A2 anyway)
--- .1 X---- B1 5
---- B2 8
So A can pick A1 to get 7.1 expected value, no need to continue checking below A2.
Changing the branch distributions to go the other way, we get:
CHANCE MIN
A1 -8.1- .1 9---- B1 9
\ ---- B2 10
- .9 -10---- B1 -10
A2 4.5-- .1 0---- B1 0
\ ---- B2 5
--- .9 5---- B1 5
---- B2 8
In this case, A will pick A2 but cannot stop the search before
checking everything below A2.
Submissions are to be solo.