HTN planning with uncontrollable durations for emergency decision-making

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

Hierarchical Task Network planning uncontrollable durations temporal management emergency decision-making

1 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.

2 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.

2.1 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].

2.2 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.

3 Formalism

This section introduces the necessary background firstly, and then defines our problem.

3.1 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.

Definition 1. A Simple Temporal Network with Uncertainty (STNU) is a 3-tuple N =< X, Lr, Lc >, where X is a set of time-points x₁, … x_n, divided into two disjoint sets of controllable time-points R and contingent time-points C. Lr is a set of requirement constraints R_ij = [a_ij, b_ij], formally a_ij ≤ x_j - x_i ≤ b_ij. Lc is a set of contingent constraints C_ij = [c_ij, d_ij], formally c_ij ≤ x_j - x_i ≤ d_ij. For the constraints C_ij we require x_j ∈ C and 0< c_ij < d_ij < ∞.

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.

Definition 2. An STNU is dynamically controllable (DC) if there exists a dynamic strategy for assigning controllable time-points during execution which guarantees that all of the constraints in the network will be satisfied no matter how the contingent durations turn out.

3.2 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 =< s₀, ω₀, D >, where s₀ is the initial state, ω₀ 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.

3.2.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.

Definition 3. (Operator) An operator is a 4-tuple O =< name (o) , pre (o) , effect (o) , duration (o) >,where name (o) is the name of the operator, pre (o) is a list of preconditions, effect (o) is the positive and negative effects, duration (o) is the duration of the operator which is represented as a temporal interval [p q]. p and q are both encoded as the functions of the variables which are in name and pre, and they are calculated when the operator is instantiated. Notice that if p = q the actions instantiated by the operator have the fixed durations.

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.

Fig.1

Example of an operator.

3.2.2 Method

A Method describes one way of accomplishing a compound task, which is defined formally.

Definition 4. (Method) A method is a 3-tuple M =< name (m) , temp (m) , sub (m) >, where name (m) is the name of the method, temp (m) is the temporal constraints which restrict the method, sub (m) is a 3-tuple sub (m) =< pre, subtasks, cons >, pre is the precondition, subtasks is the tasks in the subtask network, cons is a set of temporal constraints which constrain the temporal requirements among the subtasks.

3.2.3 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.

Definition 5. (Plan) A plan is represented as Π =< A₁, A₂, …, A_n > where A is a 3-tuple A =< a, θ_s, θ_d >, a is an action, θ_s is the start time of a, θ_d is the duration of a.

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.

4 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.

Fig.2

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 s₀ at the beginning. Task network ω is assigned by ω₀. The temporal network of tasks G is built by the temporal constraints of the tasks in ω₀. 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.

Algorithm 1. Planning algorithm: Planner(s₀, ω₀, D)
Input: the initial state s₀, the initial task network ω₀, the
planning domain D
Output: a DC plan Π
1. Π← ∅ , s ← s₀, ω ← ω₀, G ← temporal constraints of ω₀,
D =< O, M >
2. loop
3. ifω =∅ then end loop
4. non-deterministically choose a T ∈ ω
5. ifT is primitive task then
6. A ← {(a, σ) \| a is a ground instance of an operator, ∃σ,
σ (T) = head (a), s ⊨ pre (a)}
7. ifA =∅ then return failure
8. else
9. non-deterministically choose a pair (a, σ) ∈ A
10. s ← (s - effect^- (a)) ∪ effect⁺ (a)
11. a ← add θ_d
12. Π ← Π ∪ a
13. ω ← ω - T
14. else ifT is compound task then
15. C ← {(m, σ) \|m is an instance of a method, ∃σ, σ (T)
= head (m), s ⊨ pre (m)}
16. whileC≠ ∅ do
17. non-deterministically choose a pair (m, σ) ∈ C
18. construct the temporal network of subtasks S
19. if Check_TN(G, S) is not false then
20. ω ← ω - T ∪ subtasks
21. G ← Check _ TN (G, S)
22. quit while
23. end while
24. end loop
25. Π← assign θ_s from G
26. returnΠ

5 Temporal constraint management

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.

5.1 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.

5.2 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

Definition 6. Given a time-point λ, if there does not exist a temporal constraint u - λ ≤ a (a < 0) in the temporal network, λ is one of the earliest time-points.

