Research On Backwards Generated Goals For Planning

Intelligence planning (AI planning) is one of the most advanced research branches of AI. Intelligent planning techniques can be used in many areas, such as spacecraft, satellites, robot controlling, scheduling of factory floor assembly line work, logistics management and some kinds of game play, etc. So, research in AI planning has gradually become a hot spot.Essentially, Intelligence planning is reasoning for actions. In Intelligence planning problem, there is a given initial state, a goal and a limited set of actions; the action set contains some actions. What Intelligence planning should do is to find a plan which contains several actions arranged in a certain order. If agents act these actions orderly, certain goal can be achieved. The purpose of Intelligence planning is to achieve the original goal the faster the more efficiency the better.State-space planning algorithm is one of the classical algorithms in planning fields. In This planning algorithm, the space of searching is a part of the state space:a node represents a state, an arc represents an action, and a plan is represented by a path from the initial state to the target state. Prime planning algorithms without domain knowledge are inefficient, with a large number of nodes to be extended. To improve efficiency, heuristic information can be used to reduce the searching overhead. Planning algorithm using heuristic information is called heuristic planning. Forward planning algorithm is a simple planning algorithm, which starts from the initial state and applies the appropriate actions constantly until the target state is achieved. Forward State Planning with Heuristics is arguably the most successful and most mature approach, which involves estimation for the distance from current state to the original goal. And most Heuristics are based on relaxation of problem. This kind of estimation is information, such as beneficial operations or precursor state, about problem, which is extracted from reasoning process step by step. With this information, planning can expand along the direction with more chances to achieve the goal.In this paper, we propose a new method which takes advantage of information about the goal state. This method implements the backwards planning process from the goal state to initial state by extracting useful information from the goal state and the last actions which make the goal to be achieved. In addition, a heuristic function is designed to guide algorithm to choose appropriate nodes to extend. Backward reasoning and backwards generate intermediate goals are executed alternately until the initial state is reached with a solution path from the goal to initial state generated at the same time. Since the goal state is a set of propositions, so there are several actions that can be applied to the goal state. These actions may be not independent, so we should select those independent actions by using Mutex of planning-graph techniques and then apply those actions to current state. In this way, on the one hand, the effectiveness and feasibility of action set are ensured. Meanwhile the idea that multiple actions are considered at the same time is realized. This method can reduce both the depth of the search tree and the amount of extended nodes. Therefore, this algorithm can improve planning performance substantially.In this way, the level of time complexity and space complexity can be lowered, and the search can be completed more quickly. Firstly, the searching from initial state to goal state is transformed into the one from goal state to initial state. Then a partial ordered action set is got by tracing back the generation of the intermediate goals. Finally, a complete solution plan to the problem is generated. This approach lies in the expansion of information (the expansion of the intermediate goals set and the computation of heuristic function).