1) (agents and environment simulators - 5%):
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) A fully autonomous car.
c) An internet shopping agent specializing in purchasing kitchen appliances.
d) An agent that can play 3x3 tic-tac-toe.
e) An agent that can play Gomoku
2) (Search - 20%):
Show the run of the following algorithms on the setting of question 6
below, where the agent starting at V0 needs to save as many people as possible,
where costs are as defined in assignment 1.
Assume that h(n) is the heuristic defined in class (based on number of
people in the groups that cannot be saved if considered in isolation).
a) Greedy search (f(n) = h(n)), breaking ties in favor of states where the
higher node number.
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.
d) Repeat a-c but using h'(n) = 2*h(n) as the heuristic. Is h'(n) admissible?
3) (Game trees 10%):
Consider a 3-person game (A, B, C) with complete information and STOCHASTIC environment.
Suppose A has 5 possible moves. Provide a game tree example that shows that for
each of the following set of "loyalties", A will have a different optimal move:
a) Each agent out for itself, and they cannot communicate (with ties broken anti-cooperatively).
b) B and C are semi cooperative (they break ties cooperatively)
d) B and C are partners aiming to maximize the sum of their scores
d) Paranoid assumption: B and C are against A
e) Even more paranoid assumption: B and C are against A, plus A is a firm believer in Murphy's
laws: "mother nature is a b*!=h", and believes the environment makes the worst thing for A always happen.
Explain your answer by showing the computed values in the internal nodes in each case.
Note that you should probably make the example more concise by allowing
only ONE choice of action for some of the players, or only ONE possible "stochastic" outcome
in some of the branches.
4) (Game-tree search - alpha-beta pruning - 15%)
In the adversarial version of the hurricane evacuation problem:
a) Construct an example where the optimal first move is no-op (assuming such an action is allowed),
or argue that this cannot be the case.
b) Construct and show an example (including the static heuristic evaluation function and
search tree), with a tree depth of at least 4 ply.
c) Show where alpha-beta pruning can decrease search effort in the tree from b.
5) (Propositional logic - 10%)
For each of the following sentences, determine whether they are
satisfiable, unsatisfiable, and/or valid. For each sentence
determine the number of models (over the propositional
variables in the sentence).
Note: some items seem hard, but if you use some (natural) intelligence, easier than it may seem.
a) (not A and not B and not C and not D and not E and F) or (A and B and C and D and E)
b) (A or B or C or D or E or F) and (not A or not B or not C or not D or not E or not F)
c) (A or B and (D or not A) and (E or A) -> (B or C and (not D or E))) and (A and not A)
d) (A and (A -> B) and (B -> C)) -> C
e) not ((A and (A -> B) and (B -> C)) -> C)
f) (A -> not A) or (not A -> A)
Bonus question: in cases a, b, c, also trace the run of the DPLL algorithm
for satisfiability with this formula as input (i.e. explain any recursive calls and
cases encountered).
6) (FOL and situation calculus - 40%)
We need to represent and reason within the scenario defined by assignment 1.
For simplicity, we will assume only one agent.
a) Write down the axioms for the behavior of the world using FOL and
situation calculus.
Use the predicates:
Vertex(v) ; v is a vertex
Edge(e, v1, v2) ; e is an edge in the graph between v1 and v2
Shelter(v) ; Vertex v is contains a Hurricane shelter
Weight(e,w) ; Weight of edge e is w
Deadline(v,t) ; The deadline for vertex v is at time t
Also use the fluents (situation-dependent predicates)
Loc(v,s) ; Agent is at vertex v in situation s
Carrying(n,s) ; Agent is carrying n people in situation s.
Safe(n,s) ; In situation s, n people are safe
At(v,n,s) ; There are n people at vertext v in situation s
Time(t,s) ; The time since creation is t in situation s
Constants: as needed, for the edges and vertices, and simple actions (terminate).
Functions:
traverse(e) ; Denotes a traverse move action across edge e
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, V0, V2)
Edge(E3, V2, V3)
Edge(E4, V1, V3)
Edge(E5, V1, V2)
Weight(E1,3)
Weight(E2,1)
Weight(E3,2)
Weight(E4,2)
Weight(E5,1)
Deadline(V2,2)
Deadline(V0,5)
Shelter(V0)
; with situation S0 fluents being (note that this is a partial, "closed world assumption" description).
Loc(V0, S0)
Carrying(0, S0)
At(V1, 1, S0)
At(V3, 2, S0)
Safe(0, S0)
Time(0, S0)
b) Now, we need to find a sequence of actions that will result some people
being safe, starting from S0 (which you found in question 1 above),
and prove a theorem that some (not zero) people are safe as a result
(but do not need to prove optimality). Do this by the following steps:
A) Convert the knowledge base into 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.
For simplicity, you may (recommended!) omit the time keeping and the deadline requirements for
action success from the KB before doing the proof. (Say exactly which axioms you are
changing in order to do that, if you decide to simplify).
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: (16:00), Tuesday, December 10, 2019 ( strict deadline).
Submissions are to be solo.