\n \n \n
\n
\n\n \n \n \n \n \n \n Towards Intelligent Companion Systems in General Aviation using Hierarchical Plan and Goal Recognition.\n \n \n \n \n\n\n \n Prakash Jamakatel; Pascal Bercher; Axel Schulte; and Jane Jean Kiam.\n\n\n \n\n\n\n In
Proceedings of the 11th International Conference on Human-Agent Interaction (HAI 2023), pages 229–237, 2023. Association for Computing Machinery\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{Jamakatel2023HTNAviation,\n author = {Prakash Jamakatel and Pascal Bercher and Axel Schulte and Jane Jean Kiam},\n title = {Towards Intelligent Companion Systems in General Aviation using Hierarchical Plan and Goal Recognition},\n booktitle = {Proceedings of the 11th International Conference on Human-Agent Interaction (HAI 2023)},\n year = {2023},\n publisher = {Association for Computing Machinery},\n abstract = {Modern ultralight aircraft in general aviation are equipped with an onboard Pilot Assistance System (PAS) as a companion system, meant to guide the pilot in decision-making, e.g. with plan suggestions, especially in critical situations. For more meaningful guidance, the PAS must possess an accurate and continuous understanding of the context, i.e. the pilot's intention, so that relevant decision-making support is relevant. However, in realistic settings, the pilot's intention is not communicated manually, but can only be proactively monitored by the PAS. This paper explores the possibility of embedding domain expertise using Hierarchical Task Network (HTN) planning to recognise the plan the pilot is currently trying to conduct, by judging from the pilot's actions. Furthermore, by leveraging probability theory for state estimation, since the pilot's actions can only be estimated, we derive belief values to be associated with the recognised plans. Statistical evaluation using data collected from human-in-the-loop tests shows that our intention recognition as plan recognition function is reliable enough to provide the PAS with a contextual understanding. Empirical tests also confirm that our method is efficient enough for real-time implementation.},\n pages = {229--237},\n doi = {10.1145/3623809.3623877},\n url_Paper = {https://bercher.net/publications/2023/Jamakatel2023HTNAviation.pdf}\n}\n\n
\n
\n\n\n
\n Modern ultralight aircraft in general aviation are equipped with an onboard Pilot Assistance System (PAS) as a companion system, meant to guide the pilot in decision-making, e.g. with plan suggestions, especially in critical situations. For more meaningful guidance, the PAS must possess an accurate and continuous understanding of the context, i.e. the pilot's intention, so that relevant decision-making support is relevant. However, in realistic settings, the pilot's intention is not communicated manually, but can only be proactively monitored by the PAS. This paper explores the possibility of embedding domain expertise using Hierarchical Task Network (HTN) planning to recognise the plan the pilot is currently trying to conduct, by judging from the pilot's actions. Furthermore, by leveraging probability theory for state estimation, since the pilot's actions can only be estimated, we derive belief values to be associated with the recognised plans. Statistical evaluation using data collected from human-in-the-loop tests shows that our intention recognition as plan recognition function is reliable enough to provide the PAS with a contextual understanding. Empirical tests also confirm that our method is efficient enough for real-time implementation.\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Detecting AI Planning Modelling Mistakes – Potential Errors and Benchmark Domains.\n \n \n \n \n\n\n \n Kayleigh Sleath; and Pascal Bercher.\n\n\n \n\n\n\n In
Proceedings of the 20th Pacific Rim International Conference on Artificial Intelligence (PRICAI 2023), pages 448–454, 2023. Springer\n
\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n \n slides\n \n \n \n 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 10 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@InProceedings{Sleath2023PossibleModelingErrors,\n author = {Kayleigh Sleath and Pascal Bercher},\n title = {Detecting AI Planning Modelling Mistakes -- Potential Errors and Benchmark Domains},\n booktitle = {Proceedings of the 20th Pacific Rim International Conference on Artificial Intelligence (PRICAI 2023)},\n year = {2023},\n publisher = {Springer},\n pages = {448--454},\n abstract = {AI planning systems can solve complex problems, leaving domain creation as one of the largest obstacles to a large-scale application of this technology. Domain modeling is a tedious, error-prone and manual process. Unfortunately, domain modelling assistance software is sparse and mostly restricted to editors with only surface-level functionality such as syntax highlighting. We address this important gap by proposing a list of potential domain errors which can be detected by problem parsers and modeling tools. We test well-known planning systems and modeling editors on models with those errors and report their results.},\n doi = {10.1007/978-981-99-7022-3_41},\n url_Paper = {https://bercher.net/publications/2023/Sleath2023PossibleModelingErrors.pdf},\n url_Slides = {https://bercher.net/publications/2023/Sleath2023PossibleModelingErrorsSlides.pdf},\n url_video_of_presentation = {https://www.youtube.com/watch?v=5TR7Hf9rlpI}\n}\n\n
\n
\n\n\n
\n AI planning systems can solve complex problems, leaving domain creation as one of the largest obstacles to a large-scale application of this technology. Domain modeling is a tedious, error-prone and manual process. Unfortunately, domain modelling assistance software is sparse and mostly restricted to editors with only surface-level functionality such as syntax highlighting. We address this important gap by proposing a list of potential domain errors which can be detected by problem parsers and modeling tools. We test well-known planning systems and modeling editors on models with those errors and report their results.\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Intractability of Optimal Multi-Agent Pathfinding on Directed Graphs.\n \n \n \n \n\n\n \n Xing Tan; and Pascal Bercher.\n\n\n \n\n\n\n In
Proceedings of the 26th European Conference on Artificial Intelligence (ECAI 2023), pages 2315–2321, 2023. IOS Press\n
\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n \n poster\n \n \n \n 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 10 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@InProceedings{Tan2023AcyclicDiMAPF,\n author = {Xing Tan and Pascal Bercher},\n title = {Intractability of Optimal Multi-Agent Pathfinding on Directed Graphs},\n booktitle = {Proceedings of the 26th European Conference on Artificial Intelligence (ECAI 2023)},\n year = {2023},\n publisher = {IOS Press},\n pages = {2315--2321},\n abstract = {In Multi-Agent Pathfinding (MAPF) problems, multiple agents move simultaneously to reach their individual destinations without colliding with each other. The computational complexity of the problem has been extensively studied for undirected graphs over the past decades. However, plan existence for Directed MAPF (diMAPF) was only recently studied and was shown to be in PSPACE as well as NP-hard. In this paper, we study the optimization versions (on makespan and on travel distance of agents) of diMAPF problems and show that they remain NP-hard even when various important non-trivial restrictions are imposed (e.g., when considering the problem on directed, acyclic, and planar graphs where the vertex-degrees are bounded). We have also provide membership results, thus presenting the first set of NP-completeness results for various optimal diMAPF variants.},\n doi = {10.3233/FAIA230531},\n url_Paper = {https://bercher.net/publications/2023/Tan2023optimalDiMAPFComplexity.pdf},\n url_Poster = {https://bercher.net/publications/2023/Tan2023optimalDiMAPFComplexityPoster.pdf},\n url_Slides = {https://bercher.net/publications/2023/Tan2023optimalDiMAPFComplexitySlides.pdf}\n}\n\n
\n
\n\n\n
\n In Multi-Agent Pathfinding (MAPF) problems, multiple agents move simultaneously to reach their individual destinations without colliding with each other. The computational complexity of the problem has been extensively studied for undirected graphs over the past decades. However, plan existence for Directed MAPF (diMAPF) was only recently studied and was shown to be in PSPACE as well as NP-hard. In this paper, we study the optimization versions (on makespan and on travel distance of agents) of diMAPF problems and show that they remain NP-hard even when various important non-trivial restrictions are imposed (e.g., when considering the problem on directed, acyclic, and planar graphs where the vertex-degrees are bounded). We have also provide membership results, thus presenting the first set of NP-completeness results for various optimal diMAPF variants.\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 paper\n \n \n \n poster\n \n \n \n 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 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 paper\n \n \n \n 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 Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical Plans.\n \n \n \n \n\n\n \n Simona Ondrčková; Roman Barták; Pascal Bercher; and Gregor Behnke.\n\n\n \n\n\n\n In
Proceedings of the 35th International Florida Artificial Intelligence Research Society Conference (FLAIRS 2023), 2023. \n
\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n \n flairs-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
@InProceedings{Ondrckova2023HTNParsing,\n author = {Simona Ondr\\v{c}kov\\'{a} and Roman Bart{\\'a}k and Pascal Bercher and Gregor Behnke},\n booktitle = {Proceedings of the 35th International Florida Artificial Intelligence Research Society Conference ({FLAIRS} 2023)},\n title = {Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical Plans},\n year = {2023},\n abstract = {Verification of hierarchical plans deals with the problem of whether an action sequence is causally consistent and can be obtained by a decomposition of a goal task. This second sub-problem (finding the decomposition) makes the verification problem NP-hard. The task decomposition structure is very close to a parsing tree of context-free grammar (CFG). Recently, the CFG-parsing algorithm by Cocke-Younger-Kasami (CYK) has been modified to verify hierarchical plans efficiently. Despite being fast, the algorithm can only handle totally-ordered planning domains. In this paper, we ask whether the ideas from the CYK algorithm can be extended to a more general parsing-based approach that covers \\emph{all} planning domains, i.e., including partially ordered ones. More specifically, we study the effect of modifying the domain model by limiting the number of sub-tasks in decomposition methods to two and the effect of changing the parsing strategy.},\n url_Paper = {https://bercher.net/publications/2023/Ondrckova2023CYKLessonsLearned.pdf},\n url_FLAIRS-Paper = {https://journals.flvc.org/FLAIRS/article/view/133196},\n doi = {10.32473/flairs.36.133196}\n}\n\n
\n
\n\n\n
\n Verification of hierarchical plans deals with the problem of whether an action sequence is causally consistent and can be obtained by a decomposition of a goal task. This second sub-problem (finding the decomposition) makes the verification problem NP-hard. The task decomposition structure is very close to a parsing tree of context-free grammar (CFG). Recently, the CFG-parsing algorithm by Cocke-Younger-Kasami (CYK) has been modified to verify hierarchical plans efficiently. Despite being fast, the algorithm can only handle totally-ordered planning domains. In this paper, we ask whether the ideas from the CYK algorithm can be extended to a more general parsing-based approach that covers \\emphall planning domains, i.e., including partially ordered ones. More specifically, we study the effect of modifying the domain model by limiting the number of sub-tasks in decomposition methods to two and the effect of changing the parsing strategy.\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 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 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 On the Impact of Grounding on HTN Plan Verification via Parsing.\n \n \n \n \n\n\n \n Simona Ondrčková; Roman Barták; Pascal Bercher; and Gregor Behnke.\n\n\n \n\n\n\n In
Proceedings of the 15th International Conference on Agents and Artificial Intelligence (ICAART 2023), pages 92–99, 2023. SciTePress\n
\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n \n paper-by-publisher\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 9 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@InProceedings{Ondrckova2023GroundingInVerification,\n author = {Simona Ondr\\v{c}kov\\'{a} and Roman Bart{\\'a}k and Pascal Bercher and Gregor Behnke},\n booktitle = {Proceedings of the 15th International Conference on Agents and Artificial Intelligence (ICAART 2023)},\n title = {On the Impact of Grounding on HTN Plan Verification via Parsing},\n year = {2023},\n pages = {92--99},\n publisher = {SciTePress},\n abstract = {The problem of hierarchical plan verification focuses on checking whether an action sequence is a valid hierarchical plan - the action sequence is executable and a goal task can be decomposed into it. The existing parsing-based verifier works on lifted domain models. In this paper we study whether grounding of the models could improve efficiency of the verifier. We also explore additional implementation improvements to increase the speed of the verifier},\n url_Paper = {https://bercher.net/publications/2023/Ondrckova2023GroundingInVerification.pdf},\n url_Paper-by-Publisher = {https://www.scitepress.org/PublicationsDetail.aspx?ID=gmWzZ9pf1D4=&t=1}\n}\n\n\n
\n
\n\n\n
\n The problem of hierarchical plan verification focuses on checking whether an action sequence is a valid hierarchical plan - the action sequence is executable and a goal task can be decomposed into it. The existing parsing-based verifier works on lifted domain models. In this paper we study whether grounding of the models could improve efficiency of the verifier. We also explore additional implementation improvements to increase the speed of the verifier\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 paper\n \n \n \n poster\n \n \n \n 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 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_Poster = {https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexityPoster.pdf},\n url_Slides = {https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexitySlides.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 paper\n \n \n \n poster\n \n \n \n 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 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_Poster = {https://bercher.net/publications/2023/Lin2023RepairingClassicalModelsPoster.pdf},\n url_Slides = {https://bercher.net/publications/2023/Lin2023RepairingClassicalModelsSlides.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 paper\n \n \n \n poster\n \n \n \n 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 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_Poster = {https://bercher.net/publications/2023/Lin2023TOVerificationPoster.pdf},\n url_Slides = {https://bercher.net/publications/2023/Lin2023TOVerificationSlides.pdf}\n}\n\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