Course CS638 (July-Dec 2006)
Title Aritificial Intelligence
Instructor Dr. Deepak Khemani

End Semester Solutions


1.       The graph below represents a city road map. The nodes are located on a two dimensional grid as shown. The grid interval is ten units. Edge costs are marked on the map. Starting at node S show the order in which A* Search expands nodes till it reaches the Goal G. , Mark all nodes on OPEN and CLOSED with the f-values used and parent pointers. Show the path found by A*. Use the MANHATTAN distance as the heuristic function. Is the algorithm guaranteed to find the shortest path? Give reasons for your answer.                                                                      [marks 15]


The pink coloured nodes represent closed nodes.

The uncoloured nodes represent the nodes in the open list.

The shortest path is marked with bold arcs.


2.      Describe the algorithm Ant Colony Optimization. What are the two factors that govern the movement of an ant in Ant Colony Optimization?                                                             [marks 10]


3.       Trace the progress of the algorithm AO* on the following graph. The nodes are labeled with their heuristic values. Leaves are labeled with the cost of solving them. Assume that the cost of each edge is 10. Show the evolving graph after each stage of node expansion. In the final graph clearly mark the solution found. Is the algorithm admissible on the given problem graph?                                                                                                                                    [marks 15]





4.       Describe either the Divide and Conquer Frontier Search algorithm or the Sparse Memory Graph Search algorithm. What is the motivation behind these algorithms?                                                                                                                                                                                        [marks 10]

5.       What is the main idea behind Beam Stack Search? What are the advantages and disadvantages of Beam Stack Search as compared to A*.                                                                           [marks 10]


6.       Algorithm SSS* is searching a four ply binary game tree (16 leaf nodes). The leaves of the tree, reading left to right, evaluate to 20, 10, 8, -3, 11, 6, 3, 7, -9, -12, 15, -17, 18, 21, 17, -6. Show how SSS* explores the above tree.                                                [marks 15]



7.       Forward chaining and backward chaining are unable to handle rules with disjunctive consequents. What about disjunctive antecedents in rules? Can we handle rules of the kind   (if (or (p q)) r) ? Justify your answer.                                                                                                                 [marks 12]


