Research On Hierarchical Task Network Based Emergency Response Task Planning Method

Emergency response has been gaining more and more attention from both researchers and practitioners due to the frequent occurrences of natural and manmade disasters. Efficient emergency response task planning is an important prerequisite for successful emergency response practices. Emergency response task planning problem has the properties of large scale, hierarchical decision, complex task relations, tight time constraints, limited resources and dynamic emergency situations. Commonly used mathematical programming algorithms are not sufficiently effective due to the heavy computational burdens and the limited flexibility. Hierarchical task network(HTN) planning is capable of solving large scale problems and can effectively mimicking the cognition process of decision makers. Based on the properties of emergency response, this work investigates the HTN based emergency response task planning method.Firstly, a method of generating task network for emergency response based on the snowball procedure and an associated method of analyzing task network based on social network analysis are proposed. The task network generating process provides the preliminary structure for the domain knowledge of HTN planning. The results of network analysis contribute to reasonable plan execution monitoring. Secondly, considering the fact that temporal and resource constraints are important factors in emergency response task planning while current HTN planning algorithms have limited capacity on resource and temporal constraints reasoning, a new HTN planning algorithm, called GSCCB-SHOP2 is proposed to handle with multi-capacity discrete resources and complex temporal constraints simultaneously. The new algorithm is a breakthrough for conventional HTN planning algorithms which usually only focus on temporal constraints, neglecting the reasoning of resource conflicts. Thirdly, because current static HTN planning process is powerless to handle with the dynamic environment and exceptions during plan execution, a HTN based replanning method is proposed. The replanning method mainly includes plan execution monitoring and new planning problem generating.Based on the properties of emergency response task planning and the weaknesses of current HTN planning methods, three aspects of research, including systematic domain knowledge constructing, HTN planning algorithm with temporal and resource constraints, and HTN based replanning, are investigated in this work. The fundamental aim of this work is to improve the suitability of HTN planning on emergency response task planning. The proposed emergency task network generating method is a new try on systematical domain knowledge constructing for complex planning systems. This is a new idea on domain knowledge constructing for HTN planning. The corresponding task network analysis method provide important information for targeted plan execution monitoring. The presented new HTN planning algorithm, which is the most research emphasis and difficulty of this work, has the capacity of reasoning temporal and resource constraints simultaneously and also efficient running time, making HTN planning more suitable for emergency response task planning problems. The HTN based replanning method overcomes the powerless on execution exceptions of static HTN planning.