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)
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.
B) Formally list what we need to prove, and state its negation.
C) Use resolution to reach a contradiction, thus proving the theorem.
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)?
d) Would we be able to do the proof using only backward chaining?
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.
b) An agent that plays checkers.
c) An agent that can play Klondike solitaire.
d) An autonomous robot that can win the DARPA challenge (driving in
a city).
e) An internet coordination agent (sets meetings between humans).
f) An agent that can solve peg-and-hole solitaire.
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
b) (not (((not A) or B) and ((not B) or C))) or C
c) (A and (not A)) or (B and not B)
d) (not A or B) and (C or not D)
e) A -> not A
f) (A -> not A) and (not A -> A)
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.
a) Greedy search (f(n) = h(n)), breaking ties in favor of states where the
agent is not carrying anything.
b) A* search, (f(n) = g(n)+h(n)), breaking ties in favor of states where the
agent is not carrying anything.
c) A* search, (f(n) = g(n)+h(n)), breaking ties in favor of states where the
agent IS carrying a resource.
d) Repeat a-c but using h'(n) = 3*h(n) as the heuristic. Is h'(n) admissible?
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.
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?
c) Modify your algorithm so that it is optimal for A, but where B
makes moves randomly with uniform probability.
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.
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?
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.
Justify all answers shortly!
Deadline: Noon (12:00), Wednesday, December 1, 2010 ( strict deadline).
Submissions are to be solo.