The FF Planning System: Fast Plan Generation Through Heuristic Search

Abstract

We describe and evaluate the algorithmic techniques that are used in the FF planning system. Like the HSP system, FF relies on forward state space search, using a heuristic that estimates goal distances by ignoring delete lists. Unlike HSP's heuristic, our method does not assume facts to be independent. We introduce a novel search strategy that combines hill-climbing with systematic search, and we show how other powerful heuristic information can be extracted and used to prune the search space. FF was the most successful automatic planner at the recent AIPS-2000 planning competition. We review the results of the competition, give data for other benchmark domains, and investigate the reasons for the runtime performance of FF compared to HSP.

References in corpus (3)

• The Automatic Inference of State Invariants in TIM
• On Reasonable and Forced Goal Orderings and their Use in an Agenda-Driven Planning Algorithm
• Efficient Implementation of the Plan Graph in STAN

Cited by in corpus (113)

• Narrative Planning: Balancing Plot and Character
• The Fast Downward Planning System
• Planning Through Stochastic Local Search and Temporal Action Graphs in LPG
• The 3rd International Planning Competition: Results and Analysis
• The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks
• Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators
• The Metric-FF Planning System: Translating "Ignoring Delete Lists" to Numeric State Variables
• VHPOP: Versatile Heuristic Partial Order Planner
• SAPA: A Multi-objective Metric Temporal Planner
• The Deterministic Part of IPC-4: An Overview
• FFRob: Leveraging Symbolic Planning for Efficient Task and Motion Planning
• COLIN: Planning with Continuous Linear Numeric Change
• Planning Graph Heuristics for Belief Space Search
• Approximate Policy Iteration with a Policy Language Bias: Solving Relational Markov Decision Processes
• Probabilistic Planning via Heuristic Forward Search and Weighted Model Counting
• Sampling-Based Methods for Factored Task and Motion Planning
• mGPT: A Probabilistic Planner Based on Heuristic Search
• FMAP: Distributed Cooperative Multi-Agent Planning
• A Critical Assessment of Benchmark Comparison in Planning
• Decision-Theoretic Planning with non-Markovian Rewards
• Engineering Benchmarks for Planning: the Domains Used in the Deterministic Part of IPC-4
• Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h+
• Backward-Forward Search for Manipulation Planning
• Compiling Uncertainty Away in Conformant Planning Problems with Bounded Width
• Message-Based Web Service Composition, Integrity Constraints, and Planning under Uncertainty: A New Connection
• The GRT Planning System: Backward Heuristic Construction in Forward State-Space Planning
• Relational Dynamic Bayesian Networks
• Planning with Noisy Probabilistic Relational Rules
• Marvin: A Heuristic Search Planner with Online Macro-Action Learning
• Where 'Ignoring Delete Lists' Works: Local Search Topology in Planning Benchmarks
• A Hybrid LP-RPG Heuristic for Modelling Numeric Resource Flows in Planning
• Scaling up Heuristic Planning with Relational Decision Trees
• Representation, learning, and planning algorithms for geometric task and motion planning
• ReAct! An Interactive Tool for Hybrid Planning in Robotics
• SAP Speaks PDDL: Exploiting a Software-Engineering Model for Planning in Business Process Management
• Replanning in Domains with Partial Information and Sensing Actions
• DeepSym: Deep Symbol Generation and Rule Learning from Unsupervised Continuous Robot Interaction for Planning
• Generalized Planning With Deep Reinforcement Learning
• Plan Explicability and Predictability for Robot Task Planning
• MPTP: Motion-Planning-aware Task Planning for Navigation in Belief Space
• Combined Task and Motion Planning as Classical AI Planning
• A Flexible Coupling Approach to Multi-Agent Planning under Incomplete Information
• Task and Motion Informed Trees (TMIT*): Almost-Surely Asymptotically Optimal Integrated Task and Motion Planning
• iRoPro: An interactive Robot Programming Framework
• Engineering a Conformant Probabilistic Planner
• Distributed Heuristic Forward Search for Multi-Agent Systems
• Enabling human-like task identification from natural conversation
• Heuristic-Guided Reinforcement Learning
• End-User Programming of Low- and High-Level Actions for Robotic Task Planning
• Behavior and path planning for the coalition of cognitive robots in smart relocation tasks
• What Should I Do Now? Marrying Reinforcement Learning and Symbolic Planning
• Logic programming for deliberative robotic task planning
• Learning Heuristic Search via Imitation
• TASKOGRAPHY: Evaluating robot task planning over large 3D scene graphs
• On-line Planning and Scheduling: An Application to Controlling Modular Printers
• Real-time tree search with pessimistic scenarios
• Feature Guided Search for Creative Problem Solving Through Tool Construction
• Your instruction may be crisp, but not clear to me!
• Cost Based Satisficing Search Considered Harmful
• SAS+ Planning as Satisfiability
• Structure and Problem Hardness: Goal Asymmetry and DPLL Proofs in<br> SAT-Based Planning
• Graph Transformation Planning via Abstraction
• Learning to Rank for Synthesizing Planning Heuristics
• Optimal Program Synthesis via Abstract Interpretation
• Totally and Partially Ordered Hierarchical Planners in PDDL4J Library
• Timeline-based planning: Expressiveness and Complexity
• Online Speedup Learning for Optimal Planning
• Software Architecture for Next-Generation AI Planning Systems
• Towards Stable Symbol Grounding with Zero-Suppressed State AutoEncoder
• Modeling the Mistakes of Boundedly Rational Agents Within a Bayesian Theory of Mind
• Levels of Integration between Low-Level Reasoning and Task Planning
• Duality in STRIPS planning
• Neural-Symbolic Descriptive Action Model from Images: The Search for STRIPS
• Reformulation Techniques for Automated Planning: A Systematic Review
• Learning Causal Models of Autonomous Agents using Interventions
• iCORPP: Interleaved Commonsense Reasoning and Probabilistic Planning on Robots
• Representation Learning for Classical Planning from Partially Observed Traces
• Applying Strategic Multiagent Planning to Real-World Travel Sharing Problems
• Conditional Task and Motion Planning through an Effort-based Approach
• Gradient-Based Mixed Planning with Symbolic and Numeric Action Parameters
• Generalizing the Role of Determinization in Probabilistic Planning
• Cost Optimal Planning as Satisfiability
• Towards Multi-Robot Task-Motion Planning for Navigation in Belief Space
• Investigating Human Response, Behaviour, and Preference in Joint-Task Interaction
• Towards Automated Network Mitigation Analysis (extended)
• Meta-Reinforcement Learning for Heuristic Planning
• Reasoning and Planning with Sensing Actions, Incomplete Information, and Static Causal Laws using Answer Set Programming
• Case-Based Merging Techniques in OAKPLAN
• Flexible and Efficient Long-Range Planning Through Curious Exploration
• Discrete Word Embedding for Logical Natural Language Understanding
• An Artifact-based Workflow for Finite-Element Simulation Studies
• Practical Reasoning with Norms for Autonomous Software Agents (Full Edition)
• Extracting Lifted Mutual Exclusion Invariants from Temporal Planning Domains
• Efficient Temporal Piecewise-Linear Numeric Planning with Lazy Consistency Checking
• Understanding Sample Generation Strategies for Learning Heuristic Functions in Classical Planning
• Mining useful Macro-actions in Planning
• Learning and Tuning Meta-heuristics in Plan Space Planning
• Mean-based Heuristic Search for Real-Time Planning
• Surrogate Search As a Way to Combat Harmful Effects of Ill-behaved Evaluation Functions
• Timeline-based Planning and Execution with Uncertainty: Theory, Modeling Methodologies and Practice
• Hybrid Planning for Dynamic Multimodal Stochastic Shortest Paths
• Planning with Learned Binarized Neural Networks Benchmarks for MaxSAT Evaluation 2021
• Rollout Heuristics for Online Stochastic Contingent Planning
• Optimal Mixed Discrete-Continuous Planning for Linear Hybrid Systems
• Encoding Compositionality in Classical Planning Solutions
• Psychologically inspired planning method for smart relocation task
• Efficient Constraint Generation for Stochastic Shortest Path Problems
• Domain-Independent Dynamic Programming
• Goal Recognition over Imperfect Domain Models
• D-VAL: An automatic functional equivalence validation tool for planning domain models
• Planning with Uncertainty: Symmetries, Policy Inference, and Solution Compression
• Heuristic Approaches for Goal Recognition in Incomplete Domain Models
• Une approche totalement instanciée pour la planification HTN