The Hierarchical Task Network Based Flexible And Conformant Planning

Intelligent Planning begins from the early period of Artificial Intelligence, which is an important research field. In the early period of intelligent planning, there are several assumptions, and these assumptions are useful to confine the research focus. It is well accepted that there are Eight Assumptions, all the problems satisfied these assumptions are Classical Planning Problems. But these assumptions are too strict to describe the flexible situation of real problems. It is more and more popular to relax these assumptions to build more reality planning model. Conformant Planning is a kind of planning problem on seeking plan under such conditions of uncertain initial states and action effects, and during plan take into action without the help of sensitive actions. And Flexible Planning is the concept of soft constraints in the planning problems. Flexible planner avoid"over constraint", if the planner can't find a perfect solution, it can find a solution, not so satisfying.The complexity of conformant planning is EXPSPACE-Complete and cannot been reduced. It is very difficult to seek the solution of conformant planning. But since the out coming of Blindness Robot Problem in 1974, conformant planning is regarded as the vital research subject in the field of artificial intelligence because conformant planning has important applications in commercial intelligence\ robot control\ aviation technology and intelligent system control. Actually it is not hard to imagine the wide application of conformant planning when we consider the popularity of information disagreement in daily life.Recently many ways of conformant planning have been put forward, which mostly base on classical planning technology or the extending edition of such technology. And some transform planning problems into other problems to seek solutions, such as SAT\ d-DNNF\BDD and so on. Those mechanics of solution comparatively mature and effectively seek solutions so that those change conformant planning to make these methods of calculating. Although there is relatively mature solution technology in Model Checking and SAT, there are some unconquered barriers themselves. While classical planning has certain distance with conformant planning in the ability of expressing and solution. So it can not be claimed to solves the problems of conformant planning depending expanding classical planning or converting problem to make conformant planning. There is still need further research in the field of conformant planning.This essay mainly put up the following work:1 This essay detailed summarizes the construction and tragedy of Hierarchical Task Network.2 This essay proposed a new algorithm to solve the conformant planning problem. And first time use hierarchical task network to expressive the algorithm, Conformant Hierarchical Task Network(CHTN).3 This essay proposed a structure and a solution for flexible planning.Hierarchical task network is a planning method of using layer solution to seeking solution. In such planning strategy, it is not to convert the initial state to the goal state, but to complete a task. And there is only one action in seeking plan, decomposition. There is a lot of domain knowledge could be used to express the task and the way to decompose the task to subtask network. Hierarchical task network is more expressive than the classical planning.This article firstly brings in a method of solving conformant planning problems by Hierarchical Task Network. We suggest that we can convert all the possible initial states to a certain middle state. And complete the goal task at the next step. We proved the correctness of the algorithm in strong planning domain. Then we fulfill the algorithm in the Hierarchical task network way, and name it CHTN.In this essay, we proposed two conflicts must be considered when solving the conformant planning problems, and solve them in different way. The algorithm of CHTN is suitable to the complex possible initial states. It deals with all of the difference at the beginning of the planning. It shows quicker speed in experiment and has better expansibility.When we solve the conformant planning problems, since it is so complex to deal with, we use the domain depended konwledge to deal with the problems. It is easy to accelerate the solution when with a lot of domain knowledge. When we consider special problems we always could find some method to deal with these problems easily.This essay also brings in a method of solving flexible planning through using Hierarchical Task Network. Firstly we introduce the concept of soft constraints in CSP, and use the hierarchical constraints model to describe the flexible constraint in flexible planning. It define these preconditions must be satisfied to be hard constraints, and these could be relax with some damage to the plan to be soft constraints. And give the algorithm to solve the flexible planning in hierarchical task network way.In the further research, we'd like to deal with the uncertain action effects. And the theory of hierarchical task network is an important direction. It is exciting to relax the assumption of classical planning problems, and make the planning method more useful.