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
2 ARC - NASA Ames Research Center

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.

Mots clés: temporal planning; hierarchical planning; reachability analysis; delete relaxation

Domaines: Intelligence artificielle [cs.AI]

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⟩