Combining Heuristic Search with Hierarchical Task-Network Planning: A Preliminary Report

All Papers

Important advances in automated planning have been made recently, especially with the development of domain-configurable planning systems. These planners use a domain-independent search engine for planning, but they have also the ability to exploit domain-specific planning knowledge. Examples of such planners include the well-known TLPlan, TALPlanner, and SHOP2. One challenge for domain-configurable planners is that they require a domain expert to provide planning knowledge to the system. When this knowledge is not accurate, complete, poorly expressed, the performance of these planners diminishes considerably and very quickly, even in simple planning benchmarks. In this paper, we present a preliminary report on our research aimed to mitigate this issue by combining the use of domain-specific knowledge and domain-independent heuristic search. We describe H2O (short for Hierarchical Heuristic Ordered planner), a new Hierarchical Task-Network (HTN) planning algorithm that can heuristically select the best task decompositions by using domain-independent state-based heuristics. Our experiments in the DARPA Transfer Learning Program demonstrated the potentialities of H2O: given HTNs generated by a machine-learning system, which were much less optimal than an expert would encode, H2O was able to solve problems that SHOP2 could not.