Solution to Midterm

 ComS 572, Artificial intelligence
Fall 2002
Test date: Friday, Oct 25, 2002

 Oct 26, 2002

by TA
Jie Bao
Dept of Computer Science
Iowa State University
Ames, IA, 50011
baojie@cs.iastate.edu
http://www.cs.iastate.edu/~baojie

Problem 1

What's aardvark?

 
(a)
   (~(A^B)) ^ (~(B^C))  ^ (~(C^D))
or (~A|~B) ^ (~B|~C) ^ (~C|~D)
or (A^B => False) ^ (B^C => False) ^ (C^D => False)
or (A=>~B) ^ (B=>(~A^~C)) ^ (C=>(~B^~C)) ^ (D=>~C)
 
(b)
Solution 1
   A=>B|C|D, B=>A|C|D, C=>A|B|D, D=>A|B|C, true=>A|B|C|D
and (A^B => False) ^ (B^C => False) ^ (C^D => False)
 
Solution 2
(A^B => False) ^ (B^C => False) ^ (C^D => False) (*)
 
note that:
(x^y)|(p^q) <=> (x|p)^(x|q)^(y|p)^(y|q)
(x^y)|p = (x|p)^(y|p)
 
KB + (*)
|- (A^C)|(A^D)|(B^D)
|- ((A|A)^(A|D)^(C|A)^(C|D)) | (B^D)
|- (A|B)^(A|D) ^ (A|D|B)^(A|D|D) ^ (C|A|B)^(C|A|D)
               ^ (C|D|B)^(C|D|D)
|- (A|B)^(A|D) ^ (A|D|B) ^ (A|B|C)^(A|C|D)
               ^ (B|C|D)^(C|D)
 
so the KB also includes:
ture => (A|B)
ture => (A|D)
ture => (A|D|B)
ture => (A|B|C)
ture => (A|C|D)
ture => (B|C|D)
ture => (C|D)
 
 
(c)
Solution 1
We have:
   A=>B|C|D, B=>A|C|D, C=>A|B|D, D=>A|B|C, true=>A|B|C|D
and (A^B => False) ^ (B^C => False) ^ (C^D => False)
 
And if (A=>False) ^ (D=>False)
 
   D=>A|B|C
+) A=>False
   --------
   D=>B|C
+) B^C=>False
   ----------
   D=>False
Simliarly, We have
   A=>False ^ B=>False ^ C=>False
 
   ture=>A|B|C|D
=) A=>False ^ B=>False ^ C=>False ^ D=>False
   ----------
   true=>False
 
so, can't be "(A=>False) ^ (D=>False)"
 
Solution 2
from Solution 2 of (b) we know
   true => (A|D)
+) ~A
------------
 = ture => D
+) D => False
------------
   true => false
 
Solution 3
KB |- true => (A^C)|(A^D)|(B^D)
Assume (A|D)=>False
=> (A=>False) ^ (D=>False)
=> true => false
so (A|D)=>true
 
(d)
i)  at least two aardvark cages
ii) no adjacent cages
ABCD
----
TFTF
TFFT
FTFT
 
(e)
Solution 1
   A^B => C|D
   A^C => B|D
   A^D => B|C
   B^C => A|D
   B^D => A|C
   C^D => A|B
Solution 2
   

Problem 2
(a) i
e1 = { honest_Jeff }
e2 = { honest_Tom }
 
(a) ii
ext(D):
C U { honest_Jeff}
C U { honest_Tom}
 
(b)
recall: Explanation e of q is a minimal subset of A which consistent with C and C U x |=q . E(q) is all expanation of q
 
E is Empty
C |= q , so the MINIMAL subset xof A which consistent with C and C U x |=q is NULL
so E = { NULL} = Empty
 
(c)
q is a cautious consequence of D if it holds in every extension of D
 
i.e. It holds if C U x |= q
if C |= q, it must be ture that C U x |= q
so q is a cautious consequence of D
 
solution 2
Suppose q is not a cautious consequence of d. Then it is a brave consequence. Thus, there is some extension of D such that q does not hold. However, x must be consistant with C. And c|=q. This is a contradiction. so q must be a cautious consequence of D.

Problem 3
i DFS
NOT BFS: large b
NOT IDS: finite
NOT BiS: don't know where is the goal
 
ii BFS or IDS
NOT DFS: infinite
NOT BiS: don't know where is the goal
 
iii DFS
NOT BFS: don't know the upper bound of b
NOT IDS: finite
NOT BiS: don't know where is the goal
 
iv Bidirectional Search
Knows goal state and has backward operators
 
v BFS
b is very small
NOT DFS: weaker than BFS
NOT IDS: finite
NOT BiS: don't know where is the goal
 
(b)
i) map coloring
Z = { color of countries}
C = for all x,y in Z, adj(country(x),country(y)) => ~(x = y)
D = { colors }
 
ii) examination scheduling
Z = { time duration & place of exam }
D = { time: available time span; place: available room location}
C = { place(x1)=place(x2) => not (time(x1) overlap time(x2))
      (time(x1) overlap time(x2) => not (place(x1)=place(x2))}

Problem 4 (by Dimitris)

Solution 1:

Wander randomly.  At some point decide to reach the goal.  Use A*, using the existing admissible h values on the signs, remembering the path you're taking. When you reach the goal, backtrack and update the h signs with the true min distance to the goal.  Repeat.

Solution 2:

At every node, ask the locals for the distance to each neighboring town and the h value there (or visit all neighboring towns yourself, returning to the current town each time).  Set the h value of the sign at the current town to the min(h_neighbor+cost(current,neighbor))  i.e. the min over all neighbors of the distance to go to that neighbor plus the h value on the sign there.  Use Astar to move to a new town and repeat (also works if you move to a random neighbor and repeat).

Problem 5 (by Dimitris)

The modified A* doesn't always return optimal path. Example:

(A 4+0=0)(E 100)
(B 5+0=5)(D 9+90=99)(E 100)
(C 6+0=6)(D 99)(E 100)
(A 7+0=7)(D 99)(E 100)
--> cut edge(C, A)
(B 8+0=8)(D 99)(E 100)

The optimal path S->E->C->A->D->G will never be found.