Definition 7. Given a time-point μ, if there does not exist a temporal constraint μ - w ≤ b (b < 0) in the temporal network, μ is one of the latest time-points.

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.

Algorithm 2. Search the earliest time-points and the latest
time-points: Search_Points(G)
Input: a temporal network G
Output: a set of the earliest time-points earliest, a set of the
latest time-points latest
1. str← the start times of all the tasks
2. end← the end times of all the tasks
3. earliest← ∅, latest← ∅
4. whilestr≠ ∅ or end≠ ∅ do
5. select s from str and select e from end
6. if there is no outgoing negative edges then
7. earliest ← s ∪ earliest
8. if there is no incoming negative edges then
9. latest ← e ∪ latest
10. str ← str - s, end ← end - e
11. end while
12. returnearliest, latest

6 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.

6.1 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.

Algorithm 3. Check the dynamic controllability of the temporal
network of tasks: Check_TN(E, S)
Input: a current temporal network E, a temporal network of
subtasks S
Output: a DC temporal network of tasks G
1. G← ∅
2. whileS≠ ∅ do
3. select e from S
4. S ← S - e
5. ife does not satisfy Rule 1 or Rule 2 then
6. add e into G
7. ifG is non-DC then return false
8. end while
9. inherit and substitute the temporal constraints of the
compound task in E by Search_Points(G)
10. whileE≠ ∅ do
11. select e from E
12. E ← E - e
13. ife does not satisfy Rule 1 or Rule 2 then
14. add e into G
15. ifG is non-DC then return false
16. end while
17. returnG

6.2 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.

Rule 1. Given a temporal constraint p ≤ x - y in a STNU, if a temporal constraint to be added m ≤ x - y satisfies m ≤ p, the constraint to be added is neglected.

Rule 2. Given a temporal constraint x - y ≤ q in a STNU, if a temporal constraint to be added x - y ≤ n satisfies n ≥ q, the constraint to be added is neglected.

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.

7 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.

7.1 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.

Fig.3

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.

Table 1

Flood emergency response problems

Problem	Amount of	Amount of	Mobilized	Round-trip	Number of
number	clay (ton)	stones (ton)	trucks	trucks	commuting
1	8	0	T1	–	0
2	7	7.8	T1, TA	–	0
3	14.5	7.8	T1, T2, TA	–	0
4	14.5	13.2	T1, T2, TA, TB	–	0
5	22.1	13.2	T1, T2, TA, TB	T1	1
6	30.9	13.2	T1, T2, TA, TB	T1, T2	2
7	36.7	13.2	T1, T2, TA, TB	T1, T2	3
8	30.9	20.1	T1, T2, TA, TB	T1, T2, TA	4

7.2 Experimental results

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.

Table 2
The plan of Problem 1

Actions Start time Duration

(!load T1 8 clay) [0.0 0.0] [0.3 0.3]

(!transport T1 x w 8 clay) [0.3 0.3] [0.9 1.1]

(!unload T1 8 clay) [1.2 1.4] [0.3 0.3]

(!return T1 w x) [1.5 1.7] [0.7 0.9]

(!mobilize team2 w) [0.0 0.0] [3.0 4.0]

(!repair team2 w) < (mobilize team2) end, 6> [16 18]

Actions	Start time	Duration
(!load T1 8 clay)	[0.0 0.0]	[0.3 0.3]
(!transport T1 x w 8 clay)	[0.3 0.3]	[0.9 1.1]
(!unload T1 8 clay)	[1.2 1.4]	[0.3 0.3]
(!return T1 w x)	[1.5 1.7]	[0.7 0.9]
(!mobilize team2 w)	[0.0 0.0]	[3.0 4.0]
(!repair team2 w)	< (mobilize team2) end, 6>	[16 18]

Table 3

The dispatched results of Problem 1

Actions	Start time	Duration
(!load T1 8 clay)	0.0	0.3
(!transport T1 x w 8 clay)	0.3	1.0
(!unload T1 8 clay)	1.3	0.3
(!return T1 w x)	1.6	0.9
(!mobilize team2 w)	0.0	3.7
(!repair team2 w)	3.7	17.8

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.

Table 4

The average CPU time of Problem 1 to Problem 8

Problem number	Average CPU time (second)
	Applying Rule 1 and Rule 2	Not applying Rule 1 and Rule 2	Improved SHOP2
