1) (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 can play Tic-Tac-Toe.
c) An autonomous humanoid robot that can win the DARPA robotics challenge (driving a car,
walking across debris, connecting two pipes). Scoring depends on success in the tasks,
on execution speed, and on using as little communication with the operator as possible.
d) An internet coordination agent (sets meetings between humans with conflicting goals).
e) An agent that can play peg-and-hole solitaire.
f) An agent that plays Checkers optimally.
2) (Search):
Show the run of the following algorithms on the setting of question 6
below, where the agent starting at V0 needs to reach V2 with the chems with minimal cost.
The costs are: all edges cost 1, except for E5 which costs 2.
Assume that h(n) is the cost to reach the goal state in the simplified problem
that assumes no armies, no terrorists, and no cost to travel unless with chems.
a) Greedy search (f(n) = h(n)), breaking ties in favor of states where the
agent is moving with chems, and then in favor of lower-numbered edges.
b) A* search, (f(n) = g(n)+h(n)), breaking ties as above.
c) Simplified RTA* with a limit of 2 expansions per real action, breaking ties as above.
c) Repeat a-c but using h'(n) = 2*h(n) as the heuristic. Is h'(n) admissible?
3) (Game trees and Search):
Consider a 3-person game (A, B, C) with complete information, where A and C are fully
cooperating, and where B is semi-cooperative with A and C (and vice-versa), i.e. picks
the bests score for itself, breaking ties in favor of cooperation.
However, C is a player that plays completely randomy with
a uniform distribution. Assume that players take turns in the order A, B, C,
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 by 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) Same as in case b, but now C can see A's moves, but A cannot see the moves made by C.
d) Show an example 3-ply game tree with branching factor 2, and show
the values computed in this tree in case a.
4) (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 integers between -10 and 10. 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
one can apply an adapted alpha-beta to prune some nodes,
and a similar example where changing the distribution on the chance node
edges results in no savings for pruning.
5) (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). In case b, also trace the run of the DPLL algorithm for satisfiability with this
formula as input (i.e. explain any recursive calls and cases encountered).
a) (A and (A -> B) and (B -> C)) -> C
b) (A or not B or C) and (not A or B) and (not A or not B or C) and (A or not B)
c) (A or B or C or D or E or F or G)
d) (A and B) or (C or not D or E)
e) (A and (A -> B) and (B -> C)) -> not C
f) not ((A and (A -> B) and (B -> C)) -> C)
6) (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 action costs, assume only one agent, at most one army
and one chem, and allow only the drive action.
a) Write down the axioms for the behavior of the world using FOL and
situation calculus.
Use the predicates:
Edge(e, v1, v2) ; e is an edge in the graph between v1 and v2.
Goal(v) ; Vertex v is a chem dumping (goal) site.
Also use the fluents (situation-dependent predicates)
Loc(v,s) ; Agent is at vertex v in situation s
Terrorist(e,s) ; Terrorists at edge e in situation s
Chem(v,s) ; Chem at vertex v in situation s.
Army(v,s) ; Vertex v has army in situation s
Constants: as needed, for the edges and vertices.
Functions: not needed here, except to denote actions:
drive(e,chem,army) ; Denotes a move action across edge e (may be ineffective), with or without chem
and with or without army.
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.
Let the facts representing the scenario be:
Edge(E1, V0, V1)
Edge(E2, V1, V2)
Edge(E3, V3, V1)
Edge(E4, V0, V3)
Edge(E5, V3, V2)
Goal(V2)
; with situation S0 fluents being:
Loc(V0, S0)
Terrorist(E2, S0)
Army(V0,S0)
Chem(V0,S0)
b) Now, we need to find a sequence of actions that will result in reaching the goal,
of the chem being in V2,
and prove a theorem that it will do so. Do the following steps:
A) Convert the knowledge base to conjunctive normal form. (This is very long,
so you may omit the parts not needed in the proof below).
B) Formally list what we need to prove (a theorem), and state its negation.
C) Use resolution to reach a contradiction, thus proving the theorem.
At each step of the proof, specify the resolvents and the unifier/
c) Would there be a potential problem in the proof if we did not
have "frame axioms" in our representation (i.e. stating what
did not change), and if so, what?
d) Would we be able to do the proof using only forward chaining?
Justify all answers shortly!
Deadline: Noon (12:00), Tuesday, December 3, 2013 ( strict deadline).
Submissions are to be solo.