This is a Java implementation of the GraphPlan algorithm, as described in Russell and Norvig or in Richard Dearden's lecture notes. The planner takes problems specified in a subset of PDDL as input.
Note it is intended as demonstration/example code, not as a production-quality planner. If your interest is in solving planning problems quickly, as opposed to using and extending a structured Java GraphPlanner, consider a planner such as FF or one of the other planners used in the IPC.
My planner uses ANTLR v3 to parse PDDL files. The PDDL grammer used is fairly complete, and was converted from the BNF grammar for PDDL 3.0 available here. However the rest of the program has no understanding of the parts of PDDL relating to durative actions or time constraints. The system was developed using some of the most simple PDDL examples from the 2002 International Planning Competition (these samples are included in the zip file).
Downloads
Zip files contain all required source code and JAR files.
| File | Date | Notes | |
| PDDLGraphPlan-0.2.zip | 2-Oct-2008 | Added NotGoalDesc to cope with negated goals/preconditions (contributed by Florian Marquardt), upgraded to work with ANTLR 3.1.1 | |
| PDDLGraphPlan-0.1.zip | 15-May-2007 | Initial release (uses ANTLR 3.0 beta6) |
First, unzip everything into a directory. Then you should be able to use the Windows batch file runPlanner.bat to run the planner on the example files:
> runPlanner testfiles\jugs.pddl testfiles\jug1.pddlIt should run fine on other platforms too, you'll just have to convert the batch file into an appropriate script.
The easiest way to compile the code is with Ant. Then you can just type:
> antand it will generate the ANTLR classes, compile the code and package up the class files into a JAR. If you don't want to use Ant, you will need to firstly run
generateANTLR.bat to create the required ANTLR classes, and then
invoke javac manually.
The system consists of three main parts: a PDDL parser, a plan graph builder, and a solver that finds a valid plan from the graph. Central to all of these parts is a set of domain objects that represent PDDL elements. A component diagram of the system is shown in the figure below, and these components will be described in approximately bottom-up order.
The ANTLR package contains generated code that converts a PDDL document into a syntax tree, which is then processed by classes in the Parser package to create the strongly-typed domain objects.
In the Domain package there are classes to represent domains, problems, actions, functions and predicates. There are also classes to represent the preconditions (called goal descriptions in PDDL) and effects of actions. Goal descriptions and effects are complicated slightly by the fact that literals can be of two types: functions (which have a numeric value) or predicates (with a boolean value). This means the preconditions and effects can use complex expressions involving binary comparisons, binary arithmetic, and conditionals. The Domain package abstracts away the complexity of the different types of expressions by using three interfaces: GoalDesc, which has a boolean value (e.g. a single predicate), NumericExpr, which has a numeric value (e.g. addition of two functions), and Effect, which converts a starting set of literals into a resulting set of literals. The classes implementing these interfaces belong to the Goals and Effects package.
In parallel with the three key Goals and Effects interfaces, there is a hierarchy of classes for representing functions and predicates, as these are used in different contexts. For functions, the classes in this hierarchy are: FunctionDef, which is the de nition in the domain, FunctionHeader, for when the function is referenced in the domain, FunctionInstance, for when functions are used in a problem and actual PDDL objects are matched to parameters, and FunctionLiteral, which is a FunctionInstance with a numeric value, and is used in the plan graph. These function classes implement NumericExpr, and the classes corresponding classes for predicates implement GoalDesc.
Finally, the Plan Graph component contains the PlanGraph and Level classes, which together contain the logic for constructing graphs and mutexes, and the GraphSolver class. Firstly the PlanGraph class constructs an instance of each action for each possible set of argument objects, taking into account the types of the objects. Then the Level class creates each new level in the graph, which is straightforward but involves many set operations to discover mutexes. One point to note is that the set of literals present at each level need not be consistent - that is, the same literal could be present with several different values. This means that several versions of each action need to be created at each level, one version for each value of each literal that is an argument of that action. Lastly, the GraphSolver class adds levels to the graph until the goal condition is satisfied in the literals of the final level, and then searches backwards through the graph to find a list of actions that will result in these end literals. It performs an exhaustive search, so its performance is exponential in the number of levels needed.
There are many areas in which the program could be improved, starting with a simple heuristic to guide the search through the graph. Such a heuristic would improve the performance by orders of magnitude for large problems.
An easy improvement would be to add the full set of goal descriptions supported in PDDL (missing are or, imply, exists, and forall goal descriptions). This would enable the planner to address many more of the problems from the 2002 planning competition.
Finally, although the PDDL grammar for ANTLR is very nearly complete, there are large parts of the language that are not supported in the higher levels of the application (i.e. at the parser, domain, or plan graph level). These features include durative actions, time constraints, and solution metrics.
Back to my home page