Assignment 2

CSE 473 - Autumn 2003

Work should be turned in at the start of class on the indicated dates.

1. (Written exercise: Due Wednesday Oct 8. This will be graded credit/no credit. You should not spend more than about 15 minutes on it.) Suppose you are given a problem specified in STRIPS notation that you wish to solve using state-space search that starts at the goal rather than the initial state, as described in R&N page 384.

(a) In the forward-planning case, a state (node) in the search space represents a particular state of the world. What does a node represent in the backward-planning case?

(b) Suppose you have a heuristic h(s,g) for forward-planning that returns an estimate of the distance from the (completely specified) state s to one where the goals g hold. Define a function h' for use in backward-planning in terms of h.

2. (Reading: Due Friday Oct 10.)  R&N 12.2, Hierarchical planning.

3. (Read & Summarize: Due Monday Oct 13.) R&N 7.3 and 7.4, Propositional logic.

4. (Programming project: due Wednesday, Oct 15, by 10:30am.) This project should be done in teams of two people. The task is create an A* based planner for the blocks world. Your planner will read a specification of the initial and goal states in STRIPS notation and will output a solution as specified below. Your planner does not need to read in the operator schemas: it is not a completely general STRIPS planner, but rather is specifically programmed for the blocks world.

The blocks world is described as follows:

There are K blocks and a table. Blocks are identified by integers 1 to K. Each block can sit on one other block or on the table. At most one block can be directly on another block. (You can have a stack of blocks arbitrarily high, but no two blocks and both sitting directly on the same block.  The bottom-most block of a stack must be on the table.)  The table can hold any number of blocks. If nothing is on a block it is clear. The robot arm can hold one block. If the arm holds nothing it is empty.

The kinds of propositions are:

(on block block)
(ontable block)
(clear block)
(holding block)
(empty)

There are 4 kinds of actions as specified by the following action schemas:

action (pickup block)
preconditions: (ontable block) (clear block) (empty)
makes true: (holding block)
makes false: (ontable block) (clear block) (empty)

action (unstack blocka blockb)
preconditions: (on blocka blockb) (clear blocka) (empty)
makes true: (holding blocka) (clear blockb)
makes false: (on blocka blockb) (clear blocka) (empty)

action (putdown block)
preconditions: (holding block)
makes true: (ontable block) (clear block) (empty)
makes false: (holding block)

action (stack blocka blockb)
preconditions: (holding blocka) (clear blockb)
makes true: (on blocka blockb) (clear blocka) (empty)
makes false: (clear blockb) (holding blocka)

Again, note that your program does not need to read in these schemas! They are given here in order to precisely specify the problem.

A state specified by a complete set of propositions for K blocks, one proposition per line. For example, for K=3 the following is a possible state:

(on 1 3)
(clear 1)
(ontable 2)
(ontable 3)
(clear 2)

The following is not a state because it is incomplete:

(on 1 3)
(ontable 2)

The following is not a state because it violates the intended meanings of the propositions as given in the English description of the domain:

(on 1 3)
(clear 1)
(ontable 2)
(ontable 3)
(clear 2)
(clear 3)

A solution is sequence of actions, one per line. For example:

(unstack 1 2)
(putdown 1)
(unstack 2 3)
(stack 3 1)

The format of an input file is as follows, where K is an integer and STATE is a state as described above. Note that you only need to handle goals that are complete states.  

blocksworld K
initial
STATE
goal
STATE
end

Here are some examples and the data for the reference TA-supplied solution. Notice that all but the "Path Length" can vary in reasonable solutions.

The format of an output file is as follows, where
M is an integer, the maximum number of nodes specified when the planner was run (see below).
L is an integer, the number of action in SOLUTION.
N is an integer, the number of nodes searched. A node is counted when it is inserted into the priority queue.

blocksworld K
initial
STATE
goal
STATE
solution M L N
SOLUTION
end

The output file includes a copy of the initial and goal states so that:

• the solution can be fed into the visualizer
• the solution can be checked for correctness

The visualizer is can be downloaded here and is run via the following command:

%>java -jar TRTower.jar < solution.txt

If the planner searches the maximum number of nodes without finding a solution it should print the word "timeout" in place of the line beginning "solution". If the planner encounters an error when reading the input file it should print the word "error" to the output file. (All of the test files we supply will be in the correct format, and we will not explicitly test your program for error handling. But handling erroneous input gracefully is good style for any programming task.)

If your implement your planner in Java it should be invoked by a command line of the following form:

java bwplanner MAX_NODES INPUT_FILE OUTPUT_FILE

If you use a different programming language clearly state in your writeup how it is invoked.

We will supply a java program that visualizes solution files. It is invoked by the command line:

java bwvisual OUTPUT_FILE

You should run your planner on the set of test problems that will be linked to the assignment web page. You writeup should include a table of results that for each problem gives the name of the file, the number of blocks, the length of the solution found, the number of nodes searched, and the time in seconds to find a solution. (You can obtain the time either by using the Linux "time" command or simply timing the planner with a wristwatch.)

Your writeup should describe the data structures you used to represent a state, the heuristic you used, and the table of results. Indicate whether implemented tree-search A* or graph-search A* (with a hash table of "closed" nodes). Indicate how you handled the case of a node changing priority while it is in the queue. (This can be handled either by implementing change_priority methods, or simply by allowing two copies of the node to appear in the queue.)

If you do additional work beyond what is stated in this assignment (for example, comparing different search heuristics, comparing A* to best-first search, comparing tree-search versus graph-search, handling incomplete goal states, etc.), then (i) you will learn a lot and (ii) I will remember it for extra credit when I am calculating final grades.

Additional helpful information may be posted on the assignment web page. You should check the web page at least daily until you complete the assignment. The TA and instructor will make an effort to read the cse473 mailing list over the weekend, but we may not be able to respond promptly. Therefore you would do well to have this assignment well underway before the weekend.