This version differs from the preliminary version distributed earlier in that

1. you are now required to have the state class Planning State implement the State interface of Assignment 1.
2. A few of the methods of the assignment are more completely specified.
3. A skeleton of the PlanningState class definition is now on the class web site; please use it to start your definition.
4. The final version of the test class A3 is now available on the class web site.
5. Details of the matching and unification algorithms you'll need to use, but not code for these algorithms, are now available on the class web site.

Implement a simple A*-based classical planning algorithm by defining classes PlanningState, Action, Literal , Term , LiteralList, and LiteralList as specified below. Test with the test class A3 that is available from the class web site. You will also need the AStar class and the State interface from Assignment 1. As always, you may define any additional classes, methods, or variables that you find useful. I recommend that you define at least a Substitution class and perhaps a Binding class.

The Term class should have a constructor taking a string, which is interpreted according to the naming conventions below. It should have an appropriate toString method. It should be used by your Literal class.

The Literal class should also have a constructor taking a string, according to the conventions below. It should have an appropriate toString method that prints the literal being represented in something close to a conventional notation. You should use this class in your LiteralList class. You will doubtless want to define other methods for this class to help in the matching, unification, and substitution applications that are needed in planning algorithms.

The LiteralList class is to represent lists of literals in states, and in preconditions, add lists, and delete lists for actions. It should have a default constructor and perhaps other constructors. It should have a method addLiteral to add a literal to a list, and a separate method addGroundLiteral that checks whether its argument is a ground literal before adding it to the list. It should have a method countSatisfiedSubgoals that takes a LiteralList representing a list of goals, and determines how many conjuncts (literals) are satisfied. For this method, you may assume that all literals in the goal are ground literals. It should have an appropriate toString method. You will doubtless need to have other methods and perhaps constructors for this class.

The Action class should have a constructor that builds an action from its predicate name (a string), its argument list (a list of Terms), and its preconditions, add list, and delete list (all represented as LiteralLists. The class should have appropriate selectors. It should also have analog of a toString method that takes a substitution as argument. This will be useful for representing the histories of states in terms of lists of actions with instantiated parameters.

The PlanningState class should have a default constructor, a methodthat adds a literal to the state description, and a method that adds an action to the list of permitted actions. A skeleton of this class is provided on It should implement the State interface of Assignment 1. It should have a method setGoal that provides a new goal (represented as a LiteralList for the state. It should have a toString method whose return values gives at least gives a representation of the state description and the history of the state. The description of the history should be a list of actions with instantiated parameters, as described in the previous paragraph. The method needn't give a representation of the set of permitted actions. The class should have a method findMatches that takes a set of preconditions (represented as a LiteralList) and returns a list of all unifying substitutions that make the preconditions match the state description. Please leave this method public, since it is invoked in the test class A3. You will likely need other methods and perhaps constructors as well (e.g., a method that applies an action to the state.

Use the following naming conventions: strings representing literals or argument lists are to consist of strings representing terms, separated by whitespace (as defined for the default behavior of the Scanner class. So tokens may contain parentheses, brackets, commas, and tildes. The first token in a literal is the name of the predicate (there must be a predicate name, but there needn't be any arguments). Other tokens are interpreted as variables if and only if they begin with a question mark. Predicates with the same name but different numbers of arguments are assumed to be different.

You may assume that all literals are positive and function-free, and that literals appearing in states and goals are always ground (so their arguments are always object constants). Terms appearing in preconditions, add lists, and delete lists may be variables. You should ensure that new literals in state descriptions and goals are ground literals.

You needn't ever check whether new literals equal or subsume existing literals when updating a LiteralList. You needn't index the literals or arguments in a state description. You needn't worry about equality, so it's perhaps ok if your solutions involve moving blocks onto themselves, etc. Your toString methods may use the default toString method for lists.

You may need to do a substantial amount of copying of objects for this assignment. Ideally you will be able to design your classes so that you don't have to do a huge amount of copying.

If you need to increase the size of the heap in the AStar class to get your test cases to run, feel free to do so. If you do this, please document it somewhere. Your printed output should not be overly long, if you are careful about what your toString methods print. Mine is 8 pages.

You are to turn in both hard and soft copies of all of your code (but not A3.java or State.java or AStar.java, unless you modify them), as well as a hard copy of the results of your testing. Please email a zipped file (not a *.rar file) if at all possible. Otherwise you can send me an email separate text file attachements, or submit your soft copy on a diskette. Please don't turn in a CD unless it's absolutely necessary.