Research On Some Problems Of Multi-valued Planning

Planning is the process for finding a sequence of actions with the given initial conditions. The planner can reach specific goals by performing this action sequence in turn. Planning is one of classical research problems in the field of artificial intelligence. The area of intelligent planning has made significant breakthroughs in the past more than 10 years. There are orders of magnitude improvement in the scale and efficiency of the modern planner. Multi-valued planning becomes the focus topic of intelligent planning in recent five years. There is a stirring of interest in multi-valued planning researches after planning graph. Knowledge representation of multi-valued planning is different from other planning. A multi-valued variable of this planning represents many propositions, while a Boolean variable of classical planning with two values represents a proposition. The differences of knowledge representations make action model of multi-valued planning different from that of classical planning. Multi-valued planning brings out new structure representations, solution strategies and heuristic functions. This thesis studies the properties of knowledge representation, data structures and heuristic search under the framework of multi-valued planning. The major contributions, ideas and research results are as follows:(1) The knowledge representation of multi-valued planning is used in conformant planning. Multi-valued variable is encoded by invariants of planning task. Multi-valued variable is much more compact than Boolean variable. Multi-valued variables are suited to represent planning tasks which have large state space because multi-valued variables can compress the state space and search space, and can accelerate the speed of different planners. With compression property of multi-valued variables, this thesis introduces multi-valued variables into conformant planning for solving the conformant planning problems with high time and space complexities. Conformant planning removes some unrealistic assumptions and considers non-deterministic actions with partial description of initial state. So the state space of conformant planning expands exponentially, compared with classical planning. This thesis recognizes the set of propositions which are not true at the same time in each time span. This thesis formalizes the invariants of conformant planning, and proposes the algorithm for synthesis conformant invariants. The algorithm looks the predicates which are affected by action effects as candidates of conformant invariants. Next, the algorithm tests whether the candidates meet the requirements of conformant invariants in initial state and effects of all actions. Some candidates are given up. Some candidates are modified for testing again. Others are invariants. Then, this thesis gives the definition and action model of multi-valued conformant planning task, and specifies the method for translating PDDL into multi-valued conformant planning task. And then this thesis specifies that the techniques which combine the conformant planning task with plan reuse heuristic for conformant plans.Theory analysis and experiments show that conformant invariants synthesis algorithm can synthesize right invariants of conformant tasks, and can produce multi-valued conformant tasks. Compared with Boolean code, multi-valued conformant state codes can compress great storage space. In order to show the application of multi-valued conformant planning tasks, the tasks are combined with plan reuse heuristic to find plan. The application results show the quality and the efficiency of this combination method is almost the same as that of conformant planner CFF.(2) The method for extracting action landmarks is proposed. Although landmarks show the excellent properties for accelerating the process of producing the plans in different framework of planners, the actors and the functions of landmarks are different in different framework of planners, such as precondition sorting, guiding the search direction, heuristic estimators and so on. The representative method of them is heuristic estimator. In order to improve the quality of plan, different types of landmarks are invented, such as proposition landmarks, disjunctive proposition landmarks, conjunctive proposition landmarks, action landmarks and so on. Among these landmarks, action landmarks are proposed as planning heuristic with distinguished performance. The distinguished performance is decided by the number of action landmarks and the speed of generating action landmarks. This thesis proposes the algorithm for extracting action landmarks. The algorithm is different from the method by testing connectivity and validating action landmarks with rebuilding planning graph repeatedly. The action landmarks are extracted from proposition landmarks graph of planning task by two extraction rules. All action landmarks can be extracted by building landmarks graph only once. Two extraction rules are proved to be right. Theory analysis and comparision experiments show that this algorithm proposed can guarantee the correction and find more action landmarks for the short term than verification method of action landmarks based on relaxed planning graph.(3) Admissible heuristic function based on propositional landmarks is built. The heuristics with different types of landmarks is the current trend for designing heuristic function. Proposition landmarks can be extracted directly. Proposition landmarks are the foundation of various landmarks. The main idea of landmarks count heuristic is recording the number of unreached propositional landmarks as the heuristic estimator. This method improves the success rates of planning and the length of plans. However, it can not ensure that the plan is the optimal. The reason is that the number of proposition landmarks sometimes is much more than the number of actions which need to execute for some benchmarks. This thesis analyzes why landmarks count heuristic is not admissible and compares the advantages and disadvantages of various proposition landmarks heuristics. This thesis defines corresponding action of action landmark, uses the number of corresponding actions of unreached propositional landmarks as the estimator of enhanced propositinal landmarks count heuristic function, in order to make this heuristic admissible. The admissible proof of the enhanced heuristic function is given. Comparison experiments show that the enhanced proposition landmarks count heuristic has better performance than landmarks count heuristic for some domains with strong constrains actions.In summary, the thesis deeply studies main problems of multi-valued planning areas: knowledge representation application, action landmarks extraction and building heuristic function, deeply. Utilizing the properties of multi-valued representation, multi-valued planning task is introduced into conformant planning and the application of multi-valued conformant planning task has better results. Toward the special data structures of multi-value planning, efficient method for extracting action landmarks is given. For the heuristics based on propositional landmarks under multi-valued planning framework, the algorithm of admissible propositional landmarks heuristic function is given. This research is significant in theory and application. The achievements of this thesis provide effective methods and thoughts for the research on the multi-valued planning.