Abstract
This study proposes a novel temporal planning approach based on Hierarchical Task Network (HTN) with uncontrollable durations for emergency decision-making. The objective is to generate a dynamically controllable (DC) plan which takes into account uncontrollable durations beforehand and to execute the plan via scheduling the actions dynamically. In this study, the action durations are modelled as temporal intervals by Simple Temporal Network with Uncertainty (STNU). Firstly, the temporal constraints among tasks are represented and reasoned. Next, a mechanism is proposed to hierarchically inherit the temporal constraints in HTN planning. Furthermore, two works are explored to generate a DC plan more efficiently. The one is to construct a temporal network of tasks and check its dynamic controllability. The other one is to put forward two rules to boost the DC checking in planning. An empirical study on flood emergency response is conducted to evaluate the planning approach. The experimental results demonstrate the effectiveness and efficiency of the planning approach for emergency decision-making.
Keywords
Introduction
Hierarchical Task Network (HTN) planning is widely applied in emergency decision-making due to its powerful reasoning, expressive representation and good support for large-scale domains [1–5]. The core of emergency decision-making is to organize and deploy emergency response tasks considering the special requirements via rapidly developing and implementing an effective emergency action plan. In view of considerable temporal pressure and time urgency of emergency response, the tasks involved to jointly achieve emergency objectives have complicated temporal requirements with each other. In particular, due to the uncertain characteristics of emergencies [6], there is uncertainty about the durations of actions. In realistic emergency response, the exact duration of an action generally cannot be pre-defined precisely [7, 8], because the emergency situation is constantly changing and the action durations are much likely to be influenced by unpredicted events which are not under control. For example, when a truck transports clay to a disaster area, its precise duration may be effected by some uncontrollable factors such as weather condition and traffic congestion. Therefore, it is vital for emergency decision-making to take into consideration duration uncontrollability beforehand and develop a temporal flexible plan to react to uncontrollable duration disturbances.
As one category of temporal flexible plans, dynamically controllable (DC) plans [9, 10] are able to guarantee the controllable time-points (start times of actions) to be scheduled incrementally no matter how the uncontrollable time-points (end times of actions with uncontrollable durations) turn out. The crux for HTN planning with uncontrollable durations is to develop a DC plan under the complicated temporal requirements. Firstly, different tasks execute concurrently or interact, which results in qualitative and metric temporal constraints such as makespan, concurrence, sequencing, etc. [11]. As the prerequisite of generating a DC plan, the temporal constraints should be managed in a unified way. Secondly, not only a specific action sequence is required to be generated but also the dynamic controllability of the plan should be guaranteed under the complex temporal constraints. Checking the dynamic controllability of the plan during planning poses challenges to the existing HTN planners. In general, temporal planning is difficult, particularly in regard to actions with duration uncertainty [12, 13].
The uncontrollable durations can be modelled as contingent temporal intervals by Simple Temporal Network with Uncertainty (STNU) [9, 14]. STNU distinguishes contingent constraints whose occurrences are uncontrollable. However, there still exist challenges for STNU to be implemented directly in HTN planning for emergency decision-making. Firstly, checking the dynamic controllability of a plan requires a complete STNU as input at every planning step [15], but there is not a complete STNU in HTN planning. Secondly, a mass of temporal constraints are produced in terms of the plan during planning, as well as the plan needs to be verified frequently. The two aforementioned aspects result in intensive computation. However, the current DC checking algorithms are not efficient enough to meet the urgency requirement of emergency decision-making.
Motivated by the above analysis, this study proposes a novel temporal planning approach based on HTN with uncontrollable durations for emergency decision-making. With the aim at generating and executing a temporal flexible plan regardless of outcomes of uncontrollable durations under complicated temporal requirements, a temporal enhanced HTN planner that is able to handle uncontrollable durations is developed to generate a DC plan, and a dispatcher is devised to schedule the start times of the actions in the plan dynamically during execution. Several valuable extensions are developed in HTN planning. Firstly, the action durations are modelled as temporal intervals by STNU. Secondly, the complex temporal constraints are managed jointly. The temporal constraints among tasks are represented and reasoned with casual links. A mechanism is developed to hierarchically inherit the temporal constraints in HTN planning. In particular, as the earliest tasks and the latest tasks are ought to inherit the temporal constraints from high-level tasks respectively, an algorithm is further proposed to search the earliest time-points and the latest ones in a temporal network. Thirdly, with the objectives of generating a DC plan more efficiently and detecting non-DC plans timely, we explore to construct a temporal network of tasks, as well as put forward an algorithm to check its dynamic controllability incrementally via two steps. In particular, the DC checking in planning is boosted by two rules.
This paper is organized as follows. Section 2 discusses the related work on non-HTN planning with uncontrollable durations and temporal HTN planning, respectively. Section 3 introduces the preliminaries and defines the problem. Section 4 elaborates the planning approach. Section 5 focuses on the temporal constraint management. Next in Section 6, the temporal network of tasks is constructed and checked in terms of the dynamic controllability. Two rules are proposed to boost the DC checking. Section 7 surveys the experimental results and the empirical evaluation. Finally, Section 8 concludes this paper and discusses future work.
Related work
This section reviews the literatures relevant to this study. Section 2.1 reviews the studies on non-HTN planning with uncontrollable durations. Although some HTN planning approaches only work in deterministic temporal domain, they provide a foundation for temporal HTN planning, and thus they are also discussed in Section 2.2.
Non-HTN planning with uncontrollable durations
Some non-HTN planning approaches have been put forward to address uncontrollable durations. To address the Strong Planning Problem with Temporal Uncertainty (SPPTU), Cimatti et al. [16] extended the forward state-space temporal planning and further implemented it in the planner COLIN [17]. Similarly to solve the SPPTU, Micheli et al. [18] proposed a compilation technique which translates a planning instance with uncontrollable durations into a temporal planning problem with controllable durations. Different from the above action-based planning, Cimatti et al. [19] extended the timeline-based planning with uncontrollable durations to generate a strong controllable plan. The aforementioned planning approaches all generate the strong controllable plans. Although the strong controllable plans are of value in the situations where observing is difficult or even impossible or where a complete action sequence must be known beforehand, they are conservative and unavailable upon most occasions [20].
Temporal HTN planning
There have been some HTN planning approaches considering temporal issues. SIPE-2 [21, 22] had a support for temporal reasoning such as parallel interactions and deadline goals. O-Plan2 [23] represented and handled the time constraints on tasks using incremental time constraint management. SHOP2 [24] handled concurrency of actions via Multi-Timeline Preprocessing, although SHOP2 cannot explicitly reason durative actions and concurrent actions. Yorke-Smith [25] exploited the structure of HTN plans to accelerate constraint propagation on Simple Temporal Network (STN) [26]. SIADEX [27] handled temporal knowledge such as deadlines, temporal landmarks and synchronization via STN and boosted constraint propagation by the causal structure of plans. Goldman [28] extended SHOP2 on modelling and searching durative actions. Yaman et al. [29] extended HTN representation with temporal milestones to enable complex task synchronization. However, all of the above approaches just work in deterministic temporal domains, which cannot cope with the uncontrollable durations.
There have been works handling uncertain durations in HTN planning. Biundo et al. [30] integrated the concepts for continuous probabilities into an HTN-based planning framework. Representing the action durations as normal-distributed random variables, they constructed a plan to meet some probability thresholds. Nevertheless, the approach cannot guarantee the plans are executable regardless of any outcomes of uncontrollable durations.
Formalism
This section introduces the necessary background firstly, and then defines our problem.
Preliminaries
This section gives a brief introduction to the necessary background knowledge regarding temporal reasoning with uncertainty. More details are explained in the introduction [20].
A Simple Temporal Network with Uncertainty (STNU) augments a Simple Temporal Network (STN) to include a set of contingent constraints, where each contingent constraint represents the duration that is not controlled and is thus uncertain. It is defined as follows.
Controllability means a way to execute the time-points under control, subject to all constraints. The notion is expressed in terms of the ability to obtain an appropriate control sequence under a situation. As one category of controllability, dynamic controllability is most useful in practical domains. Hence this study concentrates on generating a DC plan, and we specify dynamic controllability as follows.
Problem definition
In this section we formulate the planning problem. This section is devoted to the extensions with respect to uncontrollable durations and temporal constraints, and the rest of the formulations, such as state, task and task network, are similar to the classical HTN planning paradigms [31] such as SHOP2 [24].
The planning problem is a 3-tuple P =< s0, ω0, D >, where s0 is the initial state, ω0 is the initial task network and D is a planning domain. The planning domain D consists of a set of operators O and a set of methods M. The planning domain is given by domain experts, who encode domain knowledge, experience and expertise according to a certain specialized format. The planning domain includes the considered uncertainty. An excerpt of the planning domain on flood disaster will be shown as an instance in Section 7.1.
Operator
In practice, action execution needs a period of time. What’s more, the durations of some actions are likely to be effected by uncontrollable factors. Rather than a fixed period, the uncontrollable duration of an action may happen any time in a range, whose occurrence is completely contingent with respect to some unpredicted events. Therefore for an action, its duration ought to be modelled as an interval which has to be guaranteed.
Operators, as the abstract representation of the actions in HTN planning, are formalized as below.
An example of an operator is shown in Fig. 1. The operator describes transporting material ?material from location ?from to location ?to by truck ?truck. The duration consumed is determined by the variables including the route and the speed. Different actions instantiated by the operator may have different durations.

