@inproceedings {icaps16-148,
    track    = {​Main Track},
    title    = {Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13174},
    author   = {Ron Alford and  Gregor Behnke and  Daniel Höller and  Pascal Bercher and  Susanne Biundo and  David Aha},
    abstract = {Hierarchical Task Network (HTN) Planning is an expressive formalism used to encode domain-specific search control knowledge and to reason about procedural structures. Yet the cornucopia of modern heuristic search techniques remains largely unincorporated in current HTN planners, in part because these search techniques rely on size-bounded data structures that do not exist for all HTN problems. However, many HTN problems are either tail-recursive, allowing SHOP2-style progression-based HTN planners to reason about relatively small task networks, or acyclic, which provides termination guarantees for decomposition planners such as PANDA. We formally define size bounds for HTN progression, and show that we can find the minimum and maximum progression bound for acyclic and tail-recursive HTN problems in polynomial time. This allows us to provide three automatic translations of tail-recursive HTN problems to PDDL: linear and quadratic STRIPS translations of totally-ordered and partially-ordered problems, respectively, and a linear translation of partially-ordered problems for ADL-capable planners. Finally, we show that PDDL planners can efficiently plan with this translated HTN knowledge on a variety of domains.},
    keywords = {Classical planning,Search techniques,HTN and knowledge-based planning,Complexity analysis}
}

{"_id":"qbhk8kbqr95Ba4Zxo","bibbaseid":"alford-behnke-hller-bercher-biundo-aha-boundtoplanexploitingclassicalheuristicsviaautomatictranslationsoftailrecursivehtnproblems","downloads":0,"creationDate":"2016-03-18T12:02:41.177Z","title":"Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems","author_short":["Alford, R.","Behnke, G.","Höller, D.","Bercher, P.","Biundo, S.","Aha, D."],"year":null,"bibtype":"inproceedings","biburl":"icaps16.icaps-conference.org/papers.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","track":"​Main Track","title":"Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems","url":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13174","author":[{"firstnames":["Ron"],"propositions":[],"lastnames":["Alford"],"suffixes":[]},{"firstnames":["Gregor"],"propositions":[],"lastnames":["Behnke"],"suffixes":[]},{"firstnames":["Daniel"],"propositions":[],"lastnames":["Höller"],"suffixes":[]},{"firstnames":["Pascal"],"propositions":[],"lastnames":["Bercher"],"suffixes":[]},{"firstnames":["Susanne"],"propositions":[],"lastnames":["Biundo"],"suffixes":[]},{"firstnames":["David"],"propositions":[],"lastnames":["Aha"],"suffixes":[]}],"abstract":"Hierarchical Task Network (HTN) Planning is an expressive formalism used to encode domain-specific search control knowledge and to reason about procedural structures. Yet the cornucopia of modern heuristic search techniques remains largely unincorporated in current HTN planners, in part because these search techniques rely on size-bounded data structures that do not exist for all HTN problems. However, many HTN problems are either tail-recursive, allowing SHOP2-style progression-based HTN planners to reason about relatively small task networks, or acyclic, which provides termination guarantees for decomposition planners such as PANDA. We formally define size bounds for HTN progression, and show that we can find the minimum and maximum progression bound for acyclic and tail-recursive HTN problems in polynomial time. This allows us to provide three automatic translations of tail-recursive HTN problems to PDDL: linear and quadratic STRIPS translations of totally-ordered and partially-ordered problems, respectively, and a linear translation of partially-ordered problems for ADL-capable planners. Finally, we show that PDDL planners can efficiently plan with this translated HTN knowledge on a variety of domains.","keywords":"Classical planning,Search techniques,HTN and knowledge-based planning,Complexity analysis","bibtex":"@inproceedings {icaps16-148,\r\n track = {​Main Track},\r\n title = {Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems},\r\n url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13174},\r\n author = {Ron Alford and Gregor Behnke and Daniel Höller and Pascal Bercher and Susanne Biundo and David Aha},\r\n abstract = {Hierarchical Task Network (HTN) Planning is an expressive formalism used to encode domain-specific search control knowledge and to reason about procedural structures. Yet the cornucopia of modern heuristic search techniques remains largely unincorporated in current HTN planners, in part because these search techniques rely on size-bounded data structures that do not exist for all HTN problems. However, many HTN problems are either tail-recursive, allowing SHOP2-style progression-based HTN planners to reason about relatively small task networks, or acyclic, which provides termination guarantees for decomposition planners such as PANDA. We formally define size bounds for HTN progression, and show that we can find the minimum and maximum progression bound for acyclic and tail-recursive HTN problems in polynomial time. This allows us to provide three automatic translations of tail-recursive HTN problems to PDDL: linear and quadratic STRIPS translations of totally-ordered and partially-ordered problems, respectively, and a linear translation of partially-ordered problems for ADL-capable planners. Finally, we show that PDDL planners can efficiently plan with this translated HTN knowledge on a variety of domains.},\r\n keywords = {Classical planning,Search techniques,HTN and knowledge-based planning,Complexity analysis}\r\n}\r\n\r\n","author_short":["Alford, R.","Behnke, G.","Höller, D.","Bercher, P.","Biundo, S.","Aha, D."],"key":"icaps16-148","id":"icaps16-148","bibbaseid":"alford-behnke-hller-bercher-biundo-aha-boundtoplanexploitingclassicalheuristicsviaautomatictranslationsoftailrecursivehtnproblems","role":"author","urls":{"Paper":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13174"},"keyword":["Classical planning","Search techniques","HTN and knowledge-based planning","Complexity analysis"],"metadata":{"authorlinks":{}}},"search_terms":["bound","plan","exploiting","classical","heuristics","via","automatic","translations","tail","recursive","htn","problems","alford","behnke","höller","bercher","biundo","aha"],"keywords":["classical planning","search techniques","htn and knowledge-based planning","complexity analysis"],"authorIDs":[],"dataSources":["iMkx859KiXcegwsin","EZtZjCTnxcdTTyeij"]}