Resource-constrained Hierarchical Task Network planning under uncontrollable durations for emergency decision-making

Abstract

Emergency decision-making confronts a problem where emergency tasks coordinating to achieve emergency objectives are subject to urgent time and limited resources. Actions with uncontrollable durations make the problem more complicated. This paper proposes a novel resource-constrained Hierarchical Task Network planning approach under uncontrollable durations for emergency decision-making. The objective is to generate a dynamically controllable plan with constrained resources and execute the plan via scheduling actions dynamically. Two of the most general categories of resources in emergency decision-making, consumable resources and reusable resources, are considered. First, timed initial literals are extended to present timed resources and the constraints of timed literals are transformed to impose restrictions on actions in planning. Second, a mechanism is explored to hierarchically inherit the resource constraints of compound tasks by subtasks during Hierarchical Task Network planning. Third, two categories of resource constraints are checked, respectively. Potential resource conflicts are resolved via adding precedence constraints. Finally, experimental studies are conducted to evaluate the planning approach. The results demonstrate the effectiveness and efficiency of the planning approach for emergency decision-making.

Keywords

Hierarchical Task Network planning resource reasoning uncontrollable durations emergency decision-making

1 Introduction

One of the most critical issues of emergency decision-making is to deploy emergency tasks with limited resources and finite time. In view of severe scarcity of resources and time urgency, the emergency response is a complex mixture of emergency tasks deploying, time scheduling and resource allocation [1], in which resources and temporal issues are closely related. However, due to the uncertain events of emergencies, there is uncertainty about the durations of actions. Since the action durations are subject to unpredicted events that are not under control, the exact durations cannot be predefined precisely. Furthermore, due to the uncontrollable durations, resource allocation to actions cannot be decided in advance either, which makes emergency response under uncontrollable durations more complicated. For instance, a charging crane in the disaster area, as a rare emergency resource, loads cargos for trucks. As the loading is influenced by lots of uncontrollable exoteric factors, the loading duration is uncontrollable. What is more, the uncertain period of occupying the crane leads difficulty for other trucks in deciding when to be loaded. Therefore, the emergency task planning with uncontrollable durations and limited resources poses challenges.

Hierarchical Task Network (HTN) planning [2, 3] is an effective artificial intelligence planning technique. Due to the powerful reasoning, well expressive representation and good support for large-scale domains, especially the similarity with decision-making process of human being, HTN planning is particularly suitable for emergency task planning and has been successfully applied in a huge number of real-world emergency cases [4 –8]. So far, there have been many efforts in HTN planning considering time and resources [9 –11], but the approaches all just work in deterministic temporal domains where the durations of actions are certain and fixed, which motivates this study to explore resource-constrained HTN planning under uncontrollable durations.

To react to uncontrollable durations and resource allocation, it is vital for emergency decision-making to develop a flexible plan which takes into account uncontrollable durations beforehand and to consider limited resources. As one category of temporal flexible plans, dynamically controllable (DC) plans [12, 13] 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. To generate the DC plans, the uncontrollable durations are modelled as contingent temporal intervals by Simple Temporal Network with Uncertainty (STNU) [12, 14].

However, there still remain challenges. To begin with, the dynamic controllability of the plan should be guaranteed during planning. Checking the dynamic controllability of the plan poses challenge to HTN planning. Second, the amount of a resource consumed or used by an action may be determined by the duration. For instance, the fuel consumed by a truck increases with the duration of transportation. As the duration is uncontrollable, the amount of the resource is uncertain as well. Third, the uncertain periods of occupying resources resulted from the uncontrollable durations bring complication in distinguishing the parallel actions, which also makes it hard to allocate the resources for the succeeding actions.

Motivated by the above analysis, this study proposes a novel resource-constrained HTN planning approach under uncontrollable durations for emergency decision-making. The study takes into consideration two of the most general categories of resources in emergency decision-making: consumable resources and reusable resources. With the objective to react to the uncontrollable durations and to handle the constrained resources, a planner is devised to generate a flexible plan with constrained resources, and a dispatcher is developed to dynamically schedule the start times of the actions in the plan during execution. First, timed initial literals are extended to present timed resources and the constraints of the literals are transformed to impose restrictions on actions in planning. Second, a mechanism is explored to hierarchically inherit the resource constraints of compound tasks by subtasks during HTN planning. Third, we analyze the temporal relationships of actions in the temporal network and develop an algorithm to search parallel actions. Depending upon that, resource constraints are checked. Finally, potential resource conflicts are resolved via adding precedence constraints.

This paper is organized as follows. Section 2 reviews the related work on temporal planning with resources. Section 3 presents the formalism, definitions and notations extended in this study. Next, Section 4 gives an overview of the architecture of the planning approach, and explicates the main planning algorithm. In Section 5, we focus on hierarchical resource inheritance, resource constraint checking and potential resource conflict resolution. Section 6 surveys empirical evaluation and results of experiments. Finally, Section 7 concludes this paper and discusses future work.

2 Literature review

This section reviews the existing works related with our approach. Although our approach concentrates on HTN planning, some non-HTN planning paradigms provide a theoretical foundation. Thus, they are also discussed in this section. Since temporal reasoning is closely related with resource management, this section then introduces the temporal foundation of the planning with constrained resources. More detailed introduction to the temporal foundation is discussed in the book [15].

2.1 Resource-constrained HTN planning

A resource is an entity that one needs to use or to consume (e.g., a tool, a machine, or energy) to perform an action. Resource-constrained planning addresses the problem of how to find a set of actions for achieving a goal using a limited number of resources in a limited amount of time. There have been some resource-constrained HTN planning approaches. SIPE-2 (System for Interactive Planning and Execution) [9, 16] is capable to reason on reusable resources and consumable resources based on the mechanisms of numerical quantities reasoning. Although SIPE-2 exploits a heuristic to solve the resource conflicts in parallel actions, it does not reason about different possible orderings of the parallel actions. In addition, SIPE-2 merely computes the minimal range and the maximal range for which the parallel actions exist. Thus SIPE-2 cannot cope with the resources used by actions with uncertain durations. O-Plan2 (the Open Planning Architecture) [17], improved upon O-Plan [10], develops a resource utilization manager to detect resource utilization though optimistic and pessimistic profiles. However, since O-Plan and O-Plan2 both manage the temporal constraints based on time-points, they cannot reason on resources in non-deterministic temporal domains. REHTN (Resource Enhanced Hierarchical Task Network) [11] enhances HTN planning on resources in two aspects: hierarchical resource reasoning and accelerating resource constraint propagation. Since REHTN defines the resource timelines based on Simple Temporal Network (STN) to allocate resources, it does not work when the durations of actions are uncertain. FAPE (Flexible Acting and Planning Environment) [18] distinguishes four classes of resources: consumable resources, producible resources, discrete resources and reservoirs. Although FAPE can check the dynamic controllability of a plan, it determines the consistency of resources using the algorithms designed for deterministic temporal problems. Hence FAPE cannot resolve the resource conflicts resulted from actions with uncontrollable durations. Qi et al. [19] propose an HTN planning algorithm to cope with multi-capacity discrete resources by state updating rules. But the algorithm also uses STN to represent temporal constraints which is not feasible in non-deterministic temporal domains.