Yes, disjunctive antecedents can be handled. The given rule can be rewritten as,

 (if (or (p q)) r)               (or (not (or (p q)) r)

                     (or (and (not p) (not q)) r)

                     (and (or (not p) r) (or (not q) r)

                     (and (if p r) (if q r))


Thus the given rule is equivalent to two simple rules (if p r) and (if q r), each of which can be handled by both forward chaining and backward chaining.

8.       Is the following argument valid? Justify your answer.

a.       B (C D)

b.       (C A) E

c.       F (D E)

  A (B F)                                                                            [marks 8]


Proof by assumption.

d.       A                    assumption

e.       B                    assumption

f.         (C D)         a, e, modus ponens

g.       C                    f, simplification

h.       (C A)           g,d, conjunction

i.         E                 h, b, modus ponens

j.         ~D                  f, simplification

k.       ~D ~E         j,I, conjunction

l.         ~(D E)         k, deMorgan

m.     ~F                  l,c, modus tollens

n.       B F           e,m, CP (conditional proof)

o.       A (B F)  d,n, CP (conditional proof)



Proof by resolution refutation

Converting the facts to clause form

B (C D)                  (~B C) (~B ~D)

(C A) E                  (~C ~A ~E)

F (D E)                     (~F D E)


            Negation of goal clause

                   ~(A (B F))               A B F


The clauses are

    1. (~B C)
    2. (~B ~D)
    3. (~C ~A ~E)
    4. (~F D E)
    5. A
    6. B
    7. F


By resolution

    1. D E               from g,d
    2. ~D                    from f,b
    3. E                      from h,i
    4. (~C ~A)         from c,j
    5. C                      from a,f
    6. ~A                    from l,k
    7. NULL                from e,m


9.       Given the following facts,

       "One of Tinker, Tailor, Soldier, or Spy is the culprit. The culprit stole the document. Tinker and Soldier did not steal the document. If Tailor or Spy is the culprit, then the document must be in Paris."

      Show, after encoding the facts in predicate calculus, AND using resolution refutation, the proof of the following statement,

            "The document is in Paris."                                                                        [Marks 15]


One of Tinker, Tailor, Soldier, or Spy is the culprit.

            culprit(Tinker)  ∨ culprit(Tailor)  ∨ culprit(Soldier)  ∨ culprit(Spy)


The culprit stole the document.

            x (culprit(x) stole(x, Document)       ~culprit(x1)  stole(x1, Document)


            Tinker and Soldier did not steal the document.

            ~stole(Tinker, Document) ~stole(Soldier, Document)


      If Tailor or Spy is the culprit, then the document must be in Paris.

      (culprit(Tailor) culprit(Spy) in(Paris, Document)

                  (~culprit(Tailor) in(Paris, Document))  ∧ ~(culprit(Spy) in(Paris, Document))


      The document is in Paris

      In(Paris, Document)


      Negated goal clause,

      ~In(Paris, Document)


The clauses are,

a.       culprit(Tinker)  culprit(Tailor)  culprit(Soldier)  culprit(Spy)

b.       ~culprit(x1)  stole(x1, Document)

c.       ~stole(Tinker, Document)

d.       ~stole(Soldier, Document)

e.       ~culprit(Tailor) in(Paris, Document)

f.         ~culprit(Spy) in(Paris, Document)

g.       ~In(Paris, Document)


By resolution method,


h.       ~culprit(Tailor)                                                          from g,e

i.         ~culprit(Spy)                                                            from g, f

j.         culprit(Tinker)  culprit(Tailor)  culprit(Soldier)        from a, i

k.       culprit(Tinker)  culprit(Soldier)                                from j, h

l.         ~culprit(Tinker)                                                         from b,c

m.     culprit(Soldier)                                                         from k,l

n.       ~culprit(Soldier)                                                       from b,d

o.       NULL                                                                      from m,n




10.   Construct a Rete net for the following set of rules

Rule 1: (p greenPyramid-rule

                        (block ^name <x>)

(base ^block <x> ^shape square ^area > 1)

(side ^block <x> ^angle < 90 ^surface plane ^colour green)

(top ^block <x> ^surface point)


                                    (make (class ^block <x> ^type greenPyramid)))


Rule 2: (p cylinder-rule

(block ^name <x>)

(base ^block <x> ^shape circle ^area > 1)

(side ^block <x> ^angle  90 ^surface curved)

(top ^block <x> ^surface flat)


                                    (make (class ^block <x> ^type cylinder)))


Rule 3: (p wand-rule

(block ^name <x>)

(base ^block <x> ^shape circle ^area 1)

(side ^block <x> ^angle < 90 ^surface curved ^colour black)

(top ^block <x> ^surface point)


                                    (make (class ^block <x> ^type wand)))


Rule 4: (p dome-rule

(block ^name <x>)

(base ^block <x> ^shape circle ^area > 1)

(side ^block <x> ^angle 90 ^surface curved)

(top ^block <x> ^surface spherical)


                                    (make (class ^block <x> ^type dome)))



Show where the following tokens reside in the Rete Net.


  1. (base ^block A ^shape square ^area 20)
  2. (base ^block B ^shape circle ^area 20)
  3. (base ^block C ^shape circle ^area 1)
  4. (side ^block C ^angle < 90 ^surface curved ^colour black)
  5. (side ^block A ^angle < 90 ^surface plane ^colour green)
  6. (top ^block A ^surface point)
  7. (top ^block C ^surface point)
  8. (top ^block D ^surface point)
  9. (side ^block B ^angle  90 ^surface curved)
  10. (top ^block B ^surface flat)
  11. (block ^name A)
  12. (block ^name B)
  13. (block ^name D)


What is the conflict set?                                                                               [marks 15]




11.   Describe the heuristic function submitted by you in the game competition.

[marks 15]

 End of paper.