Research And Implementation Of Heuristic Planning Based On Causal Graph

At present, Intelligence Planning has been an important research and application field in Artificial Intelligence, and State-Space heuristic planning is a focus in intelligence planning area. HSP, FF and Fast Downward are three best known heuristic planners. HSP and FF both perform well, where HSP used the additive heuristic and FF ignored delete lists. However, they are both based on the delete-relaxation, therefore, some vital information of the planning task may be lost. Fast Downward translates a STRIPS problem to a multi-valued planning task, and exploites the underlying causal structure, thus, Fast Downward yields better performance compared with the state of the art heuristic planners in many domains, but it needs the state variables to be independent, which is always not satisfied.For the problem in Fast Downward, based on the causal graph heuristic, this paper proposes a multi-valued planning algorithm based on the novel causal graph mixed heuristic. We import max heuristic into the causal graph, design the causal graph mixed heuristic function, which is the combination of the additive heuristic and max heuristic based on the causal graph. We implement the planning algorithm-AMCG, which makes up the drawbacks of Fast Downward. The state space is reduced since we translate STRIPS problems into multi-valued formulation. The approach not only exploits the structural information in the problem, but also takes the interactions among the state variables into account. Under this strategy, we can get more accurate heuristic information to guide the search. Thus, AMCG algorithm can improve the quality of plan solution, and then reduce the search time. The application of the algorithm is more general, since the interactions among state variables usually exist in realistic problems.Based on the algorithm proposed above, we have developed a new planner AMCG by C++ programming language. The planner concludes three modules: translation, preprocess and search. Experiments have proved that the search time and plan length can be reduced under the new heuristic method, and we can make a tradeoff between them. The planner performs well that it fits into the requirements of realistic application fields.