Example of an operator.
A Method describes one way of accomplishing a compound task, which is defined formally.
Plan
Rather than a set of actions with exact start time-points and fixed durations, the plan outputted from the planner is an action sequence in which each action has two temporal intervals: one for the start time and one for the duration.
In general, θ s and θ d are represented as temporal intervals respectively. Note that θ s has a special form represented as <Z, v>, where Z is the start or the end of another action in the plan which occurs before θ s and v is the corresponding time value. It specifies a conditional decision that the action starts as soon as Z happens or has to wait until v, whichever comes first. The plan is reformulated as a dispatchable form which keeps temporal flexibility to react to duration uncontrollability.
Planning approach
In this section, we firstly introduce the architecture of the planning approach, and then specify the planning process.
The objective of this study is to investigate a novel temporal planning approach under duration uncontrollability. In general, due to the uncontrollable durations of the actions, all time-points cannot be scheduled at static times in advance [32]. A static plan is insufficient to ensure to be successful over all possible uncontrollable durations [33]. Therefore, we develop a planning approach to generate a dynamic solution, which includes an HTN planner and a dispatcher. The planner takes as input a planning problem and outputs a plan. Without exact start times and fixed durations, the durations of the actions in the plan are modelled as temporal intervals so that the start times and the durations are temporally flexible. Furthermore, the dispatcher takes as input the plan and schedules the start times of the actions to be started via monitoring the actions having been executed. The dispatcher selects time-points,locally propagates the executed durations to future time-points, which is devised based on the STNU execution [34]. As a result, the planning approach keeps temporal flexibility until execution so that it is able to react to any uncontrollableduration.
Next, we specify the planning process. Figure 2 illustrates the planning procedure of the planner. The planner is developed based on HTN planning framework, namely that compound tasks are decomposed into more specific ones until all tasks are primitive tasks that can be executed directly [31]. The capacities dealing with uncontrollable durations are enhanced. On the one hand the temporal constraints among tasks are represented and reasoned. On the other hand a mechanism is devised to inherit the temporal constraints by subtasks from high-level tasks in HTN planning. They will be discussed in Section 5. With those temporal constraints, a complete temporal network of tasks is constructed jointly. Its dynamic controllability is checked via two steps: verifying the temporal network of subtasks and then the overall temporal network of tasks. In particular, the DC checking is boosted by the proposed rules. They will be discussed in Section 6.

