Skip to content

Latest commit

 

History

History
990 lines (789 loc) · 42.6 KB

CHANGES.md

File metadata and controls

990 lines (789 loc) · 42.6 KB
Raw

Release notes

Fast Downward has been in development since 2003, but the current timed release model was not adopted until 2019. This file documents the changes since the first timed release, Fast Downward 19.06.

For more details, check the repository history (https://github.com/aibasel/downward) and the issue tracker (https://issues.fast-downward.org). Repository branches are named after the corresponding tracker issues.

Fast Downward 24.06

Released on October 10, 2024.

Highlights:

  • We have improved the translator in several dimensions. Key improvements include better error reporting for invalid PDDL, revised and faster version of the invariant algorithm and full support for negated predicates in the goal.

  • Negated axioms are now computed in the search component, and only in configurations that actually use them. This eliminates a worst-case exponential performance bottleneck in cases where negated axioms are not used. Heuristics that use negated axioms have a new option (axioms=approximate_negative) to avoid this computation at the cost of some heuristic accuracy.

  • There are many improvements to the landmark_sum and landmark_cost_partitioning heuristics. This includes a new theory of landmark progression that fixes a gap in the completeness in search configurations like LAMA and can deal directly with cyclic landmark orders, support for reasonable orders in admissible landmark heuristics, a cleaner definition of preferred operators, deterministic synthesis of reasonable orders, and performance improvements. Please note that the command-line options for landmark heuristics have changed.

  • We added a new set of operator-counting constraints (delete_relaxation_rr_constraints), which implements the delete-relaxation operator-counting constraints by Rankooh and Rintanen. The old delete_relaxation_constraints plugin using the constraints by Imai and Fukunaga has been renamed to delete_relaxation_if_constraints.

  • We added the alias seq-sat-fdss-2023 for the satisficing Fast Downward Stone Soup 2023 portfolio from IPC 2023.

  • For developers: planner component objects (such as heuristics or search algorithms) are now constructed with individual parameters rather than having all parameters encapsulated in an Options object. (We mention this primarily for developers maintaining their own forks, as this change affects more than 200 source files.)

Details:

Fast Downward 23.06

Released on July 31, 2023.

Highlights:

  • The option parser of the search component has been completely reimplemented. The new option parser has full error reporting where the old code crashed on errors or silently accepted them. This is also an important stepping stone towards a future use of Fast Downward as a library. With the change, the --evaluator, --heuristic and --landmarks options are now deprecated in favor of a new let syntax. For example,

    --evaluator h=EVALUATOR --search SEARCH_ALGORITHM

    is deprecated in favor of the expression

    --search let(h, EVALUATOR, SEARCH_ALGORITHM)

  • We now compile using the C++20 standard, so all modern C++ features can be used as long as they are supported by all main compilers Fast Downward supports (see README.md).

  • The linear programming and mixed integer programming features of Fast Downward now communicate directly with the LP/MIP solvers (SoPlex or CPLEX) rather than using the open solver interface OSI as an intermediary. This has also allowed us to move to more modern versions of these solvers.

  • The lmcount heuristic has been split into two separate heuristics called landmark_sum and landmark_cost_partitioning. The former corresponds to the old lmcount with the option admissible=false, the latter to the old lmcount with the option admissible=true.

  • The two new landmark heuristics (landmark_sum and landmark_cost_partitioning) compute preferred operators more efficiently than before. On average, this improves performance of LAMA-style planner configurations.

  • The merge-and-shrink heuristic now stores labels and their transitions more efficiently, resulting in improved speed for merge-and-shrink heuristic construction.

  • The MIASM merge strategy for merge-and-shrink (more precisely, the sf_miasm merge scoring function) now has an option to cache scores. Caching is enabled by default and greatly speeds up construction of MIASM-based merge-and-shrink heuristics.

Details:

  • option parser: We implemented a new way of defining features and parsing them from the command line. The new parser now supports defining variables for features (heuristics and landmark graphs so far) as an expression within the option string. For example, let(h, lmcut(), astar(h)) instantiates the lmcut heuristic, binds it to the variable h and uses it within the astar search algorithm.

    This change to the parser is an important stepping stone towards solving a more general problem about how components interact. Details of the new parser are described in a blog article. We also improved the documentation of enum values. https://www.fast-downward.org/ForDevelopers/Blog/TheNewOptionParser https://issues.fast-downward.org/issue1073 https://issues.fast-downward.org/issue1040

  • translator, for developers: Unreachable atoms are now filtered from mutex groups in an earlier processing step than before. In a few domains this leads to a different finite-domain representation. We could remove an old hack related to static literals in goals, which is no longer necessary. We also added some type annotations, in particular to the core data structures. https://issues.fast-downward.org/issue1079

  • translator, for users: The change described in the previous entry can lead to Fast Downward producing a slightly different finite-domain representation in some cases.

  • search algorithms, for developers: Instead of "search engine" we now say "search algorithm" everywhere. Among other things, this affects source file and directory names, namespaces, class names. The change is also reflected in the documentation. https://issues.fast-downward.org/issue1099

  • Cartesian abstractions, for developers: The cegar directory and namespace have been renamed to cartesian_abstractions to avoid confusion with CEGAR-based code in the pdbs directory. https://issues.fast-downward.org/issue1098

  • landmarks: We replaced the lmcount heuristic with two new heuristics called landmark_sum and landmark_cost_partitioning. No functionality is added or removed: landmark_sum replaces lmcount with the option admissible=false and landmark_cost_partitioning replaces lmcount with the option admissible=true. https://issues.fast-downward.org/issue1071

  • landmarks: Refactor the computation of preferred operators in the landmark heuristics (landmark_sum and landmark_cost_partitioning). The change affects configurations based on LAMA that use preferred operators. While the semantics of the code did not change, the new version is slightly faster and can solve more tasks and/or improves plan quality in an anytime configuration within the same time limit. https://issues.fast-downward.org/issue1070

  • merge-and-shrink: Improve the way that labels and their transitions are stored. We removed the class LabelEquivalenceRelation. Instead TransitionSystem now handles locally equivalent labels itself using a new LocalLabelInfo class and stores a mapping from global to local labels. Labels are now removed from label groups in batches during label reduction. With this change, we can now construct the atomic factored transition system (and the overall heuristic) in significantly more cases, reducing both memory usage and construction time. https://issues.fast-downward.org/issue927

  • merge-and-shrink: The MIASM scoring function (feature sf_miasm) now has an option to cache scores for merge candidates, enabled by default. This greatly decreases computation time of M&S abstractions with this scoring function. https://issues.fast-downward.org/issue1092

  • pattern databases: The pattern generators cegar_pattern and random_pattern now correctly support fractional values for the max_time parameter. Previously the fractional part was silently ignored. For example a timeout of 7.5 seconds was treated as 7 seconds.

  • pattern databases, for developers: We split off the computation of pattern databases from the PatternDatabase class. PatternDatabase now stores pattern, hash_multipliers and num_states in a new class Projection, used for ranking and unranking. PDBs can be computed via a function which uses an internal class PatternDatabaseFactory. Abstract operators live in their own files now, similar to MatchTree. Performance does not change due to this issue. https://issues.fast-downward.org/issue1019

  • LP/MIP solvers: So far, we used the open solver interface OSI to communicate with MIP and LP solvers. We now replaced this with our own interface to have more direct control and fewer external dependencies. We now support CPLEX 22.1.1 and SoPlex from their current main branch (released versions <= 6.0.3 are incompatible with C++20). We removed the solver options for CLP and Gurobi in the process: CLP has much worse performance than SoPlex, which is also open source, while Gurobi was never practically possible to compile with, as we did not have a CMake find script for it. Performance with CPLEX increases in MIP configurations and stays roughly the same in LP configurations. Performance with SoPlex increases for potential heuristics and decreased slightly in other configurations. Our Windows builds forced static linking because of OSI. With OSI removed, they no longer do. https://issues.fast-downward.org/issue1076 https://issues.fast-downward.org/issue1093 https://issues.fast-downward.org/issue1095

  • LP/MIP solvers, for developers: Previously, LP solvers could crash if a constraint included multiple terms for the same variable. We now protect against this with an assertion in debug mode. The change has no effect on release builds. https://issues.fast-downward.org/issue1088

  • build: The build script now performs the requested builds in the given order. For example, ./build.py debug release will perform a debug build and then a release build. Previously, the order was arbitrary, depending on Python dictionary order. https://issues.fast-downward.org/issue1086

  • C++ standard: We now compile the planner using the C++20 standard. We added tests for GCC 12 and clang 14 but dropped tests for GCC 9, clang 10, and clang 11.

    The minimal supported compilers are now:

    • g++-10
    • clang-12
    • MSVC 19.34
    • AppleClang 13.0

    Language features supported by all of these compilers may now be used in the planner. For a list of such features and more details, see the issue tracker. The list includes std::optional, so we removed the implementation of optional in src/search/ext. https://issues.fast-downward.org/issue1028 https://issues.fast-downward.org/issue1094

  • Windows build: We now enable more compiler warnings on Windows builds. In detail, we no longer ignore warnings C4800, C4512, C4706, C4100, C4127, C4309, C4702, C4239, C4996, and C4505 on Windows builds as they no longer occur in our code. Warnings in GitHub actions are now also treated as errors in Windows builds. https://issues.fast-downward.org/issue565

  • infrastructure: We fixed a problem with using CPLEX in the GitHub action builds on Ubuntu. https://issues.fast-downward.org/issue1093

  • infrastructure: We update the version of uncrustify used to fix code formatting. Instructions on how to install the new version can be found on the wiki: https://www.fast-downward.org/ForDevelopers/Uncrustify. https://issues.fast-downward.org/issue1090

Fast Downward 22.12

Released on December 15, 2022.

Highlights:

  • We now test more recent versions of Ubuntu Linux (22.04 and 20.04), macOS (11 and 12) and Python (3.8 and 3.10).

  • Most search algorithms are now faster. We fixed a performance problem related to state pruning, which also affected search configurations that did not explicitly select a pruning method.

  • All landmark factories now respect action costs. Previously, this was only the case when using admissible landmark heuristic or when using the lm_rhw landmark factory. Note that ignoring action costs (i.e., the old behaviour for landmark factories other than lm_rhw) often finds plans faster and is still possible with the adapt_costs transformation.

Details:

  • driver: Planner time is now logged in a consistent format. Previously, it would sometimes be logged in scientific notation.

  • driver, for developers: Skip pycache directory when collecting portfolios. https://issues.fast-downward.org/issue1057

  • translator: Allow importing pddl_parser without parsing arguments from command line. https://issues.fast-downward.org/issue1068

  • pruning methods: Fix a performance regression caused by spending too much time measuring elapsed time. This is now only done at verbosity level verbose or higher. Verbosity level parameter added to all pruning methods. https://issues.fast-downward.org/issue1058 Note that most search algorithms in Fast Downward always use a pruning method (a trivial method pruning nothing is used by default) and were therefore affected by this performance problem.

  • pruning methods, for developers: We cleaned up the internal structure of stubborn set pruning. https://issues.fast-downward.org/issue1059

  • landmarks: All landmark factories are now sensitive to action costs. https://issues.fast-downward.org/issue1009 When using the lmcount heuristic in inadmissible mode (option admissible=false), previously only the lm_rhw landmark factory considered action costs. Now, all landmark factories do. (This was already the case with admissible=true.) Experiments show that ignoring action costs is often beneficial when we are more interested in planner speed or coverage than plan quality. This can be achieved by using the option transform=adapt_costs(ONE).

  • landmarks: Reduce verbosity of h^m landmarks. The lm_hm landmark factory is now less verbose by default. Use verbosity level verbose or higher to enable the previous output.

  • infrastructure: Update tested OS versions and clang-tidy version. https://issues.fast-downward.org/issue1067

    • The tested Ubuntu versions are now 22.04 and 20.04.
    • The tested macOS versions are now macOS 11 and macOS 12.
    • The tested Windows version remains Windows 10.
    • We now test Python 3.10 (Ubuntu 22.04, macOS 12) and Python 3.8 (Ubuntu 20.04, macOS11, Windows 10).
    • We now use clang-tidy-12. See README.md for details.

  • infrastructure: Update delete-artifact version number in GitHub action, update zlib version in Windows build.

Fast Downward 22.06.1

Released on September 15, 2022.

This is a bugfix release fixing two serious bugs in Fast Downward 22.06:

Fast Downward 22.06

Released on June 16, 2022.

Highlights:

  • We fixed a bug in the translator component that could lead to incorrect behavior in tasks where predicates are mentioned in the goal that are not modified by any actions.

  • Various speed improvements to landmark factories. This is part of a larger ongoing clean-up of the landmark code.

  • More informative output, and more control over the output. The driver now prints the total runtime of all components. For many planner components, including all heuristics, the verbosity level can now be configured individually.

Details:

  • translator: Fix a bug where the translator would not check goal conditions on predicates that are not modified by actions. https://issues.fast-downward.org/issue1055

  • driver: Print overall planner resource limits and overall planner runtime on Linux and macOS systems. https://issues.fast-downward.org/issue1056

  • logging: verbosity option for all evaluators https://issues.fast-downward.org/issue921 All evaluators and heuristics now have their own configurable logger and no longer use g_log. These loggers have a verbosity option, which allows choosing between silent, normal, verbose and debug for all instances of evaluators created on the command line.

  • landmarks: Speed up landmark generation time by 10-20% for lm_rhw, lm_zg, and lm_exhaust by avoiding unnecessary computations in the landmark exploration. https://issues.fast-downward.org/issue1044

  • landmarks: Speed up landmark generation time by 5-15% for lm_rhw, lm_zg, and lm_exhaust by computing reachability in the landmark exploration as boolean information instead of (unused) integer cost/level information. https://issues.fast-downward.org/issue1045

  • landmarks: Improve landmark dead-end detection so that relevant static information is only computed once, instead of at every state evaluation. https://issues.fast-downward.org/issue1049

  • infrastructure: Upgrade GitHub Actions to Windows Server 2019 (Visual Studio Enterprise 2019) and Windows Server 2022 (Visual Studio Enterprise 2022). Remove Windows Server 2016, because GitHub Actions no longer support it. https://issues.fast-downward.org/issue1054

  • infrastructure: Run GitHub Actions only for the following branches: main, issue*, release-*. https://issues.fast-downward.org/issue1027

Fast Downward 21.12

Released on February 16, 2022.

Highlights:

  • Fast Downward now has a logo!

  • We added new methods for generating patterns and pattern collections based on counterexample-guided abstraction refinement and a new highly random method for generating individual patterns based on the causal graph. These methods are due to Rovner et al. (ICAPS 2019).

  • The operator-counting heuristic now has an option to use integer operator counts rather than real-valued operator counts. This makes the heuristic more accurate at a vastly increased computational cost (not generally recommended, but very useful for targeted experiments). We added a new constraint generator for Imai and Fukunaga's delete relaxation constraints (JAIR 2015). With the right option settings, the operator-counting heuristic with this new constraint generator results in the optimal delete relaxation heuristic h+.

  • Pruning methods now have a different interface. The mechanism to disable pruning automatically after a number of expansions that resulted in little pruning is now implemented as its own pruning method that wraps another pruning method. Be careful that the old syntax is still accepted by the planner, but the options that limit pruning are ignored. (This is due to an option parser bug; a fix is in the works.)

  • In our ongoing efforts to improve the landmark code, the landmark factories and landmark-count heuristic received a major overhaul. We removed irrelevant options for landmark factories, decoupled the computation of reasonable orders from landmark generation, made many internal code and data structure changes to make the code nicer to work with and fixed several long-standing bugs.

  • All pattern generators and pattern collection generators now have controllable verbosity. Similar changes to other components of the planner are planned. This is part of a general effort to make logging more configurable.

  • For developers: The internal representation of states has been overhauled, resolving the confusion between the previous classes GlobalState and State.

Details:

Fast Downward 20.06

Released on July 26, 2020.

Highlights:

  • The Singularity and Docker distributions of the planner now include LP support using the SoPlex solver out of the box. Thank you to ZIB for their solver and for giving permission to include it in the release.

  • The Vagrant distribution of the planner now includes LP support using the SoPlex and/or CPLEX solvers out of the box if they are made available when the virtual machine is first provisioned. See https://www.fast-downward.org/QuickStart for more information.

  • A long-standing bug in the computation of derived predicates has been fixed. Thanks to everyone who provided bug reports for their help and for their patience!

  • A new and much faster method for computing stubborn sets has been added to the planner.

  • The deprecated merge strategy aliases merge_linear and merge_dfp have been removed.

Details:

Fast Downward 19.12

Released on December 20, 2019.

Highlights:

  • Fast Downward no longer supports Python 2.7, which reaches its end of support on January 1, 2020. The minimum supported Python version is now 3.6.

  • Fast Downward now supports the SoPlex LP solver.

Details:

Fast Downward 19.06

Released on June 11, 2019. First time-based release.