Programming Assignment 3

Assigned: Mar. 23
Due: Apr. 27

Overview

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

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".

Example

A sample problem specification:
3
A B C
START
ON A TABLE
ON B TABLE
ON C B
GOAL
ON A C
ON B A
The corresponding output would be
MOVE C TABLE
MOVE A C
MOVE B A

Grading

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 well commented.