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.