HSP^* 2000-2004

By P@trik Haslum and Hector Geffner.

Important: This page describes and makes available the version of the HSP^* planners that participated in the 2004 planning competition (better known as "TP4"). Apart from a few minor post-competition bug-fixes, it does not cover any later versions or developments.

Please send questions, comments, bug reports, etc. to one of my email addresses.

HSP^* is a family of domain-independent (mostly-STRIPS) planners. Common to all family members is that they are based on heuristic search, using a heuristic derived automatically from the problem representation, and that they are all optimal w.r.t. some measure.

The HSP^* planners build on ideas from their non-optimal predecessors, HSP and HSPr.

HSP^* Variants

The HSP^* family currently includes:

hsp₀ (a.k.a. TP4): Basic HSP^* planner.
The planner performs a regression search, guided by an admissible heuristic called H². The H² heuristic is defined by approximating the cost of sets of (subgoal) atoms by the cost of the most costly subset of size at most 2. It is computed (by a dynamic programming method) and stored in a table before search begins.
hsp_a: The H² heurstic can be viewed as the optimal cost in an approximate regression search space. hsp_a exploits this by searching the approximate regression space for the analogously defined H^m heuristics, for m > 2. During these searches, it discovers (at least lower bounds on) the cost of some sets of (subgoal) atoms of size m, and thus it computes parts of the H^m heuristics (which are in general more accurate than H²) as a side effect. The resulting heuristic is used in a final (regression) search for a plan.
hsp_b: hsp_b improves on the H² heuristic using boosting: a series of short searches to solve, or find improved lower bounds for, the atom sets stored in the heuristic table. Using conflict detection, it may also add new atom sets to the table (which are then boosted). After boosting, it performs the same regression search as hsp₀.
hsp_c: hsp_c uses an iterated combination of approximate regression and boosting to improve the H² heuristic, and interleaves these efforts with iterations of the search for a plan.
hsp_d: hsp_d is another variant of interleaving boosting to improve the H² heuristic with plan search iterations. In difference to hsp_c, hsp_d boosts only atom sets that were used in the last search iteration.

All HSP^* planners are capable of performing several types of planning. The supported types of planning and the associated options are:

Parallel (the default): Generates parallel, non-temporal plans (i.e. graphplan style), minimizing the number of steps.
Temporal (option: -time): Generates temporal plans, minimizing makespan. Constraints imposed by reusable resources and atom locks (see Numeric Variables) are respected.
Temporal with Resources (options: -time -res): Generates temporal plans, minimizing makespan, respecting both reusable (including atom lock) and consumable resource constraints.
Sequential (option: -seq): Generates sequential plans, minimizing the number of actions.
Sequential with Cost (options: -seq -cost): Generates sequential plans, minimizing the sum of action costs (action costs are derived from the problem :metric specification: see Numeric Variables).
Sequential with Resources (options: -seq -res): Generates sequential plans minimizing number of actions, while respecting consumable resource constraints.
Sequential with Cost and Resources (options: -seq -cost -res): Generates sequential plans minimizing sum of action costs and respecting consumable resource constraints.

For more options, see sections below.

The TP4 temporal planner has participated in the 2002 & 2004 International Planning Competitions, where it did not do exceedingly well.

Usage

The five planners are called hsp0, hsp_a, hsp_b, hsp_c and d_hsp. General usage is,

 hsp0 [planning type options] [other options] [input files...]

In addition, there are some utility programs: pddlcat, which "cats" PDDL files and does some other possibly usefull things (including domain reduction), rpgc, which generates random propositional STRIPS problems, and chopshop which converts MRCPS problems to PDDL.

Input

The planners accept domain and problem specifications in a PDDL2.1-like language (see sections below, and [2], for further discussion of the differences). Any number of input files can be given, and an input file can contain several domain/problem specifications. All input is merged into a single problem instance.