2.2 Resource-constrained non-HTN planning

Besides the above HTN planning approaches, some typical non-HTN planners have investigated resource problems. IxTeT (Indexed Time Tables) [20] detects and solves sharable resource conflicts via minimal critical sets. IxTeT relies on time-points and indirectly keeps the temporal consistency. It cannot handle resources when the durations of actions are uncontollable. The enhanced parcPLAN planner (Planning Architecture with Parallel Actions, Resources and Constraints) [21] integrates temporal and resource reasoning by Boolean meta-variables. Cesta and Stella [22] define the time and resource problem and propose two propagation techniques: the profile propagation and the order propagation. Filuta [23] integrates known techniques for time and resources, which describes resource constraints by state-variables and guides the search procedure by means of domain transition diagrams. However, all the three aforementioned planning approaches manage temporal representation and reasoning based on STN, which only work deterministic temporal domains. They cannot deal with the resource problem under uncontrollable durations. Kvarnström et al. [24] extend TALplanner (Temporal Action Logic planner) [25] to generate concurrent plans, where operators have varied durations and internal state; and to deal with several different types of resources. But TALplanner does not cope with the resource conflicts caused by actions with uncontrollable durations.

2.3 Temporal reasoning

Several works exploit STN to present and check temporal constraints, and to provide the necessary foundation for resource management. A Simple Temporal Network (STN) consists of a set of real variables called time-points and a set of requirement constraints. However, STN cannot handle uncertain constraints and the aforementioned STN-based works are unable to deal with uncertain durations.

A Simple Temporal Network with Uncertainty (STNU) augments an STN to include a set of contingent constraints, where each contingent constraint represents an uncontrollable duration. An STNU is dynamically controllable (DC) if there exists a dynamic strategy for assigning the controllable time-points during execution which guarantees that all of the constraints are satisfied no matter how the contingent durations turn out. The recent studies on verifying the dynamic controllability of STNU can be divided into two major classes: full DC-checking algorithms such as Morris’ algorithms [13 , 26–28] and incremental DC-checking algorithms such as FastIDC (Fast Incremental Dynamic Controllability) [29, 30], EfficientIDC (Efficient Incremental Dynamic Controllability) [31] and EfficientIDC2 [32]. To cope with constrained resources under uncontrollable durations, this study models the uncontrollable durations as contingent temporal intervals by STNU and checks the dynamic controllability of the plan by the incremental DC-checking algorithm.

3 Problem formulation

Emergency task planning, as the core of emergency decision-making, can be typically modelled as an HTN problem. In this section we formulate the problem using the HTN model. This section concentrates on the extensions with respect to uncontrollable durations and resources, and the rest of the formulations are similar to the classical HTN planning such as SHOP2 (Simple Hierarchical Ordered Planner) [33]. This section discusses the resource-constrained planning problem with uncontrollable durations firstly and then specifies the main extensions on the planning components. Next, the plan to the problem is introduced. Finally, a running example is given to illustrate the HTN model.

The resource-constrained planning problem with uncontrollable durations is a 3-tuple P = (s₀, ω₀, D), where s₀ is the initial state, ω₀ is the initial task network, D is a planning domain. The state is a set of ground literals. The planning domain is defined as D = (O, M) where O is a set of operators and M is a set of methods.

3.1 Timed initial literals

In real-world domains, resources are not available all the times. Some resources can only be employed or mobilized under certain temporal restrictions. For instance, a road can be cordoned off for emergency vehicles only within a specific time window. Therefore, the timed resources are presented by extended timed initial literals.

Definition 1. (Timed initial literal) A timed initial literal is defined as l = (literal constraints) where literal is a predicate and constraints are a set of the timed constraints on literal.

Unlike the simple metric descriptions in Planning Domain Definition Language (PDDL) 2.2 [34] and PDDL 3.0 [35], constraints represent the complex quantitative temporal constraints on literal such as time windows and deadline. A timed initial literal represents that literal is true when constraints are satisfied. The temporal constraints will be transformed and imposed on the action when the precondition of an action contains the literal, which will be discussed in Section 4.2 in detail.

3.2 Domain knowledge

Domain knowledge consists of a set of operators and a set of methods. To handle uncontrollable durations and limited resources, operators should model the uncontrollable duration by an interval, rather than a fixed value. Furthermore, resources should be specified in operators. However, the existing HTN planning paradigms [36] do not address those. Therefore, operators are enhanced with regard to constrained resources and uncontrollable durations. They are defined below, respectively, and the examples will be given in Section 3.5.

