The DOI matches its Crossref record; 8 of the 8 references it cites were found in a registry or an index.
The Fast Downward Planning System
Open accessAbstract
Fast Downward is a classical planning system based on heuristic search. It can deal with general deterministic planning problems encoded in the propositional fragment of PDDL2.2, including advanced features like ADL conditions and effects and derived predicates (axioms). Like other well-known planners such as HSP and FF, Fast Downward is a progression planner, searching the space of world states of a planning task in the forward direction. However, unlike other PDDL planning systems, Fast Downward does not use the propositional PDDL representation of a planning task directly. Instead, the input is first translated into an alternative representation called multi-valued planning tasks, which makes many of the implicit constraints of a propositional planning task explicit. Exploiting this alternative representation, Fast Downward uses hierarchical decompositions of planning tasks for computing its heuristic function, called the causal graph heuristic, which is very different from traditional HSP-like heuristics based on ignoring negative interactions of operators. In this article, we give a full account of Fast Downward's approach to solving multi-valued planning tasks. We extend our earlier discussion of the causal graph heuristic to tasks involving axioms and conditional effects and present some novel techniques for search control that are used within Fast Downward's best-first search algorithm: preferred operators transfer the idea of helpful actions from local search to global best-first search, deferred evaluation of heuristic functions mitigates the negative effect of large branching factors on search performance, and multi-heuristic best-first search combines several heuristic evaluation functions within a single search algorithm in an orthogonal way. We also describe efficient data structures for fast state expansion (successor generators and axiom evaluators) and present a new non-heuristic search algorithm called focused iterative-broadening search, which utilizes the information encoded in causal graphs in a novel way. Fast Downward has proven remarkably successful: It won the "classical'' (i.e., propositional, non-optimising) track of the 4th International Planning Competition at ICAPS 2004, following in the footsteps of planners such as FF and LPG. Our experiments show that it also performs very well on the benchmarks of the earlier planning competitions and provide some insights about the usefulness of the new search enhancements.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
The FF Planning System: Fast Plan Generation Through Heuristic Search
Hoffmann, J., & Nebel, B. (2001) · Journal of Artificial Intelligence Research · doi:10.1613/jair.855 · Cited by 1,838
Linear-time algorithms for testing the satisfiability of propositional horn formulae
Dowling, W. F., & Gallier, J. H. (1984) · The Journal of Logic Programming · doi:10.1016/0743-1066(84)90014-1 · Cited by 1,013
The computational complexity of propositional STRIPS planning
Bylander, T. (1994) · Artificial Intelligence · doi:10.1016/0004-3702(94)90081-7 · Cited by 865
Planning Through Stochastic Local Search and Temporal Action Graphs in LPG
Gerevini, A., Saetti, A., & Serina, I. (2003) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1183 · Cited by 318
Automatically generating abstractions for planning
Knoblock, C. A. (1994) · Artificial Intelligence · doi:10.1016/0004-3702(94)90069-8 · Cited by 288
State-variable planning under structural restrictions: algorithms and complexity
Jönsson, P., & Bäckström, C. (1998) · Artificial Intelligence · doi:10.1016/s0004-3702(98)00003-4 · Cited by 94
Exhibiting Knowledge in Planning Problems to Minimize State Encoding Length
Edelkamp, S., & Helmert, M. (2000) · Lecture notes in computer science · doi:10.1007/10720246_11 · Cited by 81
Self-citation
Cited by
ProgPrompt: Generating Situated Robot Task Plans using Large Language Models
Singh, I., Blukis, V., Mousavian, A., Goyal, A., Xu, D., Tremblay, J., Fox, D., Thomason, J., & Garg, A. (2023) · 2023 IEEE International Conference on Robotics and Automation (ICRA) · doi:10.1109/icra48891.2023.10161317 · Cited by 613
Combined task and motion planning through an extensible planner-independent interface layer
Srivastava, S., Fang, E., Riano, L., Chitnis, R., Russell, S., & Abbeel, P. (2014) · 2014 IEEE International Conference on Robotics and Automation (ICRA) · doi:10.1109/icra.2014.6906922 · Cited by 459
Integrated Task and Motion Planning
Garrett, C. R., Chitnis, R., Holladay, R., Kim, B., Silver, T., Kaelbling, L. P., & Lozano-Pérez, T. (2021) · Annual Review of Control, Robotics, and Autonomous Systems · doi:10.1146/annurev-control-091420-084139 · Cited by 409
Gerevini, A. E., Haslum, P., Long, D., Saetti, A., & Dimopoulos, Y. (2009) · Artificial Intelligence · doi:10.1016/j.artint.2008.10.012 · Cited by 295
PDDLStream: Integrating Symbolic Planners and Blackbox Samplers via Optimistic Adaptive Planning
Garrett, C. R., Lozano-Pérez, T., & Kaelbling, L. P. (2020) · Proceedings of the International Conference on Automated Planning and Scheduling · doi:10.1609/icaps.v30i1.6739 · Cited by 191
Metadata
- Authors
- Helmert, M.
- Venue
- Journal of Artificial Intelligence Research
- Publisher
- AI Access Foundation
- Published
- 2006-07-12
- Volume
- 26
- Pages
- 191-246
- ISSN
- 1076-9757 (ISSN-L)
- OpenAlex
- W2161414194
- Cited by
- 510
- References
- 8
- FWCI
- 8.04
- Type
- journal article
- Language
- en
- Open access
- diamond
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.