Blackbox
Henry
Kautz
AT&T
Research
Bart
Selman
Yi-Cheng
Huang
Department
of Computer Science,
Cornell
University
Blackbox is a
planning system that works by converting problems specified in STRIPS notation
into Boolean satisfiability problems, and then solving the problems with a
variety of state-of-the-art satisfiability engines. The front-end employs the
graphplan system (Blum and Furst 1995). There is extreme flexibility in
specifying the engines to use. For example, you can tell it to use walksat Selman, Kautz, and Cohen 1994) for 60
seconds, and if that fails, then satz (Li and Anbulagan 1997) for 1000 seconds.
This gives blackbox the capability of functioning efficiently over a broad
range of problems. The name blackbox refers to the fact that the plan generator
knows nothing about the SAT solvers, and the SAT solvers know nothing about
plans: each is a "black box" to the other.
MIPS
Stefan
Edelkamp
Malte
Helmert
Institut
fuer Informatik
University
of Freiburg
Mips
abbreviates "Intelligent Model checking and Planning System" and is
being developed by Stefan Edelkamp and Malte Helmert. It is capable of handling
basic STRIPS and some ADL additions such as negative preconditions and
universally quantified conditional effects. Mips uses binary decision diagrams
(BDDs) to compactly store and maintain sets of propositionally represented
states. The concise state representation is inferred in an analysis prior to
the search and, by utilizing this representation, accurate reachability
analysis and backward chaining are carried out without necessarily encountering
exponential representation explosion.
Mips was originally designed to prove that
BDD-based exploration methods are an efficient means for implementing a
domain-independent planning system with some nice features, especially
guaranteed optimality of the plans generated. If problems become harder and
information on the solution length is available, Mips invokes its incorporated
heuristic single state search and heuristic symbolic search engines with BDDs,
thus featuring two entirely different planning algorithms, aimed to assist each
other on the same staterepresentation.
System R
Fangzhen
Lin
Hong
Kong University of Science and Technology
System R is
based on regression, and solves a goal one at a time. Briefly, given a
conjunctive goal G, it chooses the first subgoal g that has not been satisfied yet in the current
state, and work on it. Once it is achieved, say by P, it progresses the current
state through P to a new current state, moves g to the end of G, and
recursively tries to find a plan for the new G. When working on g, it regresses
g over an action to a conjunctive goal G', and tries to achieve G' recursively.
As it turned out, this simple appraoch
works extremely well in many benchmark domains such as the blocks world and
logistics domain which are natural STRIPS domains. It does not work at all in
domains such as FreeCell where the preconditions of many actions are not really
subgoals to regress to, but conditions to check in the current state, and where
numerical information is simulated by symbolic predicates
This to a large degree can be remedied by
using domain specific control information. There are basically three ways to
control the planner with domain specific information: (1) the ordering of
subgoals; (2) pruning of unachievable goals; and (3) the way a subgoal is
solved by regressing it to a new conjunctive goal. As it turned out, I used (2)
extensively in Track2 for the logistics domain, and (1) and (3) for the blocks
world.
FF
Joerg
Hoffmann
Albert
Ludwigs University
Institute
for Computer Science
FF (Fast-Forward)
is basically a variation of HSP. Interpreting the HSP heuristic as a special
case of the graph building phase in GRAPHLAN, it extends the heuristic to also
employ GRAPHPLAN's plan extraction phase. The length of the plans that
GRAPHPLAN returns give a heuristic goal distance measure, and the actions that
GRAPHPLAN selects can be used for guiding search.
Using these informations, FF employs a
novel local search strategy that combines Hill-climbing with systematic search.
It makes use of the fact that phenomena like big plateaus or local
minima---with respect to the heuristic described above---do not occur very
often in benchmark planning problems.
HSP2
Hector
Geffner
Blai
Bonet
Universidad
Simon Bolivar
Depto
de Computacion
HSP2 is
an heuristic-search planner that descends from the HSP plannerentered into the
AIPS98 Contest. The idea is similar: planning instances are mapped into
state-space search problems that are solved with heuristics extracted from
the representation. Unlike the original
HSP planner, the new version supports
forward and backward search,
several heuristics, and a more expressive modeling language (a fragment of
typed ADL). The search algorithm is Weighted A*; an A* search with the
heuristic multiplied by a constant W > 1. There are also a number of
improvements in the code. Different options (search direction/heuristic) can be
run in sequence or concurrently.
IPP
Jana
Koehler
Schindler
Lifts Ltd.
Joerg
Hoffmann
Michael
Brenner
University
of Freiburg
The IPP planning system was
developed by Jana Koehler, Joerg Hoffmann, Michael Brenner, and Frank Rittinger
at the University of Freiburg from Fall 1996 to Spring 1999. It is based on
planning graphs as originally developed by Blum and Furst, but extended them to
cover ADL, in particular conditional effects and complex logical
preconditions. IPP competed already in
the first planning competition in 1998 where it demonstrated a superior
performance in the ADL track. Today, IPP is no longer maintained and has only
entered the AIPS2000 competition to provide a basis for comparison for the
newer ADL planners as the system has only marginally changed.
PbR
Jose
Luis Ambite
Craig
Knoblock
Steve
Minton
University
of Sourthern California/Information Sciences Institute
Planning by Rewriting (PbR) is a
new paradigm for efficient high-quality planning that exploits plan rewriting
rules and local search techniques to transform an easy-to-generate, but
possibly suboptimal, initial plan into a high-quality plan. The framework has
an anytime behavior.
In PbR a plan is represented by a graph,
in the spirit of partial-order causal-link planners such as UCPOP. The nodes
are domain actions. The edges are causal links and ordering constraints. The
plan rewriting rules are specified in a declarative language. The rules are
similar to graph rewriting rules but take into account the semantics of
partial-order planning.
In the competition we used an
implementation of the Planning by Rewriting framework focusing in plan
optimization. The rewriting rules were developed semi-automatically: most of
the rules were proposed by a learning algorithm, but some were defined or
optimized manually. The initial plan generators were hand-coded for each
domain.
Propplan
Michael
Fourman
Division
of Informatics, University of Edinburgh
PropPlan is a
planner based on naive breadth-first state-space search. PropPlan uses Ordered
Binary Decision Diagrams, popularised by Bryant, to implement exhaustive state
space exploration.
Other researchers have realised that BDDs
can be applied to planning, most notably Cimatti, Giunchiglia, Giunchiglia and
Traverso, in their Planning as Model-Checking (PMC) approach.
PropPlan handles full ADL and domain
axioms. It also generalises ADL and STRIPS actions by allowing general formulae
as effects, and by separating the specification of the fluents an action may
change from the constraints it imposes on the changed values.
PropPlan compiles a planning problem to a
propositional representation, but, unlike SAT-based planners such as BlackBox,
or the PMC approach of Giunchiglia et al., PropPlan does not introduce
propositional variables to represent actions. In PropPlan, (generalized) STRIPS
operators are represented directly by efficient operations on BDDs in n state
variables, rather than, as is traditional in model checking, as abstract
transition relations requiring 2n variables. ADL actions are also represented
directly by efficient operations on BDDs. Multiple conditional effects are
handled by a sequence of BDD operations that grows linearly with the number of
conditional effects, rather than by exponential case analysis.
The competition version of PropPlan is
based on a simple elimination of timeless predicates, followed by
straigntforward, forward chaining exhaustive breadth-first search to establish
a layered set of reachable states until the goal-set is reached, then backward
chaining for plan extraction.
Experiments with disjunctive
representations of state-space, backward chaining search, invariant extraction,
and dependency analysis (both forwards and backwards) have all failed to yield
useful improvements to this simplistic approach.
SHOP
Dana
Nau
Yue
(Jason) Cao
Hector
Munoz-Avila
Amnon
Lotem
Department
of Computer Science
University
of Maryland
SHOP (Simple Hierarchical Ordered Planner).
SHOP is a domain-independent HTN planning system with the
following characteristics.
1.
SHOP plans for tasks in the same order that they will later be
executed.
·
This avoids some goal-interaction issues that arise in other HTN
planners, so that the planning algorithm is relatively simple.
2.
Since SHOP knows the complete world-state at each step of the
planning process, it can use highly expressive domain representations. For example, it can do planning problems
that require complex numeric computations.
3.
The expressive power of SHOP's domain representations can be used
to encode highly efficient domain-dependent planning algorithms into SHOP.
TokenPlan
Patrick
Fabiani
Yannick
Meiller
ONERA
(center of Toulouse - France)
TokenPlan is a
planner being devellopped by Patrick Fabiani and Yannick Meiller at ONERA
(center of Toulouse - France). Interested in planning under uncertainty in
dynamic environments, for autonomous systems, our approach aims at combining
Classical AI planning and Game theory. Roughly, our idea is to make
game-theoretic approaches more efficient by taking advantage of the
capabilities of classical AI planning to handle sets of states instead of
single states. The challenge is then to be able to handle sets of states
relevant to the criteria which are to be optimized by the game-theoretic
approach - that is to be able to control the level of splitting of the search
space.
More technically, our planner is based on
the use of Petri nets with labelled colored tokens. The pddl-domain is
converted in a Petri net (to a place corresponds a predicate, to a transition
corresponds an operator). When a token marks a place, it carries on its label a
particular binding for the predicate's variables. From the initial marking,
tokens are propagated through the Petri net so that we can build the graph of
the tokens'possible motions. As in Graphplan, this graph is searched backward
(and may be extended further if no solution is found, and so on).
Tokens belong to different classes. A
transition can be triggered iff all of its preconditions are marked by same
color tokens. In case there is a unique class, then we have a Graphplan-like
approach (there is no splitting of the search space). If a new class is created
each time a transition is triggerred, then we have a FSS-like approach (full
splitting). Of course we can have all intermediate situations (which is what we
wanted).
In all cases where full splitting is not
being used, it is necessary to compute mutex relations. Using colored tokens
allows us to avoid computing part of these mutex relations (the "permanent
mutex relations"): indeed 2 instances of a same predicate carried by 2
tokens of same color are mutex.
For the competition we've used only the
no-splitting approach (therefore with the automatic color encoding of part of
the mutex relations). For the backward search, we used some code kindly
provided by Subbarao Kambhampati. The current version is implemented in
Lisp. Desperatly brief version : Our planner is based on the use of colored
Petri nets. Its main feature is to allow control over the splitting level of
the search space (therefore providing approaches ranging from the
Graphplan-like ones to the FSS-like ones - including intermediate ones). Also,
when it is necessary to compute mutex relations, part of them are
"naturally" encoded through the tokens'colors.
During the competition we used settings
corresponding to a graphplan-like approach (i.e. no splitting at all) - due to
Tokenplan's current state of devellopment. The current version is implemented
in Lisp, with some code kindly provided by Subbarao Kambhampati for the
backward search.
STAN
Maria
Fox
Derek
Long
Computer
Science Dept., University of Durham, UK
STAN is now a hybrid of two planning
strategies:
1.
The original Graphplan-based STAN algorithm;
2.
A forward planner using a heuristic function based on the length
of the relaxed plan (as in HSP and FF).
The key new contribution that STAN makes
is the use of domain analysis techniques to select automatically between these
strategies, depending on a number of domain features, and to inform search
within these strategies. These domain analysis techniques now go way beyond
type and invariant analysis and include the automatic identification of certain
combinatorial optimisation sub-problems and the invocation of specialised
solvers for tackling them. For example, STAN can use them to determine when a
domain involves transportation between locations or bounded numerical
computations which often indicate the presence of renewable or restricted
resources. When these features are detected STAN abstracts them out of the
planning problem and uses special purpose techniques to deal with them. The
recognition and abstraction of route-planning sub-problems accounts for STAN's
excellent performance in Logistics, and the identification and treatment of
numbers to handle the restricted resources in FreeCell accounts for its similar
performance there. We are currently working on identifying construction
sub-problems and the integration of more sophisticated specialised solvers for
route-planning and resource allocation tasks.
BDDPlan
Hans-Peter
Stoerr
Dresden
University of Technology
Artificial
Intelligence Institute, Department of Computer Science
BDDPlan is
an exploration on how to use BDDs to support reasoning in the Fluent Calculus,
an framework for reasoning about actions in first order logic (with some second
order extensions). The main idea is based on model checking algorithms which do
an implicit breadth first search. It has an PDDL front end and integrates some
optimizations like bidirectional search, partitioning of the transition
relation, identification of constant fluents, search frontier reduction and a
limited form of hand optimization by exclusion of actions and fluents from the
search process.
Some advantages of the used algorithm are
that - it always returns a shortest
plan or is able to prove there isn't
a plan - one would be able to
enumerate all plans from the results of the
preprocessing stage without further computation intensive search - it is able to produce exponential length
plans. On the other hand, it has often very large memory requirements.
TALplanner
Jonas
Kvarnstrom
Patrick
Doherty
Patrik
Haslum
Linkoping
University
TALplanner is a forward-chaining
planner inspired by the work of Bacchus and Kabanza with TLplan.
Domain-dependent search control knowledge expressed as temporal logic formulas
is used to effectively control forward
chaining. Development of TALplanner is based on using intuitions from previous development of TAL, a narrative temporal logic for reasoning about action and change
in incompletely specified domains. TAL
has extremely rich expressivity and solutions to the frame, ramification and qualification problems in
well-defined world domains. The
symbiosis between TAL and TALplanner has led to a concurrent version of
TALplanner and an extension for use of resources. These extensions are
implemented. TALplanner uses TAL
formulas to express control knowledge, goal statements, complex plan operators,
resources and resource constraints, domain constraints, and dependency constraints. Both boolean and
non-boolean fluent domains are permitted and semantic attachment techniques may
be used for doing arithmetic, etc. A goal narrative is provided as input to
TALplanner and a TAL narrative is returned as output. The narratives have a
formal semantic intepretation in TAL. In fact, generation of a plan may be
viewed as generation of a narrative in TAL and generated plans may be formally
reasoned about much like narratives in TAL.
Whereas TLplan uses MITL formulas and
formula progression, TALplanner uses temporal logic formulas from TAL and
direct evaluation of formulas in states, although a formula progression version
of TALplanner is also implemented. Whereas MITL is a first-order modal linear
temporal logic, TAL is a first-order metric linear temporal logic with a
standard semantics and is based on the use of narratives.
AltAlt
Biplav
Srivastava
Terry
Zimmerman
BinhMinh
Do
XuanLong
Nguyen
Zaiqing
Nie
Ullas
Nambiar
Romeo
Sanchez
Arizona
State University
Computer
Science & Engineering
AltAlt
started out as "a little of this, and a little of that". It is a
student-only effort where a group of graduate students parallely toyed with a
number of alternative planning ideas (GP-HSP [AAAI-00], GP-CSP[AIPS-00]) and
evaluated them before fielding the better one. The actual idea used in the
competition, GP-HSP, which became the official AltAlt planner, uses effective
and admissible heuristics extracted from the planning graph to drive the
backward state space search. AltAlt was
developed in Lisp and later ported to C for the competition (round1). A problem
we faced was that the relatively newer C version was hard to try better
heuristics with, as the competition progressed, even when newer heuristics were
easily seen to be feasible in the Lisp version.
GRT
Ioannis
Refanidis
Ioannis
Vlahavas
Dimitris
Vrakas
Aristotle
University
Greece
The GRT (Greedy Regression Table) planner
is a domain independent heuristic state space planner for STRIPS worlds. The
heuristic adopted by the planner works as it follows: In a pre-processing phase
it constructs a table, the records of which are indexed by the ground facts of
the domain. Each record contains an estimate for the distance between a fact
and the goals, i.e. the number of actions needed to apply to the goals in order
to achieve this fact. While computing
these estimates, it takes into account the positive interactions that occur
while trying to achieve several facts simultaneously.
With the term "positive interactions" we refer to the
situation where the achievement of a fact supports the achievement of other
facts. The planner utilizes a simple best-first search strategy and exploits
the above computed distances in order to obtain estimates for the distances
between the intermediate states and the goals.
Past performance results have shown that GRT is quite competitive
against other state-of-the-art planners in specific domains. Future extensions in GRT include:
· Management of local optimal states that arise in some domains and heuristic state-space planners cannot overcome, based on the exploitation of state-constraints.
·
Management of resources that are used in some domains and are nt
effectively represented within the STRIPS formalism.
· Full support of all the ADL/PDDL features.