1) (FOL and situation calculus)
We need to represent and reason within the scenario defined by assignment 1.
a) Write down the axioms for the behavior of the world using FOL and
situation calculus. Assume only one agent.
Use the predicates:
>, < ; (in order to check if the agent can clear the ice, etc).
Edge(e, v1, v2) ; e is an edge between vertex v1 and vertex v2.
Goal(v) ; The agent's goal is vertex v.
Also use the fluents (situation-dependent predicates)
Salt(v, w, s) ; Vertex v has w units of salt in situation s.
Ice(e, i, s) ; Edge e has i units of ice in situation s.
Carrying(w, s) ; Agent is carrying w units of salt in situation s.
Loc(v,s) ; Agent is at vertex v in situation s
Functions:
+, - (in order to compute remaing amount of salt, etc.)
And the actions: move(e), load(w).
b) Write down the additional facts representing the following scenario in situation S0.
Edge(E1, Vstart, Vmid)
Edge(E2, Vmid, Vend)
Goal(Vend)
; Situation S0
Salt(Vstart, 2, S0)
Ice(E1, 0, S0)
Ice(E2, 1, S0)
Carrying(0, S0)
Loc(Vstart, S0)
c) Now, we need to find a sequence of actions that will result in reaching the goal,
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.
d) 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)?
e) Would we be able to do the proof using only forward chaining?
2) (search and logic)
Finding an explanation for observed evidence is known as abductive
reasoning. The input is a KB of definite Horn clauses (i.e. "rules",
see below), and a function that assigns each literal a
non-negative cost.
Also part of the input is a set of literals E (the observed
evidence) to be explained.
An explanation is a set of assumed literals A, that together with KB
proves E.
In this exercise, we wish to solve the weighted abduction
version: given E, find an explanation A where
the sum of the costs of the literals in A is minimal. For example, consider
the following KB:
R1: a -> b
R2: b and c -> d
R3: a -> c
R4: x -> d
The cost of assumption for literals is as follows:
cost(b) = 7
cost(c) = 5
cost(d) = 21
cost(a) = 10
cost(x) = 50
For the case where we wish to find an explanation for E = {d},
one possible explanation is A = {d} for a cost of 21.
But it is not an optimal explanation, because A = {a}
also an explanation, with a weight of 10.
a) Formalize the weighted abduction problem as a search problem,
where the state is a partial solution A', and where an operator adds
any literal not in the partial solution.
b) Same as (a), but this time a lexicographical ordering of literals
is given (say a, then b, etc.), and one can add a literal x only
if no literal y greater than x is in A'.
c) Assume that we use uniform-cost search, are we assured of finding
the minimal explanation using version a? If not, are we assured of such
using option b? You need to sketch the proof for your answer.
d) We wish to use A* to perform weighted abduction. Find an
admissible heuristic for versions a, b, (they may all be the
same heuristic, and it does NOT have to be a GOOD heuristic).
Now, show an execution of A* using your heuristic to solve the
weighted abduction problem, given as input the above KB and
the evidence to be explained E = {d}.
Use only one of the search problem versions a, b - your choice
(hint: which would result in the shortest trace?)
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 or 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) (A or B) and ((not C) or not D)
e) A -> not (A or B)
f) (A -> not A) and (not A -> A)
4) (Game trees and search)
Consider the game to be implemented in assignment 2, but this time with a stochastic
element: an agent can attempt to cross an icy edge, and succeeds with a given
probability p (say p=0.1) even if it is carrying no salt.
You may assume a time limit as desired for the length of the game in
each scenario.
a) Show a scenario with p=0 (no random element) where for the first agent to
move (Clarification: not "whoever is the first to move", i.e. this need be
shown only for one of the agents) under zero-sum scoring,
moving in a certain direction (say, crossing edge E1) gets a negative score,
but under semi-cooperative the above action is optimal.
b) In the game p > 0 zero-sum scoring, show a scenario
where whoever is the first agent to move, gets a negative score.
In both cases, you must PROVE the scores by generating the respective game tree, either
to a terminal position or prove that you can prune some branches.
c) Suppose the game is fully cooperative, that is, the agents try to minimize the sum
of their costs (with p=0). Find heuristics:
1) One that is a lower bound, but non-trivial.
2) One that is an optimistic upper bound, but non-trivial
5) (Game-tree search - alpha-beta pruning)
a) Consider the tic-tac-toe position (with O to move):
| X |
-----------------
X | O | O
-----------------
| X |
Give an example in ordering the complete search tree starting from this position
where alpha-beta pruning saves as little as possible, and another where the savings
is maximal. How many nodes are pruned in each case?
You may denote moves by Xxy or Oxy in order to save space.
(Clarification: in the case with no pruning, no need to specify
the tree explicitly, only estimate the number of nodes).
b) Consider the same scenario as above, except that after every move by
O, a random mark (equally probable to be X or O, uniformly distributed
over the free locations) is generated. Draw and evaluate the
search tree, and state where pruning is possible.
6) (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 billiards ion a real table.
b) An agent that plays chess.
c) An agent that can play spider solitaire.
d) An autonomous robot that can win the DARPA challenge (driving in
a city).
e) An internet shopping agent (flights reservation domain).
f) An agent that can solve the 8-puzzle.
Justify all answers shortly!
Deadline: Noon (12:00), Wednesday, December 9, 2009 ( strict deadline).
Submissions are to be solo.