Compiling HTN Plan Verification Problems into HTN Planning Problems

Plan Verification is the task of deciding whether a sequence of actions is a solution for a given planning problem. In HTN planning, the task is computationally expensive and may be up to NP-hard. However, there are situations where it needs to be solved, e. g. when a solution is post-processed, in systems using approximation, or just to validate whether a planning system works correctly (e. g. for debugging or in a competition). There are verification systems based on translations to propositional logic and on techniques from parsing. Here we present a third approach and translate HTN plan verification problems into HTN planning problems. These can be solved using any HTN planning system. We collected a new benchmark set based on models and results of the 2020 International Planning Competition. Our evaluation shows that our compilation outperforms the approaches from the literature.

Authors

• Daniel Höller
• Julia Wichlacz
• Pascal Bercher
• Gregor Behnke

Keywords

• Plan Verification
• HTN Planning
• Problem Compilation