Analyzing External Conditions to Improve the Efficiency of HTN Planning

Abstract

One difficulty with existing theoretical work on HTN planning is that it does not address some of the planning constructs that are commonly used in HTN planners for practical applications. Although such constructs can make it difficult to ensure the soundness and completeness of HTN planning, they are important because they can greatly improve the efficiency of planning in practice. In this paper, we describe a way to achieve some of the advantages of such constructs while preserving soundness and completeness, through the use of what we will call external conditions. We describe how to detect some kinds of external conditions automatically by preprocessing the planner's knowledge base, and how to use this knowledge to improve the efficiency of the planner's refinement strategy. We present