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.
Type de document :
Communication dans un congrès
ICAPS Workshop on Heuristics and Search for Domain-independent Planning (HSDIP), Jun 2016, London, United Kingdom. 2016
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal-univ-tlse3.archives-ouvertes.fr/hal-01319768
Contributeur : Arthur Bit-Monnot <>
Soumis le : lundi 23 mai 2016 - 08:34:54
Dernière modification le : dimanche 22 octobre 2017 - 10:30:02

Fichier

reachability-hsdip.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01319768, version 1

Citation

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. 2016. 〈hal-01319768〉

Partager

Métriques

Consultations de la notice

146

Téléchargements de fichiers

62