1	0.031	0.109	0.187
2	0.125	0.437	0.515
3	0.515	2.621	3.994
4	3.885	10.745	14.728
5	4.337	19.254	25.771
6	8.470	78.282	131.291
7	no plans (0.203)	no plans (2.278)	no plans (2.950)
8	no plans (0.421)	no plans (3.479)	no plans (4.227)

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.

Fig.4

Comparison between applying and not applying Rule 1 and Rule 2.

8 Conclusions and future work

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).

References

Erol

, Hendler

and Nau

, HTN planning: Complexity and expressivity, Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, Washington, USA, 1994, pp. 1123–1128.

Asunción

M.D.L.

, Castillo

, Fdez-Olivares

, García-Pérez

Ó.

, González

and Palao

, SIADEX: An interactive knowledge-based planner for decision support in forest fire fighting, AI Communications18(4) (2005), 257–268.

Biundo

and Schattenberg

, From abstract crisis to concrete relief: A preliminary report on combining state abstraction and htn planning, Proceedings of the 6th European Conference on Planning, Toledo, Spain, 2001, pp. 157–168.

Erol

, Hendler

and Nau

, UMCP: A Sound and Complete Procedure for Hierarchical Task-network Planning, Proceedings of the 2nd International Conference on Artificial Intelligence Planning Systems, Chicago, Illinois, USA, 1994, pp. 249–254.

Currie

and Tate

, O-Plan: The open planning architecture, Artificial Intelligence52(1) (1991), 49–86.

Ntuen

C.A.

, Balogun

, Boyle

and Turner

, Supporting command and control training functions in the emergency management domain using cognitive systems engineering, Ergonomics49(12-13) (2006), 1415–1436.

Smirnov

, Pashkin

, Chilov

and Levashova

, Context-based disaster management support, Proceedings of the IEEE Workshop on Distributed Intelligent Systems: Collective Intelligence and Its Applications (DIS’ 06), Prague, Czech Republic, 2006, pp. 291–296.

Turoff

, Chumer

, Van de Walle

and Yao

, The design of a dynamic emergency response management information system, Journal of Information Technology Theory and Application5(4) (2004), 1–36.

Vidal

and Fargier

, Handling contingency in temporal constraint networks: From consistency to controllabilities, Journal of Experimental & Theoretical Artificial Intelligence11(1) (1999), 23–45.

10.

Morris

, Muscettola

and Vidal

, Dynamic control of plans with temporal uncertainty, Proceedings of the 17th International Joint Conference on Artificial Intelligence, Seattle, Washington, USA, 2001, pp. 494–502.

11.

Tang

and Shen

G.Q.

, Decision-making model to generate novel emergency response plans for improving coordination during large-scale emergencies, Knowledge-Based Systems90 (2015), 111–128.

12.

Mausam and Weld

D.S.

, Planning with durative actions in stochastic domains, Journal of Artificial Intelligence Research31(1) (2008), 33–82.

13.

Beaudry

, Kabanza

and Michaud

, Planning for Concurrent Action Executions Under Action Duration Uncertainty Using Dynamically Generated Bayesian Networks, Proceedings of the 20th International Conference on Automated Planning and Scheduling, Toronto, Ontario, CA, 2010, pp 10–17.

14.

Vidal

and Ghallab

, Dealing with Uncertain Durations In Temporal Constraint Networks dedicated to Planning, Proceedings of the 12th European Conference on Artificial Intelligence, Budapest, Hungary1996, pp. 48–54.

15.

Nilsson

, Kvarnström

and Doherty

, Efficientidc: A faster incremental dynamic controllability algorithm, Proceedings of the 24th International Conference on Automated Planning and Scheduling, Portsmouth, New Hampshire, USA, 2014.

16.

Cimatti

, Micheli

and Roveri

, Strong temporal planning with uncontrollable durations: A state-space approach, Proceedings of the 29th AAAI Conference on Artificial Intelligence, Austin, Texas, USA, 2015, pp. 3254–3260.

17.

Coles

, Coles

, Fox

, Long

, COLIN: lanning with continuous linear numeric change, Journal of Artificial Intelligence Research44 (2012), 1–96.

18.

Micheli

, Do

and Smith

D.E.

, Compiling Away Uncertainty in Strong Temporal Planning with Uncontrollable Durations, Proceedings of the 24th International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina, 2015, pp. 1631–1637.

19.

Cimatti

, Micheli

and Roveri

