\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 paper\n \n \n \n slides\n \n \n \n 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 paper\n \n \n \n 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 \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 paper\n \n \n \n poster\n \n \n \n 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 On the Efficient Inference of Preconditions and Effects of Compound Tasks in Partially Ordered HTN Planning Domains.\n \n \n \n \n\n\n \n Conny Olz; and Pascal Bercher.\n\n\n \n\n\n\n In
Proceedings of the 5th ICAPS Workshop on Hierarchical Planning (HPlan 2022), pages 47–51, 2022. \n
\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n \n 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 15 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@InProceedings{Olz2022POPrecsAndEffects,\n author = {Conny Olz and Pascal Bercher},\n booktitle = {Proceedings of the 5th ICAPS Workshop on Hierarchical Planning (HPlan 2022)},\n title = {On the Efficient Inference of Preconditions and Effects of Compound Tasks in Partially Ordered HTN Planning Domains},\n year = {2022},\n Pages = {47--51},\n abstract = {Recently, preconditions and effects of compound tasks based on their possible refinements have been introduced together with an efficient inference procedure to compute a subset of them. However, they were restricted to total-order HTN planning domains. In this paper we generalize the definitions and algorithm to the scenario of partially ordered domains.},\n url_Paper = {https://bercher.net/publications/2022/Olz2022POPrecsAndEffects.pdf},\n url_presentation = {https://youtu.be/QsQsXBYu0yI}\n}\n\n
\n
\n\n\n
\n Recently, preconditions and effects of compound tasks based on their possible refinements have been introduced together with an efficient inference procedure to compute a subset of them. However, they were restricted to total-order HTN planning domains. In this paper we generalize the definitions and algorithm to the scenario of partially ordered domains.\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n A Study of the Power of Heuristic-based Pruning via SAT Planning.\n \n \n \n \n\n\n \n Christopher Johnson; Pascal Bercher; and Charles Gretton.\n\n\n \n\n\n\n In
Proceedings of the 14th Workshop on Heuristics and Search for Domain-independent Planning (HSDIP 2022), 2022. \n
This paper has also been accepted at KEPS 2022.\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n \n presentation\n \n \n \n openreview\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n \n \n abstract \n \n\n \n \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@InProceedings{Johnson2022aSATPruning,\n author = {Christopher Johnson and Pascal Bercher and Charles Gretton},\n booktitle = {Proceedings of the 14th Workshop on Heuristics and Search for Domain-independent Planning (HSDIP 2022)},\n title = {A Study of the Power of Heuristic-based Pruning via SAT Planning},\n year = {2022},\n abstract = {Planning as SAT (satisfiability) is the method of representing a horizon-bounded planning problem as a Boolean SAT problem, and using a SAT decision procedure to solve that problem. Representations are direct, thus a solution plan can be obtained directly from a satisfying valuation. By querying a SAT solver over a series of horizon lengths, up to a completeness threshold, this approach can be the basis of a complete planning procedure. SAT planning algorithms have been theoretically contrasted with IDA∗ search, a heuristic state-based search algorithm, where a theoretical exponential separation is demonstrated in favour of the SAT approach. Here a nominated heuristic is implemented in SAT with the query formulae encoding heuristic information.\nWe make two practical contributions related to this background. First, we provide to the best of our knowledge the first practical implementation of a theoretical SAT encoding of the h-2 heuristic. Second, we empirically evaluate SAT-based pruning by implementing heuristics h-max and h-2.},\n note = {This paper has also been accepted at KEPS 2022.},\n url_Paper = {https://bercher.net/publications/2022/Johnson2022SATBasedHeuristicPruning.pdf},\n url_presentation = {https://www.youtube.com/watch?v=HFntrSAyszU},\n url_openReview = {https://openreview.net/forum?id=c2-QShxGZt}\n}\n\n
\n
\n\n\n
\n Planning as SAT (satisfiability) is the method of representing a horizon-bounded planning problem as a Boolean SAT problem, and using a SAT decision procedure to solve that problem. Representations are direct, thus a solution plan can be obtained directly from a satisfying valuation. By querying a SAT solver over a series of horizon lengths, up to a completeness threshold, this approach can be the basis of a complete planning procedure. SAT planning algorithms have been theoretically contrasted with IDA∗ search, a heuristic state-based search algorithm, where a theoretical exponential separation is demonstrated in favour of the SAT approach. Here a nominated heuristic is implemented in SAT with the query formulae encoding heuristic information. We make two practical contributions related to this background. First, we provide to the best of our knowledge the first practical implementation of a theoretical SAT encoding of the h-2 heuristic. Second, we empirically evaluate SAT-based pruning by implementing heuristics h-max and h-2.\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n A Study of the Power of Heuristic-based Pruning via SAT Planning.\n \n \n \n \n\n\n \n Christopher Johnson; Pascal Bercher; and Charles Gretton.\n\n\n \n\n\n\n In
Proceedings of the 11th Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2022), 2022. \n
This paper has also been accepted at HSDIP 2022, the linked openReview reviews are from HSDIP.\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n \n openreview\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n \n \n abstract \n \n\n \n \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@InProceedings{Johnson2022bSATPruning,\n author = {Christopher Johnson and Pascal Bercher and Charles Gretton},\n booktitle = {Proceedings of the 11th Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2022)},\n title = {A Study of the Power of Heuristic-based Pruning via SAT Planning},\n year = {2022},\n abstract = {Planning as SAT (satisfiability) is the method of representing a horizon-bounded planning problem as a Boolean SAT problem, and using a SAT decision procedure to solve that problem. Representations are direct, thus a solution plan can be obtained directly from a satisfying valuation. By querying a SAT solver over a series of horizon lengths, up to a completeness threshold, this approach can be the basis of a complete planning procedure. SAT planning algorithms have been theoretically contrasted with IDA∗ search, a heuristic state-based search algorithm, where a theoretical exponential separation is demonstrated in favour of the SAT approach. Here a nominated heuristic is implemented in SAT with the query formulae encoding heuristic information.\nWe make two practical contributions related to this background. First, we provide to the best of our knowledge the first practical implementation of a theoretical SAT encoding of the h-2 heuristic. Second, we empirically evaluate SAT-based pruning by implementing heuristics h-max and h-2.},\n note = {This paper has also been accepted at HSDIP 2022, the linked openReview reviews are from HSDIP.},\n url_Paper = {https://bercher.net/publications/2022/Johnson2022SATBasedHeuristicPruning.pdf},\n url_openReview = {https://openreview.net/forum?id=c2-QShxGZt}\n}\n\n
\n
\n\n\n
\n Planning as SAT (satisfiability) is the method of representing a horizon-bounded planning problem as a Boolean SAT problem, and using a SAT decision procedure to solve that problem. Representations are direct, thus a solution plan can be obtained directly from a satisfying valuation. By querying a SAT solver over a series of horizon lengths, up to a completeness threshold, this approach can be the basis of a complete planning procedure. SAT planning algorithms have been theoretically contrasted with IDA∗ search, a heuristic state-based search algorithm, where a theoretical exponential separation is demonstrated in favour of the SAT approach. Here a nominated heuristic is implemented in SAT with the query formulae encoding heuristic information. We make two practical contributions related to this background. First, we provide to the best of our knowledge the first practical implementation of a theoretical SAT encoding of the h-2 heuristic. Second, we empirically evaluate SAT-based pruning by implementing heuristics h-max and h-2.\n
\n\n\n
\n\n\n\n\n\n