Towards Search Node-Specific HTN Heuristics

While effective in hierarchical task network (HTN) planning, heuristic search currently relies on few pre-selected heuristics. However, during progression-based search, many search nodes exhibit specific properties, e.g., they may become totally ordered or acyclic, allowing for the application of specialized heuristics. For these search nodes, we conducted an experimental evaluation, employing reachability analysis to examine the special cases encountered during search. Measuring how often various special cases occur informs us which heuristics developed for special cases – selected on a per-search node basis – are most promising. As a side contribution, we propose a slight modification of a technical definition used to define properties of the task hierarchy.