Introduction to Artificial Inteligence

Homework assignment - simulators, agents, search and logic

1) For each of the following domains, which type of agent is appropriate
(table lookup, reflex, goal based, or utility based):
   a) An agent that solves the 8 puzzle.
   b) An agent that plays backgammon.
   c) An agent that can imitate Saddam Hussein.
   d) An autonomous robot for exploring the bottom of the sea.

   EXPLAIN each choice in about 2 sentences.

2) We are given a search problem that has a path cost equal to the number
   of operators applied on the path to reach the goal (i.e. the path length,
   as in, e.g. the 8 puzzle). The branching factor is bounded by b (i.e. is
   never more than b). We are given a perfect admissible heuristic h, i.e. is
   never wrong. 
   How many expansion steps are needed in A* to find an optimal solution of
   length d, in the worst case, if:

     1) There is exactly ONE optimal solution.
     2) There are k optimal solutions.

   You need to PROVE your answer!

3) Give an example of a 2-ply (the ply count not including the random element, i.e.
   the tree should have a move by each opponent) EXPECTI-minimax game tree 
   where modified alpha-beta pruning saves NOTHING, and another where the savings
   is maximal. The tree should have branching factor 2 -
   both for players and random element, which can be assumed to be a (not necessarily
   balanced) coin. How many nodes are pruned in each case?

4) Use truth tables to show that the following sentences are valid:
   a)  (P <=> ~Q)    <=>   ((~P v ~Q) ^ (P v Q))
   b)  ~(P ^ Q)     <=>   (~P v ~Q)
   c)  (~P => Q)     <=>   ~(~P ^ ~Q)


5) Which of the following are valid, satisfiable, or neither. For each
   satisfiable sentence, how many models does it have (assuming that each
   sentence contains ALL the variables in the world).
   a) Good => Good
   b) Good => Bad
   b) Bad => Good
   c) (Bad => ~Good) => (Good => ~Bad)
   d) (Good => ~Good)
   e) Big v Dumb v (Big => Dumb)
   f) Good v Bad v Ugly

6) Represent the following sentences in FOPC - define the vocabulary first.
   a) Every cloud has a silver lining.
   b) All men are mortal, but cats have 9 lives.
   c) Some polititians can fool all stupid people all of the time.
   d) Every dog has more than 2 legs and exactly one tail.
   e) There is a barber who shaves all men in town who do not shave 
      their barber.


7)  In the wumpus world, in situation S0, the robot is in room (x, y), which has 
    the gold.
    The move(dx, dy) action moves the robot by dx and dy, resp. (no "turn" necessary
    in this version).
    If the robot has the gold, the gold moves with the robot, and is considered
    to be in the room (in_room(gold, (x, y), S)).
    The pickup action results in the robot holding the gold (has_gold),
    if the gold is in the same room as the robot.

    a) Write down the axioms for the above information for variant of
       wumpus world.
    b) Can you prove that in_room(gold, (x+dx, y+dy), 
                             result(move(dx, dy), result(grab, S0)))
       with your axioms? If yes, do so. If not, what is missing?
    c) Can you prove that in_room(gold, (x+dx, y+dy), result(move(dx, dy), result(wait, 
                                             result(grab, S0))))
       with your axioms? If yes, do so. If not, what is missing?

    Predicates are: has_gold(situation), in_room(object, room, situation).
    Actions are: grab, move(dx, dy), wait.



Deadline: December 5, 2002, at 12 noon.