Research On The Heuristic-search-based AI Planning

Planning is the process of making decisions before taking actions: with a domain theory, an initial state and a goal, planning answers the question of"how to achieve the goal with a course of actions". AI planning focus on the theories, models and techniques that enable agents to do planning automatically. AI planning has been a main research field of Artificial Intelligence and have made big breakthrough in the recent fifteen years. A lot of successful research makes AI planning be a hot topic among those in Artificial Intelligence. Among the various planning methods, heuristic-search-based planning has been a powerful framework for efficient planning. There exist a number of search-based planners with rather good performance, such a HSP, FF and Fast Downward. This thesis makes an in-depth study on heuristic and pruning techniques, which are two keys underlying every search-based planning system.Based on the recent advances in planning, we have done the following works. On classical planning, we developed a new method for adjusting existing heuristic functions, and the application of this method on the heuristic function of Fast-Forward (FF) shows big improvement in terms of both solving-ability and solving-efficiency. We generalized the famous helpful actions pruning to a complete pruning technique on planning tasks with actions with conditional effects. On conformant planning, we designed a planner called JLU-CD that is able to handle conformant planning tasks with uncertain initial state. Based on a kind of human's common knowledge, we developed a novel heuristic function which is then extended to variants that concerning computation cost and informativeness. Specifically, we make the following contributions.(1) Heuristic function is a key to search-based planning; the more accurate a heuristic function is the higher probability it has of leading the search to the optimal solution. We obtain more accurate heuristic functions by adjusting existing ones and raise a method named post-adjustment. The adjusting is based on the"relaxed plan"generated within the computation of a heuristic function. Post-adjustment is motivated by the fact that ignoring delete lists has been a popular method in designing heuristic functions and based on which many existing heuristics define a relaxed plan either explicitly or implicitly. We view relaxed plans as an information source for doing adjustment to heuristic functions: the orders of actions as temporal constraints and delete effects of actions as negative interactions among sub-goals. We firstly defined a notion of relaxed action execution for post-adjustment,where the satisfaction of an action's precondition is not required. We then simulate the execution of a relaxed plan from the initial state with the relaxed action execution semantics, and take the number of unsatisfied conditions of an action as an error. The errors of every actions are finally combined to be an adjustment-function relative to the original heuristic guessing the cost for extending the relaxed plan into a valid plan. The novelty of our method is the concern of temporal constraints over actions imposed by a relaxed plan that were ignored by Yoon et al. in their learning to adjust method. We applied post-adjustment to hFF and got a new heuristic called h(FF,prv). Experimental results show that h(FF,prv) improves upon hFF much, especially, on hard problems. (2) Search-based methods face a huge state paces and hence need effective pruning techniques to reduce the search space."Helpful actions pruning"is such a one and its basic idea has been exploited in many state-of-the-art planning systems, such as YAHSP and Fast Downward. However,"helpful actions pruning"is not so effective in ADL domains where conditional effects exist. We study the property of"helpful actions pruning"in a formal way. Firstly, we generalize its idea to a complete prune technique for STRIPS planning called"goal-relevant actions", and then use a type of ADL tasks to prove the incompleteness of the"goal-relevant actions pruning"in ADL planning, which then motivates a complete pruning technique called"goal-and-confrontation relevant actions". We also discuss some issues on using the latter pruning technique in a practical way. Two key findings of our work in this part are: a) FF's inefficiency on ADL tasks is mostly due to the over-pruning of"helpful actions pruning", not the"enforced hill-climbing"algorithm; b) the expressiveness of ADL requires the planning algorithm to have more complicate reasoning procedure.(3) Conformant planning is currently a main topic of AI planning, which concerns the problem of finding a sequence of actions in the case where initial state and effects of actions are uncertain and observations are not available during plan execution. Belief-state-based search methods for conformant planning are also powerful in conformant settings, as shown by POND and Conformant FF. We designed a planner called JLU-CD in this favor. JLU-CD reduces the memory cost of storing search space by translating a planning task with binary variables into one with multiple-valued variables. In this paper, we present some engineering issues and key techniques in the implementation. In JLU-CD, to represent belief-state explicitly by a set of possible states, we designed an algorithm for enumerating models of a formulae based on the well-known DP procedure in the automated theorem proving. To compute the reachable facts on a belief state efficiently, we designed an algorithm that eliminate redundant computation based on the transitivity of the reachability relation. Some future work on JLU-CD is also discussed.(4) Our fourth work is the design of a novel conformant planning heuristic function. This heuristic function is motivated by human's knowledge in handling problems with uncertainty: reducing uncertainty in the problem as much as possible before solving it. We discovered a kind of reduction called"strong-plan-reuse"among possible states in a belief state. To be specific, if the classical plan to goal for a possible state could be part of the plan for another possible state, we say the latter one can reuse the plan for the former one. The possibility of"strong-plan-reuse"is helpful for us in reducing uncertainty by executing a sequence of actions to transform one possible state into another one and then start planning there. As exact test of the possibility of"strong-plan-reuse"is as hard as the planning problem, we use the causal graph based heuristic hCG to got an approximate estimate. The estimations are then represented in a directed graph, where nodes stand for possible state and weighted arcs denote the estimate of cost of"strong-plan-reuse". Based on the graph, we developed a new heuristic called"strong-paln-reuse enhanced additive heuritic"--hadd-pr. The interesting result is that hadd-pr is a generalization of the additive heuristic hadd over belief-state with more information on positive interactions among possible states. We also make two extensions of hadd-pr: hlrt and hmix. While hlrt employs a"look-ahead one step"strategy to save computation cost, hmix is a combination of hadd and hlrt, and thus contains more information. Experimental results on benchmarks show JLU-CD with hmix has competitive solving-ability with Conformant FF. In conclusion, the work in this thesis concerns heuristics and pruning techniques. On the former, we developed a method to make heuristic functions more accurate in classical planning and raise a new heuristic function for conformant planning based on the discovery of human's common knowledge in handling problems with uncertainty. On the latter, we analyzed the incompleteness of"helpful actions pruning"and developed a complete pruning technique based on"confrontation". All the work is helpful in designing techniques to pursue efficiency in other types of planning systems.