@InProceedings{Wu2022HTNLinearization,
  author       = {Ying Xian Wu and Songtuan Lin and Gregor Behnke and Pascal Bercher},
  booktitle    = {33rd {PuK} Workshop ``Planen, Scheduling und Konfigurieren, Entwerfen'' ({PuK} 2022)},
  title        = {Finding Solution Preserving Linearizations For Partially Ordered Hierarchical Planning Problems},
  year         = {2022},
  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.},
  url_Paper    = {https://bercher.net/publications/2022/Wu2022HTNLinearization.pdf},
  url_Slides   = {https://bercher.net/publications/2022/Wu2022HTNLinearizationSlides.pdf},
  url_Workshop = {http://www.member.uni-oldenburg.de/juergen.sauer/PuK/PuK2022/index.html},
  keywords     = {workshop}
}

{"_id":"cnaRbtQ2Pkt9W6GB6","bibbaseid":"wu-lin-behnke-bercher-findingsolutionpreservinglinearizationsforpartiallyorderedhierarchicalplanningproblems-2022","author_short":["Wu, Y. X.","Lin, S.","Behnke, G.","Bercher, P."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Ying","Xian"],"propositions":[],"lastnames":["Wu"],"suffixes":[]},{"firstnames":["Songtuan"],"propositions":[],"lastnames":["Lin"],"suffixes":[]},{"firstnames":["Gregor"],"propositions":[],"lastnames":["Behnke"],"suffixes":[]},{"firstnames":["Pascal"],"propositions":[],"lastnames":["Bercher"],"suffixes":[]}],"booktitle":"33rd PuK Workshop ``Planen, Scheduling und Konfigurieren, Entwerfen'' (PuK 2022)","title":"Finding Solution Preserving Linearizations For Partially Ordered Hierarchical Planning Problems","year":"2022","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.","url_paper":"https://bercher.net/publications/2022/Wu2022HTNLinearization.pdf","url_slides":"https://bercher.net/publications/2022/Wu2022HTNLinearizationSlides.pdf","url_workshop":"http://www.member.uni-oldenburg.de/juergen.sauer/PuK/PuK2022/index.html","keywords":"workshop","bibtex":"@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 keywords = {workshop}\n}\n\n","author_short":["Wu, Y. X.","Lin, S.","Behnke, G.","Bercher, P."],"key":"Wu2022HTNLinearization","id":"Wu2022HTNLinearization","bibbaseid":"wu-lin-behnke-bercher-findingsolutionpreservinglinearizationsforpartiallyorderedhierarchicalplanningproblems-2022","role":"author","urls":{" paper":"https://bercher.net/publications/2022/Wu2022HTNLinearization.pdf"," slides":"https://bercher.net/publications/2022/Wu2022HTNLinearizationSlides.pdf"," workshop":"http://www.member.uni-oldenburg.de/juergen.sauer/PuK/PuK2022/index.html"},"keyword":["workshop"],"metadata":{"authorlinks":{}},"downloads":26},"bibtype":"inproceedings","biburl":"https://bercher.net/bibtex/bibliography.bib","dataSources":["jTtEZEw8NJc375xGA","WvkzCyK6mKXCp2WFz","rta5EvLvgMEDFTyZk","bPpsmYWjffAy6QHP5","wYF8yPQT6a4TgShWe"],"keywords":["workshop"],"search_terms":["finding","solution","preserving","linearizations","partially","ordered","hierarchical","planning","problems","wu","lin","behnke","bercher"],"title":"Finding Solution Preserving Linearizations For Partially Ordered Hierarchical Planning Problems","year":2022,"downloads":26}