Lightweight Automated Planning Toolkit
Miquel Ramirez miquel.ramirez@gmail.com Nir Lipovetzky nirlipo@gmail.com Last update: February 2013
-
Overview of toolkit components
-
Building lwaptk
-
Search algorithms implemented
-
Examples
-
Contributing
-
Requirements
-
OVERVIEW ===========
lwaptk separates search engines from the data structures used to represent planning tasks. This second component receives the name of 'interface' since it is indeed the interface that provides the search model to be solved.
At the moment of writing this, the following interfaces are offered:
-
'agnostic': this interface does not depend on a particular planning language, so it is easy to wrap PDDL parsers, separating parsing representation of planning tasks from a representation optimized for off-line planning. This interface should also make easy to integrate STRIPS planners into applications by suitably defining planning tasks programatically.
-
'ff': this interface wraps FF parsing components to obtain 'agnostic' looking tasks.
Future interfaces planned are:
-
'hsps': this interface wraps Patrik Haslum's HSP codebase, which supports parsing of PDDL 3.0 features.
-
'SAS+': this interface is meant to support SAS representations natively. Since there is no SAS-based planning language, this will probably be useful to integrate planners into applications that are able to define SAS planning tasks programatically.
Search engine components are meant to be modular, allowing users of lwaptk to assemble and combine features of different search engines to come up with customized search strategies, within reason and without sacrificing (much) efficiency. In order to do so, lwaptk makes heavy use of C++ templates and the Static Strategy design pattern. At the time of writing this, the modularity and decoupling of components isn't as high as I would like, there's still a lot of work to do :)
lwaptk is bound to change rapidly and dramatically over the next months, so please keep this in mind when using this library.
- BUILDING lwaptk ==================
In order to build lwaptk you need to install scons (a GNU Makefile replacement) in your system. Refer to http://www.scons.org for directions on how to achieve this.
In order to compile some of the examples, you will also need a version >= 1.49 of the Boost C++ libraries available on your system.
You can check the version you have either manually by looking at the macro defined in boost/version.hpp or, on debian systems, by running
dpkg -s libboost-dev.
Be aware that systems such as the Ubuntu 12.04LTS release ship with older versions of Boost.
Finally, lwaptk requires the Judy library (http://judy.sourceforge.net/index.html) to support the bitmap array class 'Varset Judy'. NOTE: This dependency will be optional or entirely deprecated in the future.
Issue the command
$ scons
at the root of the source directory to obtain the (static) library containing essential data structures and other miscellaneous utilities. If debug symbols are needed, the command
$ scons debug=1
builds the library with optimizations disabled and debug symbols enabled.
Building the libraries for the different interfaces (and planning task representation) is achieved by invoking scons in a similar manner in the corresponding folder.
- SEARCH ALGORITHMS IMPLEMENTED ================================
- include/aptk/at_bfs.hxx
Any-time Best First Search.
- include/aptk/at_bfs_dq.hxx
Any-time Best First Search with two open lists (the PREFERRED list, for nodes generated by preferred operators, and the OPEN list, for the rest).
- include/aptk/at_bfs_dq_mh.hxx
Best First Search with three open lists and two heuristic estimators. The search frontier is split into three lists:
BOTH: holds nodes generated by actions deemed as 'preferred' by both heuristic
estimators
PREFERRED: holds nodes generated by actions deemed as 'preferred' by the
primary heuristic estimator
OPEN: holds nodes generated by actions not deemed as 'preferred' by the primary
heuristic estimator
- include/aptk/at_wbfs.hxx, include/aptk/at_wbfs_dq.hxx, include/aptk/at_wbfs_dq_mh.hxx
Any-time Weighted A*, with weight W decaying according to fixed decay parameter. Variants include single queue and multiple queue (either with one or two heuristic estimators).
- include/aptk/at_rwbfs.hxx, include/aptk/at_rwbfs_dq.hxx, include/aptk/at_rwbfs_dq_mh.hxx
Any-time Restarting Weighted A* described on
with weight W decaying according to fixed decay parameter. Variants include single queue and multiple queue (either with one or two heuristic estimators).
3.2. Contract Search
- include/aptk/das.hxx
The Deadline Aware Search algorithm described in
- EXAMPLES ===========
The examples for the 'planner agnostic' interface can be found on
examples/agnostic-examples
and cover the following topics:
* agnostic-examples/assembling_strips_problems
Shows how to define a STRIPS planning problem programatically.
* agnostic-examples/successor_generation
Discusses the different way of generating successors during search.
* agnostic-examples/bfs
* agnostic-examples/bfs-double-queue
* agnostic-examples/bfs-double-queue-secondary-heuristic
Shows how can one assemble available components to deliver a
planner built around a BFS search engine, with multiple queues and
secondary heuristics, on a parametrized planning task.
* agnostic-examples/das
Shows how can one assemble available components to deliver a
planner built around Deadline Aware Search.
- CONTRIBUTING ===============
Anybody can contribute to lwaptk by submitting code or patches to
when (if) there's enough people interested and making contributions to the codebase, I will setup a 'github' organization to centralize the efforts. People making significant contributions will be granted commit permissions upon request.
- REQUIREMENTS ==============
lwaptk requires the following libraries: * boost::program_options * varjudy
In order to compile lwaptk, we recommend need g++ 4.6 or better. However, any compiler able to handle both boost libraries and C++0x standard new features, should also be usable (we have been able to compile it under Visual Studio 2010 and llvm).