Work should be turned in at the start of class on the indicated dates.
1. Due Oct 1: Read & Summarize: R&N 3.1-3.5 (uninformed search).
2. Due Oct 3: Read & Summarize: R&N 4.1-4.2 (heuristic search).
3. Due Oct 6: Written Exercises:
(a) Which search method(s) described in the readings above might run forever using TREE-SEARCH but must eventually stop when using GRAPH-SEARCH (assuming that a solution does indeed exist)?
(b) On page 101 of R&N the statement appears:
Computation time is not, however, A*'s main drawback. Because it keeps all generated nodes in memory (as do all GRAPH-SEARCH algorithms), A* usually runs out of space long before it runs out of time.
This statement is not precisely correct. Although a GRAPH-SEARCH version of A* must keep all nodes in the "closed" list, a TREE-SEARCH version can discard nodes after they are expanded. Suppose you are searching an infinite tree with branching factor b using A*, and you are about to expand a node that is at distance k from the starting node.
(i) State the best case number of nodes in the priority queue at this point in order of magnitude notation. State a sufficient property of the heuristic function h that leads to this best case.
(ii) State the worst case number of nodes in the priority queue at this point in order of magnitude notation. State a sufficient property of the heuristic function h that leads to this best case. (Try to come up with a property that is more general than, say, h=0 for all nodes.)
(c) Describe a representation of Rubik's Cube as a state-space search problem and an admissible heuristic. Clearly state why your heuristic is admissible. Are you able to tell whether your heuristic is also consistent (see page 99)?
4. Due Oct 6: Read: R&N 11.1-11.2 (planning with state-space search). (You do not need to turn in a summary.)
Assignment 2 will be to create a planning system using state-space search that generates a sequence of commands to control a (simulated) robot arm. Insights gained from working on this simple domain, called the blocks world, have yielded useful new algorithms for search and planning for over 30 years.
I will be out of town Sept 30 - Oct 3. Prof. Oren Etzioni will lecture on Oct 1, and the TA Jeffrey Bigham will lecture on Oct 3. If you have questions about course material while I am away please contact Jeffrey. If you have questions about registration or other academic issues that cannot wait until I return please talk to Crystal Eney, Megan Reardon, or Elizabeth Rowson.