Durative Actions Although the input language accepted by the HSP^* planner looks like PDDL2.1, it does not follow PDDL2.1 level 3 (durative action) semantics. Instead the planners assume, like TGP, an "interval semantics" of durative actions. For an action A executed over the interval [S,T] (where T = S+dur(A)), it is assumed that

all preconditions of A must hold at S,
persistent preconditions (i.e. those not deleted by the action) must hold throughout the interval [S,T],
all effects, whether additions or deletions, take place at some, not exactly known, point in the interior of the interval [S,T].

This implies that the execution of two actions can not overlap in time if they are "mutex", by the standard definition (i.e. one deletes a precondition or effect of the other). It also means that an action that adds and deletes the same proposition is inconsistent (except in certain cases, which are interpreted specially: see below).

Note that action durations are required to be > 0. The planners accept actions with zero duration (mainly because instantiated problem specifications tend to contain some "useless" actions, e.g. (move X Y Y), with zero duration and these are filtered out by preprocessing), but may behave incorrectly in their presence.

Numeric Variables Numeric variables (i.e. non-constant functions in the problem specification) and action conditions/effects on them are treated as resources or cost. A resource is called reusable iff it is only borrowed (not consumed or produced by any action), and consumable otherwise. Consumable resources are restricted to be decreasing only.

Resources are identified by certain "patters" in action conditions/effects:

An action that has the effects
(at start (decrease (<fun> ...) <amount>))
(at end (increase (<fun> ...) <amount>))
is said to "borrow" <amount> of the resource specified by (<fun> ...). According to the strict definition of borrowing, the action should also have a precondition (<fun> ...) >= <amount>, but this can left out (in which case it is considered implicit).
Similarly, an action that has the precondition
(at start (<pred> ...))
and the effects
(at start (not (<pred> ...)))
(at end (<pred> ...))
is said to "lock" the atom specified by (<pred> ...). This means the atom will be treated as a reusable resource with unit capacity.

If the problem specifies a :metric (other than total-time) a cost for each action is calculated as the actions net effect on the metric expression. Cost is always minimized: if the :metric expression specifies maximize the expression is multiplied by -1.

Action costs are required to be > 0. As with durations, the planners accept actions with zero cost, but may behave incorrectly in their presence.

DKEL Support Input files may also contain domain knowledge items specified in DKEL syntax (see [5]). There are some restriction on the accepted items:

Only :invariant and :irrelevant items are allowed.
:invariant items can only contain :set-constraints. The set constraint can contain positive and negated atoms, setof expressions, but not equalities (this also applies to the contents of setof expressions). at-least constraints are accepted, but will be mostly ignored.
:irrelevant items can only contain :action elements.
The :context of an item or setof expression is restricted to be a single literal or a conjunction, and may only contain static predicates (including equality).

Misc. Features and Restrictions

Typing is supported, including type hierarchies but not either-types.
Equality, negative preconditions and negative goals are allowed.
Predicates, functions, types, objects and actions all exist in the same "namespace", which means the same name can not be used for different kinds of things. Note also that object is reserved as the name of the top domain of the type heirarchy (some domains specifications seem to demand this).
No difference is made between durative and non-durative actions. Actions can be declared with either :action or :durative-action: the :duration specifier and timing keywords for preconditions and effects are accepted regardless.
Action duration specification can be simplified to
:duration <expression>
where <expression> may contain constants, functions (of the action arguments) and the arithmetic operators. Functions appearing in :duration specifications must be static, i.e. not modified by any action.

Common Options

