Temporal Extension To Hierarchical Task Network Planning Paradigm

Automated Planning is one of fundamental problems in Artificial Intelligence. Classical planning problem is a primitive models in the automated planning research, it is defined as a process to generate a sequence of actions, which could transform the current state to a specific goal state. The goal states need to contain all the goal conditions. With the development of the automated planning techniques, some planning paradigms which break the classical planning’s assumptions are arising. Those new planning models are more applicable to real‐world problems but more difficult to solve, when they broke the classical assumptions. In classical planning there are several assumptions to simplify temporal representation. Since time is a critical constraints to every real world problem. It is worthy to break classical assumptions in the class planning in this way. Such as parallel planning, temporal planning and uncontrollable temporal planning problems.This thesis proposed several paradigms on dealing with temporal related planning problems based on Hierarchical Task Network(HTN) planning paradigm. HTN is one kind of non‐classical planning paradigms, it has the same definition about action and state, but different in the goal description and the process reaching the goal. Hierarchical task network is not searching for a state, it is aiming to accomplish some goal tasks or complex task network. The solving process is not to search in the state/action space, but to decompose the complex tasks. The decompose process will recursively carried until all of the tasks in the network is primitive task. In the HTN planning paradigm, primitive task is just like the action in the classical planning, defined by the actions those can be applied by the agents directly. HTN is one of the most applicable planning paradigms because it can use dense domain knowledge in the solving process.Parallel planning is one kind of the non‐classical planning problems, it is not aiming to find a sequence of actions, and this kind of planning paradigm needs to find a kind of plan in which several actions can be applied concurrently. It is more likely to capture the real world problems. Scheduling several actions at the same time in the same state need to guarantee those actions are not mutex to each other. Mutex actions cannot be applied at the same time. A parallel plan will be much shorter than a sequential plan.Use HTN planning paradigm to solve parallel planning problem is taking the advantage of dense domain knowledge provided by the HTN methods. To make the solving process more flexible, we use the goal‐base hierarchical task network paradigm framework to capture the parallel planning problem. It can use domain knowledge just like HTN planning, and use heuristic search like other domain independent planners. This kind of model will be more flexible than those just use heuristic search, or those just use HTN paradigm. The goal‐based hierarchical planning will be more applicable than HTN when the domain knowledge is not complicated.There is a problem in the parallel planning problem. When the solver finds some applicable actions in a state, it will be the number of power set of branches in the searching space. When solving the problem by HTN planning paradigm, we can use domain knowledge to decide which action set can be applied at the same time. It will be much easier to solve than the classical approaching. Some parallel planning models are based on multi‐agents. In this thesis, we are assume that agents are just another kind of resource.This thesis redefines the temporal planning problem; and makes it compose an action’s network. Temporal planning is planning for durative actions and needs to reason the durative relations between actions. Since we define the temporal planning problem for a network, it is nature to solve it by task networks. In the planning system, we deny the temporal sequential between states. There are several remarkable works which have been proposed by using HTN framework in solving temporal planning, but most of them use STNs framework to represent the temporal relations in the task network.Using HTN planning to deal with temporal planning problem can dedicate temporal constraints to the higher‐level task pair. When those compound tasks are decomposed into sub tasks, the new sub tasks will inherit the temporal relations, and it is just the process for the constraint propagation in the solving procedure. We can define the constraints in the task decompose method to capture the domain knowledge which is useful to improve the solving procedure.This thesis defines the temporal planning problem with uncontrollable action durations as Uncertain Temporal Planning Problem. Actions, which has uncontrollable duration, is common in the real world problem. It is a hard problem in the temporal planning, however. Uncontrollable duration of actions will cause uncertain relations between them. Reasoning for the uncertain temporal constraints is a hard problem already.Neither expected action durations nor worst‐case action durations could replace the uncertain temporal interval in the planning solving process. To solve this problem, a strong planning process for this uncertain temporal planning problem has been designed. This thesis creates a Hierarchical Task Network framework to capture the uncertain temporal planning problem. In the task network we can represent the uncontrollable duration of actions and the uncertain temporal constraints. We can use the solving techniques for uncertain temporal problems in the CSP field to decide whether the current task network is capable of generating a strong plan.