Planning procedure of the HTN planner.
Algorithm 1 depicts the detailed planning procedure in pseudocode, which is extended on SHOP2. The planner takes as input a planning problem as defined in Section 3.2. Line 1 initializes the indispensable variables in Algorithm 1. The plan Π is assigned by an empty set. The state s presents the current state at each step of planning and is assigned by the initial value s0 at the beginning. Task network ω is assigned by ω0. The temporal network of tasks G is built by the temporal constraints of the tasks in ω0. As Line 2 describes, the framework of the algorithm can be regarded as a loop that plans each step and moves forward. Once a DC plan is obtained successfully or the algorithm returns failure, the cyclic procedure quits and the planning ends. From Line 5 to Line 13, when the current task T is a primitive task, an operator o is instantiated. If there is a substitution σ such that the head of the action a unifies with T and the current state s satisfies pre (a), a set of actions A is instantiated. Line 7 checks the set of actions A. If A is not null, a is non-deterministically chosen, and s is updated by (s - effect- (a)) ∪ effect+ (a). The duration of the action θ d is added to a. Π is appended with a and ω is substituted by ω - T. Lines 14–23 describe the situation where the current task T is a compound task. C is a set of instances via decomposing T under a substitution σ where the head of the method m unifies with T. If C is not null, a pair (m, σ) is non-deterministically chosen. The constraints among subtasks and the constraints of the makespan of T constitute the temporal network of subtasks S. At Line 19, Algorithm 3 is invoked to check the dynamic controllability of S and G incrementally. If they are both DC, ω is substituted by ω - T ∪ subtasks and G is updated. Unless one of them is DC, another pair (m, σ) is selected. Finally, when ω is empty, the start times of the actions in Π are assigned from G. As a result, a DC plan Π is obtained.
The tasks in real-world emergency response will execute concurrently or interleave, which results in complex temporal constraints such as makespan, precedence, sequencing and concurrence. On the one hand, the temporal constraints among tasks that drive from domain knowledge ought to be represented directly. On the other hand, the temporal constraints that are implied in complex relationships are required to be reasoned. Furthermore, the temporal constraints are inherited by the subtasks from the high-level tasks in task decomposition. In order to deal with the temporal constraints as mentioned above, this section discusses the temporal constraint management with uncontrollable durations in HTN planning. Section 5.1 represents and reasons the temporal constraints among tasks. Section 5.2 explores the hierarchical temporal constraint inheritance.
Temporal constraints among tasks
In HTN planning, a compound task T may have the constraints that limit its makespan. It specifies the task itself has to be finished or started in a limited period. Formally, the temporal constraints are represented by j ≤ T _ end - T _ start and T _ end - T _ start ≤ k (0 ≤ j < k) where T _ start and T _ end are the start time and the end time of the task respectively. By default, they are 0 ≤ T _ end - T _ start and T _ end - T _ start≤ ∞ respectively.
The temporal constraints among tasks in HTN planning are related with the task decomposition structures. There are two types of task decomposition structures in HTN planning: total-order and partial-order [35], which specify two ways of forming subtask network during the HTNs decomposition. The total-order structure assumes the subtasks are executed in turn, which implies a sequential temporal relationship among the subtasks. But the subtasks in the partial-order structure may interleave or be executed in parallel. Therefore, assume that a compound task T is decomposed into the subtasks T1, T2, …, Tn. In the total-order structure, the temporal constraints of the subtasks are 0 ≤ Tr _ start - Ts _ end and Tr _ start - Ts _ end≤ ∞ (r = 2, 3, …, n, s = 1, 2, …, n - 1, r = s + 1). In the partial-order structure, the temporal constraints of the subtasks are specified as j ≤ Tr _ end - Ts _ start, Tr _ end - Ts _ start ≤ k or j ≤ Tr _ start - Ts _ end, Tr _ start - Ts _ end < k (r = 1, 2, …, n, s = 1, 2, …, n, r ≠ s, 0 ≤ j < k).
Unlike the above explicit temporal constraints, the temporal constraints implied in causal links are implicit and should be reasoned [36]. When the precondition of an action is supported by another action, there is a causal link between the two actions. The former action is named the consumer of the proposition, and the latter is the provider [35]. It implies the provider should execute before the consumer. Therefore, the temporal constraint 0 ≤ Tconsum - er _ start - Tprovider _ end should be specified. For example, the action ! transport transports clay by truck and the action !load loads clay for trucks. Obviously !transport cannot start until !load ends, because one of the preconditions of !transport is that !load has ended. Thus, there is a causal link where !load is the provider and the action !transport is the consumer, and the constraint 0 ≤ transport _ start - load _ end is reasoned. Different from SIADEX which just exploits the causal relationship of the causal link, the causal links are checked and the reasoned temporal constraints are added before a primitive task is instantiated.
Hierarchical temporal constraint inheritance
As compound tasks are decomposed into subtasks, the temporal constraints are inherited hierarchically by the subtasks from the compound tasks meanwhile. This section discusses the detailed process of inheriting complex temporal constraints from compound tasks during planning. The inheritance is different in terms of the task decomposition structures, namely the total-order structure and the partial-order structure. Consequently, the two different inheritance modes are specified as follows.
In the total-order structure, assuming that a compound task T is decomposed into the subtasks T1, T2, …, Tn, the earliest start time T1 _ start inherits the temporal constraints of T _ start, and the latest end time Tn _ end inherits the temporal constraints of T _ end. Given T _ duration = Tn _ end - T1 _ start, Tn _ end - T1 _ start inherits the temporal constraints of T _ duration. Given a task Tr (r = 1, 2, …, n), if Tr _ end-Tr _ start is default, the temporal constraints 0 ≤ Tr _ end - Tr _ start and Tr _ end - Tr _ start ≤ l (given T _ duration ≤ l) are inherited.
In the partial-order structure, assuming that a compound task T is decomposed into the subtasks T1, T2, …, Tn, the earliest start times inherit the temporal constraints of T _ start, and the latest end times inherit the temporal constraints of T _ end. Furthermore, each of the latest end times minus each of the earliest start times inherits the temporal constraints of T _ duration. Given a task Tr (r = 1, 2, …, n), if Tr _ end - Tr _ start is default, the temporal constraints 0 ≤ Tr _ end - Tr _ start and Tr _ end - Tr _ start ≤ l (given T _ duration ≤ l) are inherited.
In order to inherit the temporal constraints of high-level tasks, the earliest start tasks and the latest end tasks in subtask network should be selected. However, in the partial-order structure the subtasks have no explicit temporal sequence. It is impossible to decide directly which tasks happen earliest or end latest. Hence it is more realistic to search the earliest times and the latest ones according to their relationship in the temporal network
Definitions 6 and 7 provide the theoretical foundation for searching the earliest time-points and the latest ones. It means a time-point is one of the earliest time-points provided that there are no other time-points that precede it. Similarly, if there are no other time-points that are behind it, it is one of the latest time-points.
Depending upon the definitions, this study proposes an algorithm that searches the earliest time-points and the latest ones in a temporal network to inherit temporal constraints. The searching procedure is depicted in Algorithm 2. It is no doubt that the earliest time-points must be the start times of tasks and the latest time-points must be the end times of tasks. Therefore, Algorithm 2 searches the earliest time-points in the start times of tasks, and the latest time-points in the end times, respectively. The temporal network in the algorithm is represented by a distance graph, where a negative edge represents the temporal constraint that the terminus of the edge minus the origin is less than the negative weight of the edge [37]. Thus, Line 6 decides whether a start time is one of the earliest time-points via the outgoing negative edges, which is equal to Definition 6. Similarly, Line 8 decides whether an end time is one of the latest time-points via the incoming negative edges, which is equal to Definition 7.
Checking dynamic controllability
Having specified the temporal constraint management, the key issue is to discuss whether or not a DC plan can be obtained under those constraints. Thus, this section specifies the process in terms of checking dynamic controllability. In Section 6.1, we develop a temporal network of tasks, as well as discuss its dynamic controllability. Section 6.2 proposes two rules to boost the DC checking in planning.
Checking the dynamic controllability of the temporal network of tasks
For an executable plan regardless of uncontrollable durations, it is requisite to verify whether or not the plan is DC. One rational way is to check the dynamic controllability of the plan every time when new actions are added into it. Once the plan turns into be non-DC, the planning backtracks to search for other available actions. Nevertheless, the disadvantage of the aforementioned means is obvious that the planning will backtrack frequently when selecting applicable actions to meet the temporal constraints, which results in considerable computation. Therefore, this study explores a more efficient way which forms a temporal network of tasks in HTN planning and checks its dynamic controllability. The temporal network of tasks is constructed by the durations of tasks and the temporal constraints among tasks. The temporal network of tasks reflects the temporal network which corresponds to the HTN structure in planning. When the temporal network of tasks is non-DC, it means that the plans under the HTN structure are not DC. Therefore, to verify the temporal network of tasks is able to timely detect non-DC plans, instead of detecting until all the actions are instantiated. As a result, checking the dynamic controllability of the temporal network of tasks is more efficient and of help to search branches during HTN planning.
The temporal constraints in terms of the initial task network build the temporal network of tasks firstly. When a compound task is decomposed, its constraints in the temporal network are inherited and substituted by its subtasks, which then forms a new temporal network. Once the initial task network is decomposed into all primitive tasks, a DC plan is obtained. The dynamically controllability of the temporal network is maintained when compound tasks decompose. Therefore, checking the dynamic controllability of the temporal network of tasks includes two steps. Firstly, the temporal network of subtasks is verified. Because it is impossible for a task network to be DC provided that the subtask network is non-DC. It is able to detect non-controllability earlier and help to select a subtask network. Next, the temporal constraints of the compound task are inherited by the subtasks and the overall temporal network of tasks is verified.
Algorithm 3 depicts the detailed process of checking the dynamic controllability of the temporal network of tasks. We adopt an incremental way to check the dynamic controllability of the temporal network of tasks, because it is more suited for planning [38]. Algorithm 3 is supported by the state-of-the-art incremental DC checking algorithm EfficientIDC2 [39] at Line 7 and Line 15. The other reason why EfficientIDC2 is chosen is that it is the fastest incremental DC checking algorithm [40], which has the best performance. The first step, Lines 2–8, verifies whether the temporal network of the subtasks is DC. Line 3 selects a constraint and Line 5 judges whether it satisfies Rule 1 or Rule 2, which will be introduced in Section 6.2. At Line 9, Algorithm 2 is invoked to search the earliest time-points and the latest ones. They inherit the temporal constraints of the compound task respectively. Lines 10–16, as the second step, verify the overall network incrementally.
Boosting DC checking
During HTN planning, a large amount of the temporal constraints that have no effect on the dynamic controllability of the plan are produced. In addition, the number of them increases dramatically as the planning goes forward. Verifying those temporal constraints results in extra and useless computation. For this reason, two rules are explored to identify those constraints. The rules are specified as below.
The rules mean if there has been a constraint that has stronger binding than the constraint to be added, whether or not the new constraint is added into the STNU has no effect on its dynamic controllability. Nevertheless, the addition leads to futile computation at every verification which costs much time. For this reason, once a constraint is identified by the rules before being added into the STNU, it is neglected.
Empirical study
A realistic case of flood emergency response and the experimental results are discussed in this section to validate the effectiveness and efficiency of the planning approach. To begin with, the flood emergency response problem that is characterized by complex temporal requirements and uncontrollable durations is introduced. Next, the structures of the plan and the dispatched results are presented via a simple problem respectively. Finally, with the scale of the problem increasing, a set of experiments are conducted to demonstrate the performance of the planning approach. Every experiment is run twice by the planner, one applying Rule 1 and Rule 2 but the other not, to compare their performance. We also compare the proposed approach with the improved HTN planner SHOP2 on the same experiments. Although several efforts in planning allowing for uncertain durations are taken, to the best of our knowledge, there have been no previous works investigating uncontrollable durations in HTN planning so far. Therefore, we design our experiments to validate the planning approach.
Flood emergency response problem
Flood disaster is one of the most severe natural disasters in China. The emergency response tasks are required to be involved and they have qualitative or metric temporal relationships mutually. More important, due to unexpected emergencies, the durations of some actions in flood emergency response are uncontrollable. In this section, a realistic flood emergency response case is selected to validate the planning approach.
In view of the high level water in flood season, seepage often happens in the dam area w. Unless handled timely, it is likely to give rise to severe disasters or even dam break. Therefore, the flood emergency response problem in this paper is to mobilize a professional repairing team to the damaged dam w and to transfer tons of clay and stones there to block up the seepage area. There are several temporal constraints that have to be taken into account: (1) According to the weather forecast, a peak flow is coming soon. In order to prevent more severe damage, all the tasks should be completed in 24 hours. (2) Dam repairing cannot start until the repairing team arrives. (3) Similarly, dam repairing cannot start until all clay and stones are transported. (4) The required clay is dug out in the place x and the stones are mined in the quarry y. They are transferred to the damaged dam w concurrently.
An excerpt of the planning domain on flood disaster is given as an example in Fig. 3. An example of an operator has been shown in Fig. 1. Here we focus on a method. The method mission describes how to complete a task that transports material ?material to the disaster area ?to. It consists of four operators: ! load, ! transport, ! unload and ! return, which are constrained orderly.

