Planning Through Stochastic Local Search and Temporal Action Graphs in LPG

Abstract

We present some techniques for planning in domains specified with the recent standard language PDDL2.1, supporting 'durative actions' and numerical quantities. These techniques are implemented in LPG, a domain-independent planner that took part in the 3rd International Planning Competition (IPC). LPG is an incremental, any time system producing multi-criteria quality plans. The core of the system is based on a stochastic local search method and on a graph-based representation called 'Temporal Action Graphs' (TA-graphs). This paper focuses on temporal planning, introducing TA-graphs and proposing some techniques to guide the search in LPG using this representation. The experimental results of the 3rd IPC, as well as further results presented in this paper, show that our techniques can be very effective. Often LPG outperforms all other fully-automated planners of the 3rd IPC in terms of speed to derive a solution, or quality of the solutions that can be produced.

References in corpus (6)

• The FF Planning System: Fast Plan Generation Through Heuristic Search
• PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains
• SHOP2: An HTN Planning System
• The 3rd International Planning Competition: Results and Analysis
• The Automatic Inference of State Invariants in TIM
• Efficient Implementation of the Plan Graph in STAN

Cited by in corpus (16)

• The Fast Downward Planning System
• The 3rd International Planning Competition: Results and Analysis
• The Deterministic Part of IPC-4: An Overview
• Compiling quantum circuits to realistic hardware architectures using temporal planners
• An Approach to Temporal Planning and Scheduling in Domains with Predictable Exogenous Events
• Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h+
• Message-Based Web Service Composition, Integrity Constraints, and Planning under Uncertainty: A New Connection
• Finding Similar/Diverse Solutions in Answer Set Programming
• On-line Planning and Scheduling: An Application to Controlling Modular Printers
• Structure and Problem Hardness: Goal Asymmetry and DPLL Proofs in<br> SAT-Based Planning
• Planning for Compilation of a Quantum Algorithm for Graph Coloring
• Automated Algorithm Selection: Survey and Perspectives
• Domain-independent generation and classification of behavior traces
• Case-Based Merging Techniques in OAKPLAN
• On the Tractability of Minimal Model Computation for Some CNF Theories
• An Empirical Study of the Effects of Spurious Transitions on Abstraction-based Heuristics