PropPlan: yet another planner!
PropPlan is an AI planner based on naïve breadth-first state-space search.
PropPlan uses Ordered Binary Decision Diagrams, introduced by Bryant, to represent large sets of states efficiently. This allows us to implement exhaustive, breadth-first state-space exploration. Like Graphplan, PropPlan uses forward chaining to establish a layered set of reachable states until the goal-set is reached, then backward chaining for plan extraction.
You can run PropPlan online, it uses the Planning Domain Definition Language, PDDL. The current version accepts full STRIPS and ADL constructs, and also domain-axioms. Resource constraints are implemented using bounded quantifiers. Several example domains are provided, or you can write your own.
Run PropPlan Online
This link allows you to run PropPlan over the web. You can edit the examples given or cut and paste your own PDDL definitions into your browser. PropPlan Online uses HTTPrequest and will only run on browsers that support this.
Languages
PropPlan is written in StandardML, is compiled with PolyML under Linux, and uses the PolyML C interface to call David Long's C-library, BDDLIB, or the BuDDy BDD library (which is more portable, but slower), to do most of its work. The online version uses BDDLIB, and its web interface uses Perl and Javascript.
Publications
Sourcecode is available. The latest release is browsable here. CVS repository can be accessed on sourceforge.
To retrieve the current development version use the command:cvs
-d:pserver:anonymous@propplan.cvs.sourceforge.net:/cvsroot/propplan
export -DNOW PropPlan
When asked for password,
hit return.
Michael P. Fourman. Logics for action. In Proceedings of the 3rd Indian International Conference on Artificial Intelligence IICAI, pages 1223-1237, Pune, India, December 2007. EDI-INF-RR-1153.
Michael P. Fourman. Categorical perspectives. In 14th International Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR), Yerevan, Armenia, October 2007. EDI-INF-RR-1172.
Michael P. Fourman. Local perspectives on action. In Johan van Benthem, Shier Ju, and Frank Veltman, editors, A Meeting of the Minds: Proceedings of the Workshop on Logic, Rationality and Interaction, pages 145-157, Beijing, August 2007. College Publications, London. EDI-INF-RR-1138.
Michael P. Fourman. Propositional planning. In Workshop on Model-Theoretic Aproaches to Planning, AIPS 2000, April 2000. EDI-INF-RR-0034.
Future Plans
A web services interface to PropPlan is planned ...
PropPlan is based on a naïve breadth-first search. We hope that it can be improved substantially. In particular, it may be fruitful to follow GraphPlan more closely, while retaining the use of BDD representations for sets of states (and also using them to represent sets of actions). HSP derives a heuristic function, used to direct its search, from an approximation to the problem (ignoring delete effects of actions), and builds a set of global mutex invariants, used to prune the search space. Both these constructions can be related directly to PropPlan's propositional representation of a planning problem. We hope that these ideas will contribute improvements to the performance of future versions of PropPlan. It will also be interesting, and hopefully instructive to consider the type analyses of STAN in this setting.
The initial stages of this research were supported by an EPSRC travel grant, Propositional Planning GR/N31894/01