Conformant Planning Sovling Based On Graph Plan And Heuristic Search

Planning is a very important branch in the research of Artificial Intelligence, andis a relative early aspect of Artificial Intelligence area. Planning reasons on therelations of the resources and actions according to the analysis of the area knowledgeand the goals given, and at last obtains a action sequence which can reach the goalfrom the initial state. At the early stage of the planning research, in order tosimplifying the problems and reinforcing the pertinence of the problems, planningresearchers put forward a few assumptions to the planning problems, this assumptionsdefined the Classical Planning. But these assumptions are too strict to capture the realworld problems, in order to let Planning have wider application to the real world, allkinds of Planning which do not obey these assumptions in the Classical Planning takeplace.Such as conformant planning, possibilistic planning, flexible Planning etc.Conformant planning is the planning problems which have uncertainty in theinitial state and the action effect, and the agent has no sensing capability in theplanning process. The plan obtained from the planning process can reach the goalstate at all situations. Conformant planning can be transformed to the search problemsin the belief state space. The elements in the belief state contain all real world statesat the present.In the research of the classical planning, the application of the relaxed planninggraph can be considered to be successful. The “relax” is the idea in which we replacethe delete effect of the actions, which mean the delete list is empty. And then we takea forward search to the initial state and the actions which have no delete effect. Thelength of the plan obtained is just the heuristic value we want. But in the conformantplanning, because existence of the uncertainty and the raising in the complexity,Conformant-FF planner expanded the “relax”. It keeps only two propositions in everyaction CNF formula. This method ignores the soundness in relaxed plan process, butthe real planning process is complete and sound. Although the “relax” make processof the heuristic value producing more efficient, but for the proposition selection in the CNF is blind and the large decreasing of the proposition quantity, makes the qualityof the heuristic value is not very good.According to the properties of A*algorithm,if the heuristic value of a admissibleheuristic fuctions is the more closer to the optimistic value, the heuristic function hasa more stronger heuristic ability. This paper proposes a new method for theconformant planning, according to the analysis of the relaxed graph heuristics in theConformant-FF.takes3-CNF,4-CNF action relaxed function, makes a search processin the belief state space with the heuristic value, and compares this method withconformant, makes a few suggestions to the relaxed planning graph based heuristicsearch in the conformant planning. The experiment result indicate that the heuristicability of the action relaxed function3-CNF,4-CNF is stronger than the2-CNF inconformant-FF.