WPI Worcester Polytechnic Institute

Computer Science Department

CS4341 Introduction to Artificial Intelligence 
Project 3 - B 2003


  1. Part I: Thursday, December 04, 10 am (beginning of class). 
  2. Part II: Tuesday, December 09, 9:00 pm. 

Homework and Project Goal:

The purpose of this project is to implement a planning system. Given a collection of operators, an initial situation and a goal situation, this planning system will construct a most general plan of actions (instantiations of the operators) that when performed in sequence transform the initial situtation into the goal situation, if such plan exists, and will report failure otherwise.

The goal of this project and homework matches the following Course Objectives:

Part I. Homework Assignment:

Follow by hand on a piece of paper the planning procedure described in class as well as in Chapter 15 of Winston's book to the planning problem described in planning3.txt. See below for the Input conventions. An outline of this planning procedure is described below. Your solution to the homework must show all establishes, threatens, and before links, as well as all the steps of the procedure including failure/backtracking branches. As an illustration, see the answers to the planning problem in my D2001 offering of this course

Outline of the Planning Procedure

Homework Submission:

The homework is due at 10 am on Thursday Dec. 04, 2003.  Please hand in one HARDcopy of your group solutions to the homework assignment by the beginning of the class on Thursday Dec. 04.

Homework Grading:

Part II. Project Assignment:

Input Specifications:

The input file consists of 4 different parts (see the test files listed above for illustration):

  1. A "declaration" of the variables used in the input file, and a list of the values they can assume. This declaration is of the following form:
         <type> <value1> <value2> ... <valuei> <variable1> <variable2> ... <variablej>

  2. A list of IF ADD DELETE rules. Each rule is written in the following format
         OPERATOR <operator name> <argument1> <argument2> ... <argumenti>
    Each condition (pre or postcondition) consists of three parts: one relational symbol and two arguments. We hereby call these conditions "relational statements". Examples of relational statements are:
         move-to ?x table
         stack-on ?x ?y
         read ?x nil 
         sell car nil
    Identifiers that start with a question mark denote variables. Note that in the last two cases, the second argument is not needed and so "nil" is used there as a placeholder for the second argument. This is just to simplify your life as you can assume that all the relational statements have 2 arguments.

    Operators are separated by lines that contain the string "#####"

  3. A list of facts in the initial situation. This section of the file starts with a line containing the string "INITIAL". Each fact follows the same format described for relational statement above. This section of the file ends with a line containing the string "#####".

    In the case of an initial empty initial situation, this section of the file will look like:


  4. A list of facts in the goal situation. This section of the file starts with a line containing the string "GOAL". Each fact follows the same format described for relational statement above. This section of the file ends with an empty line.

Output Specifications:

Your output should be a full, partially ordered plan of actions your program can construct to transform the initial situation into the goal situation, if such a plan exists or the word "FAILURE" if such a plan is impossible. In the case that a plan exists, some of the actions may need to be executed before others, and so your output should specify any "before" constraints of your plan.

Your output should consist of two parts:

  1. The word "ACTIONS:" followed by the list of actions in the plan (each on its own line), ideally printed following a kind of "breadth-1st", level by level traversal of the plan starting from the initial situation.
  2. Followed by the title "BEFORE CONSTRAINTS:" and the full list of "before" constraints.
For instance, the Winston's solution for the block planning problem described in planning1.txt (see Winston's figure 15.8) would be printed out as:
moveblock d b table
moveblock a c table
moveblock a table b
moveblock b table c
moveblock d b table BEFORE moveblock a table b
moveblock d b table BEFORE moveblock b table c
moveblock a c table BEFORE moveblock a table b
moveblock a c table BEFORE moveblock b table c

Your Code:

Your code must implement the outline of the planning procedure above. In particular, your code must have functions that handle the instantiation of the variables in an operator; the construction of all applicable instantiations of the operators to achieve a subgoal; the search tree with "establishes", "threatens", and before links; the depth-1st search for the plan; etc.

Although you are welcome to look at other code to guide the design of your program, you MUST submit your own original code.

Project Submission:

Project 3 Part II is due at 9 pm on Tuesday December 09, 2003.  One (and only one) member of your group should submit the following files using the turnin program. The name of the turnin directory is proj3.

Project Grading:

Note that below we don't assign points to each of the test cases but to the process that they are following to construct the answer. Hence the test cases should be used to give the grader an idea of what your program does right or wrong.

Graduate Credit Problem:

Due on Tuesday, Dec. 09 at 9 pm.  (Adapted from Dean, Allen, and Aloimonos's book). Discuss how you would need to modify your planning system so that it is able to handle planning situations in which there is a pool of resources that need to be allocated and disallocated. Discuss the extensions needed to handle each of the following type of resources:
  1. (10 points)Resources that are discrete and reusable, for instance tools, cpus, etc.
  2. (10 points)Resources that are continuous, for instance fuel.
  3. (10 points)Resources that are non-reusable, for instance parts.
  4. (10 points)Resources that are shareable, for instance vehicles.