Considering Quality Of Plan In HTN Emergency Task Planning Approach

In recent years, the amount of emergency events is increasing and there occur many new types of emergency events. These facts not only had serious impact on the economy and society of the related areas, but also posed a big challenge to the emergency management department for responding to the emergency event scientifically and effectively. Emergency action plan making is a crucial step of the emergency response decision-making for emergency events. It needs to make the emergency action plan and execute the plan quickly after the emergency event occurs. The conventional mathematical model is not good at solving the complex problem of emergency action plan making. HTN(Hierarchy Task Network)planning, which is one of the most important approaches of Artificial Intelligence planning,can reason side of actions by using domain knowledge, and has been used in emergency action plan making problem successfully. However, the existing HTN planning approaches only focus on how to get the valid plan quickly, and they do not consider how to generate the high quality plan. In many cases, the effectiveness of emergency response has been affected by the quality of the emergency action plan. The low quality emergency action plan may lead to the failure of the current emergency tasks, even give more troubles to the other emergency tasks. As a result, it requires further study of HTN planning approach to generate high quality emergency action plan for emergency response decision-making.Concentrated on the need of high quality emergency action plan for some realistic situations in emergency action plan making problem, this thesis designs some HTN planning task approaches contributed to generate the high quality emergency action plan with consideration of the temporal preferences, time flexibility and multi-objective optimization in emergency action plan making. In detail, the contributions of this thesis are listed as follows:(1) Aiming to generate the emergency action plan satisfying the emergency decisionmakers preferences, a temporal HTN emergency task planning approach, TPHTN, is proposed. TPHTN extends STN(Simple Temporal Networks) to STNP(Simple Temporal Networks with Preferences) for expressing the temporal constraints and temporal preferences information in emergency action plan making problem. Furthermore, TPHTN extends the representations of operator and method to express the temporal preferences in domain knowledge. In the planning process of TPHTN, three definitions of level consistency(?-,?- and ?- level consistency) are proposed to estimate the quality of STNP, and a new heuristic search is designed to choose the suitable operator/method to apply based on the quality of the corresponding STNP. When the planning process is terminated, TPHTN will generate a high quality plan satisfying the decision-makers preferences.(2) Aiming to generate the high quality plan to respond to the temporal exception in the emergency action plan execution, a new HTN emergency task planning approach which considers time flexibility, FHTN-CON, is proposed. The approach includes two components:emergency action plan generating and emergency action plan execution. In the emergency action plan generating component, STN is used to express the complex temporal constraints in planning and an STN-based heuristic search is designed to guide the search direction.When the plan generating component is terminated, it will generate a high quality emergency action plan with time flexibility. In the emergency action plan execution component,it monitors the plan execution process, and checks the validation of the current plan when the temporal exception occurs, if and only if the plan is invalid, the approach will replan.FHTN-CON can reduce the number of unnecessary replanning when the temporal exception occurs during the plan execution.(3)Aiming to generate the emergency action plan with mult-objective optimization,a multi-objective HTN emergency task planning approach, PSA, is proposed. First, the conventional HTN planning operator is extended to express the multiple features of the operator; second, PSA evaluates the emergency action plan based on preference relations;third, the planning algorithm of PSA combines heuristic search and Anytime search. The heuristic search can guide the planning direction and the Anytime search can prune the HTN planning space by pruning strategy. Finally, PSA can generate the high quality emergency action plans continuously with planning time extending.(4)Considering the situation that the preferences information between the multiple objectives in the multi-objective emergency action plan making problem is unknown, a multi-objective HTN emergency task planning approach based on dominance relations,DSA, is proposed. First, DSA evaluates the emergency action plan based on dominance relations; second, the planning algorithm of DSA combines heuristic search and Anytime search. Unlike PSA, the heuristic search in DSA ranks the methods and operators based on dominance relations and the Anytime search in DSA prune the planning space based on dominance relations. The Anytime search not only improves the efficiency of the planning approach, but also ensures that the plan generated later is not dominated by the plan generated earlier. Finally, DSA will return a non-dominated emergency action plan set for the emergency decision maker to choose from.