Research On Strategies Of Heuristic Search In AI Planning

AI planning has been a main research field of Artificial Intelligence. In recent ten years,the research of AI planning has made a big breakthrough and obtained significantimprovement in both planning efficiency and quality of the plans. Heuristic search planninghas been a hot topic and one of the most powerful planning methods. The basic idea ofheuristic search framework is to guide the search procedure with some domain knowledge andmake the search direction going towards to the goal rapidly. The usage of heuristicinformation can mitigate the combination explosion of the search space effectively.The main difficulty of heuristic search planning is the poor performance for problemswith complicated structure or big size. Researchers have introduced kinds of new searchalgorithms into the heuristic search planning framework, and it is still a huge challenge todesign an accurate and common heuristic function. Moreover, pruning is another importantstrategy to control the size of the search space.This thesis mainly focuses on the search algorithm and pruning strategy, both of whichare crucial to performance of planning systems based on heuristic search. With theinformation provided by heuristic evaluation, the selected search algorithm determines theorder to explore the states in the search space. The difference of various search algorithms isthe tie-breaking rule in face of all the candidate states. Good decision can help to solve theplanning problem quickly and obtain a shorter solution, which would save the cost of thesearch procedure. Therefore, the rule of tie-breaking has a great influence on the behavior ofsearch algorithm. We proposed flexible heuristic search algorithms for classical andconformant planning tasks according to their structures, the main contributions include:The idea of landmark-counting heuristic is to guide the search towards the states thatachieve more landmarks, which seems to be a segment heuristic of the search space. Weproposed a search algorithm that decomposes the planning task with the estimation of thelandmark-counting heuristic, where the original planning task is decomposed into severalsmaller sub-tasks implicitly. During the forward search, the decrease of thelandmark-counting heuristic value causes the task decomposition. Such sub-task procedure isrepeated until the estimation of the landmark-counting heuristic decreased to zero in the goalstate. The landmark-counting heuristic plays an assistant role in the whole search procedure,evaluating the computation that is necessary to reach the goal from each search state, whichmakes a better use of the landmark information. Experiment results on the representationalbenchmarks show the superiority of our algorithm. Compared to the multi-queue heuristicsearch and the task decomposition that treats the landmarks as mandatory intermediate subgoals, our planning algorithm based on the implicit task decomposition leads aconcentrated search direction, which could guide the forward search procedure towards thegoal faster and cut down the search space dramatically.The planning system Conformant-FF translates conformant planning tasks into beliefspace search problems and adopts the enforced hill-climbing algorithm guided by the relaxedplan heuristic function. However, the helpful actions given by implications about theunknown propositions may make mistakes on domains that contain plenty of uncertaininformation, which makes Conformant-FF show bad performance on such domains. Withregard to this limitation, we propose a conformant planning algorithm that reduces thenondeterministic degree of belief states. The algorithm includes two phases of enforcedhill-climbing, which are used to reduce belief states and search for the goal respectively.Before searching for the given goal condition, the initial belief state is reduced furthest to anintermediate state which is much more deterministic. After that, the precision of heuristicevaluation is improved and the second normal enforced hill-climbing phase is executed fromthis intermediate state. We implement our idea based on Conformant-FF, design a planningsystem named CFF-Lite and experiment on a number of conformant benchmarks. The resultsshow that CFF-Lite can decrease the difficulty of conformant planning problems by reducingbelief states and our algorithm outperforms Conformant-FF in both planning efficiency andthe quality of plan.Heuristic evaluation of the search states is one of the most time-consuming parts duringthe search procedure, thus the number of visited states affects the time efficiency directly.Pruning strategy controls the size of the search space when expanding the search states, whichcould decrease the states visited by the search algorithm. Excellent pruning strategy shouldkeep the states that are helpful to solve the problem faster and dump all the states that wouldget far away from the goal state or slow the search process down. Pruning is quite importantfor the performance of heuristic search algorithms. Heuristic function based on relaxed planprovides the helpful action pruning strategy, where the actions that may get closer to the goalare recognized as helpful. The helpful actions generate a set of promising successors to eachsearch state, bringing a compression of the search space. We propose to construct new pruningstrategies for conformant and contingent planning tasks on basis of helpful actions. Ourcontributions are as follows:On analysis of the conformant relaxed plans, we get the “solving by cases” semantic ofthe implication paths for subgoals in the relaxed planning graph and introduce a furtherdefinition of helpful implication paths. We propose the novel pruning strategy of helpfulimplication paths for conformant planning tasks. A helpful implication path is usually madeup of several helpful actions. When expanding the belief states, executing all actions within ahelpful implication path can achieve some subgoal while executing an individual action cannot due to incomplete information. This strategy usually explores a much further range of thesearch space within one search iteration, and thus leads to the goal faster. We experiment on a number of conformant benchmarks to evaluate our idea. The results show that our pruningstrategy performs better than the old helpful action strategy for conformant planning tasks.The pruning strategy of helpful implication path can concentrate on the uncertainty of theestimated belief state when exploring the search space, reduce the number of visited states andbring an improvement of runtime efficiency.To overcome the shortcoming that helpful actions under contingent planning fail to findbranching plans, a pruning strategy with enforced observations is presented. We change theway to treat the effects with unknown condition in the first level, making the uncertainty ofthe estimated belief state have opportunities to be observed. Then the adjusted relaxed plancan collect the observation actions that sense the truth value of the current unknownpropositions, and recognize them as helpful actions, which means to perform enforcedobservations to the uncertain information in the environment. The branching plan represents aconditional semantic that applies different actions according to the result of observation atruntime. With our revision, the unreasonable conformant actions can be excluded from the setof helpful actions and consequently we cut all the non-branching plans out of the solutionspace, which can improve the planning efficiency as well as the plan quality. Experimentresults on the representational contingent benchmarks have proven the superiority of ourpruning strategy in generating branching plans.In conclusion, this thesis concerns the search algorithms and pruning strategies inheuristic search planning framework for classical planning and nondeterministic planning, thecontributions are significant for the improvement of planning efficiency and the plan quality.