Research On Lookahead Strategy For Automated Planning

In about recent twenty years, automated planning technology has been advanced in terms of both solving efficiency and solving ability. The main leverage is from the idea of heuristic search based planning method. On this direction, many successful heuristics were developed to reduce the search space of a heuristic search procedure. In this paper, we investigated a new way in reducing the search space of such procedure.We incorporated two strategies into the search process. One strategy is expanding the search space with one action in each step, and the other strategy is expanding with a sequence of actions that is called macro actions. The latter strategy is called lookahead strategy. With lookahead strategy, the search algorithm can not only look one-step forward but also two or more step ahead. Therefore, the search effort towards a goal state can be reduced largely.Our key objective is to design a new method to build macro actions as long as possible. Towards this, we proposed a method that incorporates information from both the Relaxed Planning Graph (RPG) and the Landmark Graph (LG), which is different from previous works that consider only information from the RPG. Because that RPG reflects ordering of actions when delete effects were ignored and LG reflects actions’ ordering with respect to delete effects, our method has the potential to build longer macro actions than previous approaches do.In this dissertation, we review notions, techniques, and recent progress related to our work. We present our designed greedy best-first algorithm that incorporates lookahead strategy, and our algorithms for constructing macro actions using both RPG and LG. We also show, by example, the advantage of searching with macro actions. The algorithms were implemented on top of LAMA, a state-of-the-art automated planning system, and resulted in a new planning system we called LAMA-Macro. Preliminary results on benchmarks problems show that LAMA-Macro is better than LAMA in terms of the number of evaluated states.