CSci 5511: In Class Activities

1. Week 1 - Thursday September 4.
   To prepare for this activity you need to
   • select and read a paper from The Singularity Issue of IEEE Spectrum. The papers are all very short and written for a general public;
   • write 8-10 lines of comments about the paper you have read;
   • bring to class your written comments on Thursday and use them to help in group discussion;
   • turn in your written comments (do not forget to include your name) to get credit.
   Here is the distribution of papers read:

   Can Machines Be Conscious?	10
   I, Rodney Brooks, Am a Robot	8
   Reverse Engineering the Brain	8
   Waiting for the Rapture	7
   Signs of the Singularity	5
   Teaching AI to Be Sociable	5
   The Consciousness Conundrum	4
   Rupturing the Nanotech Rapture	3
   Two Paths to the Singularity	2
   Economics of the Singularity	1
   others	5

2. Week 2 - Thursday September 11.
   You are given the following problem: "Given a 5-gallon jug filled with water and an empty 2-gallon jug how can you have precisely 1 gallon inthe 2-gallon jug?"
   1. What is the state-space for the problem?
   2. initial state?
   3. goal test?
   4. operators (called in the textbook the successor function)?
   5. path cost?
   6. is the state-space a tree or a graph?
3. Week 3 - Thursday September 18.
   You are given the following graph, where each node has an identifier (a letter) and an h value. A number along an arc indicates the cost of the arc.
   1. Show in what order A* expands nodes from Start to Goal. For each node expanded during the search show its f and g values. If a node is reached on multiple paths show its f and g values each time the node is reached, and indicate its parent node.
   2. What is the solution path found?
4. Week 4 - Thursday September 25.
   This is question 4.3 in the textbook. Prove each of the following statements
   1. breadth-first search is a special case of uniform cost search
   2. breadth-first search is a special case of best-first search
   3. depth-first search is a special case of best-first search
   4. uniform-cost search is a special case of best-first search
   5. uniform-cost search is a special case of A*
5. Week 5 - Thursday October 2.
   Answer key
6. Week 6 - Tuesday October 14.
   
   1. Play a tic-tac-toe game with another student on a 4x4 board with the objective of placing 3 consecutive elements in a row/column/diagonal.
   2. Write down the rules you use when deciding where to put your piece. Be as precise as possible, as if you were to describe an algorithm.
7. Week 7 - Thursday October 23.
   You are given the following set of sentences in propositional logic:
   1. (P or Q) implies R
   2. S implies Z
   3. Z implies P
   4. S
   5. S implies U
   6. U implies Q
   7. Using modus ponens and forward chaining prove that R is entailed by the set of sentences above.
   8. Convert the sentences above to conjunctive normal form and prove R using resolution.
8. Week 8 - Thursday October 30.
   You are given the following pairs of expressions. For each pair show the most general unifier, if they can be unified, or explain why they cannot be unified. The unification algorithm is on page 278 of the textbook.
   1. UNIFY[p(A, x, y, x), p(z, A, B, z)]
   2. UNIFY[r(f(y), B), r(x, f(B)]
   3. UNIFY[p(A, f(x,B), g(f(A,x))), p(A, f(A,y), g(f(x,y)))]
   4. UNIFY[r(f(y), y, x), r(x, f(A), f(v))]
   Answers:
   1. yes, they can be unified {z/A, x/A, y/B}
   2. no, they cannot be unified because B cannot be unified with f(B)
   3. no, they cannot be unified because {x/A, y/B} so we cannot unify x/y
   4. yes, they can be unified {x/f(y), y/f(A), v/f(A)}
9. Week 9 - Thursday November 6.
   Question on resolution.
   Solution
10. Week 10 - Thursday November 13.
    For each of the following sentences, decide if the logic sentence given is a correct translation of the English sentence or not. If not explain briefly why not and correct it:
    1. Every city has a dogcatcher who has been bitten by every dog in town.
       Ax Ay Az City(x) and DogCatcher(y) and Dog(z) and LivesIn(z,x) -> BittenBy(y,z)
    2. One purple mushroom is poisonous.
       Ex Mushroom(x) and Purple(x) and Poisonous(x)
    3. An object is clear if nothing is on it.
       Ex Ay Clear(x) -> not On(y,x)
    4. John loves all his dogs.
       Ax Dog(x) and Owner(John, x) and Loves(John, x)
    5. John loves his dog.
       Ex Dog(x) and Owner(John, x) -> Loves(John, x)
    Answers:
    1. The sentence says that all dogcatchers is every city have been bitten by every dog. To be correct we need to replace Ay with Ey. So it should be
       Ax Ey Az City(x) and DogCatcher(y) and Dog(z) and LivesIn(z,x) -> BittenBy(y,z)
    2. The sentence says that at least one purple mushroom is poisonous. To say there is exactly one purple mushroom that is poisonous we need to say:
       Ex Mushroom(x) and Purple(x) and Poisonous(x) and Ay [Mushroom(x) and Purple(x) and Poisonous(x) -> x=y]
    3. The sentence says that if an object is clear there is nothing on it. To be correct it should be
       Ax Ay not On(y,x) -> Clear(x)
    4. The sentence says that everything is a dog owned and loved by John. We need to replace the last and with ->. [This is one of the common mistakes explained in the textbook. Recall that with the universal quantifier you need an implication.] So it should be
       Ax Dog(x) and Owner(John, x) -> Loves(John, x)
    5. The sentence says that if John owns a dog he loves it. [This is the other common mistake explained in the textbook. Recall that with the existential quantifier you need a conjunction.] To be correct it should be
       Ex Dog(x) and Owner(John, x) and Loves(John, x)
11. Week 11 - Thursday November 25.
    The TA cupcake planning problem. See class forum.
12. Week 12 - Thursday December 4.
    The Graphplan problem For additional explanations on the problem look at the description of mutexes in the class notes.

    

13. Week 13 - Tuesday December 9.
    You are given the following STRIPS actions:
    Action: Pick(o,x),
    Precond: Emptyhand(Robot) and At(Robot,x) and At(o,x)$
    Effect: not Emptyhand(Robot) and Holding(Robot,o) and not At(o,x)

    Action: Drop(o,x),
    Precond: At(Robot,x) and Holding(Robot,o)
    Effect: Emptyhand(Robot) and not Holding(Robot,o) and At(o,x)

    1. Write the successor state axiom for EmptyHand(r)
    2. Write the successor state axiom for Holding(r,o)