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

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

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;

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;

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;

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.

OPEN IN VIEWER

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.

OPEN IN VIEWER

Fig.2

Example of an operator.

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.

OPEN IN VIEWER

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.

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

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 ∑ i = 1 n R ( C i ) + ∑ i = 1 n R ( P i ) ≤ 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 ∑ i = 1 n R ( C i ) + ∑ i = 1 n R ( P i ) ≤ 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.

OPEN IN VIEWER

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.

OPEN IN VIEWER

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.

OPEN IN VIEWER

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

OPEN IN VIEWER

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

6.1 Flood emergency response problem

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.

OPEN IN VIEWER

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]

OPEN IN VIEWER

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.

OPEN IN VIEWER

Fig.8

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

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.

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.