정보력이 높은 허용 가능 휴리스틱들은 최적의 해를 찾기 위한 탐색을 보다 효율적으로 유도할 수 있다. 하지만 계획 문제 명세로부터 이러한 정보력이 높은 휴리스틱들을 추출하는 것은 일반적으로 매우 많은 계산 노력을 요구한다. 이러한 문제점들에 효과적으로 대처하기 위해, 본 논문에서는 최적 계획수립 문제들을 보다 효율적으로 풀 수 있는 확장 계획 그래프(EPG)와 MAX+ 휴리스틱을 제안한다. 확장 계획 그래프를 이용하는 MAX+ 휴리스틱은 효과적인 방법으로 (부속)목표 조건들간의 긍정적, 부정적 상호작용들을 찾아내고, 이들을 최소 목표 도달 거리 계산에 이용한다. 따라서 MAX+ 휴리스틱은 허용성을 보장할 뿐만 아니라, 종래의 최대 휴리스틱보다 더 높은 정보력을 가진다. 본 논문에서는 MAX+ 휴리스틱을 계산하는 알고리즘을 제시하고, MAX+ 휴리스틱의 정확성과 효율성을 알아 보기 위한 실험적 분석에 대해 설명한다.
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.
