조건부 계획수립을 위한 효과적인 그래프 기반의 휴리스틱 (Effective Graph-Based Heuristics for Contingent Planning)

서지정보

· 발행기관 : 한국정보처리학회
· 수록지 정보 : 정보처리학회 논문지 / 18권 / 1호 / 29 ~ 38페이지
· 저자명 : 김현식, 김인철, 박영택

초록

계획 문제 명세로부터 영역-독립적인 휴리스틱을 유도해내기 위해서는 주어진 계획문제에 대한 간략화와 간략화된 계획문제에 대한 해 도출 과정이 요구된다. 본 논문에서는 초기 상태의 불확실성과 비결정적 동작 효과를 모두 포함한 조건부 계획문제를 풀기 위한 새로운 융합 계획그래프와 이것을 이용한 GD 휴리스틱 계산법을 소개한다. 융합 계획그래프는 고전적 계획 문제 풀이를 위한 휴리스틱 계산에 이용되는 간략화된 계획그래프를 조건부 계획문제에 적용할 수 있도록 확장한 자료구조이다. 융합 계획그래프에서는 감지 동작과 비결정적 동작들을 포함한 조건부 계획 문제에 대한 휴리스틱을 얻기 위해, 전통적인 삭제 간략화외에도 감지 동작과 비결정적 동작들에 대한 효과-융합 간략화를 추가로 이용한다. 융합 계획 그래프 의 전향 확장과 병행적으로 진행되는 GD 휴리스틱 계산에서는 목표조건들 간의 상호 의존성을 분석하여 전체 목표 집합에 대한 최소 도달비용을 추정할 때 불필요한 중복성을 배제한다. 따라서 GD 휴리스틱은 기존의 겹침 휴리스틱보다 더 적은 계산시간을 요구하면서도, 최대 휴리스틱이나 합산 휴리스틱보다 더 높은 정보력을 가진다는 장점이 있다. 본 논문에서는 GD 휴리스틱의 정확성과 탐색 효율성을 확인하기 위한 실험적 분석에 대해 설명한다.

영어초록

In order to derive domain-independent heuristics from the specification of a planning problem, it is required to relax the given problem and then solve the relaxed one. In this paper, we present a new planning graph, Merged Planning Graph(MPG), and GD heuristics for solving contingent planning problems with both uncertainty about the initial state and non-deterministic action effects. The merged planning graph is an extended one to be applied to the contingent planning problems from the relaxed planning graph, which is a common means to get effective heuristics for solving the classical planning problems. In order to get heuristics for solving the contingent planning problems with sensing actions and non-deterministic actions, the new graph utilizes additionally the effect-merge relaxations of these actions as well as the traditional delete relaxations. Proceeding parallel to the forward expansion of the merged planning graph, the computation of GD heuristic excludes the unnecessary redundant cost from estimating the minimal reachability cost to achieve the overall set of goals by analyzing interdependencies among goals or subgoals. Therefore, GD heuristics have the advantage that they usually require less computation time than the overlap heuristics, but are more informative than the max and the additive heuristics. In this paper, we explain the experimental analysis to show the accuracy and the search efficiency of the GD heuristics.

참고자료

· 없음