Compiling HTN Plan Verification Problems into HTN Planning Problems

Abstract

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.