@InProceedings{Ondrckova2023HTNParsing,
  author           = {Simona Ondr\v{c}kov\'{a} and Roman Bart{\'a}k and Pascal Bercher and Gregor Behnke},
  booktitle        = {Proceedings of the 35th International Florida Artificial Intelligence Research Society Conference (FLAIRS 2023)},
  title            = {Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical Plans},
  year             = {2023},
  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 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.},
  url_Paper        = {https://bercher.net/publications/2023/Ondrckova2023CYKLessonsLearned.pdf},
  url_FLAIRS-Paper = {https://journals.flvc.org/FLAIRS/article/view/133196},
  doi              = {10.32473/flairs.36.133196},
  keywords         = {conference}
}

{"_id":"X722DccD2uKezjcST","bibbaseid":"ondrkov-bartk-bercher-behnke-lessonslearnedfromthecykalgorithmforparsingbasedverificationofhierarchicalplans-2023","author_short":["Ondrčková, S.","Barták, R.","Bercher, P.","Behnke, G."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Simona"],"propositions":[],"lastnames":["Ondrčková"],"suffixes":[]},{"firstnames":["Roman"],"propositions":[],"lastnames":["Barták"],"suffixes":[]},{"firstnames":["Pascal"],"propositions":[],"lastnames":["Bercher"],"suffixes":[]},{"firstnames":["Gregor"],"propositions":[],"lastnames":["Behnke"],"suffixes":[]}],"booktitle":"Proceedings of the 35th International Florida Artificial Intelligence Research Society Conference (FLAIRS 2023)","title":"Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical Plans","year":"2023","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 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.","url_paper":"https://bercher.net/publications/2023/Ondrckova2023CYKLessonsLearned.pdf","url_flairs-paper":"https://journals.flvc.org/FLAIRS/article/view/133196","doi":"10.32473/flairs.36.133196","keywords":"conference","bibtex":"@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 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 keywords = {conference}\n}\n\n","author_short":["Ondrčková, S.","Barták, R.","Bercher, P.","Behnke, G."],"key":"Ondrckova2023HTNParsing","id":"Ondrckova2023HTNParsing","bibbaseid":"ondrkov-bartk-bercher-behnke-lessonslearnedfromthecykalgorithmforparsingbasedverificationofhierarchicalplans-2023","role":"author","urls":{" paper":"https://bercher.net/publications/2023/Ondrckova2023CYKLessonsLearned.pdf"," flairs-paper":"https://journals.flvc.org/FLAIRS/article/view/133196"},"keyword":["conference"],"metadata":{"authorlinks":{}},"downloads":3},"bibtype":"inproceedings","biburl":"https://bercher.net/bibtex/bibliography.bib","dataSources":["zKgS72cAu6Ez7npdh","bPpsmYWjffAy6QHP5","wYF8yPQT6a4TgShWe"],"keywords":["conference"],"search_terms":["lessons","learned","cyk","algorithm","parsing","based","verification","hierarchical","plans","ondrčková","barták","bercher","behnke"],"title":"Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical Plans","year":2023,"downloads":3}