HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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
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 metadata

Cited literature [16 references]  Display  Hide  Download

Contributor : Arthur Bit-Monnot Connect in order to contact the contributor
Submitted on : Monday, May 23, 2016 - 8:34:54 AM
Last modification on : Monday, April 4, 2022 - 3:24:37 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