1) (FOL and situation calculus)
We need to represent and reason within the scenario defined by assignment 1.
For simplicity, we will ignore the issue of transit times and flooding.
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(ag, v) ; Agent ag's goal is vertex v.
Agent(ag) ; ag is an agent.
Car(c) ; c is a car.
Also use the fluents (situation-dependent predicates)
InCar(ag, c, s) ; Agent ag is in car c in situation s.
Loc(o,v,s) ; Object o is at vertex v in situation s
Constants: as needed, including constants for the agents and cars:
Agents A1, A2 ... and cars C1, C2 ...
Functions: not needed here, except to denote actions:
drive(e) ; Denotes a move action across edge e (may be ineffective).
switch(ag, c) ; Denotes agent ag attempting to switch to car c.
and of course the "Result" function:
Result(a,s) ; Denotes the situation resulting from doing action a in
; situation s.
You may wish to add auxiliary predicates or fluents in order to simplify the axioms. you
are allowed to do so provided you explain why they are needed.
Add the facts representing the following scenario in situation S0.
Edge(E1, Vstart, V1)
Edge(E2, V1, Vend)
Car(C1)
Agent(A1)
Goal(A1, Vend)
; Situation S0
Loc(A1, Vstart, S0)
Loc(C1, Vstart)
Loc(C2, V1)
InCar(A1, C1, S0)
b) Now, we need to find a sequence of actions that will result in reaching the goal,
of agent A1 being in Vend,
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 forward 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 Poker.
b) An agent that can play Spider solitaire.
c) An autonomous robot that can win the DARPA challenge (driving in
a city).
d) An internet coordination agent (sets meetings between humans).
e) An agent that can solve a Soduku puzzle.
f) An agent that plays Go.
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 and B and C) or not D
b) (not (A and ((not A) or B) and ((not B) or C))) or C
c) (A and (not A)) and (B and not B)
d) (A and not B) and (C or not D)
e) not A -> A
f) (A -> not A) or (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 as quickly as possible. The speed of C1 is 50, and
that of C2 is 100. Length of E1 and E2 are 100 each, and the time to switch is
0.2. Assume that h(n) uses simple Dijsktra in the graph and assumes
that the agent is in the fastest available car.
a) Greedy search (f(n) = h(n)), breaking ties in favor of states where the
agent is in a faster car.
b) A* search, (f(n) = g(n)+h(n)), breaking ties in favor of states where the
agent is in a faster car.
agent is not carrying anything.
c) A* search, (f(n) = g(n)+h(n)), breaking ties in favor of states where the
agent is in a slower car.
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 1, C also scores 1, B scores -1
and D scores -1. However, B is a player that plays completely randomy with
a known distribution. 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 the game now is partial information: A cannot communicate with C,
and C cannot see the moves made A, but
A can see all moves made by C, is your algorithm
still optimal? In what cases, if any, can you run into problems?
c) Show an example 4-ply game tree with branching factor 2, and show
the values computed in this tree case a.
6) (Game-tree search - alpha-beta pruning)
a) Give an example of a 4-ply game tree (branching factor 2)
where alpha-beta pruning saves NOTHING, and another where the savings
is maximal. How many nodes are pruned in each case?
b) Suppose that we know ahead of time that the terminal values can only
be 0 or plus 1 or minus 1. Is there a case where alpha-beta can save even
more search than the best case above (show it, or prove that it cannot help).
c) 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 14, 2011 ( strict deadline).
Submissions are to be solo.