1316.34 패턴 데이터베이스 기반 휴리스틱

1. 패턴 데이터베이스의 정의

패턴 데이터베이스(Pattern Database, PDB)는 Culberson과 Schaeffer(1998)가 제안한 휴리스틱 기법으로, SAS+ 변수의 부분 집합(패턴)에 대한 투영 공간에서 모든 추상 상태의 최적 비용을 사전 계산하여 테이블에 저장하는 방식이다. 탐색 중 휴리스틱 평가는 단순한 테이블 조회로 수행되어 극히 빠르다.

2. PDB의 구성 과정

2.1 단계: 패턴 선택

SAS+ 변수의 부분 집합 P = \{v_{i_1}, v_{i_2}, \ldots, v_{i_k}\}를 패턴으로 선택한다. 패턴에 포함되지 않은 변수는 투영에서 무시된다.

2.2 단계: 추상 상태 공간 구성

패턴 P의 변수만으로 구성된 추상 상태 공간을 구성한다. 추상 상태의 수는:

\lvert S^P \rvert = \prod_{v_j \in P} \lvert D_j \rvert

2.3 단계: 역방향 BFS로 최적 비용 계산

추상 목표 상태에서 역방향 BFS(또는 Dijkstra)를 수행하여, 모든 추상 상태에서 목표까지의 최적 비용을 계산한다.

2.4 단계: 테이블 저장

각 추상 상태와 최적 비용을 해시 테이블 또는 배열에 저장한다.

3. 런타임 휴리스틱 평가

탐색 중 상태 s의 휴리스틱 값은 다음과 같이 계산된다:

h^{\text{PDB}}(s) = \text{lookup}(\alpha_P(s))

여기서 \alpha_P(s)는 상태 s를 패턴 P에 투영한 추상 상태이다. 이 평가는 O(k) (k: 패턴 크기)의 투영 계산과 O(1)의 테이블 조회로 수행된다.

4. 가산 PDB (Additive PDB)

단일 패턴의 PDB는 정보성이 제한적이므로, 여러 패턴의 PDB 값을 합산하여 더 정보적인 휴리스틱을 구성한다:

h^{\text{add-PDB}}(s) = \sum_{i=1}^{m} h^{P_i}(s)

합산이 허용 가능하려면, 패턴 간에 연산자 비용이 겹치지 않아야 한다(비용 분할, cost partitioning):

• 각 연산자의 비용을 패턴들에 분배
• 각 패턴은 할당된 비용만으로 PDB를 계산
• 합산 결과가 허용 가능

5. iPDB (Incremental PDB)

Haslum et al.(2007)이 제안한 iPDB는 소규모 패턴에서 시작하여 휴리스틱의 정보성을 분석하면서 패턴을 점진적으로 확장하는 기법이다:

iPDB():
    patterns ← {individual variables}
    REPEAT:
        candidate ← SELECT_BEST_EXTENSION(patterns)
        IF improvement(candidate) > threshold:
            patterns ← patterns ∪ {candidate}
        ELSE:
            BREAK
    RETURN PDB(patterns)

6. PDB의 특성

7. 로봇 도메인에서의 패턴 선택

로봇 도메인에서 효과적인 패턴의 예시:

• {로봇 위치}: 이동 비용의 하한 추정
• {물체 위치, 로봇 위치}: 개별 물체 배달 비용 추정
• {배터리 잔량, 로봇 위치}: 에너지 제약 하의 이동 비용 추정

8. 참고 문헌

• Culberson, J. C. & Schaeffer, J. (1998). “Pattern Databases.” Computational Intelligence, 14(3), 318–334.
• Haslum, P., Botea, A., Helmert, M., Bonet, B., & Koenig, S. (2007). “Domain-Independent Construction of Pattern Database Heuristics for Cost-Optimal Planning.” Proceedings of AAAI, 1007–1012.
• Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.