Planning Solving Based On Local Search And Distributed Flexible Graphplan

Artificial intelligence planning is one of the most advanced research areas of AI, and it is also a intercrossed subject, which contains knowledge representation, automated reasoning, nonmonotonic logic, human-computer interaction, cognitive science and so on. Researches on classical planning can be traced back to the initial developmental stage of AI. In 1995, Blum and Furst proposed the Graphplan method based on planning graph, and designed an excellent planner named Graphplan. This approach makes artificial intelligence planning one of the hotspots of AI so far.Recently, scholars research not only on how to improve problems solving efficiency, but also on how to extend scope and quality of planning problems. Graphplan can solve problems expressed by STRIPS successfully, but it cannot get more details of the real world. To solve this problem, Ian Miguel proposed Flexible Graphplan on 14th artificial intelligence conference held on 2000. Then he improved the solving efficiency by introducing Fussy rrDFCSP technique and published results on Artificial Intelligence magazine.Flexible Graphplan is an extension of Graphplan. A finite number of membership degrees composed the subjective degree of truth of the proposition and satisfaction degree of the plan.Because Flexible Graphplan has the capacity of evaluate the quality of the plan, PDDL3 uses the flexible constrains and preference to describe a planning problem. This method is regarded as an improvement and extension of the previous planning problems. Unlike the other planners, Fexible Graphplan focuses on more complicated and realistic problems.With the development of cyber technique, distributed system has been a hotspot. The motivation behind distributed planning is to get the efficiency of parallel processing, the robustness of distributed systems and the simplicity of incremental construction and debugging. Due to an inherent distribution of resources such as knowledge, capability, information, and expertise among the agents, an agent in a distributed problem solving system is unable to accomplish its own tasks alone, or at least can accomplish its tasks better(more quickly, completely, precisely, or certainly) when working with others.In this paper, firstly, we propose two distributed flexible graphplan system: DFGP and IG-DFGP. Decomposition of goal and action set in DFGP is carried out manually and that in IG-DFGP is carried out automatically based on a new representation called interaction graphs. The sub-problems are compiled to rrDFCSPs. Our experimental results show that both these distributed planners are orders of magnitude faster than Graphplan.In addition, heuristic search methods are another important research field, because search method poses an magnitude influence on efficiency and quality of plan.Fast-Downward is a classical planning system based on heuristic search. It can deal with general deterministic planning problems encoded in the propositional fragment of PDDL2.2, including advanced features like ADL conditions and effects and derived predicates (axioms). Like other well-known planners, such as HSP and FF, Fast-Downward is a progression planner, searching the space of world states of a planning task in the forward direction. Unlike most other heuristic planners, whose state evaluations are based on ignoring negative interactions of operators, Fast-Downward uses hierarchical decompositions of planning tasks for computing its heuristic function, which we call the causal graph heuristic. FAST-DOWNWARD uses best-first search in its search phase. If there exits a plan, this search strategy assures finding the solution. Due to it chooses the state with the minimum heuristic value as the promising state, so the quality of the heuristic function is very important. Best-first search strategy computes all successors of the current state, while handling the large scale problems, it costs time and space. Although local search algorithm cannot ensure that it can find the solution, when there exits a plan, the expenditure of local search is less than best-first search, especially in solving large scale problems. Nowadays, many planners have already use local search strategy.In this paper, we implement enhanced hill-climb algorithm of local search method to instead the search strategy of the Fast-Downward. The experiments also show that the time overall is faster than best-first search method.