Planning Algorithm Based On Heuristic Graph

Intelligent planning as an important branch of Artificial intelligence research,The main idea is, Starting from the known problems, Scheduled based on the objectives to be achieved,with A limited set of actions and Limited resources provided to implement the reasoning,Action sequence to achieve goals from analyzing as planning solutions.In today's industrial production and all areas of public life,intelligent planning has been widely applied.1995,Carnegie Mellon University, Blum and Furst, who put on graph theory is introduced into the field of intelligent planning,Nothing to do with the area of making intelligent planning algorithm efficiency has been improved significantly,and this also marks the emergence of modern intelligent planning system.As the field of intelligent planning in recent years as an important planning methods.Graph planning for the development of intelligent planning has played a powerful role in promoting.The proposition and the predicate on the map in this particular data structure,Analysis diagram logical relationships between nodes,and according to their structural characteristics Figure,regularity conclusions summarized,the whole search space as the search graph, and Planning solutions obtained,But in the expansion process and. the solution extraction phase,If you do not take into account the additional information the problem itself,Graph planning algorithm is Blindness,No information on the expansion of search methods need to generate a large number of nodes and it also contains many of them useless nodes,A waste of the memory also increases the algorithm's time complexity.Therefore, the research field of intelligent planning staff in the planning problem solving characteristics of both the algorithm itself based on the design characteristics of a variety of heuristics.Makes the solution of the whole solution space search is not blindness.Therefore, the original of the planning algorithm based on the design of appropriate heuristic to improve the efficiency,since HSP came in theAISP98,The researchers take full account of the planning graph structure of various factors that can be used to improve the solution efficiency,full use of the information given inspiration,From the space complexity and time complexity to enhance two aspects.As the problem size increases gradually,Of the planning algorithm time complexity and space complexity are polynomial growth in the size of,Basic reason is that Search space does not contain a complete solution,Therefore, before planning in the state space contains the complete solution,Extraction of all solutions are useless,These useless search will greatly increase the time complexity,reduce the efficiency of the algorithm,Therefore, many researchers tried various ways to delay the time of extraction solution or problems in the state space into information to guide the searching.Combination of these two,according to the knowledge,this article is on target with the proposition of the state layer,Heuristic function determined by setting the next node to be expanded,At the same time according to mutually exclusive relationship between nodes heuristic values obtained,Extended by adding further nodes to delay the start time of extraction solution,made before the start of the extraction solution in the extended state space planning must include a complete solution,and because the value added inspiration,played the entire state space reduction effect of about.And in the course of the search solution,Before using the state space between each node in the first phase of additional heuristic search for solutions to guide planning.Planning algorithm makes the solution of the classical chart in the extraction process is similar to the random depth-first into a heuristic guided depth-first search to improve the efficiency.