The HSP* 2005+ Download and Documentation Page

This page contains the HSP* planner collection, along with some documentation. It is called "HSP* 2005+" because the latest proper release was the version that participated in the 2004 planning competition. Quite a bit has changed since then, and it keeps changing. The source code and documentation on this page is only updated sporadically, and may be out of date.

Different planners built on the HSP* code participated in the 2008 and 2014 International Planning Competition (IPC). The source code of the versions in the competitions are available from the IPC web pages (to the extent that those still survive). Those are, however, "snapshots", in the sense that they have not been updated since the respective competitions (no bugs fixed, no new bugs introduced).

The HSP* package contains several planners, and some other (more or less useful) planning-related tools:

hsp0.
Basic regression (backward search) planner. Implements both sequential (cost-optimal), parallel and temporal planning, and a variety of heuristics, search algorithms etc.
hsp_f.
Basic progression (forward search) planner. Implements only sequential (cost-optimal) planning, but with a variety of heuristics, search algorithms etc.
hsp_a, hsp_b, hsp_c, d_hsp.
Variations of the regression planner using different combinations of relaxed search and boosting. See the HSP* 2000-2004 page and the the JAIR paper for more details.
hsp_p.
Optimal planner for net-benefit problems.
pddlcat.
Tool for doing (quite a lot of different) stuff with planning problems/PDDL files. See use cases below for further description.
create_nb_problems, analyze_deadlines
Tools used in the construction of problem instances for some IPC5 domains.
test_nbb, test_ppc, test_sd, roverMSP_to_TSP.
Tools used for solving/analysing problems in some IPC5 domains. See my additional IPC5 resources page and paper in the ICAPS'07 workshop on the International Planning Competition for more details.
rpgc, random_sas
Tools for generating random STRIPS and SAS problems, respectively.
test_ilb
Implementation of the h+/h++ solver (ICAPS'12, IPC 2014). Please note additional compilation instructions below.

Download

hsps.tar.gz
HSP* sources, as of March 29th 2016.
bison++-1.21-8.tar.gz
flex++-2.3.8-7.tar.gz
Versions of bison++/flex++ required to compile HSP*.

Past Versions

Instructions for Compiling

First, the HSP* package uses old C++ adaptions of the Flex/Bison parser generator tools. Since they seem to have disappeared off the web completely, I make the versions I've used available here. They come with their own installation instructions/dependencies/problems. If you do not want to mess with them, you can try using the "fake" option (see below). Note that these are not the GNU flex++ and bison++! If you use the (newer) GNU versions of these programs, compiling will fail!

Configuration is manual: copy the files config.h and makedefs from the subdirectory locals to the main source directory and edit the copies. The important configuration settings and compile-time options are described in those files.

If you can't (or haven't the got the guts to try to ;)) compile/install and use the required flex++ and bison++ programs, there is an option to "fake" them, by simply copying pregenerated scanner and parser source files. See documentation in makedefs for how to enable this option. Note however that only the linux version of the pregenerated files is up-to-date. The other two (cygwin and solaris) haven't been updated for years. If you're compiling for a platform other than linux, you can still try using the linux pregenerated files. It may work (there isn't that much platform dependence in the generated files), or you may have to patch the files a bit. Who knows.

The makedefs file contains a number of settings commented "Additional flags for ... - only required to compile hspIAO/pddl3sim/SPP/MOST". You can safely ignore most of these, since neither hspIAO, pddl3sim, spp or MOST is included in the source archive. Note however that some of these settings are relevant to compiling the test_ilb program (cf. below).

Once you're done with configuration, run make and hope it works. Note, however, that the default make target only compiles some of the programs mentioned above. make extra should get you most of the others.

Compiling test_ilb (h+/h++ solver)

First, test_ilb is not built by default. To compile it, you need to do make libs and then make test_ilb separately.

Second, the h+ solver (which is also used by the h++ incremental lower bound) uses a minimum-cost hitting set solver. Several hitting set solvers are available, and which one is used is configured at compile time, by changing options in the makedefs file and #define's in ilb.h and ilb.cc. The options available, in order of decreasing efficiency, are:

  1. using CPLEX;
  2. using SCIP;
  3. using my built-in hitting set implementation, with LP-based lower bound; and
  4. using my buit-in hitting set implementation without the LP-based lower bound.
Note: There is a substantial performance difference between these solvers, which reflects in the performance of the h+ solver. If at all possible, use the CPLEX configuration. Do not use the 4th option at all.

Compiling with CPLEX.

Compiling with SCIP.

Compiling built-in hitting set solver, with LP-based lower bound.

Compiling built-in hitting set solver, without LP-based lower bound. Note that this configuration is very inefficient. Do not use it!

Instructions for Use

The total number of options and valid option combinations accepted by each of the planners/tools is gargantuan. I will not (most likely can not) provide an exhaustive list. Instead, presented below are a few "use cases", i.e., how to make them do certain specific things. But here are a few general hints/observations:

The currently described use cases are:

  1. Cost-optimal delete-relaxed planning (h+).
  2. Forward search cost-optimal planning.
  3. Makespan-optimal temporal planning.
  4. Generating a Petri net (mole input) from PDDL.
  5. Computing a reduced operator set (a.k.a. redop).

Cost-optimal delete-relaxed planning (h+)

To run, do: 

test_ilb [-ce] -h -a -s [-split -dom] [-z] [-no-R1] [-R2] [-p] [-v <n>] <PDDL files>

Options:

-ce
Use incremental compilation of conditional effects. Default is to compile out all conditional effects up-front (exponential compilation). For h+, this is only relevant if the input domain has actions with conditional effects that remain after grounding.
-split and -dom
Use splitting and dominance checking. These options should be used when test_ilb was compiled with the built-in hitting set solver, and have no effect if it was compiled with CPLEX or SCIP as the hitting set solver.
-z
Do not optimise inclusion of zero-cost actions in the plan. In the vast majority of cases, this speeds up (or at least doesn't hurt) the computation of a cost-optimal delete-relaxed plan, but it may decrease the performance of the h++ incremental lower bound.
-no-R1 and -R2
The h+ solver has two relevance analysis techniques specifically for delete-relaxed problems. The first uses back-chaining on first achievers (as described in the ICAPS 2012 paper, and similar to Florian Pommerening's technique), and is enabled by default; option -no-R1 switches it off. The second checks pair-wise state-dependent action dominance and removes dominated actions (as described by Nathan Robinson). This analysis is more expensive, but sometimes useful, and off by default; option -R2 switches it on.
-p
Print delete-relaxed plan (by default, only the h+ value, along with solver stats, is printed at the end).
-v <n>
Set verbosity level to <n> (0, ...).

Forward search cost-optimal planning

To run, do: 

hsp_f -cost [options] <PDDL files>

Relevant options divide, roughly, into four categories: preprocessing/miscellaneous, heuristic, search algorithm and output.

Preprocessing/miscellaneous options

A note concerning invariants: Some of the heuristics (e.g., PDB heuristics) depend on having a collection of "at-most-1" or "exactly-1" invariant sets over the atoms in the problem. A search-based method for finding invariants is switched on by default (and also switched on by any option that enables a heuristic or inference method that depends on invariants). The invariant finding method may be computationally expensive for some problems, and is best disabled when invariants are not needed.

-rm
Use standard backchaining relevance analysis.
-prep-1
Limit reachability analysis to h1 only (default is h2 analysis, which may in some cases be very time-consuming; but, on the other hand, if it is, it's likely that any heuristic is also going to be so).
-no-prep
Disable reachability analysis.
-no-extend
Disable "implied goal" finding. Implied goals are atoms that are not specified as part of the goal condition, but must be true in reachable state that satisfies the goal condition. Turning these into explicit goals is helpful for some heuristics (allows more accurate estimates of the cost of reaching a goal state). However, the procedure for finding implied goals can be computationally expensive, and it depends on having "exactly-1" invariants.
-quick-find
Use a simpler (and usually faster) algorithm for invariant finding.
-no-find
Disable invariant finding. Note that this option must appear after any other option that switches on invariant finding (such as any PDB heuristic).
-no-verify
Disable verification of invariants (on by default whenever invariant finding is on). Invariant verification often serves to strengthen "at-most-1" invariants, proving that they are in fact "exactly-1" invariants, which is useful for some things (typically, for PDB heuristics).
-dba-semantics
Use delete-before-add semantics. The default behaviour of the planner (as of all programs in the HSP* family) is to consider an action that adds and deletes the same atom to be inconsistent (and hence removed during preprocessing). However, PDDL semantics dictate that in fact, deletes take place before adds (if they happen at the same time point), so such an action will behave as if the atom was not deleted, only added. This option makes the planner use the PDDL-compliant semantics instead. (It does not change the interpretation of effects of durative actions, however, which is another mess altogether.)

Heuristic options

The default heuristic is a simple PDB heuristic. It has one PDB for each goal variable (in the induced SAS+ representation of the problem) containing only that variable, and take the max over sums of additive PDBs where applicable (summing can be disable with -no-add, though there's no earthly reason to do so).

-0
Use no heuristic (i.e., blind search).
-almost-blind
Use no the "almost blind" heuristic. This assigns a heuristic estimate equal to the minimum action cost to any non-goal state.
-f1
Use the h1 heuristic, recomputed for every state.
-f
Similar to option -f1, but instead of (re)computing h1, computes only a simple goal reachability check (i.e., the value of this heuristic will always be either 0 or +INF). This can be surprisingly effective.
-r
Use the "reversed h2" heuristic, i.e., the h2 regression heuristic computed on the reversed problem. (This does not recompute h2 in every state.) See IPC6 planner description for more details.
-rAH
Use the additive h2 heuristic, with the default 0/1 action partitioning method, combined with problem reversal. This is the heuristic used by the IPC6 planner. This heuristic can be much better than the basic reversed h2, but in some cases is no better at all, and often significantly more expensive to precompute and evaluate. It's usually worth testing both to see which works best.
-rAH -fpia
Use the additive h2 heuristic, with fractional action cost splitting, combined with problem reversal. Sometimes this produces a better heuristic, sometimes not.
-use-lse
Use "linear scan evaluators" for the components of additive h2 (so, this option only has an effect in combination with -rAH). This generally makes heuristic evaluation faster.
-ipdb
Use PDB heuristic with local search pattern selection (as described in AAAI-07 paper).
-ipdb-param <d_skip> <s_max;gt; <i_min> <n_trials> <n_samples>
Use PDB heuristic with local search pattern selection with non-default parameters. Parameters are:
  • d_skip: "skip distance" in each step of the local search, i.e., number of new patterns to add to the collection (default: 1).
  • s_max: max number of local search steps (default: unlimited).
  • i_min: minimum acceptable improvement; local search stops if the estimated improvement offered by the best neighbour is less than this value (range: [0,1]; default: 0.01).
  • n_trials: number of "trials" to use in estimating the value of a pattern collection (default: 10).
  • n_samples: number of samples per trials (default: 100).
The total number of samples used for estimation is bounded by n_trials * n_samples. After each completed trial, a confidence interval for the improvement of each neighbour is calculated, and pattern collections that appear to be dominated based on these intervals are not evaluated further.
-pdb-size <N>
Specifies the maximum size of any single PDB, in number of abstract states.
-pdb-total-size <N>
Specifies the maximum total PDB size, in number of abstract states (applies only to local search PDB construction).
-no-inc
Disables the use of constrained projection for PDBs.
-pdb-fast
Use the new & improved procedure for computing PDBs. This works only if all actions in the induced SAS+ representation of the problem are "safe", meaning they specify a precondition on every variable appearing in the postcondition. Whether actions are safe or not depends on the problem, and the invariants used to convert it to SAS+ representation. Safeness can be ensured by adding option -sas-safe, but this may increase the size of the SAS+ representation.
-apx-add and -ac
Use an approximate, instead of optimal, algorithm for finding cliques / additive groups of PDBs.

Search algorithm options

The default search algorithm is IDA* with no enhancements (pretty stupid default, since it's possibly the least efficient of all available algorithms).

-bfs
Use A*.
-tt [-tt-size <N>]
Use a transposition table (applies to IDA* and branch-and-bound).
-cc
Use cycle checking (applies to IDA* and branch-and-bound).
-bb
Use branch-and-bound. The default initial upper bound is +INF, i.e., the search behaves like a plain DFS until the first solution has been found. A different initial upper bound can be specified with -c <cost bound>.
-bfida
Use iterative-deepening breadth-first heuristic search (BFIDA). See Zhou & Hansen, ICAPS-04. There are some short-comings in the implementation of this algorithm: First, duplicate detection is limited to one layer, and thus not complete. This means the algorithm may fail to terminate on unsolvable problems. Second, solution reconstruction is not implemented. Thus, using this algorithm the planner will only find the optimal plan cost, but not produce an actual plan.

Output options

As a general rule, trace and debug output are sent to stderr, while the actual result (plan and/or summary statistics at the end) are sent to stdout. To save the plan to a file, use output redirection.

-v <N>
Set verbose level to <N>. Verbose level 0 is a bit special: it produces a one-line statistics summary at the end (in addition to the plan). If combined with either the -ipc or -pddl plan format options, this line is commented (using ;;).
-ipc
Write plan in IPC (validator) format. This means that the invocation hsp_f [...] -v 0 -ipc > x.soln should result in a plan file (x.soln) that is accepted by the IPC validator (assuming the planner found a plan, of course).
-pddl
Write plan in "PDDL format". This is a custom format, the main point of which is that it is accepted by pddlcat (which can do all kinds of stuff with plans) and that it, unlike the IPC plan format, does not depend on the beginning/end of the file to mark the beginning/end of the plan (so one file can contain any number of plans).

Examples

The IPC6 planner configuration: 

hsp_f -strict -dba-semantics -rm -cost -rAH -use-lse -bfs -v 0 -ipc domain.pddl problem.pddl > problem.soln
i.e. this uses both relevance and reachability analysis in the preprocessing step, PDDL-compliant action semantics, additive h2, with the default 0/1 action partitioning scheme, on the reversed problem as the heuristic, A* as the search algorithm and outputs a validator-friendly plan.

As above but using only reversed h2 instead: 

hsp_f -cost -strict -dba-semantics -rm -r -bfs -v 0 -ipc domain.pddl problem.pddl > problem.soln

Almost blind planner: 

hsp_f -cost -rm -almost-blind -no-extend -bfs -v 0 -ipc domain.pddl problem.pddl > problem.soln

AAAI-07 PDB planner: 

hsp_f -cost -rm [-quick-find -ac] -ipdb -pdb-size 2000000 -pdb-total-size 20000000 -bfs -v 0 -ipc domain.pddl problem.pddl > problem.soln
OR 
hsp_f -cost -rm -no-find [-ac] -ipdb -pdb-size 2000000 -pdb-total-size 20000000 -bfs -v 0 -ipc domain.pddl problem.pddl invariants.pddl > problem.soln

The second form uses a file with prespecified invariants to construct the SAS+ representation, while the first uses some automatic method to discover them. See description of preprocessing options above for the meaning of -quick-find, -no-find, -ac, etc. The PDB construction process has some parameters which can be set by using the option -ipdb-param d s i nt ns in place of -ipdb-param.

Makespan-optimal temporal planning ("TP4")

Warning: First, note that the planner is limited to so-called "conservative" temporal planning. It will interpret PDDL's temporal annotations ("at start", "at end" and "over all") in certain peculiar ways that are not always consistent with the PDDL semantics.

Delete effects are assumed to take place at the start of the action, and add effects at the end. Preconditions must hold at start, and must not be interfered with by any concurrent action throughout execution.

Handling of resources: The planner identifies certain propositions and numeric fluents as "resources". An atom p that is required (precondition) at start, deleted at start, and added at end, by an action a is considered to be a unary resource used by that action. Unary resources affect only when actions can take place concurrently.

Numeric fluents are interpreted as two types of resources: Reusable, which follow the same pattern as the atomic unary resources, i.e., are required and consumed at start and returned (produced) at end, and consumable resources, which are required and consumed only. The identification of resources is based on finding certain patterns in action preconditions and effects. Any numeric conditions and effects that are not identified as resources may be ignored!.

Warning #2: I have not used or tested the temporal planner for many years. It is quite possible that other changes to the code have introduced bugs into it. Also, even if it does work correctly, it should not be expected to be very efficient.

To run, do:

hsp0 -time [-res] [options] <PDDL files>

The preprocessing, search algorithm and output options are roughly the same as described for cost-optimal planning above. The opton -res enables certain types of resource handling in the state space and heuristics. (This means that if this option is not used, some resource constraints may be ignored by the planner even when it is able to identify them in the PDDL input.)

Generating a Petri net (mole input) from PDDL

(a.k.a. "petrification")

This is done by pddlcat. The process of converting a planning problem, specified in PDDL, to a (1-safe) Petri net consists of the following steps:

  1. Instantiation (a.k.a. grounding). This also includes compiling away some PDDL features, such as conditional effects, negative preconditions, trajectory constraints, and what not).
  2. Preprocessing (reachability and/or relevance analysis). The purpose of this step is to reduce the size of the (instantiated) problem.
  3. Changing the (conjunctive) goal condition to a "goal action" (i.e., a single action with the goal as precondition and a special atom as effect; the goal of the problem then consists of this atom only). The name of the goal action is GoalAction0, and the name of the special atom is GoalReached.
    For petrification, this is done twice, i.e., the goal is changed to another special atom (normally called FINI) and another special action (normally called Finish0) that achieves this atom is added. The reason for this (if memory serves) is that mole stops as soon as it generates the "target transition", whereas to obtain optimal plans we need it to stop only when it dequeues the target transition.
    Note that for mole to generate optimal plans, the cost/duration of these special actions have to be set (with the option -epsilon) to a value that is guaranteed to be smaller than half the cost/duration of any real action in the problem.
  4. "1-Safeing" (making the problem 1-safe). This may require adding some new (complementary) atoms to the problem. It may also create multiple "copies" of actions. Because of this, action names will change: in particular, the name of the second goal action (which will be the target transition for mole) will normally become Finish0_at_0.
  5. Output in ll_net format.
To run, do: 
pddlcat -petrify [options] <PDDL files>
Relevant options are:
-remove
Enable simple relevance analysis (this may reduce problem/net size).
-prep-1
Limit reachability analysis to h1 only (the objective of reachability analysis is to reduce problem/net size; however, the cost of the h2 analysis, which is default, is sometimes prohibitively high).
-no-prep
Disable reachability analysis.
-complete-negation
By default, some analysis is done so that only the complementary atoms that are needed for 1-safing the problem are added. This option make pddlcat add a complementary atom for every atom in the problem that does not already have one (after preprocessing). Don't think there's any reason to use this option.
-no-inference
By default, some analysis is done to identify "implicit" complementary atoms, because this may reduce the number of such atoms that have to be added. However, in some cases this analysis is very expensive, so one may wish to disable it.
If the option -complete-negation is also used, this option must come after it to take effect.
-cost OR -time
Specifies whether to use action cost or action duration as "transition cost" in the output. If neither option is used, the default is to assign every transition a cost of 1.
-epsilon <value>
Set the cost/duration of the special goal actions. This must be a value smaller than half the cost/duration of any real action in the problem. The default value is 0.01.
-PR
Enable place replication.

Some examples of (sensible) use would be: 

pddlcat -petrify -cost -remove my_domain.pddl my_problem.pddl
This generates a net for cost-optimal planning (assuming the cost of every real action is greater than 0.02), and applies all kinds of analysis in an atempt to generate a net that is as small as possible. 
pddlcat -petrify -cost -remove -prep-1 -no-inference my_domain.pddl my_problem.pddl
This applies only the less expensive forms of analysis - suitable for large problems. 
pddlcat -petrify -time -PR -remove my_domain.pddl my_problem.pddl
This generates a net for makespan-optimal planning, with place replication.

Assuming the PDDL problem definition is in the file my_problem.pddl, the output file will be named my_problem.net. The way to run mole on it would be: 

mole -s bestfirst max -T Finish0_at_0 my_problem.net
for cost-optimal plannning, and 
mole -time -s bestfirst max -T Finish0_at_0 my_problem.net
for makespan-optimal planning.

Computing a reduced operator set (redop)

This functionality is now implemented in pddlcat. To use it, do the following:

pddlcat [parsing/preprocessing options] -redop -a [redop options] domain.pddl problem.pddl > redop-output.dkel

This produces as output a file which contains DKEL :irrelevant action items for each action removed. (Without the -a option, the output is the complete problem definition with the DKEL items added.)

If you cannot parse PDDL with DKEL extensions, you can generate a (ground) domain/problem with these actions removed as follows:

pddlcat [parsing/preprocessing options] -prep -p -no-problem domain.pddl problem redop-output.dkel > reduced-domain.pddl
pddlcat [parsing/preprocessing options] -prep -p -no-domain domain.pddl problem redop-output.dkel > reduced-problem.pddl

The parsing and preprocessing options are as documented above (i.e., -remove, -prep-1, -dba-semantics, etc).

RedOp-specific options are:

-bound N
Set the bound on the length of the replacing sequence. The default is N = 3. Setting the bound to inf means searching for replacement sequences of any length. (This can be very slow.)
-rep
This modifies the output. Instead of a set of :irrelevant items, representing a set of ground actions that can be removed, output one :replaceable item for every redundant action. Note that it is not necessarily the case that all replaceable actions can be removed; there can be cycles of replaceability such that removing all these actions makes the problem unsolvable. Also note that the HSP* planners (and other tools in the suite) cannot parse DKEL with :replaceable items.

For the second stage (producing grounded output), there are several options that affect how PDDL output is formatted. These include -no-dkel, -no-metric, -no-pddl2, -no-pddl3, -pddl1, -no-negation, -write-nary, -write-parameters, -write-requirements, and perhaps some others. For a complete understanding of how PDDL output is generated, read the code :)