Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical Plans
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 c...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
LibraryPress@UF
2023-05-01
|
| Series: | Proceedings of the International Florida Artificial Intelligence Research Society Conference |
| Subjects: | |
| Online Access: | https://journals.flvc.org/FLAIRS/article/view/133196 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849762894637432832 |
|---|---|
| author | Simona Ondrčková Roman Barták Pascal Bercher Gregor Behnke |
| author_facet | Simona Ondrčková Roman Barták Pascal Bercher Gregor Behnke |
| author_sort | Simona Ondrčková |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-e175cd22dc9542f69fc584d801f137fa |
| institution | DOAJ |
| issn | 2334-0754 2334-0762 |
| language | English |
| publishDate | 2023-05-01 |
| publisher | LibraryPress@UF |
| record_format | Article |
| series | Proceedings of the International Florida Artificial Intelligence Research Society Conference |
| spelling | doaj-art-e175cd22dc9542f69fc584d801f137fa2025-08-20T03:05:35ZengLibraryPress@UFProceedings of the International Florida Artificial Intelligence Research Society Conference2334-07542334-07622023-05-013610.32473/flairs.36.13319669502Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical PlansSimona Ondrčková0https://orcid.org/0000-0001-9081-4988Roman Bartákhttps://orcid.org/0000-0002-6717-8175Pascal Bercherhttps://orcid.org/0000-0002-0795-4320Gregor BehnkeCharles UniversityVerification 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.https://journals.flvc.org/FLAIRS/article/view/133196hierarchical planningparsinghierarchical plan verificationplan verification |
| spellingShingle | Simona Ondrčková Roman Barták Pascal Bercher Gregor Behnke Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical Plans Proceedings of the International Florida Artificial Intelligence Research Society Conference hierarchical planning parsing hierarchical plan verification plan verification |
| title | Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical Plans |
| title_full | Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical Plans |
| title_fullStr | Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical Plans |
| title_full_unstemmed | Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical Plans |
| title_short | Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical Plans |
| title_sort | lessons learned from the cyk algorithm for parsing based verification of hierarchical plans |
| topic | hierarchical planning parsing hierarchical plan verification plan verification |
| url | https://journals.flvc.org/FLAIRS/article/view/133196 |
| work_keys_str_mv | AT simonaondrckova lessonslearnedfromthecykalgorithmforparsingbasedverificationofhierarchicalplans AT romanbartak lessonslearnedfromthecykalgorithmforparsingbasedverificationofhierarchicalplans AT pascalbercher lessonslearnedfromthecykalgorithmforparsingbasedverificationofhierarchicalplans AT gregorbehnke lessonslearnedfromthecykalgorithmforparsingbasedverificationofhierarchicalplans |