CS 343 Artificial Intelligence
Due: February 10, 2009
Homework 1: Search
Consider the 3 blocks world in which only one block can be on another block and
in which the operators include: picking up a block from the table, putting a
block down on the table, stacking a block on another block, and unstacking a
block from another block. The complete state space for this problem is
- In the figure, states in this space are given arbitrary numbers as names
in order to easily refer to them.
- When drawing search trees, number the nodes in the order they are
expanded, circle these numbers to distinguish them from the numbers naming the
- Assume that all children of a state are shown in a search tree but that
states resulting in a cycle in the resulting path from the root are eliminated
as dead-end states as soon as they are generated (draw an X through them).
- If heuristic search is being used, next to each node generated, show the
value of the evaluation function (e.g. "h=2" if just using h, or "1+2=3"
for g+h=f when using A*).
- When there is an undetermined decision (tie) regarding which node to expand
next, assume nodes with lowered numbered state names are preferred (i.e.
expand node 1 before node 2, etc.).
- Assume a goal is detected immediately when it is generated (rather
than waiting until it is expanded), except for A*, where waiting to
check for goal-hood until expansion is critical to guaranteeing an optimal
solution (with an admissable heuristic).
Consider the problem of starting in state 5 with the goal of getting to state 17:
- Draw the search tree resulting from depth-first search. How many nodes
are expanded? (That's "expanded" not "generated"; remember "expansion"
is when a node's successors are generated.)
- Draw the search tree resulting from breadth-first search. How many nodes are
expanded? Is depth-first or breadth-first better for this specific problem? Why?
- Draw the search tree resulting from best-first search using as an
evaluation function the number of blocks not in the correct place as an
estimate of the remaining distance to the goal. For example, the heuristic
value for state 5 is 2 since blocks A and C are not in the correct place (but
block B is) relative to the goal state, 17. How many nodes are expanded?
Could another search strategy perform any less search in solving this specific
problem? Why or why not?
- Assume that ties are broken randomly rather than always choosing the node
with the lowest number. Repeat problem 3, showing search trees for each of the
possible random outcomes (each with its corresponding probability) and compute
the expected number of nodes expanded.
- Repeat problems 3 and 4 for hill-climbing instead of best-first search.
Which expands fewer nodes? Why?
- Draw the search tree resulting from using A* with g being
the number of operators executed and h being the same
heuristic as above and assuming tie-breaking based on node numbers. Is this
heuristic admissable? Why or why not? How many nodes are expanded? Is this
better or worse than best-first and hill-climbing for this case? Why?