Extended Graph-Based Heuristics for Optimal Planning

More informative ones of admissible heuristics can help to conduct search more efficiently to obtain optimal solutions. However, in general, to derive highly informative heuristics from problem specifications requires lots of computational effort. To address this problem, we propose an Extended Planning Graph(EPG) and MAX+ heuristics for solving optimal planning problems more efficiently. MAX+ heuristics utilizing EPG graphs can find both positive and negative interactions between (sub)goal conditions in an effective way, and then consider them to estimate the minimal goal distance. Therefore MAX+ heuristics can not only guarantee admissibility, but also have more information than the existing max heuristics. In this paper, we present the algorithm to compute MAX+ heuristics, and then explain empirical analysis to investigate the accuracy and the efficiency of the MAX+ heuristics.