Scorpion is an optimal classical planner that uses saturated cost partitioning to combine multiple abstraction heuristics. It also contains implementations of many other cost partitioning algorithms over abstraction and landmark heuristics. Scorpion is based on the Fast Downward planning system (version 22.06), which is described below. We regularly port the latest changes from Fast Downward to Scorpion and also try to port Scorpion features back to Fast Downward.
Please use the following reference when citing Scorpion: Jendrik Seipp, Thomas Keller and Malte Helmert. Saturated Cost Partitioning for Optimal Classical Planning. Journal of Artificial Intelligence Research 67, pp. 129-167. 2020.
After installing the requirements (see below), compile the planner with
./build.py
and see the available options with
./fast-downward.py --help # driver
./fast-downward.py --search -- --help # search component
For more details (including build instructions for Windows), see the documentation about compiling and running the planner. The plugin documentation shows which plugins are available (heuristics, search algorithms, etc.) and how to use them.
We recommend using the following configuration:
./fast-downward.py \
--transform-task preprocess-h2 \
../benchmarks/gripper/prob01.pddl \
--search "astar(scp_online([
projections(sys_scp(max_time=100, max_time_per_restart=10)),
cartesian()],
saturator=perimstar, max_time=1000, interval=10K, orders=greedy_orders()),
pruning=limited_pruning(pruning=atom_centric_stubborn_sets(), min_required_pruning_ratio=0.2))"
The preprocess-h2
call prunes irrelevant operators in a preprocessing
step. The search configuration uses partial order
reduction and
maximizes over
diverse,
subset-saturated
cost partitioning heuristics computed
online during
the search. The underlying abstractions are Sys-SCP pattern
databases and Cartesian
abstractions.
(In Downward Lab you can use
add_algorithm(name="scorpion", repo="path/to/repo", rev="scorpion", component_options=[], driver_options=["--transform-task", "preprocess-h2", "--alias", "scorpion"]
to run the recommended Scorpion configuration.)
To simplify the installation process, we provide an executable
Singularity container for
Scorpion. It accepts the same arguments as the fast-downward.py
script
(see above).
# Download the container (tested with Singularity 3.5),
singularity pull scorpion.sif library://jendrikseipp/default/scorpion:latest
# or build the container yourself.
sudo singularity build scorpion.sif Singularity
# Then run recommended configuration (available via "scorpion" alias).
./scorpion.sif --transform-task preprocess-h2 --alias scorpion PROBLEM_FILE
If you prefer to run the Scorpion version from IPC 2018 (which uses an older Fast Downward version and different abstractions), we recommend using the Scorpion IPC repo.
--transform-task preprocess-h2
to use it.--transform-task
command allows you to run arbitrary preprocessing
commands that transform the SAS+ output from the translator before
passing it to the search.IntHashSet
.--dump-predicates
and --dump-static-atoms
to write files with
information that's useful for learning domain control knowledge.cegar(..., search_strategy=incremental)
: use incremental search for
Cartesian abstraction
refinement
(default).
hillclimbing(..., max_generated_patterns=200)
: limit the number of
patterns generated by hill climbing.
systematic(..., pattern_type=interesting_general)
: compute interesting
patterns for general cost partitioning.
We use Cartesian abstractions in the example configurations below
([cartesian()]
). You can also use pattern database heuristics, e.g.,
[projections(systematic(2))]
, or mix abstractions, e.g.,
[projections(systematic(3)), cartesian()]
. Some of the algorithms below
are also part of vanilla Fast Downward, but are only implemented for PDB
heuristics.
ocp([cartesian()])
canonical_heuristic([cartesian()])
ucp([cartesian()], opportunistic=false)
ucp([cartesian()], ..., opportunistic=true)
gzocp([cartesian()], ...)
scp([cartesian()], ...)
(offline), scp_online([cartesian()], ...)
(online)pho([cartesian()], ..., saturated={false,true})
(offline),
operatorcounting([pho_abstraction_constraints([cartesian()], saturated={false,true})])
(online)You can also compute the maximum over abstraction heuristics:
maximize([cartesian()])
The plugin documentation shows all options for cost partitioning heuristics.
sys_scp(max_pattern_size=X, max_pdb_size=Y, max_collection_size=Z, ..., saturate=false)
sys_scp(...)
Example using A* search and saturated cost partitioning over BJOLP landmarks:
--evaluator
"lmc=lmcount(lm_merged([lm_rhw(), lm_hm(m=1)]),
admissible=true, cost_partitioning=suboptimal, greedy=true,
reuse_costs=true, scoring_function=max_heuristic_per_stolen_costs)"
--search
"astar(lmc, lazy_evaluator=lmc)"
Different cost partitioning algorithms (all need admissible=true
):
lmcount(..., cost_partitioning=optimal)
lmcount(..., cost_partitioning=canonical)
lmcount(..., cost_partitioning=pho)
lmcount(..., cost_partitioning=suboptimal, greedy=false, reuse_costs=false)
lmcount(..., cost_partitioning=suboptimal, greedy=false, reuse_costs=true, scoring_function=min_stolen_costs)
lmcount(..., cost_partitioning=suboptimal, greedy=true, reuse_costs=false, scoring_function=max_heuristic)
lmcount(..., cost_partitioning=suboptimal, greedy=true, reuse_costs=true, scoring_function=max_heuristic_per_stolen_costs)
eager()
search):
brfs()
dfs()
dump_reachable_search_space()
idastar(cegar(cache_estimates=false))
iw(width=2)
Fast Downward is a domain-independent classical planning system.
Copyright 2003-2022 Fast Downward contributors (see below).
For further information:
This version of Fast Downward has been tested with the following software versions:
OS | Python | C++ compiler | CMake |
---|---|---|---|
Ubuntu 22.04 | 3.10 | GCC 11, GCC 12, Clang 14 | 3.22 |
Ubuntu 20.04 | 3.8 | GCC 9, GCC 10, Clang 10, Clang 11 | 3.16 |
macOS 12 | 3.10 | AppleClang 14 | 3.24 |
macOS 11 | 3.8 | AppleClang 13 | 3.24 |
Windows 10 | 3.8 | Visual Studio Enterprise 2019 (MSVC 19.29) and 2022 (MSVC 19.31) | 3.22 |
We test LP support with CPLEX 12.9, SoPlex 3.1.1 and Osi 0.107.9. On Ubuntu, we test both CPLEX and SoPlex. On Windows, we currently only test CPLEX, and on macOS, we do not test LP solvers (yet).
The following list includes all people that actively contributed to Fast Downward, i.e. all people that appear in some commits in Fast Downward's history (see below for a history on how Fast Downward emerged) or people that influenced the development of such commits. Currently, this list is sorted by the last year the person has been active, and in case of ties, by the earliest year the person started contributing, and finally by last name.
The current version of Fast Downward is the merger of three different projects:
In addition to these three main sources, the codebase incorporates code and features from numerous branches of the Fast Downward codebase developed for various research papers. The main contributors to these branches are Malte Helmert, Gabi Röger and Silvia Richter.
The following directory is not part of Fast Downward as covered by this license:
For the rest, the following license applies:
Fast Downward is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or (at
your option) any later version.
Fast Downward is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <https://www.gnu.org/licenses/>.