Research Of Temporal Planning Algorithm Based On Flexible GraphPlan

Artificial intelligence planning is an important research area in artificial intelligence. A.L.Blum and M.L.Furst introduced a fast planning method through graph analysis——Graphplan in 1995.Just as Graphplan, for a solution, Flexible Graphplan alternates between two phases: flexible graph expansion and solution extraction. Except this, Flexible Graphplan introduces soft constraints, truth degrees of propositions, satisfaction degrees of actions and satisfaction degrees of goals. Plan satisfaction degrees are calculated from the satisfaction degrees of their constituent instantiated operators and goals, enabling a direct comparison amongst a number of plans containing different compromises. A range of plans of different lengths and containing alternative compromises can be synthesized from a given flexible planning problem. The user can then select the one which is deemed to offer the best compromise between length and satisfaction degree.The flexible actions are instantaneous; the flexible planner can't deal with durative actions defined by Planning Domain Description Language 2.1 (PDDL2.1).This paper proposes concepts of path graph and mobile actions. This paper proposes also presents an algorithm which is able to deal with durative actions. The basic method is to find a flexible plan with instantaneous actions through flexible graph expansion and solution extraction firstly. Secondly, a path graph is abstracted from the flexible graph. Analyze the relationships between actions in the flexible plan, find out mobile actions. Thirdly let mobile actions and other actions parallel to shorten the executive of the plan. The start time of actions in the plan should be calculated according to the relationships between actions in the flexible plan, so a flexible temporal plan will be found.The flexible temporal algorithm in flexible Graphplan Framework is able to deal with durative actions and put out temporal plan. The plan is more reasonable. We implemented the algorithm and experimented on"logistics"domain. The experimental results have shown that temporal compressing algorithm is efficient to reduce the execution time of flexible temporal plan.Providing such an ability is a significant step forward for the real-world utility of planning research. Flexible is a new area, but there are little research about temporal planning in flexible Graphplan framework. So this research on flexible temporal planning is very important both theoretically and practically.