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 chess.
c) An agent that can pass the Turing test.
d) An autonomous robot for exploring Mars
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 an admissible heuristic h, that is
never wrong by more than 1. There is exactly ONE optimal solution. How
many expansion steps are needed in A* to find an optimal solution of
length d, in the worst case, if:
1) There is NO other solution of length less than d+2
2) There are k other solutions of length d+1
You need to PROVE your answer!
3) Invent a heuristic function for the cannibals and missionaries problem
that sometimes over-estimates, and show a case where it can lead to a
sub-optimal solution where the path cost is the number of moves (or argue
that such a case does NOT exist DESPITE the over-estimate)!
4) Give an example of a 4-ply game tree (branching factor 2)
where alpha-beta pruning saves NOTHING, and another where the savings
is maximal. How many nodes are pruned in each case?
5) Use truth tables to show that the following sentences are valid:
a) (P <=> Q) <=> ((~P v Q) ^ (P v ~Q))
b) ~(P v Q) <=> (~P ^ ~Q)
c) (P => Q) <=> ~(P ^ ~Q)
6) Which of the following are valid, satisfiable, or neither:
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
7) Represent the following sentences in FOPC - define the vocabulary first.
a) Not all students who pass algorithms pass compilers.
b) Only one student passed Algorithms.
c) Some polititians can fool all of the people all of the time.
d) Every bird has 2 wings.
e) There is a barber who shaves all men in town who do not shave
their barber.
8) Write FOL sentences that define the effects of the "grab" action in the
wumpus world.
9) In situation S0, The robot is in room R1, which has box B1,
The move action moves the robot. If the robot has the box,
the box moves with the robot.
The pickup action results in the robot holding the box (has_box),
if the box is in the same room as the robot.
a) Write down the axioms for this mini-domain.
b) Can you prove that in_room(B1, R2, result(move, result(pickup, S0)))
with your axioms? If yes, do so. If not, what is missing?
c) Can you prove that in_room(B1, R2, result(move, result(wait,
result(pickup, S0))))
with your axioms? If yes, do so. If not, what is missing?
Predicates are: has_box(situation), in_room(object, room, situation).
Actions are: pickup, move(from, to), wait.
Deadline: April 30.