Improving hierarchical task network planning performance by the use of domain-independent heuristic search

摘要

Heuristics serve as a powerful tool in classical planning. However, due to some incompatibilities between classical planning and hierarchical planning, heuristics from classical planning cannot be easily adapted to work in the hierarchical task network (HTN) setting. In order to improve HTN planning performance by the use of heuristics from classical planning, a new HTN planning named SHOP-h planning algorithm is established. Based on simple hierarchical ordered planner (SHOP), SHOP-h implemented with Python is called Pyhop-h. It can heuristically select the best decomposition method by using domain independent state-based heuristics. The experimental benchmark problem shows that the Pyhop-h outperforms the existed Pyhop in plan length and time. It can be concluded that Pyhop-h can leverage domain independent heuristics and other techniques both to reduce the domain engineering burden and to solve more and larger problems rapidly especially for problems with a deep hierarchy of tasks.