CS4341 Introduction to Artificial Intelligence 
Project 3 - B 2003

PROF. CAROLINA RUIZ 

DUE DATES:

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

• Homework and Project Goal
• Part I. Homework Assignment
  • Homework Submission
  • Homework Grading
• Part II. Project Assignment
• Input Specifications
  • Sample Input Files
    • planning1.txt
    • planning2.txt
    • planning3.txt
    • hanoi_towers.txt
• Output Specifications
• Your Code
• Project Submission
• Project Grading
• Graduate Credit Problem

Homework and Project Goal:

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

• Learning to apply course material (to improve thinking, problem solving, and decision) during the design, implementation, and analysis of computer programs that reason and/or act intelligently.
• Learning fundamental principles about and generalizations of knowledge representation techniques.
  Practice with and evaluation of this objective.
• Learning fundamental principles about and generalizations of computational problem solving strategies.
• Developing creative capacities for the design, implementation, and analysis of computer programs that reason and/or act intelligently.
• Learning to analyze and experimentally evaluate designs and implementations of the intelligent computer programs, in particular those developed during the course projects.

Part I. Homework Assignment:

• A plan is constructed using "backward search" starting from the goal state and finding operators whose postconditions match the assertions in the goal state, and then the process is applied recursively to satisfy the preconditions of those operators.

• An operator is introduced when there is an assertion in the goal state or a precondition in any of the operators currently in the plan that is still not satified by other operators in the plan or the assertions in the initial state. If there are several operators (or several different instantiations of the variables of one or more operators) that can be used to satisfy such assertion or precondition, then those alternative operators are sorted in the order described below and are explored in a depth-1st manner, allowing for backtracking.

  1. Two different operators are sorted in the order in which they appear in the input file. For instance, if the operators moveblock ?x ?y ?z and moveblock ?x ?y table in planning1.txt both apply in a given situation, then the operator moveblock ?x ?y ?z has precedence over the operator moveblock ?x ?y table because the former appears before the latter in the input file.

  2. Two different instantiations of the variables are sorted using "lexicographic" (see examples below) order over the values associated to the variables. Two values are sorted in the order in which they appear in the header of the input file. For instance, the header in planning2.txt

                room livingroom kitchen ?R1 ?R2
                object beer ?Obj
                

     state that livingroom has precedence over kitchen because it appears first in the file. Also, since ?R1 and ?R2 are of type room then the possible instantiations of each of these variables are livingroom and kitchen, and the only possible instantiation of ?Obj is beer, the possible instantiations of the operator carry ?R1 ?R2 ?Obj are:
     1. carry livingroom kitchen beer
     2. carry kitchen livingroom beer
     The first one, carry livingroom kitchen beer, has precedence over the second one, carry kitchen livingroom beer, because "livingroom kitchen" is smaller than "kitchen livingroom" in this lexicographic order.

  3. You can use the convention that the same (constant) value is NOT used to instantiate more than one variable of an operator. For instance, for the operator "moveblock ?x ?y ?z", you can eliminate from consideration instantiations like ?x = a, ?y = a, ?z = a; and like ?x = a, ?y=b, ?z = a, since in those cases the same value ("a") is used for more than one variable.

     Also, for "carry ?R1 ?R2 ?Obj", the possible instantiations are:

     1. carry livingroom kitchen beer
     2. carry kitchen livingroom beer

     eliminating from consideration:

     • carry livingroom livingroom beer
     • carry kitchen kitchen beer

  4. You need to consider all valid instantiations of all the operators that accomplished the current subgoal, and consider one at a time until a full plan without unresolved threats is constructed. If your system finds a threat that cannot be resolved using before links, then the search needs to backtrack to consider another alternative.

  5. You may want to use the following heuristic to decide in which order to explore alternative instantiations of the applicable operators. You may use this heuristic in combination with or instead of the lexicographic order described above. Here is the heuristic: "among all possible instantiations of all the operators that establish the current subgoal, explore first the one with the least number of preconditions not yet satisfied in the current plan by the initial situation and/or by other operators already included in the plan".

  6. You search for a plan should avoid loops (i.e. applying the same instantiation of an operator more than once in a branch of the plan).

• When the postcondition of an operator 1 in the plan matches/satisfies the precondition of another operator 2 in the plan, we say that operator 1 "establishes" operator 2. A "threatening" situation is present when the postcondition of a third operator in the plan invalidates the precondition of operator 2 that operator 1 has established. A way to resolve this conflict is to add time constraints to the plan, requiring that operators 1 and 2 be executed before operator 3, or that operator 3 be executed before operators 1 and 2. If both options are impossible to satisfy, then the current branch of the search fails and the whole process backtracks.

• The search for a plan ends successfully when all the assertions in the goal state as well as all preconditions of the operators in the plan are satisfied. The search for a plan ends unsuccessfully when the search has backtracked to the end and there are no more ways to combine the operators to satisfy all conditions.

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:

• (5 points) Constructing the plan using "backwards" search.
• (30 points) Including "establishes" links correctly:
  • (20 points) identifying all alternative instantiations of the applicable operators for each subgoal.
  • (10 points) exploring those alternatives in a depth first manner, either using the "lexicographic" order, or the "heuristic" order, or a combination of the two, as described above
• (25 points) Identifying all threats correctly.
• (20 points) Resolving threats using before links if possible.
• (10 points) Backtracking appropriately if threats cannot be resolved using before links.
• (10 points) Producing a full, partially ordered plan.
• Total: 100 points.

Part II. Project Assignment:

• Your program must run on the CCC Unix machines
• You may use any high-level language (Java, Lisp, Prolog, C, C++, ...).
• Your program must adhere to the Input and Output Specifications below.
• Your program must implement the planning procedure described in class, in Chapter 15 of Winston's book, and in the outline of the planning procedure above. Your implementation must use establishes, threatens, and before links, as well as a depth-1st search with backtracking.

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>
        IF
        precondition-1
        precondition-2
        ...
        precondition-n
        ADD
        postcondition-1
        postcondition-2
        ...
        precondition-k
        DELETE
        postcondition-k+1
        postcondition-k+2
        ...
        precondition-k+m
        

   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.
   • The first relational statement above represents the action of moving object ?x to the table.
   • The second relational statement represents the action of stacking object ?x on top of object ?y.
   • The third relational statement represents the action of reading object ?x.
   • The fourth relational statement represents the action of seling a car.
   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:

       INITIAL
       #####
       

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.

 
ACTIONS:
moveblock d b table
moveblock a c table
moveblock a table b
moveblock b table c
BEFORE CONSTRAINTS:
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.

• proj3_readme.txt: Containing:
  • the names of the members of your group
  • FOR EACH GROUP MEMBER, describe in detail the precise contribution of the group member to the overall project under submitted.
  • code documentation following the Departmental Documentation Standard
  • instructions on compiling and running your program
• proj3_script.scr: A capture script of your program working on each of the sample files above
• The source code for your program
• A complete description of any other heuristics you used in your program to make your plan construction better.
• Any ancillary files that your program requires

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.

• (10 points) Documentation.
• (30 points) Including "establishes" links correctly:
  • (20 points) identifying all alternative instantiations of the applicable operators for each subgoal.
  • (10 points) exploring those alternatives in a depth first manner, either using the "lexicographic" order, or the "heuristic" order, or a combination of the two, as described above
• (25 points) Identifying all threats correctly.
• (20 points) Resolving threats using before links when possible.
• (10 points) Backtracking appropriately if threats cannot be resolved using before links.
• (05 points) Producing a full, partially ordered plan using "backwards" search.
• Total: 100 points.

Graduate Credit Problem:

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.