Example of the planning domain.
Since the number of the trucks is limited, when the demand for the clay or the stones increases, the mobilized trucks have to commute repeatedly. Hence the scale of the problem increases. In view of the above consideration, eight problems with incremental scales are selected as Table 1 shows.
Flood emergency response problems
The structures of the plan and the dispatched results are shown via a simple problem. Next, as the scale of the problem increases, the performance is demonstrated. All the experiments are run on a Windows 7 PC with Intel Core quad-core processor 3.1 GHz and 4 GB RAM. We develop our planner based on SHOP2 and implement the proposed approach. The HTN planner and the dispatcher are both encoded in Common LISP.
The plan of Problem 1, the simplest one, is shown as Table 2. The action !load loads eight tons of clay onto the truck T1. The action !transport transports eight tons of clay from the site x where the clay is excavated to the dam area w. Then the action !unload unloads the clay and T1 returns to x by the action !return. Meanwhile, the action !mobilize mobilizes a professional repairing team team2 to the dam area w. Finally, team2 repairs the seepage area in w by !repair. Note that the start time of !repair means the action starts as soon as !mobilize ends or waits until six hours, whichever comes first. Next, we simulate the real execution situation and record the real dispatched results. The dispatched results are shown as Table 3. They accomplish the planning problem satisfying the temporal requirements.
The plan of Problem 1
The plan of Problem 1
The dispatched results of Problem 1
With the scale of the problem increasing, the planning approach is tested by the more complicated problems. The performance of the planning approach is demonstrated in two aspects. On the one hand, each problem is run twice by the planning approach, one applying the rules proposed in Section 6.2 and the other not, to compare their performance. On the other hand, since the existing HTN planning cannot handle the uncontrollable durations, we improve SHOP2 via modelling the uncontrollable durations by STNU, and run it on the same experiments. The experimental results are shown in Table 4. Each experiment is run five times and the average CPU time is recorded. Problem 7 and Problem 8 have no experimental results because there have been no DC plans for them under the temporal requirements of the problems. The data in the brackets of Problem 7 and Problem 8 are the average CPU time that is taken to detect there are no plans.
The average CPU time of Problem 1 to Problem 8
The results in Table 4 show that the improved SHOP2 needs more runtime in all the problems. Although the improved SHOP2 can handle the uncontrollable durations, it cannot detect non-DC plans early, which results in backtracking frequently. Furthermore as Fig. 4 shows, with the scale of the problem increasing, the planning approach applying Rule 1 and Rule 2 keeps high efficiency. Its performance benefits from pruning a mass of the temporal constraints that have no effect on the dynamic controllability of the plan.

