Programming Assignment 3
Assigned: Mar. 23
Due: Apr. 27
In this assignment you will build a SAT-based planner for
the blocks world. The SAT solver will be the same implementation of
Davis-Putnam that you built for programming assignment 2. What is
new in this assignment, therefore, are the front and back ends.
As in programming assignment 2, the three parts of the planner should be
constructed as three separate programs, each of which reads from
standard input and writes to standard output.
Problem specification and output formats
A problem specification, input to the front end, take the following form
- 1. N, the maximum number of actions in the plan. (Time points go from
0 to N.)
- 2. A list of the names of blocks on one line.
The table has name TABLE and is
not included in this list.
- 3. The keyword START on one line..
- 4. The representation of the starting situation. This consists of
a sequence of assertions "ON block-name object-name"
one assertion per line.
- 5. The keyword GOAL on one line.
- 6. The representation of the goal, in the same format as (4).
The front end uses the
propositional encoding of blocks world problems,
to output a corresponding propositional
encoding for the SAT solver (Davis-Putnam). The back end takes the valuation
found by the SAT-solver and outputs the corresponding plan.
The plan is a sequence of actions
"MOVE B O", one per line. If no plan exists, then the back end should
output the flag "NO PLAN EXISTS".
A sample problem specification:
A B C
ON A TABLE
ON B TABLE
ON C B
ON A C
ON B A
The corresponding output would be
MOVE C TABLE
MOVE A C
MOVE B A
The front end is worth 90% of the grade; the back end is worth 10%.
(Since you did the Davis-Putnam program in assignment 2, you don't get
any more points for that.)
In each of these, a program that does
not compile will get a maximum of 10%; a correct program
will get 90%; the remaining 10% is for being well-written and