Delete-free Reachability Analysis for Temporal and Hierarchical Planning (full version)

Arthur Bit-Monnot 1 David E. Smith 2 Minh Do 2
1 LAAS-RIS - Équipe Robotique et InteractionS
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
Abstract : Reachability analysis is a crucial part of the heuristic computation for many state of the art classical and temporal planners. In this paper, we study the difficulty that arises in assessing the reachability of actions in planning problems containing sets of interdependent actions, notably including problems with required concurrency as well as hierarchical planning problems. In temporal planners, this complication has been addressed by augmenting a delete-free relaxation with additional relaxations, but this can result in weak pruning of the search space. To overcome this problem, we describe a more sophisticated method for reachability analysis that uses Dijkstra's algorithm for propagation of times through a reach-ability graph, combined with a pruning mechanism that recognizes unachievable cycles. We also extend our approach to handle hierarchical planning problems, in which an action and its subactions are naturally interdependent. Evaluations were conducted on a diverse set of temporal domains using FAPE, a constraint-based temporal and hierarchical planner.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download
Contributor : Arthur Bit-Monnot <>
Submitted on : Monday, May 23, 2016 - 8:34:54 AM
Last modification on : Friday, June 14, 2019 - 6:31:11 PM


Files produced by the author(s)


  • HAL Id : hal-01319768, version 1


Arthur Bit-Monnot, David E. Smith, Minh Do. Delete-free Reachability Analysis for Temporal and Hierarchical Planning (full version). ICAPS Workshop on Heuristics and Search for Domain-independent Planning (HSDIP), Jun 2016, London, United Kingdom. ⟨hal-01319768⟩



Record views


Files downloads