The Study Of Flexible Planning Based On Resource Constraints

Recently tremendous advances have been made in the performance of AI planning systems. However, increased performance is only one of the prerequisites for bringing planning into the realm of real applications; Advances in the scope of problems that can be represented and solved must also be made.Traditionally, planning problems are cast in terms of imperative constraints that are either wholly satisfied or wholly violated, which limits the classical planning algorithms only to solve small-scaled model problems. It is argued herein that this framework is too rigid to capture the full subtlety of many real problems, which leads to no solution found or low-quality solution. In order to solve the problem above, it gives birth to a new planning problem named flexible planning problem. Flexible planning supports the soft constraints which are often found in reality.However, real world is complex. Real world applications require modeling a number of more sophisticated features, including uncertainty, sensing, varying action durations, and metric problem.In this paper, we study the flexible planning problem based on resource constraints. We put forward some new basic concepts, including flexible planning task with resource constraints, flexible action with resource constrains, and so on. Based on these concepts, we propose a heuristic search method to solve the problem. We get heuristic information by relaxed flexible graphplan. In the process of constructing a planning graph, we put action satisfaction degree into consideration, by which we can cut off the states produced by actions that don't satisfy the user need. This method reduces the size of the state space and improves the search speed efficiently. Then we utilize the heuristic information to guide a novel search algorithm--Partial Backtrack Searching Algorithm--searching in the state space. This search algorithm is a variant form of classic BACKTRACK algorithm. It is different from classic BACKTRACK algorithm that Partial Backtrack Searching Algorithm doesn't backtrack to all state nodes, but part of them when it fails in finding the successor of the current state. This method can effectively use the information and results which have been produced ahead.Based on the algorithms we put forward, we have implemented the planner called FPBR (Flexible Planning Base on Resource constrains). Our method has been validated by a set of problems of the FlexLog domain.Resource constraints exist everywhere in our real life, but it is still one of the most difficult planning problems in planning community. The research on flexible planning based on resource constraints is very important both in theory and practical.