Planning Type Options:: (see HSP^* Variants above)
-time: Temporal planning.
-res: Resource-Constrained planning.
-seq: Sequential planning.
-cost: Optimal-Cost planning (using problem :metric).
Preprocessing Options:: Standard preprocessing detects static atoms and actions (by simple reachability analysis) and removes them from the problem.
-no-prep: Disable standard preprocessing.
-rm: Detect and remove irrelevant atoms, using standard reverse reachability.
-use-strict-borrow: Use the strict definition of "borrow" (with explicit precondition) when identifying reusable resources.
-use-extended-borrow: Use the extended definition of "borrow" when identifying reusable resources. This is needed to find such resources in some domains, e.g. the UMTS domain.
Heuristic Options:: The default base heuristic is H².
-1: Use H¹ as base heuristic.
-load: Read heuristic table from input file(s).
Search Options:: The default search algorithm is IDA^*, without transposition table or cycle check.
-tt: Enable transposition table (applies only to IDA^*).
-cc: Enable cycle checking (applies to IDA^* and branch-and-bound).
-cut / -no-cut: Enable/Disable pruning techniques (right-shift cuts in parallel/temporal planning, commutativity cuts in sequential). Cuts are enabled by default with IDA^* and branch-and-bound, and disabled by with A^*.
-bfs: Use best-first search (A^*).
-px <threshold>: Use partial expansion A^* search, with the specified threshold (0 is usually a good threshold value).
-bb <initial bound>: Use DFS branch-and-bound, with the specified initial upper bound.
Limit Options:
-t <seconds>: Set a CPU time limit.
Printing Options:
-v <n>: Set verbose level (<n> = 0 .. 4). Default is approximately 1.
-strict-ipc: Output plan in IPC format (with strict epsilon separation between actions to ensure that the plan is valid according to PDDL2.1 semantics). Note that epsilons are not included in the makespan, and thus not minimized. This option is only supported by hsp0 and hsp_a.
-pddl: Output plan in PDDL format (a format that can be read and validated with pddlcat).
-no-plan: Don't print the plan.

`hsp0`

-post: Use two-stage optimization (see [2] for a description). This applies only to temporal planning, and is (possibly) usefull only when actions have non-integer durations.
-all: Find (and print) all optimal plans.

In addition to the above, hsp0 also has a lot of extra debug and test options. For a full list, see the source code :)

`hsp_a`

By default, hsp_a performs m-approximate searches for m = 3,4,... until either a non-approximate solution is found, or the m+1-approximate solution cost is the same as the m-approximate solution cost. A fixed limit on m can be set using the -m option (3 - 4 are usually good values). Approximate regression searches are made using IDAO^*, an extension of IDA^* to AND/OR-graphs, but alternative search algorithms can be chosen.

-m <m>: Limit approximate searches to max <m>.
-itest: Use Iterative Test instead of IDAO^*.
-mm: Use mini-max instead of IDAO^*.
-no-alpha: Disable the "alpha cut" in IDAO, meaning all successors to an AND-node are searched. This increases the amount of information gained during the search slightly, but at a rather large computational cost. It is usually not worth the price.
-save: Write heuristic to h.pddl after approximate regression searches are finished.
-post: Use two-stage optimization (as described for hsp0 above).

`hsp_b`

hsp_b performs boosting searches for entries in the heuristic table (i.e. sets of atoms) in order of increasing estimated cost. The boosting search for an entry ends when a solution is found (then the optimal cost of the atom set becomes known) or when its estimated cost has increased so that it is no longer the least costly entry in the table. The boosting process ends when the next entry to boost has an estimated cost greater than that of the problem goals. When entries are solved, new entries may be added to the table by conflict detection: the new entries consist of the just solved atom set plus one atom that is deleted by the plan found for the solved set.

-cd <n>: Limit size of atom sets added by conflict detection to <n> (3 is usually a good value). By default, there is no limit, and this can lead to unnecessarily large sets being added to the heuristic table.
-no-cd: Disable conflict detection (thus, only atoms sets computed by base heuristic are boosted).
-f: Fix boosting limit at initially estimated goal cost.
-wps <w>: Limit the amount of "work" per boosting search to <w>. "Work" is measured by number of heuristic evaluation (which is roughly linearly related to time).
-save: Write heuristic to h.pddl after boosting is finished.

