Sheet 2

1. Explain why problem formulation must follow goal formulation.

facing north. You can turn the robot to face north, east, south, or west. You can direct the robot to move
forward a certain distance, although it will stop before hitting a wall.
a. Formulate this problem. How large is the state space?
b. In navigating a maze, the only place we need to turn is at the intersection of two or more
corridors. Reformulate this problem using this observation. How large is the state space now?
c. From each point in the maze, we can move in any of the four directions until we reach a turning
point, and this is the only action we need to do. Reformulate the problem using these actions. Do
we need to keep track of the robot’s orientation now?
d. In our initial description of the problem we already abstracted from the real world, restricting
actions and removing details. List three such simplifications we made.

2. Suppose two friends live in different cities on a map, such as the Romania map shown in
Figure 3.2. On every turn, we can simultaneously move each friend to a neighboring city
on the map. The amount of time needed to move from city i to neighbor j is equal to the
road distance d(i, j) between the cities, but on each turn the friend that arrives first must
wait until the other one arrives (and calls the first on his/her cell phone) before the next
turn can begin. We want the two friends to meet as quickly as possible.
a. Write a detailed formulation for this search problem. (You will find it helpful to define some
formal notation here.)
b. Let D(i, j) be the straight-line distance between cities i and j. Which of the following heuristic
functions are admissible? (i) D(i, j); (ii) 2 · D(i, j); (iii) D(i, j)/2.
c. Are there completely connected maps for which no solution exists?
d. Are there maps in which all solutions require one friend to visit the same city twice?

3. Show that the 8-puzzle states are divided into two disjoint sets, such that any state is
reachable from any other state in the same set, while no state is reachable from any state
in the other set. (Hint: See Berlekamp et al. (1982).) Devise a procedure to decide which
set a given state is in, and explain why this is useful for generating random states.
4. Consider the n-queens problem using the “effi√cient” incremental formulation given on
page 72. Explain why the state space has at least 3 n! states and estimate the largest n for
which exhaustive exploration is feasible. (Hint: Derive a lower bound on the branching factor by considering
the maximum number of squares that a queen can attack in any column.)
5. Give a complete problem formulation for each of the following. Choose a formulation
that is precise enough to be implemented.
a. Using only four colors, you have to color a planar map in such a way that no two adjacent
regions have the same color.
b. A 3-foot-tall monkey is in a room where some bananas are suspended from the 8-foot ceiling. He
would like to get the bananas. The room contains two stackable, movable, climbable 3-foot-high
crates.
 G

Figure 3.31 A scene with polygonal obstacles. S and G are the start and goal states.

c. You have a program that outputs the message “illegal input record” when fed a certain
file of input records. You know that processing of each record is independent of the
other records. You want to discover what record is illegal.
d. You have three jugs, measuring 12 gallons, 8 gallons, and 3 gallons, and a water faucet.
You can fill the jugs up or empty them out from one to another or onto the ground. You
need to measure out exactly one gallon.

6. Consider the problem of finding the shortest path between two points on a plane that has
convex polygonal obstacles as shown in Figure 3.31. This is an idealization of the problem
that a robot has to solve to navigate in a crowded environment.
a. Suppose the state space consists of all positions (x, y) in the plane. How many states are
there? How many paths are there to the goal?
b. Explain briefly why the shortest path from one polygon vertex to any other in the scene
must consist of straight-line segments joining some of the vertices of the polygons.
Define a good state space now. How large is this state space?
c. Define the necessary functions to implement the search problem, including an A CTIONS
function that takes a vertex as input and returns a set of vectors, each of which maps the
current vertex to one of the vertices that can be reached in a straight line. (Do not forget
the neighbors on the same polygon.) Use the straight-line distance for the heuristic
function.
d. Apply one or more of the algorithms in this chapter to solve a range of problems in the
domain, and comment on their performance.

7. On page 68, we said that we would not consider problems with negative path costs. In
this exercise, we explore this decision in more depth.
a. Suppose that actions can have arbitrarily large negative costs; explain why this possi-
bility would force any optimal algorithm to explore the entire state space.
 b. Does it help if we insist that step costs must be greater than or equal to some negative
constant c? Consider both trees and graphs.
c. Suppose that a set of actions forms a loop in the state space such that executing the set in
some order results in no net change to the state. If all of these actions have negative cost,
what does this imply about the optimal behavior for an agent in such an environment?
d. One can easily imagine actions with high negative cost, even in domains such as route
finding. For example, some stretches of road might have such beautiful scenery as to
far outweigh the normal costs in terms of time and fuel. Explain, in precise terms,
within the context of state-space search, why humans do not drive around scenic loops
indefinitely, and explain how to define the state space and actions for route finding so
that artificial agents can also avoid looping.
e. Can you think of a real domain in which step costs are such as to cause looping?
8. The missionaries and cannibals problem is usually stated as follows. Three mission-
aries and three cannibals are on one side of a river, along with a boat that can hold one or
two people. Find a way to get everyone to the other side without ever leaving a group of mis-
sionaries in one place outnumbered by the cannibals in that place. This problem is famous in
AI because it was the subject of the first paper that approached problem formulation from an
analytical viewpoint (Amarel, 1968).
a. Formulate the problem precisely, making only those distinctions necessary to ensure a
valid solution. Draw a diagram of the complete state space.
b. Implement and solve the problem optimally using an appropriate search algorithm. Is it
a good idea to check for repeated states?
c. Why do you think people have a hard time solving this puzzle, given that the state space
is so simple?
9. Define in your own words the following terms: state, state space, search tree, search
node, goal, action, transition model, and branching factor.
10. What’s the difference between a world state, a state description, and a search node?
Why is this distinction useful?
11. An action such as Go(Sibiu) really consists of a long sequence of finer-grained actions:
turn on the car, release the brake, accelerate forward, etc. Having composite actions of this
kind reduces the number of steps in a solution sequence, thereby reducing the search time.
Suppose we take this to the logical extreme, by making super-composite actions out of every
possible sequence of Go actions. Then every problem instance is solved by a single super-
composite action, such as Go(Sibiu)Go(Rimnicu Vilcea)Go(Pitesti)Go(Bucharest). Explain
how search would work in this formulation. Is this a practical approach for speeding up
problem solving?
12. Prove that G RAPH -S EARCH satisfies the graph separation property illustrated in Fig-
ure 3.9. (Hint: Begin by showing that the property holds at the start, then show that if it holds
before an iteration of the algorithm, it holds afterwards.) Describe a search algorithm that
violates the property.
 x 12
