Research On Heuristic Search Based Algorithms For Optimal Planning

AI planning is one of the oldest research areas in traditional artificial intelligence. In recent years, new planning techniques as heuristic search and propositional reasoning greatly improved the efficiency of traditional planning methods. Meanwhile applica-tions of AI planning are also growing, making AI planning again become one of the hottest research topics of artificial intelligence. In the past decade, heuristic function designing methods as delete relaxation and landmark have attracted attention of many researchers, and there are a lot of research results. However, most studies are directed to satisfying planning and non-admissible heuristic functions. This paper focuses on how to design efficient and accurate admissible heuristic functions, which can be used by A*algorithm to improve the efficiency of optimal planning.The paper includes three studies, The first is the use of MAXSAT encoding to compute the optimal delete relaxation heuristic function h+, the purpose is to com-pute planning-specific heuristic functions using general proposition automated reason-ing techniques. Secondly, we study the technique of lazy heuristic evaluation when multiple admisible heuristic functions are available. The technique enable us to re-duce computation time incured by expensive heuristic functions and allow us to use more expensive heuristic functions. Finally, we propose a generalized landmark called multi-value landmark, which can be used to model cardinality constraints. Admissible heuristics more accurate than delete relaxation ones can be extracted from multi-valued LANDMARKS. Specifically, the research is as follows:1. Given a heuristic function, A*algorithm can find the optimal solution by expanding minimal number of nodes. But when there are two or more heuristic functions, it’s not efficient to use the maximum heuristic. This paper presents a lazy heuristic function evaluation techniques for A*algorithm, the techinque can improve the efficiency of the search process by reducing the time spent on expensive heuristics without increasing the number of node expansion. The technique makes it possible to use computationally expensive cost heuristic functions in A*algorithm.2. We examine the problem of computing h+by encoding it as a MAXSAT problem. We develop a new encoding that utilizes constraint generation to support the com-putation of a sequence of increasing lower bounds on h+. At the same time, we ponit out that unsatisfiable cores of our MAXSAT encoding are action landmark, Using this connection we observe that our MAXSAT computation can be initialized with a set of LANDMARKS computed by LM-cut. The resulting heuristic is shown to dominate LM-cut function.3. Considering the limit of traditional LANDMARKS, we propose multi-value LAND-MARKS to model cardinality constraints. We show that multi-valued LANDMARKS can produce admissible heuristics more close to optimal heuristic function h*than delete relaxations and LANDMARKS relaxations. Meanwhile, we define the con-cept of regular transition propositions. By using connection of regular transition propositions and multi-valued LANDMARKS, we devise a linear programming based multi-valued LANDMARKS heuristic function hLPML. Experiments on benchmark planning problems show that compared to traditional landmark heuristics, hLPML is more informative and can achieve better coverage performance.