`hsp_c`

hsp_c combines approximate searches and boosting in an iterative way. In each iteration, a single IDA^* iteration is performed to check if there is a solution within the current bound. If not, a cost-bounded m-approximate search is made, followed by a fixed-limit boost without conflict detection. m is initially 3 and is incremented when the m-approximate search finds a solution.

-m <m>: Limit approximate searches to <m>.
-itest: Use Iterative Test instead of IDAO^*.
-no-boost: Disable boosting.
-no-init-boost: Disable initial boosting. (Normally, a round of boosting is performed before the first iteration.)
-save: Write heuristic to h.pddl after plan found or search interrupted.

`d_hsp`

d_hsp alternates between IDA^* iterations and fixed-limit boosts (by default with conflict detection, but this can be limited or disabled). However, only table entries that were used to evaluate a state encountered in the preceeding IDA^* iteration are boosted.

-cd <n>: Limit size of atom sets added by conflict detection to <n>.
-no-cd: Disable conflict detection alltogether.
-dwps: Dynamically calculate a limit on the amount of "work" per boosting search (based on the amount of work spent in last search iteration).
-wps <w>: Limit the amount of "work" per boosting search to <w>.
-save: Write heuristic to h.pddl after plan found or search interrupted.

IPC Settings

The following options should (approximately) reproduce the results of (temporal) hsp₀ and hsp_a from the 2004 planning competition:

 hsp0 -time -rm -use-extended-borrow -strict-ipc <domain> <problem>
 hsp_a -time -rm -use-extended-borrow -strict-ipc -m 3 <domain> <problem>

For the satellite domain, a different setting was used:

 hsp0 -time -rm -use-extended-borrow -strict-ipc -post -cc <domain> <problem>
 hsp_a -time -rm -use-extended-borrow -strict-ipc -m 3 -post -cc <domain> <problem>

Note that the planners can not handle timed initial litterals, nor (due to the different interpretation of durative actions) the compiled versions of such domains.

Downloading and Compiling

Source tarball: hsps.tar.gz.
Domains, problems and scripts for experiments reported in the ECP'01 paper [3] are in a separate archive: ecp01_exp.tar.gz. The MRCPS problems, sets J12, J14 and J16, are not included in the archive, but are available from PSPLib, and can be converted using the chopshop program.

HSP^* has been developed using g++ 3.2. Whether it will compile using any other compiler is not known.
To compile the parser requires bison++/flex++. Last I checked, these can be fetched from ftp://ftp.th-darmstadt.de/pub/programming/languages/C++/tools/flex++bison++/. Note that this is not the standard GNU bison or flex.
For convenience, pregenereated parser and scanner files are included in the source archive. To use them, copy {grammar,scanner}.pregen.{h,cc} to the corresponding name without ".pregen". However, these files were generated on a solaris machine, and may not work on all platforms.
Compilation settings and compile-time options are set by editing the makedefs and config.h files. For most non-esotheric platforms, the default settings should be adequate.

Publications

The following papers describe work on or related to the HSP^* planners.

[1] P. Haslum Improving Heuristics Through Search. European Conference on Artificial Intelligence, 2004 (short paper).
[2] P. Haslum TP4'04 and hsp^*_a. In 4th IPC systems descriptions booklet (available as a whole from http://ipc.icaps-conference.org).
[3] P. Haslum & H. Geffner, Heuristic Planning with Time and Resources. European Conference on Planning, 2001.
[4] P. Haslum & H. Geffner, Admissible Heuristics for Optimal Planning. Proc. International Conference on AI Planning and Scheduling, 2000.
[5] P. Haslum & U. Scholz Domain Knowledge in Planning: Representation and Use. ICAPS Workshop on PDDL, 2003.

/P@trik Haslum, July 2004

HSP* 2000-2004

Usage

Input

Downloading and Compiling

Publications

HSP^* 2000-2004