Introduction to Artificial Inteligence
Mid-term Exam 1 - Solutions
Question 1) Answers to parts 1-4 is in the figure below.
Note that since this is 2-ply, some of the elements in the evaluation
are always 0.
| |
-+-+-
1 | |
-+-+-
| |
| | | |X | |
-+-+- -+-+- -+-+-
1 |X| -1 | | -2 | |X
-+-+- -+-+- -+-+-
| | | | | |
| |O | | | |X | |X | |X | |X | |X | | O| | | |O |O| | |
-+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+-
|X| |X|O |O| | | | | | | | |O |O|X | |X | |X | |X O| |X
-+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+-
| | | | | | | |O O| | |O| | | | | | | | | | | | |
1 2 -1 0 U 0 U 1 U 1 U -2 -1 U -1 U 0 U 0 U
Eval values - for bottom rows (part 2). Values for non-leaves is for part 3.
The best move is clearly X in the center, valued at 1.
For part 4, all assuming ordering is as drawn, leaf nodes markes U are
unevaluated (pruned) in alpha-beta pruning.
If instead of MIN nodes we have EXPECATION nodes, all we need to do is take
expectations at this level with uniform probability. Care must be taken with
tree nodes representing multiple symmetrical positions. We get the following
tree evaluations:
| |
-+-+-
1.5 | |
-+-+-
| |
| | | |X | |
-+-+- -+-+- -+-+-
1.5 |X| 3/8 | | -6/8 | |X
-+-+- -+-+- -+-+-
| | | | | |
4/8 4/8 1/8 2/8 1/8 2/8 2/8 1/8 2/8 2/8 2/8 2/8
| |O | | | |X | |X | |X | |X | |X | | O| | | |O |O| | |
-+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+-
|X| |X|O |O| | | | | | | | |O |O|X | |X | |X | |X O| |X
-+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+- -+-+-
| | | | | | | |O O| | |O| | | | | | | | | | | | |
1 2 -1 0 U 0 U 1 U 1 U -2 -1 U -1 U 0 U 0 U
Where probabilities for a (multiple) position is listed above each leaf
node.
Question 2)
Part 1) Block(A) ^ Block(B) ^ Block(C) ^ Table(T) ^ On(A,B,S0) ^
On(B,C,S0) ^ On(C, T, S0) ^
(forall x ~On(x,A,S0)) ^
(forall x On(x,B,So) => x=A) ^
(forall x On(x,C,So) => x=B) ^
(forall x On(x,T,So) => x=C)
Note that it is also possible to say, instead of the last 4 lines:
~On(B,A,S0) ^ ~On(C,A,S0) ^ .... ^~On(B,T,S0)
but this is long and would require O(n*n) terms for a situation with
n objects - so is to be discouraged (although full credit in this exam).
Part 2) We will state the English equivalent for each axiom. Note that it
is easier if we had a predicate ClearTop(x,s), and in fact in many
representations of blocks world this predicate is used, but you
were expressly DISALLOWED using the extra predicate. That means
we need to "factor it out" in the FOL description, by using:
~(exists w On(w,x,s)) in place of ClearTop(x,s).
After a successful Puton(x,y) action, block x will be on y,
and if x is on some object z, it will no longer be on z after
the action.
forall x,y,z,s (Block(x)^(~ exists w On(w,x,s))^ ~(x=y) ^ On(x,z,s) ^
(Table(y) v (Block(y) ^ (~ exists w On(w,y,s)))) =>
(On(x,y,result(Puton(x,y),s)) ^
~On(x,z,result(Puton(x,y),s)))
where the head of the rule (except for On(x,z,s)) tests the condition
for the success of PutOn(x,y).
If there is something (a) on an object (b) after a PutOn(x,y) action,
either this is a successful action with objects x=a and y=b, or
a was on b before the action. (Alternatly, this means that if a was NOT
on b before the action, it will not be there after the action,
unless...)
forall a,b,x,y,s On(a,b,result(PutOn(x,y),s)) =>
((a=x ^ b=y ^ Block(x)^(~ exists w On(w,x,s)) ^
~(x=y)^ (Table(y) v
(Block(y) ^ (~exists w On(w,y,s))))) v
On(a,b,s))
Finally, if some block a was on b and a was not moved by some
action PutOn(x,y), then a remains on b:
forall a,b,x,y,s (On(a,b,s) v ~(x=a) v
(exists w On(w,x,s)) v (x=y) v
(exists w On(w,y,s) ^ ~Table(y))) =>
On(a,b, result(PutOn(x,y,s)))
where ~(x=a) means the action is irrelevant (does not involve a),
and the rest is conditions under which the action will fail and then
obviously cannot affect anything. Naturally, there are numerous ways
of encoding the information in the above axioms.
Question 3)
1) False. The hardest problems are knowledge representation, etc.
which we do not even know how to formalize as a problem, in the general
case.
ELABORATION: even among FORMALIZABLE problems, there
are some that are undecidable, and yet they are solved in practice for
useful special cases, and problems that are NP-hard are solved in
practice (for "intelligent agents"), obvsiously, too.
2) False. In hard problems, we sometimes give up optimality (thus
admissibility) for faster results. Inadmissible heuristic may be faster!
ELABORATION: perfect heuristic is optimal AND provides fast search, but
CANNOT BE COMPUTED IN PRACTICE as it usually requires optimal solution
of the problem to compute, in which case we no longer need it anyway!
3) True. Just set h(n)=0 unifrmly, and with g(n) equal to node depth
(or if path cost is 1 per arc) we get exactly BFS.
4) True. Effective branching factor is number of child nodes generated
and expanded on the average (usually geometric average). With a good
heuristic, the number of expanded nodes is much smaller.