Hierarchical task network planning with resources and temporal constraints

摘要

Planning problems in many real-world areas are characterized by the involvement of various types of resources and complex temporal and functional relationships among numerous tasks. Hierarchical Task Network (HTN) planning is suitable for large-scale practical planning problems due to its hierarchical task decomposition principle and expressiveness for domain knowledge representation. In this paper, we propose an HTN planning algorithm named GSCCB-SHOP2 to handle multi-capacity discrete resources and complex temporal constraints simultaneously during planning. The algorithm integrates three carefully designed and interrelated sub-modules. First, the Resource model realizes resource reasoning with the designed state updating rules. Second, the Check Consistency and Backtrack (CCB) module is designed to determine temporal constraints and maintain the consistency of those constraints. Third, the Guide Search (GS) module is designed to improve the resource utilization and thus shorten the makespan performance of the generated action plan. Experimental studies are conducted to verify the efficiency of the proposed algorithm.