Definition 2. (Operator) An operator is a 5-tuple O = (name (o), pre (o), effect (o), duration (o), resource (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 defined as a temporal interval [p q]. p and q are the functions of the variables which are represented in name and pre. They are calculated when the operator is instantiated. Notice that if p = q the actions instantiated by the operator have the fixed durations;

resource (o) is a set of the resources consumed or used by the operator, which is defined as resource (o) = {(R, Q)} where R is a consumable resource or a reusable resource and Q is the amount of R. The consumable resource is consumed when the operator is instantiated while the reusable resource is used during the execution and then released. Q can be the function of duration (o), which is an interval [Q_min Q_max] accordingly. Q_min and Q_max are calculated when the operator is instantiated.

A method describes one way of accomplishing a compound task. On the one hand, the temporal restrictions on the method should be indicated such as makespan and precedence. The resource limitations should also be specified. On the other hand, the temporal constraints among subtasks are enhanced to present the temporal relationships of the subtasks.

Definition 3. (Method) A method is a 4-tuple M = (name (m), taskres (m), tasktemp (m), sub (m)) where

name (m) is the name of the method;

taskres (m) is a set of resource constraints on m, which is defined as taskres (m) = {(R, b)}. R is a consumable resource or a reusable resource and b is maximum available amount of R for m;

tasktemp (m) is a set of temporal constraints on m;

sub (m) is a 3-tuple sub = (pre, subtasks, tempcons), where pre is the precondition, subtasks is the tasks in the subtask network, tempcons is a set of temporal constraints among subtasks.

In real emergency responses, resources are often scarce. A method has the resource constraints which describe the upper bound of the available resources for the method. The resources used or consumed by the subtasks cannot exceed the amount. There are no mandatory requirements for a method to at least use or consume a certain amount of resources. Therefore, the lower bound on the resources is not constrained. The operators are instantiated into the actions as well as the used or consumed resources. The resource constraints presented in the methods will be inherited and be checked, which are elaborated in the subsequent sections.

3.3 Task network

A task network reflects the problem solving process including decomposing compound tasks and instantiating primitive tasks. Extending the traditional task network in HTN, resource constraints and temporal constraints are explicitly kept track of. Each constraint specifies a requirement that must be satisfied by the tasks in the task network. The formalism is defined as follows.

Definition 4. (Task network) A task network is a 3-tuple ω = (U, RC, TC) where

U is a set of task nodes;

RC (u) = {(R, b)} is a set of resource constraints, where R is a consumable resource or a reusable resource, b denotes the maximum available amount of R by the task u;

TC is a set of temporal constraints.

3.4 Plan

A Plan is a solution to a planning problem. Given uncontrollable durations and limited resources, the plan with exact start time-points and fixed durations fails when uncontrollable durations happen. Therefore, we consider uncontrollable durations beforehand and generate the DC plans. In addition, the allocated resources should be explicated for the actions in the plan. Thus, the plan is maintained temporally robust and is dispatched dynamically in execution. The formalism is defined as follows, and a detailed example of the plan will be given in the experiment section.

Definition 5. (Plan) A plan is defined as π = (Ac, Res, Tim) where

Ac is a set of actions;

Res is a list of the resources allocated to each action in Ac;

Tim = (starttime, endtime, duration, rel) is an STNU where starttime is a set of time-points which denote the start of the actions in Ac, endtime is a set of time-points which denote the end of the actions in Ac, duration contains the durations of the actions in Ac, rel contains relative time relationships between those time-points.

3.5 A running example

A running example is given in this section to illustrate the HTN model. A reservoir is damaged by a flood and the planning problem is to transport several tons of clay to the disaster area by trucks. A method can achieve the problem by decomposing the compound task into four primitive tasks: load, transport, unload and return. The method is given in Fig. 1. The method describes how to complete a task that transports the material ?material to the disaster area ?to. It consists of four operators: !load, !transport, !unload and !return, which are ordered. As resources are scarce in the disaster area, only one truck can be used and 500 liters of fuel can be consumed. Given the tight deadline for emergency, the task must be completed in three hours. The two aforementioned requirements are formulated as resource constraints and temporal constraints respectively.

Fig.1

Example of a method.

The operators, !load, !transport and !return, have the uncontrollable durations. The operator !transport depicts how to transport the material ?material from the location ?from to the location ?to by the truck ?truck. The duration is determined by the variables including the speed and the mileage. The operator uses a truck during the execution and consumes fuel. The fuel consumption is determined by the mileage. The operator is given in Fig. 2. The operator !load loads clay on the trucks and the operator !unload unloads. The trucks return by the operator !return.

The planning problem is hierarchically decomposed into the four primitive tasks by the method, and the primitive tasks are instantiated into the actions. The actions consume fuel and use the truck. Meanwhile the actions inherit and are restricted by the resource constraints and the temporal constraints in the method. The resource constraints are checked at each planning step. The detailed planning process and the time and resource reasoning will be discussed in the subsequent sections.

Fig.2

Example of an operator.

4 Planning process

In this study, resources and time reasoning are tightly integrated into planning, rather than being separately allocated after a plan is generated, because most of real problems are overconstrained and the separate processing cannot cope with the complicated problems with a huge number of constraints [37]. This section firstly gives a concise overview of the planning approach and then explicates the planning algorithm.

4.1 Framework

The planning approach mainly consists of two components as Fig. 3 illustrates: a planner and a dispatcher. The planner takes as inputs a planning problem and outputs a DC plan with the allocated resources. The dispatcher takes as input the DC plan and schedules the start times of the actions to be started via monitoring the actions having been executed during the plan execution. The dispatcher is developed based upon the STNU execution [38]. As a result, the planning approach keeps flexibility until execution so that it is able to react to the uncontrollable durations.

Fig.3

The framework of the planning approach.

The planner handles the constrained resources and the uncontrollable durations by the coordination of the action reasoning core, the resource manager and the temporal reasoning module. Actions are instantiated using the HTN principles [2]. The action reasoning core refines abstract tasks for a partial plan and incrementally constructs an STNU based upon the temporal constraints. The temporal reasoning module checks its dynamic controllability. The resource manager deals with resource reasoning via hierarchical resource constraint inheritance, checking resource constraints and resolving potential resource conflicts. Once potential conflicts are detected, the manager attempts to resolve the potential conflicts via adding precedence constraints.

4.2 Planning algorithm

As Algorithm 1 depicts, the planning algorithm takes as input a planning problem P = (s₀, ω₀, D) as well as the initial partial plan ψ₀ and the initial temporal network G₀, and outputs a plan π. The partial plan ψ contains the actions that have been instantiated during planning, and G is the temporal network corresponding to ψ. They are the variables of the planning algorithm. In general, ψ₀ and G₀ are empty sets. To guarantee to backtrace when there are no applicable instances of operators or methods to search, the algorithm plans each step recursively.

When the current task is a primitive task (Lines 3–20), an operator is instantiated. Before the action comes into effect, two major steps are required: dynamic controllability checking and resource checking. First, the algorithm incrementally constructs a temporal network G′ based on the current partial plan, and checks its dynamic controllability (Lines 7–8). When the action uses or consumes a resource, it should be restricted by the timed constraints of the resource. If the precondition of the action contains the timed initial literals, the constraints of the literals are transformed to add into temporal network. Those constraints define the feasible time periods with regard to constrained resources when the action can be executed. Besides the timed constraints, the temporal network is constructed via adding the temporal constraints of the task TC (T) and the duration of the action duration (a). There are two reasons for verifying the temporal network in Line 8. On the one hand, if the current partial plan is not DC, it is not necessary to check the resources any more. This verification avoids useless computation. On the other hand, a DC plan underlies the latter analysis regarding the temporal relationship of actions. In this study, the algorithm adopts the incremental DC checking to verify the constructed temporal network, in that it is more suitable for planning [39]. It is supported by the state-of-the-art algorithm EfficientIDC2 [32]. Second, the algorithm checks the resource constraints (Line 9 and Line 12), which will be introduced in Section 5.2. Provided that there exits potential resource conflicts, they are attempted to be resolved (Lines 10–11), which will be introduced in Section 5.3 in more detail. If the conflicts cannot be resolved, another action instance is selected. When the temporal network is DC and the resources are consistent, the action changes the state, and is appended to the partial plan with its resources (Lines 13–15). Meanwhile, the task network is updated (Line 16).

When the current task is a compound task (Lines 21–31), an instance of the method is selected. The temporal constraints of the task TC (T) are inherited and updated (Line 25). The subtasks inherit the resource constraints of the task RC (T) (Line 26), which will be introduced in Section 5.1 in more detail. And the subtasks are also restricted by the constraints among them. Meanwhile, the task network is updated (Line 27).

Finally, once all the compound tasks are decomposed and the primitive tasks are instantiated, namely ω =∅, π is generated via being assigned by ψ (Line 33). Tim in π is assigned by G (Line 34). A plan is outputted (Line 35).

Algorithm 1. Planning algorithm: Plan (s, ω, D, ψ, G)
Input: the current state s, the task network ω, the planning
domain D, the current partial plan ψ, the temporal network G
Output: a plan π
1. ifω≠ ∅ then
2. non-deterministically pop a T ∈ ω that has no predecessors
in ω
3. ifT is a primitive task then
4. Active ← {(a, σ) \|a is a ground instance of an operator,
σ is a substitution such that a is relevant for σ (T), a is
applicable to s}
5. whileActive≠ ∅ do
6. non-deterministically pop a pair (a, σ) ∈ Active
7. G′← incrementally expand G by adding TC (T),
duration (a) and the timed constraints
8. ifG′ is DC then
9. if detecting potential resource conflicts by
Search_actions then
10. select the actions with the conflict Δ
11. G′← Resolve_conflicts (Δ, G′)
12. if there are no resource conflicts then
13. s′ ← (s - effect^- (a)) ∪ effect⁺ (a)
14. a ← add res
15. ψ′ ← ψ ∪ a
16. ω′ ← ω - T
17. π ← Plan (s′, ω′, D, ψ′, G′)
18. ifπ is not failure then returnπ
19. end while
20. ifActive =∅ then return failure
21. else ifT is a compound task then
22. Active ← {(m, σ) \|m is a ground instance of a method,
[-0.2pt] σ is a substitution such that m is relevant for σ (T),
m is applicable to s}
23. whileActive≠ ∅ do
24. non-deterministically pop a pair (m, σ) ∈ Active
25. TC′← inherit TC (T) by the earliest and the latest
[-0.2pt] subtasks, add tasktemp (m)
26. RC′← inherit RC (T) by the subtasks, add taskres (m)
27. ω′ ← ω - T ∪ subtasks
28. π ← Plan (s, ω′, D, ψ, G)
29. ifπ is not failure then returnπ
30. end while
31. ifActive =∅ then return failure
32. else ifω =∅ then
33. π ← ψ
34. π← assign G
35. returnπ

5 Resource management

Having specified the framework and the main planning algorithm, this section focuses on the resource management for planning. This study concentrates on two of the most general categories of resources in emergency decision-making: consumable resources and reusable resources [40]. A consumable resource is a resource that is consumed by an action, while a reusable resource is a resource that is used by an action during its execution and is released when the action ends. The two resources have different properties, which determine different behaviors and constraints. Hence, in this paper we discuss the two resources, respectively.

The framework of resource management is shown as Fig. 4. Hierarchical resource constraint inheritance provides intact constraints for the later resource analysis. Analyzing action relationships severs for detecting resource conflicts. When potential resource conflicts are checked, they are resolved via adding precedence constraints.

Fig.4

The framework of the resource management.

5.1 Hierarchical resource constraint inheritance

Hierarchical resource constraint inheritance occurs when a compound task decomposes, namely the compound task propagates its resource constraints to subtasks. This study proposes a resource constraint inheritance mechanism in HTN planning with uncontrollable durations. The aim is to keep intact constraints during planning.

The hierarchical resource constraint inheritance is closely related to the way of task decomposing. There are two types of task decompositions in HTN planning: total-order task decomposition and partial-order task decomposition [41], which specify two ways of forming new task network in planning. Assume a compound task C decomposes into the compound tasks C₁, C₂, …, C_n and the primitive tasks P₁, P₂, …, P_n, where C has a constraint on a resource R (C) ≤ k (k > 0). In the total-order decomposition, for a reusable resource the subtasks inherit the constraint R (C_i) ≤ k or R (P_i) ≤ k (i = 1, 2, …, n); for a consumable resource the subtasks inherit the constraint $\sum_{i = 1}^{n} R (C_{i}) + \sum_{i = 1}^{n} R (P_{i}) \leq k$ . In the partial-order decomposition, for a reusable resource the subtasks inherit the constraint ∑R (C_j) + ∑R (P_j) ≤ k where P_j and C_j are the tasks that use the resource simultaneously; for a consumable resource the subtasks inherit the constraint $\sum_{i = 1}^{n} R (C_{i}) + \sum_{i = 1}^{n} R (P_{i}) \leq k$ .

5.2 Checking resource constraints

Resources play an important role in constraining the structure of a plan [42, 43]. Consumable resources impose constraints on actions during the lifetime of the plan, while reusable resources impose constraints on parallel actions at a time-point or during a period [44]. In other words, for consumable resources the total consumed amount must not exceed the maximum capacity [45], while for reusable resources, at any interval of time, the concurrent usage that are beyond the maximum available quantity are not allowed. Therefore, checking consumable resources needs calculating the maximal resource consumption, and checking reusable resources requires acquiring the concurrence of actions. However, some durations of actions are uncertain before execution, which makes it difficult to identify parallel actions directly. Hence, before elaborating the resource constraint checking, it is necessary to discuss the temporal relationship of actions firstly.

5.2.1 Analyzing action relationship

The objective of analyzing action relationships is to judge parallel actions according to the constraints in the temporal network and to serve for the resource checking. For simplicity, we begin to discuss the temporal relationship in terms of two actions. There are three types of the constraints between two actions: start-start, start-end, end-end, which mean different temporal requirements between the actions. Meanwhile, there are three categories of temporal relationships that may occur: follow, overlap and unordered. Given that an action starts after the other action ends, the former action follows the latter. When two actions execute simultaneously, they overlap. If an action may follow or overlap with the other action, they are unordered.

As Fig. 5 shows, assume A1 and A2 are two actions and there is a temporal constraint u ≤ start (A2) - start (A1) ≤ v between them.

Fig.5

The start-start constraint between two actions.

Case 1. if v > y, A1 and A2 are unordered, which means A2 may overlap with A1 or execute after A1.

Case 2. if -u > q, A1 and A2 are unordered, which means A1 may overlap with A2 or execute after A2.

Case 3. if v < y and -u < q, A1 and A2 overlap.

As Fig. 6 shows, assume there is a temporal constraint u ≤ end (A1) - start (A2) ≤ v.

Fig.6

The start-end constraint between two actions.

Case 4. if v < 0, A2 follows A1.

Case 5. if u > 0, since an equivalent temporal constraint y - v ≤ start (A2) - start (A1) ≤ x - u will be derived in the light of the triangular reductions [13], the relationship can be judged by Case 1–3.

Case 6. if u < 0 and v > 0, A1 and A2 are unordered.

As Fig. 7 shows, assume there is a temporal constraint u ≤ end (A1) - end (A2) ≤ v.

Fig.7

The end-end constraint between two actions.

Case 7. if u > 0 or v < 0, an equivalent constraint between the start time of one action and the end time of the other action will be derived, thus go to the start-end cases.

Case 8. if u < 0 and v > 0, two equivalent constraints y - v ≤ end (A2) - start (A1) and u + q ≤ end (A1) - start (A2) will be derived, thus go to the start-end cases.

Since the incremental update rules of STNU [29] do not derive the temporal constraints that have no effect on the dynamic controllability, it is not certain that there are the constraints between every two actions. The cases discussed above cover the majority of the situations, but the absence of the direct constraints between two actions obscures the relationship reasoning. Therefore, if there is not a direct temporal constraint between two actions, they are unordered. Furthermore, if a₁ follows a₂ and a₂ follows a₃, then a₁ follows a₃.

Depending upon the aforementioned theoretical analysis, an algorithm is developed to reason on parallel actions. As Algorithm 2 depicts, the algorithm takes as input a set of actions that use a reusable resource, and outputs a set of parallel actions. Every two actions are selected and judged (Line 3). If they are overlapping or unordered, they are a part of the parallel actions (Lines 4–5). Finally, the algorithm merges the pairs that contain the same actions one another (Line 7) and outputs them (Line 8).

Algorithm 2. Searching parallel actions: Search_actions (Δ)
Input: a set of actions Δ
Output: a set of parallel actions
1. Parallel← ∅
2. loop
3. choose two different actions a_i, a_j from Δ
4. ifa_i, a_j are the overlapping case or the unordered case
then
5. Parallel ← Parallel ∪ (a_i, a_j)
6. end loop
7. merge the pairs in Parallel
8. returnParallel

5.2.2 Detecting resource conflicts

Resource constraints are checked when an action is instantiated as Algorithm 1 shows. In other words, the resource constraints are checked before an action is added into the partial plan. A consumable resource may have a set of constraints with a form as ∑R (A_i) + R (A) ≤ k where A_i is an action in the partial plan which consumes the resource and A is the instantiated action. Similarly, a reusable resource has a set of constraints as ∑R (A_j) + R (A) ≤ k where A_j is an action in the partial plan which uses the resource simultaneously along with A.

5.3 Resolving potential resource conflicts

A potential resource conflict happens when the amount of a reusable resource used by unordered actions exceeds the available capacity. The potential resource conflicts do not signify that the reusable resource is scarce, while they mean that there may be the conflicts resulted from using a reusable resource simultaneously. Consequently, the possible conflicts should be resolved to achieve resource consistency.

The basic theory underlying the potential resource conflict resolution is to transform the unordered actions to the follow cases via adding precedence constraints. The detailed rules are specified below.

Rule 1. If two actions are Case 1, a precedence constraint end (A1) - start (A2) ≤0 is added.

Rule 2. If two actions are Case 2, a precedence constraint end (A2) - start (A1) ≤0 is added.

Rule 3. If two actions are Case 6, a precedence constraint end (A1) - start (A2) ≤0 is added.

Depending upon on Rule 1–3, an algorithm is proposed to resolve potential resource conflicts. As Algorithm 3 depicts, the algorithm takes as input a temporal network and the actions that potentially collide on a resource. From an overall perspective, the algorithm resolves the resource conflicts recursively to guarantee to search every action. When two actions are detected to be unordered by Case 1, Case 2 or Case 6 (Line 4), a precedence constraint is added as Rules 1–3 (Line 6). If two actions are unordered where there are no direct constraints, a set that contains two ordered tuples are created (Line 11). Two kinds of the precedence constraints are added (Line 15), which ensures two orders are added via backtrack. If the temporal network keeps DC, the algorithm goes on until the potential conflicts are resolved. Finally, an improved temporal network without the potential resource conflicts is outputted (Line 9 and Line 18).

Algorithm 3. Potential resource conflicts resolving:
Resolve_conflicts (Δ, G)
Input: a set of actions Δ, a temporal network G
Output: a temporal network N
1. if there are no potential resource conflicts then returnG
2. whileΔ≠ ∅ do
3. pop a pair of actions a_i, a_j from Δ
4. ifa_i, a_j are unordered cases then
5. G′ ← G
6. add the precedence constraint between a_i, a_j into G′ as
Rules 1–3
7. ifG′ is DC then
8. N← Resolve_conflicts (Δ, G′)
9. ifN is not failure then returnN
10. i fa_i, a_j are unordered then
11. X ← {< a_i, a_j >, < a_j, a_i >}
12. whileX≠ ∅ do
13. pop a pair of actions
14. G′ ← G
15. add the precedence constraint into G′
16. ifG′ is DC then
17. N← Resolve_conflicts (Δ, G′)
18. ifN is not failure then returnN
19. end while
20. end while
21. ifΔ≠ ∅ then return failure

6 Experimental evaluation

In this section, two typical practical cases in emergency decision-making, flood emergency response and medical rescue, and a standard domain in International Planning Competition are selected to validate the effectiveness and efficiency of the planning approach. Futhermore, a conceptual comparison with the planning approaches related to this study is discussed. Although the two practical cases are both concentrated on emergency domains, the essence of the problems have much in common with other engineering domains such as logistics and medical scheduling and the approach is also applicable to those domains. In flood emergency response problem, a problem is taken as an example to show the structure of the generated plan and the dispatched results, respectively. With the scales of the problems increasing, a set of experiments are conducted to demonstrate the performance of the planning approach.

Although several efforts allowing for resource reasoning in planning are taken, to the best of our knowledge, there have been no previous works dealing with constrained resources under uncontrollable durations in HTN planning so far. Therefore, we design our experiments to validate the planning approach. To evaluate the performance of the approach in uncertain temporal domains, a set of experiments are run on the problems with constrained resources in comparison with the problems with sufficient resources. Resources no longer constrain the planning procedure in the domains with sufficient resources. They all take into consideration the uncontrollable durations. In addition, to evaluate the performance of the approach in deterministic temporal domains, a set of experiments are carried in comparison with the state-of-the-art HTN planner FAPE.

6.1 Flood emergency response problem

6.1.1 Problem description

Flood emergency response involves dispatching emergency resources to distribution centers under complex temporal requirements. In this section, a realistic flood emergency response case is selected to validate the planning approach.

To respond to the flood disaster, several tons of clay need to be excavated at E and transported to the disaster area F by trucks, and one or two excavators load clay for the trucks. From the view of resources, the amounts of the excavators and the trucks are limited. When two or more trucks are ready to be loaded, an excavator can only serve for one truck simultaneously. From the view of time, given the urgency of the emergency, all the tasks must be finished in 5 hours. The durations of some actions are uncontrollable.

As the required clay increases, more transportations are required and more trucks intend to use the excavators simultaneously, which may result in more complicated resource conflicts. In view of the above consideration, ten problems with incremental complexity are selected and the basic information is introduced as Table 1 shows. To demonstrate the performance of the approach, the ten problems are also run with the sufficient resources, namely there are five available excavators at E. Besides the number of the excavators, all the other experimental conditions are the same. The experiments are carried out on a PC with Intel Core quad-core processor 3.1 GHz, 4 GB RAM and Windows 7 operating system. The planner and the dispatcher are both encoded in Common LISP.

Table 1
Flood emergency response problems

Problem Number Amount of clay (ton) Resources Basic information

Trucks Excavators

1 16 T1, T2 E1, E2 Excavators: E1, E2

2 16 T1, T2 E1 Loading speed: 20–40 t/h

3 23 T1, T2, TA E1, E2 Trucks: T1, T2, TA, TB

4 23 T1, T2, TA E1 Speed of trucks: 80–100 km/h

5 30 T1, T2, TA, TB E1, E2 Capacity of trucks: 8 t

6 30 T1, T2, TA, TB E1 Route between E and F: 40 km

7 36 T1, T2, TA, TB E1, E2 Unloading duration: 0.1 h

8 36 T1, T2, TA, TB E1

9 45 T1, T2, TA, TB E1, E2

10 45 T1, T2, TA, TB E1

Problem Number	Amount of clay (ton)	Resources	Basic information
1	16	T1, T2	E1, E2	Excavators: E1, E2
2	16	T1, T2	E1	Loading speed: 20–40 t/h
3	23	T1, T2, TA	E1, E2	Trucks: T1, T2, TA, TB
4	23	T1, T2, TA	E1	Speed of trucks: 80–100 km/h
5	30	T1, T2, TA, TB	E1, E2	Capacity of trucks: 8 t
6	30	T1, T2, TA, TB	E1	Route between E and F: 40 km
7	36	T1, T2, TA, TB	E1, E2	Unloading duration: 0.1 h
8	36	T1, T2, TA, TB	E1
9	45	T1, T2, TA, TB	E1, E2
10	45	T1, T2, TA, TB	E1

6.1.2 Experimental results

The forms of the plan and the dispatched results are shown via a simple problem. Next, as the scale of problems increases, the performance is demonstrated.

We choose Problem 2 to show the plan as Table 2. In Problem 1 two trucks are loaded by two excavators, thus Problem 1 has no resource conflicts on the excavators. But in Problem 2 there is only one excavator, which results in the resource conflicts on the excavator. The planner resolves the conflicts and generates the plan. The plan keeps temporal flexibility and specifies the allocated resources. Next, we simulate the real execution and record the real dispatched results. The dispatched results are shown as Table 3.

Table 2
The plan of Problem 2

Number Ac Res Tim

starttime endtime duration rel

a1 (!load T1 8 clay) E1, T1 [0.0 0.0] [0.2 0.4] [0.2 0.4] 0 ≤ a2_start - a1_end

a2 (!transport T1 E F 8 clay) T1 [0.2 0.4] [0.6 0.9] [0.4 0.5] 0 ≤ a5_start - a2_end

a3 (!load T2 8 clay) E1, T2 [0.2 0.4] [0.4 0.8] [0.2 0.4] 0 ≤ a7_start - a5_end

a4 (!transport T2 E F 8 clay) T2 [0.4 0.8] [0.8 1.3] [0.4 0.5] 0 ≤ a3_start - a1_end

a5 (!unload T1 8 clay) T1 [0.6 0.9] [0.7 1.0] [0.1 0.1] 0 ≤ a4_start - a3_end

a6 (!unload T2 8 clay) T2 [0.8 1.3] [0.9 1.4] [0.1 0.1] 0 ≤ a6_start - a4_end

a7 (!return T1 F E) T1 [0.7 1.0] [1.1 1.5] [0.4 0.5] 0 ≤ a8_start - a6_end

a8 (!return T2 F E) T2 [0.9 1.4] [1.3 1.9] [0.4 0.5]

Number	Ac	Res	Tim
a1	(!load T1 8 clay)	E1, T1	[0.0 0.0]	[0.2 0.4]	[0.2 0.4]	0 ≤ a2_start - a1_end
a2	(!transport T1 E F 8 clay)	T1	[0.2 0.4]	[0.6 0.9]	[0.4 0.5]	0 ≤ a5_start - a2_end
a3	(!load T2 8 clay)	E1, T2	[0.2 0.4]	[0.4 0.8]	[0.2 0.4]	0 ≤ a7_start - a5_end
a4	(!transport T2 E F 8 clay)	T2	[0.4 0.8]	[0.8 1.3]	[0.4 0.5]	0 ≤ a3_start - a1_end
a5	(!unload T1 8 clay)	T1	[0.6 0.9]	[0.7 1.0]	[0.1 0.1]	0 ≤ a4_start - a3_end
a6	(!unload T2 8 clay)	T2	[0.8 1.3]	[0.9 1.4]	[0.1 0.1]	0 ≤ a6_start - a4_end
a7	(!return T1 F E)	T1	[0.7 1.0]	[1.1 1.5]	[0.4 0.5]	0 ≤ a8_start - a6_end
a8	(!return T2 F E)	T2	[0.9 1.4]	[1.3 1.9]	[0.4 0.5]

Table 3

The dispatched results of Problem 2

Number	Ac	Res	starttime	endtime	duration
a1	(!load T1 8 clay)	E1, T1	0.0	0.4	0.4
a2	(!transport T1 E F 8 clay)	T1	0.4	0.9	0.5
a3	(!load T2 8 clay)	E1, T2	0.4	0.7	0.3
a4	(!transport T2 E F 8 clay)	T2	0.7	1.2	0.5
a5	(!unload T1 8 clay)	T1	0.9	1.0	0.1
a6	(!unload T2 8 clay)	T2	1.2	1.3	0.1
a7	(!return T1 F E)	T1	1.0	1.4	0.4
a8	(!return T2 F E)	T2	1.3	1.8	0.5

By the action !load, the excavator E1 loads eight tons of clay onto the truck T1, and then loads eight tons of clay onto the truck T2. T1 and T2 both transport the clay from the site E where the clay is excavated to the dam area F. Finally, T1 and T2 unload the clay and return E, respectively. T2 uses the excavator until loading T1 ends, which avoids the resource conflict on E1.

As more clay is required, the scales and complexity of the problems increase. The experimental results are shown in Fig. 8. Every experiment is run ten times and the average CPU time is recorded. With the complexity of the problem increasing, the planner needs more time to generate a plan. But the time increases in the acceptable range. The two group of the results demonstrate that the problems with sufficient resources have lower time cost. The reason may be that the problems need not to resolve the potential resource conflicts. In the domains with constrained resources the more complex the problem is, the more potential resource conflicts need to be handled.

To demonstrate the dependability of the approach, we also run the ten problems under the condition where there are no excavators. The approach cannot generate the DC plans for those problems and therefore has no corresponding runtime. The reason is that the resources are so scarce that there are no plans under that condition. The approach is able to generate a plan via searching different available plans when there exist plans to the problem, while the approach cannot generate a plan if the problem has no solution.

Fig.8

Time performance of the planner in the flood emergency response problems.

6.2 Medical rescue problem

6.2.1 Problem description

Major emergencies often cause casualties and medical rescue plays a significant role in emergency responses. When an emergency breaks out, the local government sets up a temporary medical aid station in the disaster area. In this section, a medical rescue case is selected to validate the planning approach.

A heavy earthquake has struck a county and the local government sets up a temporary medical aid station to rescue the injured. The patients are divided into four levels according to the degree of the injury: D1, D2, D3 and D4. D1, D2, D3 needs different numbers of doctors and nurses respectively, and the duration of the treatment is uncertain within a certain range. If a patient is diagnosed as D4, the patient should be transferred to the nearby hospital as the injury is too serious to be treated in the temporary medical aid station. The detailed information of the treatment is shown in Table 4. Medical staff is a vital resource in the medical rescue but there are only two doctors and two nurses at the station. As the number of the patients increases, more treatments are required. Eight problems with the incremental complexity are selected and the patients are shown in Table 5. Eight problems with sufficient resources are also run to illustrate the performance of the approach. In the compared problems there are 20 doctors and 20 nurses in the station. The experiments are carried out on a PC with Intel Core quad-core processor 3.1 GHz, 4 GB RAM and Windows 7 operating system. The planner and the dispatcher are both encoded in Common LISP.

Table 4
The treatments for the patients

Degree of the injury Doctor Nurse Duration of the treatment

D1 0 1 [0.2 0.3]

D2 1 1 [0.4 0.8]

D3 1 2 [1.0 1.5]

D4 – – –

Degree of the injury	Doctor	Nurse	Duration of the treatment
D1	0	1	[0.2 0.3]
D2	1	1	[0.4 0.8]
D3	1	2	[1.0 1.5]
D4	–	–	–

Table 5

Medical rescue problems

Problem Number	Patients
1	D1, D1
2	D1, D1, D2
3	D1, D2, D2
4	D1, D2, D2, D3
5	D1, D2, D2, D3, D4
6	D1, D1, D1, D2, D3, D4
7	D1, D2, D2, D3, D3, D4, D4
8	D2, D2, D2, D3, D3, D3, D4, D4, D4

6.2.2 Experimental results

As the form of the plan and the dispatch results have been shown in the first experiment, this experiment mainly discusses the experimental results and the performance of the approach. The experimental results are shown in Fig. 9. Every experiment is run ten times and the average CPU time is recorded. Similar to the flood emergence response problems, the time cost of the approach increases with the scales and the complexity of the problems. Since the scales of the problems are lower than the flood emergence response problems, the time cost is lower than those. The problems with constrained resources consume more time owing to resolving potential resource conflicts.

Fig.9

Time performance of the planner in the medical rescue problems.

6.3 Airport domain

To verify the time performance of the proposed approach in deterministic temporal domain, airport domain [46] is selected and the proposed approach is compared with the state-of-the-art HTN planner FAPE. As one of the standard domains in the 4th International Planning Competition, airport domain has four different versions and this section adopts the temporal version. In airport domain, the planner has to control the ground traffic on an airport. The problem is to coordinate inbound and outbound airplanes on the airport to reach planed runways or parking positions and avoid resource collisions. Because a road unit is a reusable resource and two airplanes must not both occupy the same road unit. Eight problems with incremental complexity are selected. In problems 1–3 there are two airplanes, and in problems 4–8 there are three airplanes. FAPE is run on a virtual machine with 3GB RAM and Ubuntu operating system, and the proposed approach is run on a PC with 4GB RAM and Windows 7 operating system. The runtime is limited within 500 seconds.

Table 6 shows the time performance of FAPE and the proposed approach. The results indicate that the proposed approach performs better than FAPE. FAPE takes more time when the complexity of the problems increases, while the proposed approach keeps high efficiency.

Table 6
Time performance of FAPE and the proposed approach in airport domain

Problem number FAPE (s) Proposed approach (s)

1 9.52 0.32

2 7.33 0.41

3 70.26 0.69

4 170.41 1.03

5 450.63 1.55

6 timeout 2.74

7 timeout 3.04

8 timeout 4.12

Problem number	FAPE (s)	Proposed approach (s)
1	9.52	0.32
2	7.33	0.41
3	70.26	0.69
4	170.41	1.03
5	450.63	1.55
6	timeout	2.74
7	timeout	3.04
8	timeout	4.12

6.4 Conceptual comparison

This section briefly discusses the conceptual comparison with the planning approaches related to this study. Compared with other approaches, this work has some features. First, this study is able to reason on consumable resources and reusable resources in uncertain temporal domains. The approach checks resource constraints and resolves resource conflicts resulted from actions with uncontrollable durations. Second, different from the approaches that use timelines or STN to handle temporal constraints, this study models uncontrollable durations as time intervals and checks the dynamic controllability of the plan. Hence the plan keeps temporal flexible. Third, instead of a fixed plan, this study generates a dynamically controllable plan and executes the plan via scheduling actions dynamically. Fourth, compared with non-HTN planning approaches, HTN planning in this study has its advantages on action reasoning and domain knowledge representation, which is good for its time performance and practical application.

7 Conclusions and future work

The key to emergency decision-making is to deploy emergency response tasks via developing an emergency action plan considering uncontrollable durations and limited resources. This study proposes a resource-constrained HTN planning approach under uncontrollable durations for emergency decision-making. Timed initial literals are extended to present timed resources and the constraints of the literals are transformed to impose restrictions on actions in planning. A mechanism is explored to hierarchically inherit the resource constraints of compound tasks by subtasks during HTN planning. The temporal relationships of actions in the temporal network are analyzed and an algorithm is proposed to search parallel actions. Then the resource constraints are checked. Potential resource conflicts are resolved via adding precedence constraints. The empirical studies show that the planning approach is effective and efficient.

The proposed approach in this study plans each step recursively and backtracks when the current instance fails or no instances are searched. The plan is guaranteed to be temporal consistent and DC by the temporal reasoning module. The resources involved in the plan are checked to keep consistency after the potential resource conflicts are resolved. Therefore, if there exits a DC plan for the planning problem with constrained resources under uncontrollable durations, the proposed approach can generate it and execute clearly. However, this study just allows for reusable resources and consumable resources under uncontrollable durations. The future work might explore more other categories of resources which have practical value such as producible resources.

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

Smith

D.E.

, Frank

and Jónsson

A.K.

, Bridging the gap between planning and scheduling, The Knowledge Engineering Review15(01) (2000), 47–83.

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.

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.

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.

Hayashi

, Tokura

, Ozaki

and Hasegawa

, Emergency HTN Planning, In Intelligent Automation and Computer Engineering, Springer, 2010, pp. 27–40.

Liu

, Wang

, Qi

, Zhao

and Wang

, Hierarchical task network-based emergency task planning with incomplete information, concurrency and uncertain duration, Knowledge-Based Systems112 (2016), 67–79.

Zhao

, Wang

, Qi

and Liu

, HTN planning with uncontrollable durations for emergency decision-making, Journal of Intelligent & Fuzzy Systems33(1) (2017), 255–267.

Wilkins

D.E.

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

10.

Currie

and Tate

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

11.

Wang

, Wang

, Qi

and Wang

, A resource enhanced HTN planning approach for emergency decision-making, Applied Intelligence38(2) (2013), 226–238.

12.

Vidal

and Fargier

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

13.

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.

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, Hungary, 1996, pp. 48–54 .

15.

Barták

, Morris

R.A.

and Venable

K.B.

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

16.

Wilkins

D.E.

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

17.

Tate

, Drabble

and Kirby

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

18.

Dvorak

, Bartak

, Bit-Monnot

, Ingrand

and Ghallab

, Planning and Acting with Temporal and Hierarchical Decomposition Models, Proceedings of the 26th International Conference on Tools with Artificial Intelligence, Limassol, Cyprus, 2014, pp. 115–121.

19.

, Wang

, Muñoz-Avila

, Zhao

and Wang

, Hierarchical task network planning with resources and temporal constraints, Knowledge-Based Systems113 (2017), 17–32.

20.

Labone

and Ghallab

, Planning with Sharable Resource Constraints, Proceedings of the 14th International Joint Conference on Artificial Intelligence, Montreal, Canada, 1995, pp. 1643–1649.

21.

El-Kholy

and Richards

, Temporal and Resource Reasoning in Planning: The ParcPLAN Approach, Proceedings of the 12th European Conference on Artificial Intelligence, Budapest, Hungary, 1996, pp. 614–618.

22.

Cesta

and Stella

, A Time and Resource Problem for Planning Architectures, Proceedings of the 4th European Conference on Planning: Recent Advances in AI Planning, Toulouse, France, 1997, pp. 117–129.

23.

Dvořák

and Barták

, Integrating Time and Resources into Planning, Proceedings of the 22nd IEEE International Conference on Tools with Artificial Intelligence, Arras, France, 2010, pp. 71–78.

24.

Kvarnström

, Doherty

and Haslum

, Extending TAL Planner with Concurrency and Resources, Proceedings of the 14th European Conference on Artificial Intelligence, Berlin, Germany, 2000, pp. 501–505.

25.

Kvarnström

and Doherty

, TAL Planner: A temporal logic based forward chaining planner, Annals of Mathematics and Artificial Intelligence30(1-4) (2000), 119–169.

26.

Morris

and Muscettola

, Temporal Dynamic Controllability Revisited, Proceedings of the 20th National Conference on Artificial Intelligence, Pittsburgh, Pennsylvania, USA, 2005, pp. 1193–1198.

27.

Morris

, A Structural Characterization of Temporal Dynamic Controllability, In Principles and Practice of Constraint Programming-CP 2006, Springer, 2006, pp. 375–389.

28.

Morris

, Dynamic Controllability and Dispatchability Relationships, In Integration of AI and OR Techniques in Constraint Programming, Springer, 2014, pp. 464–479.

29.

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.

30.

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.

31.

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.

32.

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.

33.

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.

34.

Edelkamp

and Hoffmann

, PDDL2.2: The language for the classical part of the 4th international planning competition (Technical Report 195), (Albert-Ludwigs-Universitat Freiburg, Institut fur Informatik, 2004.

35.

Gerevini

A.E.

, Haslum

, Long

, Saetti

and Dimopoulos

, Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners, Artificial Intelligence173(5–6) (2009), 619–668.

36.

Georgievski

and Aiello

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

37.

Garrido

and Barber

, Integrating planning and scheduling, Applied Artificial Intelligence15(5) (2001), 471–491.

38.

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.

39.

Nilsson

, Kvarnström

and Doherty

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

40.

Bedrax-Weiss

, McGann

and Ramakrishnan

, Formalizing Resources for Planning, Proceedings of the 13th International Conference on Automated Planning and Scheduling Workshop on PDDL, Trento, Italy, 2003, pp. 7–14.

41.

Ghallab

, Nau

, Traverso

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

42.

Laborie

, Algorithms for Propagating Resource Constraints in AI Planning and Scheduling: Existing Approaches and New Results, Proceedings of the 6th European Conference on Planning, Toledo, Spain, 2001.

43.

Laborie

, Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results, Artificial Intelligence143 (2003), 151–188.

44.

Long

, Fox

, Sebastia

and Coddington

, An Examination of Resources in Planning, Proceedings of the 19th Workshop of the UK Planning & Scheduling Special Interest Group, Milton Keynes, England, UK, 2000.

45.

Nakhost

, Hoffmann

and Müller

, Resource-Constrained Planning: A Monte Carlo Random Walk Approach, Proceedings of the 22nd International Conference on Automated Planning and Scheduling, Atibaia, Sao Paulo; Brazil, 2012, pp. 181–189.

46.

Hoffmann

and Edelkamp

, The deterministic part of IPC-4: An overview, Journal of Artificial Intelligence Research24(1) (2005), 519–579.

Resource-constrained Hierarchical Task Network planning under uncontrollable durations for emergency decision-making

Abstract

Keywords

1 Introduction

2 Literature review

2.1 Resource-constrained HTN planning

2.2 Resource-constrained non-HTN planning

2.3 Temporal reasoning

3 Problem formulation

3.1 Timed initial literals

3.2 Domain knowledge

3.3 Task network

3.4 Plan

3.5 A running example

4.1 Framework

5 Resource management

5.2 Checking resource constraints

5.2.1 Analyzing action relationship

5.3 Resolving potential resource conflicts

6 Experimental evaluation

6.1 Flood emergency response problem

6.1.1 Problem description

6.2.1 Problem description

Table 4 The treatments for the patients Degree of the injury Doctor Nurse Duration of the treatment D1 0 1 [0.2 0.3] D2 1 1 [0.4 0.8] D3 1 2 [1.0 1.5] D4 – – –

Table 6 Time performance of FAPE and the proposed approach in airport domain Problem number FAPE (s) Proposed approach (s) 1 9.52 0.32 2 7.33 0.41 3 70.26 0.69 4 170.41 1.03 5 450.63 1.55 6 timeout 2.74 7 timeout 3.04 8 timeout 4.12

7 Conclusions and future work

Footnotes

Acknowledgments

References

Table 4
The treatments for the patients

Degree of the injury Doctor Nurse Duration of the treatment

D1 0 1 [0.2 0.3]

D2 1 1 [0.4 0.8]

D3 1 2 [1.0 1.5]

D4 – – –

Table 6
Time performance of FAPE and the proposed approach in airport domain

Problem number FAPE (s) Proposed approach (s)

1 9.52 0.32

2 7.33 0.41

3 70.26 0.69

4 170.41 1.03

5 450.63 1.55

6 timeout 2.74

7 timeout 3.04

8 timeout 4.12