x2 x2

x 16

Figure 3.32 The track pieces in a wooden railway set; each is labeled with the number of
copies in the set. Note that curved pieces and “fork” pieces (“switches” or “points”) can be
flipped over so they can curve in either direction. Each curve subtends 45 degrees.

13. Which of the following are true and which are false? Explain your answers.
a. Depth-first search always expands at least as many nodes as A∗ search with an admissi-
ble heuristic.
b. h(n) = 0 is an admissible heuristic for the 8-puzzle.
c. A∗ is of no use in robotics because percepts, states, and actions are continuous.
d. Breadth-first search is complete even if zero step costs are allowed.
e. Assume that a rook can move on a chessboard any number of squares in a straight line,
vertically or horizontally, but cannot jump over other pieces. Manhattan distance is an
admissible heuristic for the problem of moving the rook from square A to square B in
the smallest number of moves.

14. Consider a state space where the start state is number 1 and each state k has two
successors: numbers 2k and 2k + 1.
a. Draw the portion of the state space for states 1 to 15.
b. Suppose the goal state is 11. List the order in which nodes will be visited for breadth-
first search, depth-limited search with limit 3, and iterative deepening search.
c. How well would bidirectional search work on this problem? What is the branching
factor in each direction of the bidirectional search?
d. Does the answer to (c) suggest a reformulation of the problem that would allow you to
solve the problem of getting from state 1 to a given goal state with almost no search?
e. Call the action going from k to 2k Left, and the action going to 2k + 1 Right. Can you
find an algorithm that outputs the solution to this problem without any search at all?

15. A basic wooden railway set contains the pieces shown in Figure 3.32. The task is to
connect these pieces into a railway that has no overlapping tracks and no loose ends where a
train could run off onto the floor.
a. Suppose that the pieces fit together exactly with no slack. Give a precise formulation of
the task as a search problem.
b. Identify a suitable uninformed search algorithm for this task and explain your choice.
c. Explain why removing any one of the “fork” pieces makes the problem unsolvable.
 d. Give an upper bound on the total size of the state space defined by your formulation.
(Hint: think about the maximum branching factor for the construction process and the
maximum depth, ignoring the problem of overlapping pieces and loose ends. Begin by
pretending that every piece is unique.)

16. On page 90, we mentioned iterative lengthening search, an iterative analog of uni-
form cost search. The idea is to use increasing limits on path cost. If a node is generated
whose path cost exceeds the current limit, it is immediately discarded. For each new itera-
tion, the limit is set to the lowest path cost of any node discarded in the previous iteration.
a. Show that this algorithm is optimal for general path costs.
b. Consider a uniform tree with branching factor b, solution depth d, and unit step costs.
How many iterations will iterative lengthening require?
c. Now consider step costs drawn from the continuous range [ϵ, 1], where 0 < ϵ < 1. How
many iterations are required in the worst case?
d. Implement the algorithm and apply it to instances of the 8-puzzle and traveling sales-
person problems. Compare the algorithm’s performance to that of uniform-cost search,
and comment on your results.

17. Describe a state space in which iterative deepening search performs much worse than
depth-first search (for example, O(n2) vs. O(n)).
18. Write a program that will take as input two Web page URLs and find a path of links
from one to the other. What is an appropriate search strategy? Is bidirectional search a good
idea? Could a search engine be used to implement a predecessor function?
19. Consider the vacuum-world problem defined in Figure 2.2.
a. Which of the algorithms defined in this chapter would be appropriate for this problem?
Should the algorithm use tree search or graph search?
b. Apply your chosen algorithm to compute an optimal sequence of actions for a 3 × 3
world whose initial state has dirt in the three top squares and the agent in the center.
c. Construct a search agent for the vacuum world, and evaluate its performance in a set of
3 × 3 worlds with probability 0.2 of dirt in each square. Include the search cost as well as
path cost in the performance measure, using a reasonable exchange rate.
d. Compare your best search agent with a simple randomized reflex agent that sucks if
there is dirt and otherwise moves randomly.
e. Consider what would happen if the world were enlarged to n × n. How does the per-
formance of the search agent and of the reflex agent vary with n?

20. Prove each of the following statements, or give a counterexample:

a. Breadth-first search is a special case of uniform-cost search.
b. Depth-first search is a special case of best-first tree search.
c. Uniform-cost search is a special case of A∗ search