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/02-Lin/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/02-Lin/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/02-Lin/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 (4)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n A Visual Studio Code Extension for Automatically Repairing Planning Domains.\n \n \n \n\n\n \n Songtuan Lin; Mohammad Yousefi; and Pascal Bercher.\n\n\n \n\n\n\n In ICAPS 2024 Demonstrations, 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{Lin2024VSPlugin,\n  author    = {Songtuan Lin and Mohammad Yousefi and Pascal Bercher},\n  booktitle = {ICAPS 2024 Demonstrations},\n  title     = {A Visual Studio Code Extension for Automatically Repairing Planning Domains},\n  year      = {2024},\n  abstract  = {We demonstrate a Visual Studio Code extension which aims at providing modeling assistance for modeling planning domains in PDDL. More specifically, the extension can identify potential flaws in a domain and propose respective corrections by taking as input a set of counter-example plans, which are known to be valid but actually contradict the domain. Those input plans shall be provided by the user. The flaws are then identified and corrected by making changes to the domain so as to turn those plans into solutions, i.e., the changes are regarded as potential corrections to the domain. Currently, the extension only supports corrections that add predicates to or remove predicates from actions' preconditions and effects.}\n}\n\n
\n
\n\n\n
\n We demonstrate a Visual Studio Code extension which aims at providing modeling assistance for modeling planning domains in PDDL. More specifically, the extension can identify potential flaws in a domain and propose respective corrections by taking as input a set of counter-example plans, which are known to be valid but actually contradict the domain. Those input plans shall be provided by the user. The flaws are then identified and corrected by making changes to the domain so as to turn those plans into solutions, i.e., the changes are regarded as potential corrections to the domain. Currently, the extension only supports corrections that add predicates to or remove predicates from actions' preconditions and effects.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Modeling Assistance for Hierarchical Planning: An Approach for Correcting Hierarchical Domains with Missing Actions.\n \n \n \n \n\n\n \n Songtuan Lin; Daniel Höller; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 17th International Symposium on Combinatorial Search (SoCS 2024), 2024. AAAI Press\n \n\n\n\n
\n\n\n\n \n \n \"Modeling 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 3 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Lin2024HTNModelFixing,\n  author    = {Songtuan Lin and Daniel H\\"oller and Pascal Bercher},\n  booktitle = {Proceedings of the 17th International Symposium on Combinatorial Search (SoCS 2024)},\n  title     = {Modeling Assistance for Hierarchical Planning: An Approach for Correcting Hierarchical Domains with Missing Actions},\n  year      = {2024},\n  publisher = {AAAI Press},\n  abstract  = {The complexity of modeling planning domains is a major obstacle for making automated planning techniques more accessible, raising the demand of tools for providing modeling assistance. In particular, tools that can automatically correct errors in a planning domain are of great importance. Previous works have devoted efforts to developing such approaches for correcting classical  (non-hierarchical) domains. However, no approaches exist for hierarchical planning, which is what we offer here. More specifically, our approach takes as input a flawed hierarchical domain together with a plan known to be a solution but actually contradicting the domain (due to errors in the domain) and outputs corrections to the domain that add \\emph{missing} actions to the domain and make the plan a solution. The approach achieves this by compiling the problem of finding corrections as another hierarchical planning problem.},\n  url_Paper  = {https://bercher.net/publications/2024/Lin2024HTNModelFixing.pdf}\n}\n\n
\n
\n\n\n
\n The complexity of modeling planning domains is a major obstacle for making automated planning techniques more accessible, raising the demand of tools for providing modeling assistance. In particular, tools that can automatically correct errors in a planning domain are of great importance. Previous works have devoted efforts to developing such approaches for correcting classical (non-hierarchical) domains. However, no approaches exist for hierarchical planning, which is what we offer here. More specifically, our approach takes as input a flawed hierarchical domain together with a plan known to be a solution but actually contradicting the domain (due to errors in the domain) and outputs corrections to the domain that add \\emphmissing actions to the domain and make the plan a solution. The approach achieves this by compiling the problem of finding corrections as another hierarchical planning problem.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n NaRuto: Automatically Acquiring Planning Models from Narrative Texts.\n \n \n \n\n\n \n Ruiqi Li; Leyang Cui; Songtuan Lin; and Patrik Haslum.\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 \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{Li2024DomainLearning,\n  author    = {Ruiqi Li and Leyang Cui and Songtuan Lin and Patrik Haslum},\n  booktitle = {Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024)},\n  title     = {NaRuto: Automatically Acquiring Planning Models from Narrative Texts},\n  year      = {2024},\n  publisher = {AAAI Press},\n  abstract  = {Domain model acquisition has been identified as a bottleneck in the application of planning technology, especially within narrative planning. Learning action models from narrative texts in an automated way is essential to overcome this barrier, but challenging because of the inherent complexities of such texts. We present an evaluation of planning domain models derived from narrative texts using our fully automated, unsupervised system, NaRuto. Our system combines structured event extraction, predictions of commonsense event relations, and textual contradictions and similarities. Evaluation results show that NaRuto generates domain models of significantly better quality than existing fully automated methods, and even sometimes on par with those created by semi-automated methods, with human assistance.}\n}\n\n
\n
\n\n\n
\n Domain model acquisition has been identified as a bottleneck in the application of planning technology, especially within narrative planning. Learning action models from narrative texts in an automated way is essential to overcome this barrier, but challenging because of the inherent complexities of such texts. We present an evaluation of planning domain models derived from narrative texts using our fully automated, unsupervised system, NaRuto. Our system combines structured event extraction, predictions of commonsense event relations, and textual contradictions and similarities. Evaluation results show that NaRuto generates domain models of significantly better quality than existing fully automated methods, and even sometimes on par with those created by semi-automated methods, with human assistance.\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 25 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
\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 (10)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Automated Action Model Acquisition from Narrative Texts.\n \n \n \n \n\n\n \n Ruiqi Li; Leyang Cui; Songtuan Lin; and Patrik Haslum.\n\n\n \n\n\n\n CoRR, abs/2307.10247. 2023.\n \n\n\n\n
\n\n\n\n \n \n \"AutomatedPaper\n  \n \n \n \"Automated 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 3 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@article{Li2023DomainLearning,\n  author       = {Ruiqi Li and Leyang Cui and Songtuan Lin and Patrik Haslum},\n  title        = {Automated Action Model Acquisition from Narrative Texts},\n  journal      = {CoRR},\n  volume       = {abs/2307.10247},\n  year         = {2023},\n  url          = {https://arxiv.org/abs/2307.10247},\n  doi          = {10.48550/ARXIV.2307.10247},\n  url_Paper    = {https://arxiv.org/pdf/2307.10247.pdf},\n  abstract     = {Action models, which take the form of precondition/effect axioms, facilitate causal and motivational connections between actions for AI agents. Action model acquisition has been identified as a bottleneck in the application of planning technology, especially within narrative planning. Acquiring action models from narrative texts in an automated way is essential, but challenging because of the inherent complexities of such texts. We present NaRuto, a system that extracts structured events from narrative text and subsequently generates planning-language-style action models based on predictions of commonsense event relations, as well as textual contradictions and similarities, in an unsupervised manner. Experimental results in classical narrative planning domains show that NaRuto can generate action models of significantly better quality than existing fully automated methods, and even on par with those of semi-automated methods.}\n} \n\n
\n
\n\n\n
\n Action models, which take the form of precondition/effect axioms, facilitate causal and motivational connections between actions for AI agents. Action model acquisition has been identified as a bottleneck in the application of planning technology, especially within narrative planning. Acquiring action models from narrative texts in an automated way is essential, but challenging because of the inherent complexities of such texts. We present NaRuto, a system that extracts structured events from narrative text and subsequently generates planning-language-style action models based on predictions of commonsense event relations, as well as textual contradictions and similarities, in an unsupervised manner. Experimental results in classical narrative planning domains show that NaRuto can generate action models of significantly better quality than existing fully automated methods, and even on par with those of semi-automated methods.\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 Experimental Results for the AAAI 2023 Paper ``On Total-Order HTN Plan Verification with Method Preconditions – An Extension of the CYK Parsing Algorithm''.\n \n \n \n\n\n \n Songtuan Lin; Gregor Behnke; Simona Ondrčková; Roman Barták; 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{Lin2023ExperimentalResultsTOVerification,\n  author       = {Songtuan Lin and Gregor Behnke and Simona Ondr\\v{c}kov{\\'{a}} and Roman Bart{\\'{a}}k and Pascal Bercher},\n  title        = {Experimental Results for the AAAI 2023 Paper ``On Total-Order HTN Plan Verification with Method Preconditions -- An Extension of the CYK Parsing Algorithm''},\n  year         = {2023},\n  copyright    = {Creative Commons Attribution 4.0 International},\n  doi          = {10.5281/zenodo.7704558},\n  publisher    = {Zenodo},\n}\n\n
\n
\n\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Accelerating SAT-Based HTN Plan Verification by Exploiting Data Structures from HTN Planning.\n \n \n \n \n\n\n \n Songtuan Lin; Gregor Behnke; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 26th European Conference on Artificial Intelligence (ECAI 2023), pages 1489–1496, 2023. IOS Press\n \n\n\n\n
\n\n\n\n \n \n \"Accelerating paper\n  \n \n \n \"Accelerating poster\n  \n \n \n \"Accelerating slides\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 6 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Lin2023ImprovedHTNVerifyViaSAT,\n  author     = {Songtuan Lin and Gregor Behnke and Pascal Bercher},\n  title      = {Accelerating SAT-Based HTN Plan Verification by Exploiting Data Structures from HTN Planning},\n  booktitle  = {Proceedings of the 26th European Conference on Artificial Intelligence (ECAI 2023)},\n  year       = {2023},\n  publisher  = {IOS Press},\n  pages      = {1489--1496},\n  abstract   = {Plan verification is the task of deciding whether a given plan is a solution to a planning problem. In this paper, we study the plan verification problem in the context of Hierarchical Task Network (HTN) planning, which has been proved to be NP-complete when partial order (PO) is involved. We will develop a novel SAT-based approach exploiting the data structures solution order graphs and path decomposition trees which encodes an HTN plan verification problem as a SAT one. We show in our experiments that this new approach outperforms the current state-of-the-art (SOTA) planning-based approach for verifying plans for POHTN problems.},\n  doi        = {10.3233/FAIA230428},\n  url_Paper  = {https://bercher.net/publications/2023/Lin2023ImprovedHTNVerifyViaSAT.pdf},\n  url_Poster = {https://bercher.net/publications/2023/Lin2023ImprovedHTNVerifyViaSATPoster.pdf},\n  url_Slides = {https://bercher.net/publications/2023/Lin2023ImprovedHTNVerifyViaSATSlides.pdf}\n}\n\n
\n
\n\n\n
\n Plan verification is the task of deciding whether a given plan is a solution to a planning problem. In this paper, we study the plan verification problem in the context of Hierarchical Task Network (HTN) planning, which has been proved to be NP-complete when partial order (PO) is involved. We will develop a novel SAT-based approach exploiting the data structures solution order graphs and path decomposition trees which encodes an HTN plan verification problem as a SAT one. We show in our experiments that this new approach outperforms the current state-of-the-art (SOTA) planning-based approach for verifying plans for POHTN problems.\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 16 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 Experimental Results for the AAAI 2023 Paper ``Towards Automated Modeling Assistance: An Efficient Approach for Repairing Flawed Planning Domains''.\n \n \n \n\n\n \n Songtuan Lin; Alban Grastien; 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{Lin2023RepairingClassicalModelsExperimentalResults,\n  author       = {Songtuan Lin and Alban Grastien and Pascal Bercher},\n  title        = {Experimental Results for the AAAI 2023 Paper ``Towards Automated Modeling Assistance: An Efficient Approach for Repairing Flawed Planning Domains''},\n  year         = {2023},\n  copyright    = {Creative Commons Attribution 4.0 International},\n  doi          = {10.5281/zenodo.7690016},\n  publisher    = {Zenodo}\n} \n\n
\n
\n\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Was Fixing this Really That Hard? On the Complexity of Correcting HTN Domains.\n \n \n \n \n\n\n \n Songtuan Lin; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023), pages 12032–12040, 2023. AAAI Press\n \n\n\n\n
\n\n\n\n \n \n \"Was paper\n  \n \n \n \"Was slides\n  \n \n \n \"Was 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 27 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Lin2023RepairingHTNModelsComplexity,\n  author     = {Songtuan Lin and Pascal Bercher},\n  booktitle  = {Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023)},\n  title      = {Was Fixing this Really That Hard? On the Complexity of Correcting HTN Domains},\n  year       = {2023},\n  pages      = {12032--12040},\n  publisher  = {AAAI Press},\n  abstract   = {Automated modeling assistance is indispensable to the AI planning being deployed in practice, notably in industry and other non-academic contexts. Yet, little progress has been made that goes beyond smart interfaces like programming environments. They focus on autocompletion, but lack intelligent support for guiding the modeler. As a theoretical foundation of a first step towards this direction, we study the computational complexity of correcting a flawed Hierarchical Task Network (HTN) planning domain. Specifically, a modeler provides a (white) list of plans that are supposed to be solutions, and likewise a (black) list of plans that shall not be solutions. We investigate the complexity of finding a set of (optimal or suboptimal) model corrections so that those plans are (respective not) solutions to the corrected model. More specifically, we factor out each hardness source that contributes towards NP-hardness, including one that we deem important for many other complexity investigations that go beyond our specific context of application. All complexities range between NP and Sigma-2-p, raising the hope for efficient practical tools in the future.},\n  doi        = {10.1609/aaai.v37i10.26419},\n  url_Paper  = {https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexity.pdf},\n  url_Slides = {https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexitySlides.pdf},\n  url_Poster = {https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexityPoster.pdf}\n}\n\n
\n
\n\n\n
\n Automated modeling assistance is indispensable to the AI planning being deployed in practice, notably in industry and other non-academic contexts. Yet, little progress has been made that goes beyond smart interfaces like programming environments. They focus on autocompletion, but lack intelligent support for guiding the modeler. As a theoretical foundation of a first step towards this direction, we study the computational complexity of correcting a flawed Hierarchical Task Network (HTN) planning domain. Specifically, a modeler provides a (white) list of plans that are supposed to be solutions, and likewise a (black) list of plans that shall not be solutions. We investigate the complexity of finding a set of (optimal or suboptimal) model corrections so that those plans are (respective not) solutions to the corrected model. More specifically, we factor out each hardness source that contributes towards NP-hardness, including one that we deem important for many other complexity investigations that go beyond our specific context of application. All complexities range between NP and Sigma-2-p, raising the hope for efficient practical tools in the future.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Towards Automated Modeling Assistance: An Efficient Approach for Repairing Flawed Planning Domains.\n \n \n \n \n\n\n \n Songtuan Lin; Alban Grastien; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023), pages 12022–12031, 2023. AAAI Press\n \n\n\n\n
\n\n\n\n \n \n \"Towards paper\n  \n \n \n \"Towards slides\n  \n \n \n \"Towards 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 45 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Lin2023RepairingClassicalModels,\n  author     = {Songtuan Lin and Alban Grastien and Pascal Bercher},\n  booktitle  = {Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023)},\n  title      = {Towards Automated Modeling Assistance: An Efficient Approach for Repairing Flawed Planning Domains},\n  year       = {2023},\n  pages      = {12022--12031},\n  publisher  = {AAAI Press},\n  abstract   = {Designing a planning domain is a difficult task in AI planning. Assisting tools are thus required if we want planning to be used more broadly. In this paper, we are interested in automatically correcting a flawed domain. In particular, we are concerned with the scenario where a domain contradicts a plan that is known to be valid. Our goal is to repair the domain so as to turn the plan into a solution. Specifically, we consider both grounded and lifted representations support for negative preconditions and show how to explore the space of repairs to find the optimal one efficiently. As an evidence of the efficiency of our approach, the experiment results show that all flawed domains except one in the benchmark set can be repaired optimally by our approach within one second.},\n  doi        = {10.1609/aaai.v37i10.26418},\n  url_Paper  = {https://bercher.net/publications/2023/Lin2023RepairingClassicalModels.pdf},\n  url_Slides = {https://bercher.net/publications/2023/Lin2023RepairingClassicalModelsSlides.pdf},\n  url_Poster = {https://bercher.net/publications/2023/Lin2023RepairingClassicalModelsPoster.pdf}\n}\n\n
\n
\n\n\n
\n Designing a planning domain is a difficult task in AI planning. Assisting tools are thus required if we want planning to be used more broadly. In this paper, we are interested in automatically correcting a flawed domain. In particular, we are concerned with the scenario where a domain contradicts a plan that is known to be valid. Our goal is to repair the domain so as to turn the plan into a solution. Specifically, we consider both grounded and lifted representations support for negative preconditions and show how to explore the space of repairs to find the optimal one efficiently. As an evidence of the efficiency of our approach, the experiment results show that all flawed domains except one in the benchmark set can be repaired optimally by our approach within one second.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n On Total-Order HTN Plan Verification with Method Preconditions – An Extension of the CYK Parsing Algorithm.\n \n \n \n \n\n\n \n Songtuan Lin; Gregor Behnke; Simona Ondrčková; Roman Barták; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023), pages 12041–12048, 2023. AAAI Press\n \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 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 25 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Lin2023TOVerification,\n  author     = {Songtuan Lin and Gregor Behnke and Simona Ondr\\v{c}kov{\\'{a}} and Roman Bart{\\'{a}}k and Pascal Bercher},\n  booktitle  = {Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023)},\n  title      = {On Total-Order HTN Plan Verification with Method Preconditions -- An Extension of the CYK Parsing Algorithm},\n  year       = {2023},\n  pages      = {12041--12048},\n  publisher  = {AAAI Press},\n  abstract   = {In this paper, we consider the plan verification problem for totally ordered (TO) HTN planning. The problem is proved to be solvable in polynomial time by recognizing its connection to the membership decision problem for context-free grammars. Currently, most HTN plan verification approaches do not have special treatments for the TO configuration, and the only one features such an optimization still relies on an exhaustive search. Hence, we will develop a new TOHTN plan verification approach in this paper by extending the standard CYK parsing algorithm which acts as the best decision procedure in general.},\n  doi        = {10.1609/aaai.v37i10.26420},\n  url_Paper  = {https://bercher.net/publications/2023/Lin2023TOVerification.pdf},\n  url_Slides = {https://bercher.net/publications/2023/Lin2023TOVerificationSlides.pdf},\n  url_Poster = {https://bercher.net/publications/2023/Lin2023TOVerificationPoster.pdf}\n}\n\n
\n
\n\n\n
\n In this paper, we consider the plan verification problem for totally ordered (TO) HTN planning. The problem is proved to be solvable in polynomial time by recognizing its connection to the membership decision problem for context-free grammars. Currently, most HTN plan verification approaches do not have special treatments for the TO configuration, and the only one features such an optimization still relies on an exhaustive search. Hence, we will develop a new TOHTN plan verification approach in this paper by extending the standard CYK parsing algorithm which acts as the best decision procedure in general.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Comparing the Expressivity of STRIPS Planning with Finite-LTL vs. LTL.\n \n \n \n \n\n\n \n Songtuan Lin.\n\n\n \n\n\n\n In Proceedings of the 31st AAAI Spring Symposium Series (SSS 2023), 2023. \n \n\n\n\n
\n\n\n\n \n \n \"Comparing paper\n  \n \n \n \"Comparing slides\n  \n \n \n \"Comparing webpage\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 2 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Lin2023FLTLvsLTL,\n  author      = {Songtuan Lin},\n  booktitle   = {Proceedings of the 31st AAAI Spring Symposium Series (SSS 2023)},\n  title       = {Comparing the Expressivity of {STRIPS} Planning with Finite-{LTL} vs. {LTL}},\n  year        = {2023},\n  abstract    = {STRIPS is one of the most widely used planning frameworks for modeling planning problems in Automated Planning. A significant extension to STRIPS is allowing it to specify temporal constraints over the execution of a plan. One way to do so is to fuse the STRIPS framework with finite-LTL (f-LTL) or LTL. In this paper, I will discuss some results from our previous work about the expressivity of such combinations. Specifically, the expressivity is measured in terms of the class of formal languages that can be expressed by the framework.},\n  url_Paper   = {https://bercher.net/publications/2023/Lin2023FLTLvsLTL.pdf},\n  url_Slides  = {https://ltlf-symposium.github.io/assets/slides/SongtuanLin.pdf},\n  url_webpage = {https://ltlf-symposium.github.io/}\n}\n\n
\n
\n\n\n
\n STRIPS is one of the most widely used planning frameworks for modeling planning problems in Automated Planning. A significant extension to STRIPS is allowing it to specify temporal constraints over the execution of a plan. One way to do so is to fuse the STRIPS framework with finite-LTL (f-LTL) or LTL. In this paper, I will discuss some results from our previous work about the expressivity of such combinations. Specifically, the expressivity is measured in terms of the class of formal languages that can be expressed by the framework.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2022\n \n \n (7)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Finding Solution Preserving Linearizations For Partially Ordered Hierarchical Planning Problems.\n \n \n \n \n\n\n \n Ying Xian Wu; Songtuan Lin; Gregor Behnke; and Pascal Bercher.\n\n\n \n\n\n\n In 33rd PuK Workshop ``Planen, Scheduling und Konfigurieren, Entwerfen'' (PuK 2022), 2022. \n \n\n\n\n
\n\n\n\n \n \n \"Finding paper\n  \n \n \n \"Finding slides\n  \n \n \n \"Finding workshop\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 22 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Wu2022HTNLinearization,\n  author       = {Ying Xian Wu and Songtuan Lin and Gregor Behnke and Pascal Bercher},\n  booktitle    = {33rd {PuK} Workshop ``Planen, Scheduling und Konfigurieren, Entwerfen'' ({PuK} 2022)},\n  title        = {Finding Solution Preserving Linearizations For Partially Ordered Hierarchical Planning Problems},\n  year         = {2022},\n  abstract     = {Solving partially ordered hierarchical planning problems is more computationally expensive compared to solving totally ordered ones. Therefore, automatically transforming partially ordered problem domains into totally ordered ones, such that the totally ordered problem still retains at least one solution, would be a desired capability as it would reduce complexity and thus make it easier for planning systems to solve the problem. This is a complex endeavour, because even creating all possible linearizations of all methods in the original domain does not guarantee that solutions are preserved. It also allows the planner to use algorithms and heuristics specialised for the totally ordered case to solve the transformed problem. In this paper, we propose an algorithm for converting partially ordered problems into totally ordered ones and give criterion for when this is possible. We test our techniques on the partially-ordered track of the bench-mark set of the IPC 2020 and solve both the linearized and the original partially-ordered problems using state-of-the-art planning systems. We find that in the majority of problems across a variety of domains, the linearized problem remains solvable, and can always be solved faster than the without our proposed pre-processing technique.},\n  url_Paper    = {https://bercher.net/publications/2022/Wu2022HTNLinearization.pdf},\n  url_Slides   = {https://bercher.net/publications/2022/Wu2022HTNLinearizationSlides.pdf},\n  url_Workshop = {http://www.member.uni-oldenburg.de/juergen.sauer/PuK/PuK2022/index.html}\n}\n\n
\n
\n\n\n
\n Solving partially ordered hierarchical planning problems is more computationally expensive compared to solving totally ordered ones. Therefore, automatically transforming partially ordered problem domains into totally ordered ones, such that the totally ordered problem still retains at least one solution, would be a desired capability as it would reduce complexity and thus make it easier for planning systems to solve the problem. This is a complex endeavour, because even creating all possible linearizations of all methods in the original domain does not guarantee that solutions are preserved. It also allows the planner to use algorithms and heuristics specialised for the totally ordered case to solve the transformed problem. In this paper, we propose an algorithm for converting partially ordered problems into totally ordered ones and give criterion for when this is possible. We test our techniques on the partially-ordered track of the bench-mark set of the IPC 2020 and solve both the linearized and the original partially-ordered problems using state-of-the-art planning systems. We find that in the majority of problems across a variety of domains, the linearized problem remains solvable, and can always be solved faster than the without our proposed pre-processing technique.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Planning Domain Repair as a Diagnosis Problem.\n \n \n \n \n\n\n \n Songtuan Lin; Alban Grastien; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 33rd International Workshop on Principles of Diagnosis (DX 2022), 2022. \n \n\n\n\n
\n\n\n\n \n \n \"Planning paper\n  \n \n \n \"Planning 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 10 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Lin2022RepairAsDiagnosis,\n  author     = {Songtuan Lin and Alban Grastien and Pascal Bercher},\n  booktitle  = {Proceedings of the 33rd International Workshop on Principles of Diagnosis (DX 2022)},\n  title      = {Planning Domain Repair as a Diagnosis Problem},\n  year       = {2022},\n  abstract   = {Techniques for diagnosis have been used in many applications. We explore the connection between diagnosis and AI planning in this paper and apply the diagnosis algorithm to repair a flawed planning domain. In particular, the scenario we are concerned with is that we are given a plan which is supposed to be a solution to a planning problem, but it is actually not due to some flaws in the planning domain, and we want to repair the domain to turn the plan into a solution. For this, we will first frame this problem as a diagnosis problem and then solve it via using diagnosis algorithms.},\n  url_Paper  = {https://bercher.net/publications/2022/Lin2022RepairAsDiagnosis.pdf},\n  url_Slides = {https://bercher.net/publications/2022/Lin2022RepairAsDiagnosisSlides.pdf},\n}\n\n
\n
\n\n\n
\n Techniques for diagnosis have been used in many applications. We explore the connection between diagnosis and AI planning in this paper and apply the diagnosis algorithm to repair a flawed planning domain. In particular, the scenario we are concerned with is that we are given a plan which is supposed to be a solution to a planning problem, but it is actually not due to some flaws in the planning domain, and we want to repair the domain to turn the plan into a solution. For this, we will first frame this problem as a diagnosis problem and then solve it via using diagnosis algorithms.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Modeling Assistance for AI Planning From the Perspective of Model Reconciliation.\n \n \n \n \n\n\n \n Songtuan Lin.\n\n\n \n\n\n\n In Proceedings of the 20th ICAPS Doctoral Consortium (ICAPS DC 2022), pages 36–40, 2022. \n \n\n\n\n
\n\n\n\n \n \n \"Modeling paper\n  \n \n \n \"Modeling 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 11 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Lin2022ICAPS-DC,\n  author           = {Songtuan Lin},\n  title            = {Modeling Assistance for AI Planning From the Perspective of Model Reconciliation},\n  booktitle        = {Proceedings of the 20th ICAPS Doctoral Consortium (ICAPS DC 2022)},\n  year             = {2022},\n  pages            = {36--40},\n  abstract         = {Providing modeling assistance to domain modelers is a prominent challenge in incorporating humans into planning processes. Many efforts have been devoted to this direction in classical planning, however, only few works have been done in hierarchical planning. In this thesis, we will study a methodology for providing modeling assistance in HTN planning, which is the most commonly used hierarchical planning framework. Particularly, we will address two bottleneck problems for this purpose, namely domain model validation and domain model refinements. For the former one, we propose an approach based on plan verification, and for the latter, we view it as a model reconciliation problem and will study a novel approach for solving it.},\n  url_paper        = {https://icaps22.icaps-conference.org/dc/ICAPS_2022_paper_359.pdf},\n  url_presentation = {https://www.youtube.com/watch?v=MUYl845Dy4I&list=PLj-ZdQ5rfSEqD1SztBXJppdjIE9CQQfzV}\n}\n\n\n
\n
\n\n\n
\n Providing modeling assistance to domain modelers is a prominent challenge in incorporating humans into planning processes. Many efforts have been devoted to this direction in classical planning, however, only few works have been done in hierarchical planning. In this thesis, we will study a methodology for providing modeling assistance in HTN planning, which is the most commonly used hierarchical planning framework. Particularly, we will address two bottleneck problems for this purpose, namely domain model validation and domain model refinements. For the former one, we propose an approach based on plan verification, and for the latter, we view it as a model reconciliation problem and will study a novel approach for solving it.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Exploiting Solution Order Graphs and Path Decomposition Trees for More Efficient HTN Plan Verification via SAT Solving.\n \n \n \n \n\n\n \n Songtuan Lin; Gregor Behnke; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 5th ICAPS Workshop on Hierarchical Planning (HPlan 2022), pages 24–28, 2022. \n \n\n\n\n
\n\n\n\n \n \n \"Exploiting paper\n  \n \n \n \"Exploiting poster\n  \n \n \n \"Exploiting 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 17 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Lin2022SATviaSOGs,\n  author           = {Songtuan Lin and Gregor Behnke and Pascal Bercher},\n  booktitle        = {Proceedings of the 5th ICAPS Workshop on Hierarchical Planning (HPlan 2022)},\n  title            = {Exploiting Solution Order Graphs and Path Decomposition Trees for More Efficient HTN Plan Verification via SAT Solving},\n  year             = {2022},\n  pages            = {24--28},\n  abstract         = {The research on the plan verification problem has drawn increasing attention in the last few years. It can serve as an approach for validating a planning domain by viewing an input plan as a test case which is supposed to be a solution to a planning problem in the domain which is to be validated. In this paper, we study the plan verification problem in the context of Hierarchical Task Network (HTN) planning. Concretely, we will develop an SAT-based approach via exploiting the data structures solution order graphs and path decomposition trees employed by the state-of-the-art SAT-based HTN planner which transforms an HTN plan verification problem into an SAT formula. Additionally, for the purpose of completeness, we will also reimplement the old SAT-based plan verifier within an outdated planning system called PANDA-3 and integrate it into the new version called PANDA-pi.},\n  url_Paper        = {https://bercher.net/publications/2022/Lin2022SATbasedVerification.pdf},\n  url_Poster       = {https://bercher.net/publications/2022/Lin2022SATbasedVerificationPoster.pdf},\n  url_presentation = {https://youtu.be/DbDTuY7dOxM}\n}\n\n
\n
\n\n\n
\n The research on the plan verification problem has drawn increasing attention in the last few years. It can serve as an approach for validating a planning domain by viewing an input plan as a test case which is supposed to be a solution to a planning problem in the domain which is to be validated. In this paper, we study the plan verification problem in the context of Hierarchical Task Network (HTN) planning. Concretely, we will develop an SAT-based approach via exploiting the data structures solution order graphs and path decomposition trees employed by the state-of-the-art SAT-based HTN planner which transforms an HTN plan verification problem into an SAT formula. Additionally, for the purpose of completeness, we will also reimplement the old SAT-based plan verifier within an outdated planning system called PANDA-3 and integrate it into the new version called PANDA-pi.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n On Total-Order HTN Plan Verification with Method Preconditions – An Extension of the CYK Parsing Algorithm.\n \n \n \n \n\n\n \n Songtuan Lin; Gregor Behnke; Simona Ondrčková; Roman Barták; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 5th ICAPS Workshop on Hierarchical Planning (HPlan 2022), pages 52–58, 2022. \n \n\n\n\n
\n\n\n\n \n \n \"On paper\n  \n \n \n \"On poster\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 19 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Lin2022CYKParsing,\n  author           = {Songtuan Lin and Gregor Behnke and Simona Ondrčková and Roman Barták and Pascal Bercher},\n  booktitle        = {Proceedings of the 5th ICAPS Workshop on Hierarchical Planning (HPlan 2022)},\n  title            = {On Total-Order HTN Plan Verification with Method Preconditions -- An Extension of the CYK Parsing Algorithm},\n  year             = {2022},\n  pages            = {52--58},\n  abstract         = {In this paper, we consider the plan verification problem for totally ordered (TO) HTN planning. The problem is proved to be solvable in polynomial time by recognizing its connection to the membership decision problem for context-free grammars. The current state-of-the-art TO plan verifier solves the problem by a blind search approach in order to deal with some state constraints and henceforth results in several overheads. However, many existing TOHTN planning benchmarks do not have these constraints. Hence, we ignore them in the paper and develop a TOHTN plan verification approach which avoids those overheads in the state-of-the-art TO verifier via extending the CYK algorithm.},\n  url_Paper        = {https://bercher.net/publications/2022/Lin2022HTNCYKParsing.pdf},\n  url_Poster       = {https://bercher.net/publications/2022/Lin2022HTNCYKParsingPoster.pdf},\n  url_presentation = {https://youtu.be/AJqmbG9Bs2M}\n}\n\n
\n
\n\n\n
\n In this paper, we consider the plan verification problem for totally ordered (TO) HTN planning. The problem is proved to be solvable in polynomial time by recognizing its connection to the membership decision problem for context-free grammars. The current state-of-the-art TO plan verifier solves the problem by a blind search approach in order to deal with some state constraints and henceforth results in several overheads. However, many existing TOHTN planning benchmarks do not have these constraints. Hence, we ignore them in the paper and develop a TOHTN plan verification approach which avoids those overheads in the state-of-the-art TO verifier via extending the CYK algorithm.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Tight Bounds for Hybrid Planning.\n \n \n \n \n\n\n \n Pascal Bercher; Songtuan Lin; and Ron Alford.\n\n\n \n\n\n\n In Proceedings of the 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence (IJCAI-ECAI 2022), pages 4597–4605, 2022. IJCAI\n \n\n\n\n
\n\n\n\n \n \n \"Tight video of presentation\n  \n \n \n \"Tight paper\n  \n \n \n \"Tight slides\n  \n \n \n \"Tight 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 15 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Bercher2022TightHybridBounds,\n  author     = {Pascal Bercher and Songtuan Lin and Ron Alford},\n  booktitle  = {Proceedings of the 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence (IJCAI-ECAI 2022)},\n  title      = {Tight Bounds for Hybrid Planning},\n  year       = {2022},\n  pages      = {4597--4605},\n  publisher  = {IJCAI},\n  abstract   = {Several hierarchical planning systems feature a rich level of language features making them capable of expressing real-work problems. One such feature that's used by several current planning systems is causal links, which are used to track search progress. The formalism combining Hierarchical Task Network (HTN) planning with these links known from Partial Order Causal Link (POCL) planning is often referred to as hybrid planning. In this paper we study the computational complexity of such hybrid planning problems. More specifically, we provide missing membership results to existing hardness proofs and thereby provide tight complexity bounds for all known subclasses of hierarchical planning problems. We also re-visit and correct a result from the literature for plan verification showing that it remains NP-complete even in the absence of a task hierarchy.},\n  doi        = {10.24963/ijcai.2022/638},\n  url_video_of_presentation = {https://www.ijcai.org/proceedings/2022/video/638},\n  url_Paper  = {https://bercher.net/publications/2022/Bercher2022TightHybridBounds.pdf},\n  url_Slides = {https://bercher.net/publications/2022/Bercher2022TightHybridBoundsSlides.pdf},\n  url_Poster = {https://bercher.net/publications/2022/Bercher2022TightHybridBoundsPoster.pdf}\n}\n\n
\n
\n\n\n
\n Several hierarchical planning systems feature a rich level of language features making them capable of expressing real-work problems. One such feature that's used by several current planning systems is causal links, which are used to track search progress. The formalism combining Hierarchical Task Network (HTN) planning with these links known from Partial Order Causal Link (POCL) planning is often referred to as hybrid planning. In this paper we study the computational complexity of such hybrid planning problems. More specifically, we provide missing membership results to existing hardness proofs and thereby provide tight complexity bounds for all known subclasses of hierarchical planning problems. We also re-visit and correct a result from the literature for plan verification showing that it remains NP-complete even in the absence of a task hierarchy.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n On the Expressive Power of Planning Formalisms in Conjunction with LTL.\n \n \n \n \n\n\n \n Songtuan Lin; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 32nd International Conference on Automated Planning and Scheduling (ICAPS 2022), pages 231–240, 2022. AAAI Press\n \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 \"On 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 18 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Lin2022LTLExpressivity,\n  author    = {Songtuan Lin and Pascal Bercher},\n  booktitle = {Proceedings of the 32nd International Conference on Automated Planning and Scheduling (ICAPS 2022)},\n  title     = {On the Expressive Power of Planning Formalisms in Conjunction with LTL},\n  year      = {2022},\n  pages     = {231--240},\n  publisher = {AAAI Press},\n  abstract  = {Linear Temporal Logic (LTL) has been widely employed in various planning formalisms, e.g., in the STRIPS formalism, in order to specify constraints over state trajectories in a planning problem. In this paper, we investigate the expressive power of two planning formalisms in conjunction with LTL that are most commonly seen in non-hierarchical planning and hierarchical planning respectively, namely the STRIPS formalism and the Hierarchical Task Network (HTN) formalism. We do so by interpreting the set of all solutions to a planning problem as a formal language and comparing it with other formal ones, e.g., star-free languages. Our results provide an in-depth insight into the theoretical properties of the investigated planning formalisms and henceforth explore the common structure shared by solutions to planning problems in certain planning formalisms.},\n  doi        = {10.1609/icaps.v32i1.19806},\n  url_Paper  = {https://bercher.net/publications/2022/Lin2022LTLExpressivity.pdf},\n  url_Slides = {https://bercher.net/publications/2022/Lin2022LTLExpressivitySlides.pdf},\n  url_Poster = {https://bercher.net/publications/2022/Lin2022LTLExpressivityPoster.pdf},\n  url_video_of_presentation = {http://icaps22.icaps-conference.org/papers/49/index.html}\n}\n\n
\n
\n\n\n
\n Linear Temporal Logic (LTL) has been widely employed in various planning formalisms, e.g., in the STRIPS formalism, in order to specify constraints over state trajectories in a planning problem. In this paper, we investigate the expressive power of two planning formalisms in conjunction with LTL that are most commonly seen in non-hierarchical planning and hierarchical planning respectively, namely the STRIPS formalism and the Hierarchical Task Network (HTN) formalism. We do so by interpreting the set of all solutions to a planning problem as a formal language and comparing it with other formal ones, e.g., star-free languages. Our results provide an in-depth insight into the theoretical properties of the investigated planning formalisms and henceforth explore the common structure shared by solutions to planning problems in certain planning formalisms.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2021\n \n \n (3)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Change the World – How Hard Can that Be? On the Computational Complexity of Fixing Planning Models.\n \n \n \n \n\n\n \n Songtuan Lin; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), pages 4152–4159, 2021. IJCAI\n \n\n\n\n
\n\n\n\n \n \n \"Change paper\n  \n \n \n \"Change slides\n  \n \n \n \"Change slides-4on1\n  \n \n \n \"Change 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 32 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Lin2021FixHTNModel,\n  author     = {Songtuan Lin and Pascal Bercher},\n  title      = {Change the World -- How Hard Can that Be? On the Computational Complexity of Fixing Planning Models},\n  booktitle  = {Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021)},\n  year       = {2021},\n  publisher  = {IJCAI},\n  abstract   = {Incorporating humans into AI planning is an important feature of flexible planning technology. Such human integration allows to incorporate previously unknown constraints, and is also an integral part of automated modeling assistance. As a foundation for integrating user requests, we study the computational complexity of determining the existence of changes to an existing model, such that the resulting model allows for specific user-provided solutions. We are provided with a planning problem modeled either in the classical (non-hierarchical) or hierarchical task network (HTN) planning formalism, as well as with a supposed-to-be solution plan, which is actually not a solution for the current model. Considering changing decomposition methods as well as preconditions and effects of actions, we show that most change requests are NP-complete though some turn out to be tractable.},\n  pages      = {4152--4159},\n  doi        = {10.24963/ijcai.2021/571},\n  url_Paper  = {https://bercher.net/publications//2021/Lin2021ChangeTheWorld.pdf},\n  url_Slides = {https://bercher.net/publications//2021/Lin2021ChangeTheWorldSlides.pdf},\n  url_Slides-4on1 = {https://bercher.net/publications//2021/Lin2021ChangeTheWorldSlides4on1.pdf},\n  url_Poster = {https://bercher.net/publications//2021/Lin2021ChangeTheWorldPoster.pdf}\n}\n\n\n
\n
\n\n\n
\n Incorporating humans into AI planning is an important feature of flexible planning technology. Such human integration allows to incorporate previously unknown constraints, and is also an integral part of automated modeling assistance. As a foundation for integrating user requests, we study the computational complexity of determining the existence of changes to an existing model, such that the resulting model allows for specific user-provided solutions. We are provided with a planning problem modeled either in the classical (non-hierarchical) or hierarchical task network (HTN) planning formalism, as well as with a supposed-to-be solution plan, which is actually not a solution for the current model. Considering changing decomposition methods as well as preconditions and effects of actions, we show that most change requests are NP-complete though some turn out to be tractable.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n On the Computational Complexity of Correcting HTN Domain Models.\n \n \n \n \n\n\n \n Songtuan Lin; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of the 4th ICAPS Workshop on Hierarchical Planning (HPlan 2021), pages 35–43, 2021. \n \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 10 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{Lin2021CorrectingHTNModels,\n  author    = {Songtuan Lin and Pascal Bercher},\n  title     = {On the Computational Complexity of Correcting HTN Domain Models},\n  booktitle = {Proceedings of the 4th ICAPS Workshop on Hierarchical Planning (HPlan 2021)},\n  year      = {2021},\n  pages     = {35--43},\n  abstract  = {Incorporating user requests into planning processes is a key concept in developing flexible planning technologies. Such systems may be required to change its planning model to adapt to certain user requests. In this paper, we assume a user provides a non-solution plan to a system and asks it to change the planning model so that the plan becomes a solution. We study the computational complexity of deciding whether such changes exist in the context of Hierarchical Task Network (HTN) planning. We prove that the problem is NP-complete in general independent of what or how many changes are allowed. We also identify several conditions which make the problem tractable when they are satisfied.},\n  url_Paper = {https://bercher.net/publications//2021/Lin2021HTNChangeComplexity.pdf},\n  url_Slides = {https://bercher.net/publications//2021/Lin2021HTNChangeComplexitySlides.pdf},\n  url_Poster = {https://bercher.net/publications//2021/Lin2021HTNChangeComplexityPoster.pdf}\n}\n\n\n
\n
\n\n\n
\n Incorporating user requests into planning processes is a key concept in developing flexible planning technologies. Such systems may be required to change its planning model to adapt to certain user requests. In this paper, we assume a user provides a non-solution plan to a system and asks it to change the planning model so that the plan becomes a solution. We study the computational complexity of deciding whether such changes exist in the context of Hierarchical Task Network (HTN) planning. We prove that the problem is NP-complete in general independent of what or how many changes are allowed. We also identify several conditions which make the problem tractable when they are satisfied.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n From PCP to HTN Planning Through CFGs.\n \n \n \n \n\n\n \n Daniel Höller; Songtuan Lin; Kutluhan Erol; and Pascal Bercher.\n\n\n \n\n\n\n In Proceedings of 10th International Planning Competition: Planner and Domain Abstracts – Hierarchical Task Network (HTN) Planning Track (IPC 2020), pages 24–25, 2021. \n \n\n\n\n
\n\n\n\n \n \n \"From 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 8 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@inproceedings{Hoeller2021PCP,\n  title                    = {From PCP to HTN Planning Through CFGs},\n  author                   = {Daniel H\\"oller and Songtuan Lin and Kutluhan Erol and Pascal Bercher},\n  booktitle                = {Proceedings of 10th {I}nternational {P}lanning {C}ompetition: Planner and Domain Abstracts -- Hierarchical Task Network (HTN) Planning Track (IPC 2020)},\n  year                     = {2021},\n  pages                    = {24--25},\n  abstract                 = {The International Planning Competition in 2020 was the first one for a long time to host tracks on HTN planning. The used benchmark set included a domain describing the undecidable Post Correspondence Problem (PCP). In this paper we describe the two-step process applied to generate HTN problems based on PCP instances. It translates the PCP into a grammar intersection problem of two context-free languages, which is then encoded into an HTN problem.},\n  url_Paper                = {https://bercher.net/publications//2021/Hoeller2021PCP.pdf}\n}\n
\n
\n\n\n
\n The International Planning Competition in 2020 was the first one for a long time to host tracks on HTN planning. The used benchmark set included a domain describing the undecidable Post Correspondence Problem (PCP). In this paper we describe the two-step process applied to generate HTN problems based on PCP instances. It translates the PCP into a grammar intersection problem of two context-free languages, which is then encoded into an HTN problem.\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);