, Timelines with Temporal Uncertainty, Proceedings of the 27th AAAI Conference on Artificial Intelligence, Bellevue, Washington, USA, (2013), 195–202.

20.

Barták

, Morris

R.A.

and Venable

K.B.

, An Introduction to Constraint-Based Temporal Reasoning, Morgan & Claypool Publishers, 2014.

21.

Wilkins

D.E.

, Can AI planners solve practical problems?Computational intelligence6(4) (1990), 232–246.

22.

Wilkins

D.E.

, Practical planning: Extending the classical AI planning paradigm, Morgan Kaufmann, 2014.

23.

Tate

, Drabble

and Kirby

, O-Plan2: An open architecture for command, planning and control, In Intelligent Scheduling, Morgan Kaufmann, 1994, pp. 213–239.

24.

Nau

, Au

T.C.

, Ilghami

, Kuter

, Murdock

J.W.

, Wu

and Yaman

, SHOP2: An HTN planning system, Journal of Artificial Intelligence Research20 (2003), 379–404.

25.

Yorke-Smith

, Exploiting the Structure of Hierarchical Plans in Temporal Constraint Propagation, Proceedings of the 20th National Conference on Artificial Intelligence, Pittsburgh, Pennsylvania, USA, 2005, pp. 1223–1228.

26.

Dechter

, Meiri

and Pearl

, Temporal constraint networks, Artificial Intelligence49 (1991), 61–95.

27.

Castillo

, Fernández-Olivares

, Garcia-Perez

and Palao

, Efficiently Handling Temporal Knowledge in an HTN Planner, Proceedings of the 17th International Conference on Automated Planning and Scheduling, Cumbria, UK, 2006, pp. 63–72.

28.

Goldman

R.P.

, Durative Planning in HTNs, Proceedings of the 17th International Conference on Automated Planning and Scheduling, Cumbria, UK, 2006, pp. 382–385.

29.

Yaman

, Benyo

and Mulvehill

A.M.

, Temporal Milestones in HTNs, Proceedings of the 27th AAAI Conference on Artificial Intelligence, Bellevue, Washington, USA, 2013.

30.

Biundo

, Holzer

and Schattenberg

, Project planning under temporal uncertainty, In Planning, Scheduling, and Constraint Satisfaction: From Theory to Practice, IOS Press, 2004, pp. 189–198.

31.

Georgievski

and Aiello

, HTN planning: Overview, comparison, and beyond, Artificial Intelligence222 (2015), 124–156.

32.

Shah

, Stedl

, Williams

and Robertson

, A Fast Incremental Algorithm for Maintaining Dispatchability of Partially Controllable Plans, Proceedings of the 17th International Conference on Automated Planning and Scheduling, Providence, Rhode Island, USA, 2007, pp. 296–303.

33.

Wilkins

D.E.

, Myers

K.L.

, Lowrance

J.D.

and Wesley

L.P.

, Planning and reacting in uncertain and dynamic environments, Journal of Experimental & Theoretical Artificial Intelligence7(1) (1995), 121–152.

34.

Morris

and Muscettola

, Execution of temporal plans with uncertainty, Proceedings of the 17th National Conference on Artificial Intelligence, Austin, Texas, USA, 2000, pp. 491–496.

35.

Ghallab

, Nau

, Traverso

, Automated planning: Theory & practice, Elsevier, 2004.

36.

Estlin

T.A.

, Chien

S.A.

and Wang

, Hierarchical task network and operator-based planning: Two complementary approaches to real-world planning, Journal of Experimental & Theoretical Artificial Intelligence13(4) (2001), 379–395.

37.

Stedl

and Williams

, A fast incremental dynamic controllability algorithm, Proceedings of the International Conference on Planning and Scheduling Workshop on Plan Execution: A Reality Check, Monterey, California, USA, 2005, pp. 69–75.

38.

Nilsson

, Kvarnström

and Doherty

, Efficient processing of simple temporal networks with uncertainty: Algorithms for dynamic controllability verification, Acta Informatica (2015), 1–30.

39.

Nilsson

, Kvarnström

and Doherty

, Incremental dynamic controllability in cubic worst-case time, Proceedings of the 21st International Symposium on Temporal Representation and Reasoning, Verona, Italy, 2014, pp. 17–26.

40.

Hunsberger

, Efficient execution of dynamically controllable simple temporal networks with uncertainty, Acta Informatica (2015), 1–59.