CSci 5511: In Class Activities

1. Monday January 26
   This is Question 2.4, page 57 from the textbook. We will examine the rationality of vacuum-cleaner agent functions given the following assumptions (from page 36):
   • The performance measure awards one point for each clean square at each time step over a lifetime of 1000 steps
   • The geography of the environement is known a priori but the dirt distribution and initial location of the agent is not
   • The only actions available are Left, Right, Suck, No-op
   • The agent perceives correctly its environment and whether the location contains dirt.
   1. Explain why the simple vacuum-cleaner agent function down here is indeed rational.

         function Reflex-Vacuum-Agent(location,status] returns an action
           if status = Dirty then return Suck
           else if location = A then return Right
           else if location = B then return Left
      

   2. Describe a rational agent function for the modified performance measure that deducts one point for each movement. Does the corresponding agent program require internal state?
2. Monday February 2
   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 of water in the 2-gallon jug?
   Assume you can fill the jugs with water as many times as desired, but you cannot measure how much water is in each jug. When you move water out of a jug you can either fill up the other jug or dump the water.
   You are to formulate the problem using a state-space search representation.
   1. what is the initial state?
   2. the goal test?
   3. the actions (called in the textbook successor function)?
   4. the path cost?
   5. the state-space for the problem?
   6. is the state-space a tree or a graph?
3. Monday February 9
   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. Monday February 16
   
   1. Write the constraint equations for the following cryptoarithmetic problem:

      S E N D +
      M O R E =
      -----------
      M O N E Y
      

   2. solve it
   3. skecth the search tree to solve the problem. What heuristics did you use for each guess?
5. Monday March 2
   Show the backed-up values for all the nodes in the following game tree and show the branches that are pruned by alpha-beta.
   Track the values of alpha and beta during the process.
   For each branch pruned, explain briefly why alpha-beta prunes it
   Follow the convention used in the textbook to examine the branches in the tree from left to right.
   
6. Monday March 9
   This is question 7.8 from the textbook. Decide whether each of the following sentences is valid, unsatisfiable, or neither. Verify your decisions using truth tables or equivalence rules.
   1. Smoke -> Smoke
   2. Smoke -> Fire
   3. (Smoke -> Fire) -> (not Smoke -> not Fire)
   4. Smoke or Fire or not Fire
   5. ((Smoke and Heat) -> Fire) <-> ((Smoke -> Fire) or (Heat -> Fire))
   6. (Smoke -> Fire) -> ((Smoke and Heat) -> Fire)
   7. Big or Dumb or (Big -> Dumb)
   8. (Big and Dumb) or not Dumb
7. Wednesday March 25
   You are given the following axioms:
   1. Anyone passing his history exam and winning the lottery is happy.
   2. Anyone who studies or is lucky can pass all his exams.
   3. John did not study but he is lucky.
   4. Anyone who is lucky wins the lottery.
   • write them in predicate calculus. It is important that you choose consistent predicates for the different sentences.
   • translate them to CNF
   • Prove using resolution that ``John is happy.''
8. Wednesday April 1
   
   • Consider the following 4 sentences:
     1. At most one student knows the answer.
     2. One student knows the answer.
     3. Less than two students know the answer.
     4. At least one student knows the answer.
     5. Zero or one students know the answer,
     Circle the following sentence pairs that are logically equivalent:
     ab, ac, ad, bc, bd, be, cd, ce, de
   • Disambiguate (if necessary) and translate each of the following sentences into first order logic.
     1. All pets are either cats or dogs.
     2. Some children are tall bullies.
     3. There are only two green boxes.
9. Wednesday April 8
   You are given the following information:
   • A Buick is a kind of automobile.
   • All automobiles can be driven.
   • All automobiles have a body and four wheels.
   • A Skybird is a kind of Buick.
   • A Skybird has a sport body.
   • The particular Skybird with serial number 10789 has a red body.
   • A Skybird body has a left door and a right door.
   • The right door of a Skybird is a passenger door.
   • The left door of a Skybird is a driver door.
   • Driver doors and passenger doors have a trapezoid shape.
   • A car door has a handle.
   • The engine of a Skybird is a model 600.
   • A model 600 engine has four cylinders.
   Represent the information using a semantic network. Be precise in distinguishing classes from individual objects.
   If you had to write an algorithm to compute all the parts of an object which is represented by your semantic network how would you do it?
10. Wednesday April 22
    You are given the following information STRIPS action schemas:
    ACTION (Grab(o,p),
      PRECOND: At(o,p) and Clear(o)
      EFFECT: Held(o) and not At(o,p) and not Clear(o)
    ACTION (Drop(o,q),
      PRECOND: Held(o)
      EFFECT: not Held(o) and At(o,q) and Clear(o)
    Write the corresponding successor state axioms for the fluents Held and At.
11. Monday April 27
    You are given the following STRIPS action schemas:
    Action (MakeDrink,
      Precond:CleanCup and HaveMilk
      Effect: HaveDrink and not CleanCup and not HaveMilk)
    Action (Drink,
      Precond: Thirsty and HaveDrink
      Effect: Happy(x) and not Thirsty and not HaveDrink)
    and
    Initial State: Thirsty and CleanCup and HaveMilk
    Goal: Happy
    1. Draw the planning graph. Mark all the mutexes between action instances and between propositions, and indicate for each the type of mutex.
    2. At what level is the problem solved? why?
    Copyright: © 2009 by the Regents of the University of Minnesota
    Department of Computer Science and Engineering. All rights reserved.
    Comments to: Maria Gini
    Changes and corrections are in red.