TLPlan
Planning Using Declarative Search Control
TLPlan is a planning system that utilizes domain specific search
control information to control simple forward chaining search. When
given sufficient control information TLPlan is able to generate plans
orders of magnitude faster than domain independent planners.
Verfying this claim TLPlan was awarded distinguished performance
of the first order in the AIPS-2002
planning competition.
The system is based on two key ideas.
-
Arbitrary first-order formulas can be evaluated on the worlds
generated by forward chaining. This means that complex conditions can
be efficiently tested in each world using model checking with no need
to resort to theorem proving.
-
We can express search control knowledge declaratively using a
first-order temporal logic. By evaluating conditions on worlds we can
incrementally model check these temporal logic formulas against the
sequences of worlds generated during planning, pruning from the search
space foolish world sequences (i.e., useless action sequences).
TLPlan features
- Implemented in C and runs under UNIX and MS-Windows.
- Supports the full ADL language as defined in Pednault in his KR89
paper. This includes full support for functions and for arbitrary
first-order preconditions that might include disjunction.
- Also supports recursive ADL functions. For example,
consider a blocks world where every block has an x-y location (z
coordinate optional) and where we have an action that can slide an
entire tower of blocks to a new x-y location. To update the x-y
location of all of the blocks in the tower we need a something like a
recursively defined add list.
- Supports functions and thus domains with resources.
- With proper domain specific control information it is orders of
magnitude faster than any other AI planning system (thus verifying
that domain control information is an appropriate mechanism for moving
to the next level of AI planning performance).
- Features a rich set of features to make it easier to specify
planning domains, including a carefully designed domain specification
language.
- Comes with a wide range of implemented planning domains.
On Line Material Available
Papers
-
Planning with Resources and Concurrency:
A Forward Chaining Approach,
F. Bacchus and M. Ady, International Joint Conference on
Artificial Intelligence (IJCAI-2001), pages 417-424,
2001.
- Using
Temporal Logics to Express Search Control Knowledge for
Planning, F. Bacchus and F. Kabanza, Artificial
Intelligence, vol 116, 2000. This paper gives a detailed
description of the TLPlan system, and presents the results of an
extensive series of empirical studies comparing TLPlan and other
planning systems.
-
Using
Temporal Logic to Control Search in a Forward Chaining Planner,
F. Bacchus and F. Kabanza, New Directions in Planning, M. Ghallab and
A. Milani (Eds.) IOS Press, pages 141--153, 1996. The very first
paper on TLPlan. Superseded by the previous paper.
-
Planning for Temporally Extended Goals, F. Bacchus and F. Kabanza,
Annals of Mathematics and Artificial Intelligence, vol. 22, pages
5--27, 1998. This paper shows how the approach can be extended so as
to generate plans satisfying more complex temporally extended goals.
-
Planning
for Temporally Extended Goals, F. Bacchus and F. Kabanza, National
Conference on Artificial Intelligence (AAAI-96), pages 1215--1222,
1996. A shorter version of the previous paper.
Software
Legal Matters
The software available at this site is
copyright (c) 1993, 1997, 2003 Fahiem Bacchus and Michael Ady. All rights are
reserved. Use of this software is permitted for non-commercial
research purposes, and it may be copied only for that use. All copies
must include this copyright message. This software and any
documentation and/or information supplied with it is distributed on an
as is basis. Fahiem Bacchus and the University of Toronto make no
warranties, express or implied, including but not limited to implied
warranties of merchantability and fitness for a particular purpose,
regarding the documentation, functions or performance of such
software, documentation and/or information.
C Software
The C Software can be downloaded here. This release is the
latest version that won the AIPS2002 planning competition. The release
is a Linux executable. If you need an executable that can run on a
different architecture send me e-mail at fbacchus@cs.toronto.edu.
Implemented Planning Domains for the C-Version
This link will take you to the
location of various planning domains implemented for the C-version of
TLPlan.
C Version Reference Manual
The current documentation
is scant. But here is what we currently
have available.
C User Libraries
The C version can utilize predicates
and functions encoded as C subroutines and located in user
libraries. However the interface between the user routines and tlplan
tlplan is in the process of being redesigned, and so is not currently
documented. Some of the domains and other files in the free
distribution utilize this facility.
Source Code
We are not currently distributing source,
and probably will not do so in the future due to IP protection
issues. If you are a researcher and feel you need access to the source
please contact the authors to see what can be done.
Commercial Licenses
TLPlan is a robust peice of
software built to industrial standards. If you are interested in
commercial applications please contact the authors. Commercial
licenses can be negotiated, and unrestricted use evaluation copies can
be made available.
Scheme Software
The C-version is newer it also has a
much cleaner input syntax, many more features (e.g., defined
functions, recursive ADL actions, etc.) than the scheme
version. Nevertheless, this version is perhaps more
"hackable". For that reason we make it available here, it is
unsupported software that you use at your own risk. This code is also
much slower than the original C-version (which in turn is orders of
magnitude slower than the current C-version).
Tlplan scheme
Available as a gzipped tar
file. Developed under MIT
Scheme. The distribution includes a manual that describes the
Scheme version. Check the manual first as it contains the installation
instructions.
Look here for
Fahiem Bacchus's home page, and here for
Froduald Kabanza's home page.