Comparison between applying and not applying Rule 1 and Rule 2.
Emergency decision-making involves many tasks coordinating under complex temporal requirements. This situation is entangled by the uncontrollable durations of actions due to the uncertain factors in emergency response. This study proposes a novel temporal planning approach based on HTN with uncontrollable durations for emergency decision-making. The planning approach models the uncontrollable durations as temporal intervals by STNU. Temporal constraint management is enhanced in HTN planning, which includes representing and reasoning the temporal constraints among tasks and hierarchical temporal constraint inheritance in HTN planning. The temporal network of tasks is constructed and verified to obtain a DC plan more efficiently. The DC checking in planning is boosted. In addition, the dispatcher is devised to schedule the actions to be started in real time via monitoring the actions having been executed. The empirical study conducted on real flood emergency response validates the effectiveness and efficiency of the planning approach.
This study does not take into account the situation where different outcomes of uncontrollable durations may cause a conditional plan. It will be one of the future works. In addition, most current planning researches with uncontrollable durations assume resources are sufficient. However, the resource limitation poses new challenges. Our future work might explore the planning approach with uncontrollable durations under resource limitation.
Footnotes
Acknowledgments
This work was supported by the National Key Research and Development Plan (Grant No. 2016YFC0802509), and the National Natural Science Foundation of China (Grant Nos. 71371079, 71390524).
