On the Verification of Totally-Ordered HTN Plans
Roman Barták, Simona Ondrčková, Gregor Behnke, Pascal Bercher · 2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI) · 2021
Verifying HTN plans is an intractable problem with two existing approaches to solve the problem. One technique is based on compilation to SAT. Another method is using parsing, and it is currently the fastest technique for verifying HTN plans and the only technique supporting state constraints. In this paper, we propose an extension of the parsing-based approach to verify totally-ordered HTN plans more efficiently. This problem is known to be tractable if no state constraints are included, and we show theoretically and empirically that the modified parsing approach achieves better performance than the currently fastest HTN plan verifier when applied to totally-ordered HTN plans.