1316.33 추상화 휴리스틱의 원리
1. 추상화의 개념
추상화 휴리스틱(abstraction heuristic)은 원래 플래닝 문제를 더 작은 추상 문제(abstract problem)로 사상(mapping)하고, 추상 문제의 최적 비용을 원래 문제의 휴리스틱으로 사용하는 기법이다. 추상 문��의 상태 공간이 원래 ��제보다 작으므로 최적 비용을 ���율적으로 계산할 수 있으며, 올바른 추상화가 사���되면 허용 가능(admissible) 휴리스틱을 제공한다.
2. 형식적 정의
추상 사상 \alpha: S \rightarrow S^{\alpha}은 원래 상태 ���간의 상태를 추상 상태 공간의 상태로 사상한다. 추상화 휴리스틱은 다음과 같이 정의된다:
h^{\alpha}(s) = h^*({\alpha}(s))
여기서 h^*(\alpha(s))는 추상 상태 공간에서 \alpha(s)에서 추상 목표까지의 최적 비용이다.
3. 허�� 가능성 조건
추상화 휴리스틱이 허용 가능하려면, 추상화가 동형 축소(homomorphic reduction)이어야 한다:
- 원래 문제의 각 연산자가 추상 문제의 연산자에 대응하거나 항등 전이로 축소된다
- 추상 전이의 비용이 원래 전이의 비�� 이하이다
이 조건이 충족되면, 추상 문제의 최적 비용은 원래 문제의 최적 비용의 하한이 된다:
h^{\alpha}(s) \leq h^*(s)
4. 주요 추상화 기법
4.1 투영(Projection)
SAS+ 변수의 부분 집합에만 관심을 두고 나머지 변수를 무시하는 추상화이다:
\alpha_P(s) = s \restriction P \quad \text{(변수 집합 $P$에 대한 투영)}
투영은 패턴 데이터베이스(Pattern Database, PDB) 휴리스틱의 기초이다.
4.2 합병-축소(Merge-and-Shrink)
변수를 합병(merge)하여 새로운 합성 변수를 생성하고, 상태 공간이 너무 커지면 축소(shrink)하여 크기를 제한하는 기법이다(Helmert et al., 2007):
- 합병: 두 변수 v_1, v_2의 도메인을 결합하여 v_{12}의 도메인 = D_1 \times D_2
- 축소: 합병된 변수의 도메인이 임계값을 초과하면, 유사한 추상 상태를 통합하여 크기를 줄임
4.3 카르테시안 추상화(Cartesian Abstraction)
CEGAR(Counterexample-Guided Abstraction Refinement) 기법을 활용하여, 초기의 매우 거친 추상화를 반례에 의해 점진적으로 정제하는 기법이다(Seipp & Helmert, 2013).
5. 추상화 휴리스틱의 특성
| 기법 | 허용 가능 | 정보성 | 사전 계산 | 런타임 비용 |
|---|---|---|---|---|
| PDB | 예 | 패턴 크기에 의존 | 높음 | 낮음 (테이블 조회) |
| 합병-축소 | 예 | 높음 | 높음 | 낮음 (테이블 조회) |
| 카르테시안 | 예 | 높음 | 중간 | 낮음 |
| 투영 (단일) | 예 | 낮음~중간 | 낮음 | 낮�� |
사전 ���산(precomputation)이 필요한 대신, 런타임 시 휴리스틱 평가가 테이블 조회로 수행되어 매우 빠르다.
6. 가산 추상화(Additive Abstraction)
여러 독립적 추상화의 휴리스틱 값을 합산하여 더 정보적인 휴리스틱을 구성할 수 있다. 추상화들이 서로 독립적(겹치지 않는 연산자 비용)이면 합산 결과도 허용 가능하다.
7. 로봇 도메인에서의 추상화
로봇 도메인에서 ���상화의 자연스러운 적용:
- 위치 투영: 로봇 위치 변수만 남기고 나머지(적재, 센서 등) 무시 → 경로 비용 추정
- 물체 투영: 특정 물체의 상태만 남기고 나머지 무시 → 개별 물체 배달 비용 추정
- 로봇별 투영: 특정 로봇 관련 변수만 남기고 다른 로봇 무시 → 개별 로봇 비용 추정
8. 참고 문헌
- Helmert, M., Haslum, P., & Hoffmann, J. (2007). “Flexible Abstraction Heuristics for Optimal Sequential Planning.” Proceedings of ICAPS, 176–183.
- Seipp, J. & Helmert, M. (2013). “Counterexample-Guided Cartesian Abstraction Refinement.” Proceedings of ICAPS, 347–351.
- Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.