var bibbase_data = {"data":"\"Loading..\"\n\n
\n\n \n\n \n\n \n \n\n \n\n \n \n\n \n\n \n
\n generated by\n \n \"bibbase.org\"\n\n \n
\n \n\n
\n\n \n\n\n
\n\n Excellent! Next you can\n create a new website with this list, or\n embed it in an existing web page by copying & pasting\n any of the following snippets.\n\n
\n JavaScript\n (easiest)\n
\n \n <script src=\"https://bibbase.org/show?bib=https://bercher.net/bibtex/01-Olz/all.bib&theme=default&fullnames=1&jsonp=1&hidemenu=1&jsonp=1\"></script>\n \n
\n\n PHP\n
\n \n <?php\n $contents = file_get_contents(\"https://bibbase.org/show?bib=https://bercher.net/bibtex/01-Olz/all.bib&theme=default&fullnames=1&jsonp=1&hidemenu=1\");\n print_r($contents);\n ?>\n \n
\n\n iFrame\n (not recommended)\n
\n \n <iframe src=\"https://bibbase.org/show?bib=https://bercher.net/bibtex/01-Olz/all.bib&theme=default&fullnames=1&jsonp=1&hidemenu=1\"></iframe>\n \n
\n\n

\n For more details see the documention.\n

\n
\n
\n\n
\n\n This is a preview! To use this list on your own web site\n or create a new web site from it,\n create a free account. The file will be added\n and you will be able to edit it in the File Manager.\n We will show you instructions once you've created your account.\n
\n\n
\n\n

To the site owner:

\n\n

Action required! Mendeley is changing its\n API. In order to keep using Mendeley with BibBase past April\n 14th, you need to:\n

    \n
  1. renew the authorization for BibBase on Mendeley, and
    2. \n
  2. update the BibBase URL\n in your page the same way you did when you initially set up\n this page.\n
    3. \n
\n

\n\n

\n \n \n Fix it now\n

\n
\n\n
\n\n\n
\n \n \n
\n
\n  \n 2024\n \n \n (2)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n An ILP Heuristic for Total-Order HTN Planning.\n \n \n \n\n\n \n Conny Olz; Alexander Lodemann; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 7th ICAPS Workshop on Hierarchical Planning (HPlan 2024), 2024. \n \n\n\n\n
\n\n\n\n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Olz2024TOILPHeuristic,\n  author    = {Conny Olz and Alexander Lodemann and Pascal Bercher},\n  booktitle = {Proceedings of the 7th ICAPS Workshop on Hierarchical Planning (HPlan 2024)},\n  title     = {An ILP Heuristic for Total-Order HTN Planning},\n  year      = {2024},\n  abstract  = {Heuristic Search is still the most successful approach to hierarchical planning, both for finding any and for finding an optimal solution. Yet, there exist only a very small handful heuristics for HTN planning -- so there is still huge potential for improvements. It is especially noteworthy that there does not exist a single heuristic that's tailored towards special cases. In this work we propose the very first specialized HTN heuristic, tailored towards totally ordered HTN problems. Our heuristic builds on an existing NP-complete and admissible delete-and-ordering relaxation ILP heuristic but partially incorporates ordering constraints while reducing the number of ILP constraints. It exploits inferred preconditions and effects of compound tasks and is also admissible. Our current heuristic proves to be more efficient than the one we build on, though it still performs worse than other existing (admissible) heuristics.}\n}\n\n
\n
\n\n\n
\n Heuristic Search is still the most successful approach to hierarchical planning, both for finding any and for finding an optimal solution. Yet, there exist only a very small handful heuristics for HTN planning – so there is still huge potential for improvements. It is especially noteworthy that there does not exist a single heuristic that's tailored towards special cases. In this work we propose the very first specialized HTN heuristic, tailored towards totally ordered HTN problems. Our heuristic builds on an existing NP-complete and admissible delete-and-ordering relaxation ILP heuristic but partially incorporates ordering constraints while reducing the number of ILP constraints. It exploits inferred preconditions and effects of compound tasks and is also admissible. Our current heuristic proves to be more efficient than the one we build on, though it still performs worse than other existing (admissible) heuristics.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence.\n \n \n \n \n\n\n \n Songtuan Lin; Conny Olz; Malte Helmert; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024), 2024. AAAI Press\n \n\n\n\n
\n\n\n\n \n \n \"On paper\n  \n \n \n \"On poster\n  \n \n \n \"On slides\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 26 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Lin2024PlanVerificationComplexity,\n  author    = {Songtuan Lin and Conny Olz and Malte Helmert and Pascal Bercher},\n  booktitle = {Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024)},\n  title     = {On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence},\n  year      = {2024},\n  publisher = {AAAI Press},\n  abstract  = {In this paper we study the computational complexity of several reasoning tasks centered around the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for a grounded and a lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not yet been studied for HTN planning. For plan verification, results were available for both formalisms except for the lifted HTN planning. We will present lower and upper bounds of the complexity of plan verification in lifted HTN planning and provide some new insights into its grounded counterpart, in which we show that verification is not just NP-complete in the general case, but already for a severely restricted special case. Finally, we show the complexity concerning verifying the optimality of a given plan and discuss its connection to the bounded plan existence problem.},\n  url_Paper  = {https://bercher.net/publications/2024/Lin2024PlanVerificationComplexity.pdf},\n  url_Poster = {https://bercher.net/publications/2024/Lin2024PlanVerificationComplexityPoster.pdf},\n  url_Slides = {https://bercher.net/publications/2024/Lin2024PlanVerificationComplexitySlides.pdf}\n}\n\n
\n
\n\n\n
\n In this paper we study the computational complexity of several reasoning tasks centered around the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for a grounded and a lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not yet been studied for HTN planning. For plan verification, results were available for both formalisms except for the lifted HTN planning. We will present lower and upper bounds of the complexity of plan verification in lifted HTN planning and provide some new insights into its grounded counterpart, in which we show that verification is not just NP-complete in the general case, but already for a severely restricted special case. Finally, we show the complexity concerning verifying the optimality of a given plan and discuss its connection to the bounded plan existence problem.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2023\n \n \n (7)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Grounded (Lifted) Linearizer at the IPC 2023: Solving Partial Order HTN Problems by Linearizing Them.\n \n \n \n \n\n\n \n Ying Xian Wu; Conny Olz; Songtuan Lin; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 11th International Planning Competition: Planner Abstracts – Hierarchical Task Network (HTN) Planning Track, IPC 2023, 2023. \n \n\n\n\n
\n\n\n\n \n \n \"Grounded paper\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n\n \n  \n \n 5 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@inproceedings{Wu2023IPCLinearizer,\n  title     = {Grounded (Lifted) Linearizer at the IPC 2023: Solving Partial Order HTN Problems by Linearizing Them},\n  author    = {Ying Xian Wu and Conny Olz and Songtuan Lin and Pascal Bercher},\n  booktitle = {Proceedings of the 11th {I}nternational {P}lanning {C}ompetition: Planner Abstracts -- Hierarchical Task Network (HTN) Planning Track, {IPC} 2023},\n  year      = {2023},\n  abstrac   = {In this paper, we would like to present Grounded (Lifted) Linearizer, a hierarchical task network (HTN) planning system which won the Partial Order (PO) Agile and Satisficing tracks of the International Planning Competition 2023 on Hierarchical Task Network (HTN) Planning. This system consists of two parts. The first part is a preprocessor developed in house which transforms a POHTN problem into a total order (TO) one and which is the main contribution of this paper. The second part is an existing HTN planner. The outstanding performance of our assembled planning system thus serves as an evidence for how our preprocessor can enhance the efficiency of other existing planners.},\n  url_Paper = {https://bercher.net/publications/2023/Wu2023IPCLinearizer.pdf}\n} \n\n
\n
\n\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n The PANDADealer System for Totally Ordered HTN Planning in the 2023 IPC.\n \n \n \n \n\n\n \n Conny Olz; Daniel Höller; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 11th International Planning Competition: Planner Abstracts – Hierarchical Task Network (HTN) Planning Track (IPC), 2023. \n \n\n\n\n
\n\n\n\n \n \n \"The paper\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@inproceedings{Olz2023IPCPANDADealer,\n  title     = {The PANDADealer System for Totally Ordered HTN Planning in the 2023 IPC},\n  author    = {Conny Olz and Daniel H{\\"o}ller and Pascal Bercher},\n  booktitle = {Proceedings of the 11th {I}nternational {P}lanning {C}ompetition: Planner Abstracts -- Hierarchical Task Network (HTN) Planning Track (IPC)},\n  year      = {2023},\n  abstract  = {The PANDADealer system is an HTN planning system for solving totally ordered HTN planning problems. It builds on the heuristic progression search of the PANDApro system, and extends it with a look-ahead technique to detect dead-ends and inevitable refinement choices. The technique is based on inferred preconditions and effects of tasks, or more precisely, their decomposition methods.},\n  url_Paper = {https://bercher.net/publications/2023/Olz2023IPCPANDADealer.pdf}\n}\n\n
\n
\n\n\n
\n The PANDADealer system is an HTN planning system for solving totally ordered HTN planning problems. It builds on the heuristic progression search of the PANDApro system, and extends it with a look-ahead technique to detect dead-ends and inevitable refinement choices. The technique is based on inferred preconditions and effects of tasks, or more precisely, their decomposition methods.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n Experimental Results for the SoCS 2023 Paper ``A Look-Ahead Technique for Search-Based HTN Planning: Reducing the Branching Factor by Identifying Inevitable Task Refinements''.\n \n \n \n\n\n \n Conny Olz; and Pascal Bercher.\n\n\n \n\n\n\n 2023.\n \n\n\n\n
\n\n\n\n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@Misc{Olz2023ExperimentalData,\n  author       = {Conny Olz and Pascal Bercher},\n  title        = {Experimental Results for the SoCS 2023 Paper ``A Look-Ahead Technique for Search-Based HTN Planning: Reducing the Branching Factor by Identifying Inevitable Task Refinements''},\n  year         = {2023},\n  copyright    = {Creative Commons Attribution 4.0 International},\n  doi          = {10.5281/zenodo.7900414},\n  publisher    = {Zenodo}\n}\n\n
\n
\n\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence.\n \n \n \n \n\n\n \n Songtuan Lin; Conny Olz; Malte Helmert; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 6th ICAPS Workshop on Hierarchical Planning (HPlan 2023), pages 35–43, 2023. \n Erratum: Corollary 1 and Proposition 5 incorrectly claimed NEXPTIME and co-NEXPTIME membership, respectively. Both should be one exponential harder, which is stated correctly in the AAAI 2024 version of this paper (same Corollary and Proposition).\n\n\n\n
\n\n\n\n \n \n \"On paper\n  \n \n \n \"On slides\n  \n \n \n \"On poster\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 17 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Lin2023VerificationComplexity,\n  author     = {Songtuan Lin and Conny Olz and Malte Helmert and Pascal Bercher},\n  title      = {On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence},\n  booktitle  = {Proceedings of the 6th ICAPS Workshop on Hierarchical Planning (HPlan 2023)},\n  year       = {2023},\n  pages      = {35--43},\n  note      = {<strong>Erratum:</strong> Corollary 1 and Proposition 5 incorrectly claimed NEXPTIME and co-NEXPTIME membership, respectively. Both should be one exponential harder, which is stated correctly in the AAAI 2024 version of this paper (same Corollary and Proposition).},\n  abstract   = {In this paper we study the computational complexity of several reasoning tasks centered at the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for the grounded and the lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not been studied yet for HTN planning. For plan verification, results were available for both formalisms except the lifted representation of HTN planning. We will thus present the lower bound and the upper bound of the complexity of plan verification in lifted HTN planning and provide novel insights into its grounded counterpart, in which we show that verification is not just NP-complete in the general case, but already for a severely restricted special case. Finally, we show the computational complexity concerning the optimality of a given plan, i.e., answering the question whether such a plan is optimal, and discuss its connection to the bounded plan existence problem.},\n  url_Paper  = {https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanEx.pdf},\n  url_Slides = {https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanExSlides.pdf},\n  url_Poster = {https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanExPoster.pdf}\n}\n\n
\n
\n\n\n
\n In this paper we study the computational complexity of several reasoning tasks centered at the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for the grounded and the lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not been studied yet for HTN planning. For plan verification, results were available for both formalisms except the lifted representation of HTN planning. We will thus present the lower bound and the upper bound of the complexity of plan verification in lifted HTN planning and provide novel insights into its grounded counterpart, in which we show that verification is not just NP-complete in the general case, but already for a severely restricted special case. Finally, we show the computational complexity concerning the optimality of a given plan, i.e., answering the question whether such a plan is optimal, and discuss its connection to the bounded plan existence problem.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n A Look-Ahead Technique for Search-Based HTN Planning: Reducing the Branching Factor by Identifying Inevitable Task Refinements.\n \n \n \n \n\n\n \n Conny Olz; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 6th ICAPS Workshop on Hierarchical Planning (HPlan 2023), 2023. \n \n\n\n\n
\n\n\n\n \n \n \"A paper\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 20 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Olz2023bTOLookAhead,\n  author    = {Conny Olz and Pascal Bercher},\n  title     = {A Look-Ahead Technique for Search-Based HTN Planning: Reducing the Branching Factor by Identifying Inevitable Task Refinements},\n  booktitle = {Proceedings of the 6th ICAPS Workshop on Hierarchical Planning (HPlan 2023)},\n  year      = {2023},\n  abstract  = {In HTN planning the choice of decomposition methods used to refine compound tasks is key to finding a valid plan. Based on inferred preconditions and effects of compound tasks, we propose a look-ahead technique for search-based total-order HTN planning that can identify inevitable refinement choices and in some cases dead-ends. The former occurs when all but one decomposition method for some task are proven infeasible for turning a task network into a solution, whereas the latter occurs when all methods are proven infeasible. We show how it can be used for pruning, as well as to strengthen heuristics and to reduce the search branching factor. An empirical evaluation proves its potential as incorporating it improves an existing HTN planner such that it is the currently best performing one in terms of coverage and IPC score.},\n  url_Paper = {https://bercher.net/publications/2023/Olz2023TOLookAhead.pdf}\n}\n\n
\n
\n\n\n
\n In HTN planning the choice of decomposition methods used to refine compound tasks is key to finding a valid plan. Based on inferred preconditions and effects of compound tasks, we propose a look-ahead technique for search-based total-order HTN planning that can identify inevitable refinement choices and in some cases dead-ends. The former occurs when all but one decomposition method for some task are proven infeasible for turning a task network into a solution, whereas the latter occurs when all methods are proven infeasible. We show how it can be used for pruning, as well as to strengthen heuristics and to reduce the search branching factor. An empirical evaluation proves its potential as incorporating it improves an existing HTN planner such that it is the currently best performing one in terms of coverage and IPC score.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n A Look-Ahead Technique for Search-Based HTN Planning: Reducing the Branching Factor by Identifying Inevitable Task Refinements.\n \n \n \n \n\n\n \n Conny Olz; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 16th International Symposium on Combinatorial Search (SoCS 2023), pages 65–73, 2023. AAAI Press\n \n\n\n\n
\n\n\n\n \n \n \"A paper\n  \n \n \n \"A aaai paper\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 20 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Olz2023TOLookAhead,\n  author    = {Conny Olz and Pascal Bercher},\n  booktitle = {Proceedings of the 16th International Symposium on Combinatorial Search (SoCS 2023)},\n  title     = {A Look-Ahead Technique for Search-Based HTN Planning: Reducing the Branching Factor by Identifying Inevitable Task Refinements},\n  year      = {2023},\n  publisher = {AAAI Press},\n  pages     = {65--73},\n  abstract  = {In HTN planning the choice of decomposition methods used to refine compound tasks is key to finding a valid plan. Based on inferred preconditions and effects of compound tasks, we propose a look-ahead technique for search-based total-order HTN planning that can identify inevitable refinement choices and in some cases dead-ends. The former occurs when all but one decomposition method for some task are proven infeasible for turning a task network into a solution, whereas the latter occurs when all methods are proven infeasible. We show how it can be used for pruning, as well as to strengthen heuristics and to reduce the search branching factor. An empirical evaluation proves its potential as incorporating it improves an existing HTN planner such that it is the currently best performing one in terms of coverage and IPC score.},\n  doi            = {10.1609/socs.v16i1.27284},\n  url_Paper      = {https://bercher.net/publications/2023/Olz2023TOLookAhead.pdf},\n  url_AAAI_paper = {https://ojs.aaai.org/index.php/SOCS/article/view/27284/27057},\n  doi            = {10.1609/socs.v16i1.27284}\n}\n\n\n
\n
\n\n\n
\n In HTN planning the choice of decomposition methods used to refine compound tasks is key to finding a valid plan. Based on inferred preconditions and effects of compound tasks, we propose a look-ahead technique for search-based total-order HTN planning that can identify inevitable refinement choices and in some cases dead-ends. The former occurs when all but one decomposition method for some task are proven infeasible for turning a task network into a solution, whereas the latter occurs when all methods are proven infeasible. We show how it can be used for pruning, as well as to strengthen heuristics and to reduce the search branching factor. An empirical evaluation proves its potential as incorporating it improves an existing HTN planner such that it is the currently best performing one in terms of coverage and IPC score.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Can They Come Together? A Computational Complexity Analysis of Conjunctive Possible Effects of Compound HTN Planning Tasks.\n \n \n \n \n\n\n \n Conny Olz; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 33rd International Conference on Automated Planning and Scheduling (ICAPS 2023), pages 314–323, 2023. AAAI Press\n \n\n\n\n
\n\n\n\n \n \n \"Can paper\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Olz2023ConjunctiveHTNEffects,\n  author    = {Conny Olz and Pascal Bercher},\n  booktitle = {Proceedings of the 33rd International Conference on Automated Planning and Scheduling ({ICAPS 2023})},\n  title     = {Can They Come Together? A Computational Complexity Analysis of Conjunctive Possible Effects of Compound HTN Planning Tasks},\n  year      = {2023},\n  pages     = {314--323},\n  publisher = {AAAI Press},\n  doi       = {10.1609/icaps.v33i1.27209},\n  abstract  = {Recently, inferred effects of compound (totally ordered) HTN planning tasks were introduced. Guaranteed effects are those which hold true after all executable refinements of said task, whereas possible effects are required to hold after some of them. It is known that we can decide in P whether a single fact is a precondition-relaxed possible effect. For this relaxation it wasn't clear whether groups of effects could be determined in P as well. We show that the problem turns NP-complete for conjunctive possible effects of arbitrary size. A more positive result is that this problem is fixed-parameter tractable, i.e., for any fixed number of possible effects, we can verify (and compute) them in P. As a side product of our investigations we obtain novel results for total-order HTN planning problems with goal description: When ignoring action preconditions, plan existence is NP-complete and remains NP-hard even when the problem is additionally acyclic, regular, and delete-relaxed.},\n  url_Paper = {https://bercher.net/publications/2023/Olz2023CompoundTaskEffects.pdf}\n}\n\n\n
\n
\n\n\n
\n Recently, inferred effects of compound (totally ordered) HTN planning tasks were introduced. Guaranteed effects are those which hold true after all executable refinements of said task, whereas possible effects are required to hold after some of them. It is known that we can decide in P whether a single fact is a precondition-relaxed possible effect. For this relaxation it wasn't clear whether groups of effects could be determined in P as well. We show that the problem turns NP-complete for conjunctive possible effects of arbitrary size. A more positive result is that this problem is fixed-parameter tractable, i.e., for any fixed number of possible effects, we can verify (and compute) them in P. As a side product of our investigations we obtain novel results for total-order HTN planning problems with goal description: When ignoring action preconditions, plan existence is NP-complete and remains NP-hard even when the problem is additionally acyclic, regular, and delete-relaxed.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2022\n \n \n (2)\n \n \n
\n
\n \n \n \n\n\n
\n \n\n \n \n \n \n \n \n On the Efficient Inference of Preconditions and Effects of Compound Tasks in Partially Ordered HTN Planning Domains.\n \n \n \n \n\n\n \n Conny Olz; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 5th ICAPS Workshop on Hierarchical Planning (HPlan 2022), pages 47–51, 2022. \n \n\n\n\n
\n\n\n\n \n \n \"On paper\n  \n \n \n \"On presentation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 16 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Olz2022POPrecsAndEffects,\n  author           = {Conny Olz and Pascal Bercher},\n  booktitle        = {Proceedings of the 5th ICAPS Workshop on Hierarchical Planning (HPlan 2022)},\n  title            = {On the Efficient Inference of Preconditions and Effects of Compound Tasks in Partially Ordered HTN Planning Domains},\n  year             = {2022},\n  Pages            = {47--51},\n  abstract         = {Recently, preconditions and effects of compound tasks based on their possible refinements have been introduced together with an efficient inference procedure to compute a subset of them. However, they were restricted to total-order HTN planning domains. In this paper we generalize the definitions and algorithm to the scenario of partially ordered domains.},\n  url_Paper        = {https://bercher.net/publications/2022/Olz2022POPrecsAndEffects.pdf},\n  url_presentation = {https://youtu.be/QsQsXBYu0yI}\n}\n\n
\n
\n\n\n
\n Recently, preconditions and effects of compound tasks based on their possible refinements have been introduced together with an efficient inference procedure to compute a subset of them. However, they were restricted to total-order HTN planning domains. In this paper we generalize the definitions and algorithm to the scenario of partially ordered domains.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2021\n \n \n (2)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Revealing Hidden Preconditions and Effects of Compound HTN Planning Tasks – A Complexity Analysis.\n \n \n \n \n\n\n \n Conny Olz; Susanne Biundo; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), pages 11903–11912, 2021. AAAI Press\n \n\n\n\n
\n\n\n\n \n \n paper\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Olz2021RevealingHTNEffects,\n  author    = {Conny Olz and Susanne Biundo and Pascal Bercher},\n  booktitle = {Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021)},\n  title     = {Revealing Hidden Preconditions and Effects of Compound HTN Planning Tasks -- A Complexity Analysis},\n  year      = {2021},\n  pages     = {11903--11912},\n  publisher = {AAAI Press},\n  abstract  = {In Hierarchical Task Network (HTN) planning, compound tasks need to be refined into executable (primitive) action sequences. In contrast to their primitive counterparts, compound tasks do not show preconditions or effects. Thus, their implications on the states in which they are applied are not explicitly known: they are “hidden” in and depending on the decomposition structure. We formalize several kinds of preconditions and effects that can be inferred for compound tasks in totally ordered HTN domains. As relevant special case we introduce a problem relaxation which admits reasoning about preconditions and effects in polynomial time. We provide procedures for doing so, thereby extending previous work, which could only deal with acyclic models. We prove our procedures to be correct and complete for any totally ordered input domain. The results are embedded into an encompassing complexity analysis of the inference of preconditions and effects of compound tasks, an investigation that has not been made so far.},\n  doi       = {10.1609/aaai.v35i13.17414},\n  url_Paper = {https://bercher.net/publications/2021/Olz2021CompoundEffects.pdf}\n}\n\n\n
\n
\n\n\n
\n In Hierarchical Task Network (HTN) planning, compound tasks need to be refined into executable (primitive) action sequences. In contrast to their primitive counterparts, compound tasks do not show preconditions or effects. Thus, their implications on the states in which they are applied are not explicitly known: they are “hidden” in and depending on the decomposition structure. We formalize several kinds of preconditions and effects that can be inferred for compound tasks in totally ordered HTN domains. As relevant special case we introduce a problem relaxation which admits reasoning about preconditions and effects in polynomial time. We provide procedures for doing so, thereby extending previous work, which could only deal with acyclic models. We prove our procedures to be correct and complete for any totally ordered input domain. The results are embedded into an encompassing complexity analysis of the inference of preconditions and effects of compound tasks, an investigation that has not been made so far.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Towards Improving the Comprehension of HTN Planning Domains by Means of Preconditions and Effects of Compound Tasks.\n \n \n \n \n\n\n \n Conny Olz; Eva Wierzba; Pascal Bercher; and Felix Lindner.\n\n\n \n\n\n\n In Proceedings of the 10th Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2021), 2021. \n \n\n\n\n
\n\n\n\n \n \n \"Towards paper\n  \n \n \n \"Towards slides\n  \n \n \n \"Towards video-of-paper-presentation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Olz2021ComprehendHTNModels,\n  author    = {Conny Olz and Eva Wierzba and Pascal Bercher and Felix Lindner},\n  title     = {Towards Improving the Comprehension of HTN Planning Domains by Means of Preconditions and Effects of Compound Tasks},\n  booktitle = {Proceedings of the 10th Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2021)},\n  year      = {2021},\n  abstract  = {Hierarchical Task Network (HTN) planning is a paradigm that offers engineers a formalism for modeling planning domains in terms of possible decompositions of compound tasks. A complete decomposition of a compound task results in totally or partially ordered primitive tasks, i.e., plans in the classical sense. Existing specification languages for HTN domains, such as HDDL, do only allow the assertion of preconditions and effects for primitive tasks but not for compound ones. Recently, a method for inferring preconditions and effects for compound tasks was proposed. It was hypothesized that inferred preconditions and effects can aid knowledge engineers in understanding HTN domain specifications and in predicting the meaning of particular compound tasks. We describe preliminary results from a study that supports this hypothesis and discuss future research directions.},\n  url_Paper = {https://bercher.net/publications/2021/Olz2021ComprehendHTNModels.pdf},\n  url_Slides = {https://bercher.net/publications/2021/Olz2021ComprehendHTNModelsSlides.pdf},\n  url_video-of-paper-presentation = {https://www.youtube.com/watch?v=jLcTjrtNhaY&list=PLd_hcmfMPvAhDzHla0ZR6dNsiKBlwsx6K&index=11}\n}\n\n\n
\n
\n\n\n
\n Hierarchical Task Network (HTN) planning is a paradigm that offers engineers a formalism for modeling planning domains in terms of possible decompositions of compound tasks. A complete decomposition of a compound task results in totally or partially ordered primitive tasks, i.e., plans in the classical sense. Existing specification languages for HTN domains, such as HDDL, do only allow the assertion of preconditions and effects for primitive tasks but not for compound ones. Recently, a method for inferring preconditions and effects for compound tasks was proposed. It was hypothesized that inferred preconditions and effects can aid knowledge engineers in understanding HTN domain specifications and in predicting the meaning of particular compound tasks. We describe preliminary results from a study that supports this hypothesis and discuss future research directions.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2020\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n POP $≡$ POCL, right? Complexity Results for Partial Order (Causal Link) Makespan Minimization.\n \n \n \n \n\n\n \n Pascal Bercher; and Conny Olz.\n\n\n \n\n\n\n In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020), pages 9785–9793, 2020. AAAI Press\n \n\n\n\n
\n\n\n\n \n \n \"POP paper\n  \n \n \n \"POP spotlight-slides\n  \n \n \n \"POP poster\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 3 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Bercher2020POPvsPOCL,\n  author    = {Pascal Bercher and Conny Olz},\n  title     = {POP $\\equiv$ POCL, right? Complexity Results for Partial Order (Causal Link) Makespan Minimization},\n  booktitle = {Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020)},\n  year      = {2020},\n  pages     = {9785--9793},\n  publisher = {AAAI Press},\n  doi       = {10.1609/aaai.v34i06.6530},\n  abstract  = {We study PO and POCL plans with regard to their makespan -- the execution  time when allowing the parallel execution of causally independent actions. Partially ordered (PO) plans are often assumed to be equivalent to partial order causal link  (POCL) plans, where the causal relationships between actions are explicitly represented via causal links. As a first contribution, we study the similarities and differences of PO and POCL plans, thereby clarifying a common misconception about their relationship: There are PO plans for which there does not exist a POCL plan with the same orderings.We prove that we can still always find a POCL plan with the same makespan in polynomial time. As another main result we prove that turning a PO or POCL plan into one with minimal makespan by only removing ordering constraints (called deordering) is NP-complete. We provide a series of further results on special cases and implications, such as reordering, where orderings can be changed arbitrarily.},\n  url_Paper            = {https://bercher.net/publications/2020/Bercher2020POPvsPOCL.pdf},\n  url_Spotlight-slides = {https://bercher.net/publications/2020/Bercher2020POPvsPOCLSlidesSpotlight.pdf},\n  url_Poster           = {https://bercher.net/publications/2020/Bercher2020POPvsPOCLPoster.pdf}\n}\n\n\n
\n
\n\n\n
\n We study PO and POCL plans with regard to their makespan – the execution time when allowing the parallel execution of causally independent actions. Partially ordered (PO) plans are often assumed to be equivalent to partial order causal link (POCL) plans, where the causal relationships between actions are explicitly represented via causal links. As a first contribution, we study the similarities and differences of PO and POCL plans, thereby clarifying a common misconception about their relationship: There are PO plans for which there does not exist a POCL plan with the same orderings.We prove that we can still always find a POCL plan with the same makespan in polynomial time. As another main result we prove that turning a PO or POCL plan into one with minimal makespan by only removing ordering constraints (called deordering) is NP-complete. We provide a series of further results on special cases and implications, such as reordering, where orderings can be changed arbitrarily.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2019\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Eliminating Redundant Actions in Partially Ordered Plans – A Complexity Analysis.\n \n \n \n \n\n\n \n Conny Olz; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS 2019), pages 310–319, 2019. AAAI Press\n \n\n\n\n
\n\n\n\n \n \n \"Eliminating paper\n  \n \n \n \"Eliminating slides\n  \n \n \n \"Eliminating video of presentation\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 7 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Olz2019StepElimination,\n   author    = {Conny Olz and Pascal Bercher},\n   title     = {Eliminating Redundant Actions in Partially Ordered Plans -- A Complexity Analysis},\n   year      = {2019},\n   publisher = {AAAI Press},\n   pages     = {310--319},\n   booktitle = {Proceedings of the 28th International Conference on Automated Planning and Scheduling ({ICAPS 2019})},\n   abstract  = {In this paper we study the computational complexity of post-optimizing partially ordered plans, i.e., we investigate the problem that is concerned with detecting and deleting unnecessary actions. For totally ordered plans it can easily be tested in polynomial time whether a single action can be removed without violating executability. Identifying an executable subplan, i.e., asking whether k plan steps can be removed, is known to be NP-complete. We investigate the same questions for partially ordered input plans, as they are created by many search algorithms or used by real-world applications -- in particular time-critical ones that exploit parallelism of non-conflicting actions. More formally, we investigate the computational complexity of removing an action from a partially ordered solution plan in which every linearization is a solution in the classical sense while allowing ordering insertions afterwards to repair arising executability issues. It turns out that this problem is NP-complete -- even if just a single action is removed -- and thereby show that this reasoning task is harder than for totally ordered plans. Moreover, we identify the structural properties responsible for this hardness by providing a fixed-parameter tractability (FPT) result.},\n   doi        = {10.1609/icaps.v29i1.3493},\n   url_Paper  = {https://bercher.net/publications/2019/Olz2019StepElimination.pdf},\n   url_Slides = {https://bercher.net/publications/2019/Olz2019StepEliminationSlides.pdf},\n   url_video_of_presentation = {https://www.youtube.com/watch?v=nNoaWfHP7eQ&t=2415s&ab_channel=ICAPS}\n}\n\n
\n
\n\n\n
\n In this paper we study the computational complexity of post-optimizing partially ordered plans, i.e., we investigate the problem that is concerned with detecting and deleting unnecessary actions. For totally ordered plans it can easily be tested in polynomial time whether a single action can be removed without violating executability. Identifying an executable subplan, i.e., asking whether k plan steps can be removed, is known to be NP-complete. We investigate the same questions for partially ordered input plans, as they are created by many search algorithms or used by real-world applications – in particular time-critical ones that exploit parallelism of non-conflicting actions. More formally, we investigate the computational complexity of removing an action from a partially ordered solution plan in which every linearization is a solution in the classical sense while allowing ordering insertions afterwards to repair arising executability issues. It turns out that this problem is NP-complete – even if just a single action is removed – and thereby show that this reasoning task is harder than for totally ordered plans. Moreover, we identify the structural properties responsible for this hardness by providing a fixed-parameter tractability (FPT) result.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n\n\n\n
\n\n\n \n\n \n \n \n \n\n
\n"}; document.write(bibbase_data.data);