Landmark-based Heuristic Search Planning Method And Its Application

Intelligent planning is one of the hot topics in the field of artificial intelligence.Its theory and method can be widely used in robot path planning and event scheduling.Heuristic search-based planning is essential branch of intelligent planning area,the key solving method utilizes the heuristic information provided by domain knowledge to guide the search path in state space.Due to the high efficiency and the scalability to the problem scale,heuristic search-based planning becomes the research frontier in the field of intelligent planning,which receives extensive attention of the researchers at home and abroad.However,with the increasing complexity of problem structure and the gradual expansion of data scale in practical applications,traditional heuristic search methods are faced with the problem of state space combination explosion,which limits the improvement of solving efficiency and solving scale.To further compress the search space,to improve solution efficiency and solving scale,this paper introduces landmark to heuristic search planning to guide both the search algorithms and heuristic functions in a fine-grained way,proposes landmark-based random walk planning method,propositional landmark constrains-based heuristic evaluation method and cost pre-allocated-based heuristic evaluation method.The proposed theories were applied and proved efficiency in model-based diagnosis which is an artificial intelligence cross domain.The main contributions of this paper are detailed as follows:(1)Focusing on the inaccurate search direction problem in long distance-based search algorithm of heuristic search planning,this paper proposes landmark-based random walk planning method,which could decrease the dependence of the heuristic information and randomness of random walk search algorithm.Firstly,random walk-based planning method set random action chosen probability according to landmark information instead of equal probability to guide the directions of search,which could shrink the randomness of the original random walk-based searching algorithm,and perform fine-grained control of the search directions to achieve more landmarks gradually;Secondly,this paper introduces landmark count heuristic function to evaluate the heuristic value of the states,which could generate the plan quickly and increase the efficiency of problem solving by avoiding to visit the large number of states.In order to validate the performance of the proposed method,we evaluate our method in several classical domains in benchmarks,simulation results show that the random walk procedure could achieve long distance state transition more quickly,compress the search space obviously,increase the time efficiency while decrease the solving cost via the guidance of landmark information.(2)Focusing on the low accuracy and high computation complex problems of heuristic evaluation caused by insufficient investigation of domain knowledge.This paper proposes propositional landmark constrains-based heuristic evaluation method and cost pre-allocated-based heuristic evaluation method respectively.Firstly,propositional landmark constrains-based heuristic evaluation method,compared with landmark-cut heuristic based evaluation method,utilizes propositional landmark to modify premise positioning rule,constructs more reasonable decision graph,extracts action landmarks,perform cost assignment,and accumulates the max cost heuristic value as the final results;Secondly,cost pre-allocated heuristic evaluation method provided necessary cost by utilizing the supporting action of propositional landmark for relax planning problem,identifying the supporting actions of landmarks to be implemented in the searching path and complete cost pre-assignment which could decrease the computation cost caused by the large extraction cut set,in order to further increase the accuracy of heuristic evaluation methods;Finally,this paper combines the best first searching algorithm to increase the problem solving efficiency.In order to evaluate the performance of the proposed methods,we evaluate our method in several classical domains of benchmarks,simulation results show that the two proposed methods decrease the number of evaluated states,increase the accuracy of heuristic evaluation value while decrease the computation complexity compared with the traditional landmark-cut-based evaluation method.(3)Applying planning to model-based diagnosis area,focusing on the inaccuracy of candidate diagnostic in diagnosis problem,this paper proposes a landmark heuristic-based fault detection and accelerating method,which could guide the fault searching procedures and recover the candidate diagnosed via planning methods.Firstly,a combined model with diagnosis and planning were built.The incremental diagnosis is used as the initial state of the program and the heuristic search method is used to solve the non-fault state.Secondly,planning algorithm with fault robustness was proposed to solve the possible fault problems in the search process.Focusing on the multi-candidate trajectories in incremental diagnosis,a detecting method using trajectory planning and based on landmark is proposed.Two different fault diagnosis and repair algorithms are designed: one is to repair all possible faults using controlled events to repair faults;the other is to test by feedback of controlled events and observable events to obtain unique solutions and repair faults.Experimental results show that the proposed algorithm can effectively solve the problem of diagnosis and improved the accuracy.To conclude,this paper uses landmarks to guide both the search algorithms and evaluation functions of heuristic search-based planning methods in a fine-grained way,the efficiency of random walk was optimized while the quality and efficiency of the evaluation functions were also increased compared with traditional methods which were validated in benchmarks.The planning method is applied to model-based diagnosis which improved the efficiency of diagnosis and recovered the diagnostic results.Simulation results show that the methods proposed in this paper do can increase the efficiency and quality of problem solving,expand the application area of planning methods,which has great significance both from theoretical and practical respects.