1316.37 랜드마크 기반 휴리스틱의 원리

1. 랜드마크의 정의

플래닝에서 랜드마크(landmark)는 모든 유효한 계획에서 반드시 달성(참이) 되어야 하는 사실(fact)이다. 형식적으로, 사실 $l$ 이 플래닝 문제 $\mathcal{P}$ 의 랜드마크이려면:

$\forall \pi \in \text{Plans}(\mathcal{P}): \exists i \in \{0, \ldots, \lvert\pi\rvert\}: s_i \models l$

즉, 초기 상태에서 목표 상태까지의 모든 유효한 계획의 실행 경로에서, 적어도 한 시점에 $l$ 이 참이어야 한다(Hoffmann, Porteous, & Sebastia, 2004).

2. 랜드마크의 유형

2.1 사실 랜드마크(Fact Landmark)

특정 사실(명제)이 반드시 달성되어야 하는 랜드마크:

;; 물체를 배달하려면 반드시 집어야 함
(holding r1 box1)  → 사실 랜드마크

;; 목표 자체도 사실 랜드마크
(delivered box1 customer1)  → 목표 사실 = 랜드마크

2.2 선언적 랜드마크(Disjunctive Landmark)

여러 사실 중 적어도 하나가 달성되어야 하는 랜드마크:

;; 물체를 집으려면 로봇이 해당 위치에 있어야 함
;; 여러 경로 중 하나를 거쳐야 함
{(robot_at r1 wp1), (robot_at r1 wp2)}  → 선언적 랜드마크

2.3 액션 랜드마크(Action Landmark)

특정 액션이 모든 계획에 반드시 포함되어야 하는 경우:

;; box1이 wp1에 있고 배달이 필요하면, pick(r1, box1, wp1)이 랜드마크

3. 랜드마크와 순서 관계

랜드마크 간에는 순서 관계(ordering)가 존재한다:

3.1 자연 순서(Natural Ordering)

$l_1$ 이 $l_2$ 보다 먼저 달성되어야 하는 경우:

$l_1 \rightarrow_n l_2 \iff l_1 \text{은 } l_2 \text{ 이전에 반드시 참}$

3.2 필요 순서(Necessary Ordering)

$l_1$ 이 $l_2$ 직전에 참이어야 하는 경우:

$l_1 \rightarrow_r l_2 \iff l_1 \text{은 } l_2 \text{를 달성하는 액션의 전제 조건에 포함}$

3.3 탐욕적 필요 순서(Greedy-Necessary Ordering)

삭제 완화 문제에서의 필요 순서로, 자연 순서의 근사이다.

4. 랜드마크 휴리스틱

4.1 $h^{\text{LM-count}}$ (랜드마크 수 휴리스틱)

미달성 랜드마크의 수를 휴리스틱 값으로 사용한다:

$h^{\text{LM-count}}(s) = \lvert\{l \in \mathcal{L} \mid l \text{ has not been achieved on path to } s\}\rvert$

비허용 가능하지만 정보적이며, LAMA의 기본 휴리스틱이다.

4.2 $h^{\text{LM-cut}}$ (랜드마크 컷 휴리스틱)

Helmert와 Domshlak(2009)이 제안한 허용 가능 휴리스틱으로, 삭제 완화 문제에서의 최소 비용 컷을 계산한다. 비용 최적 플래닝에서 최고 수준의 정보성을 제공한다.

5. 랜드마크 추출

랜드마크 추출은 도메인 분석을 통해 자동으로 수행된다:

후방 체이닝: 목표에서 역방향으로 필요 조건을 추적하여 랜드마크를 식별
삭제 완화 기반: 삭제 완화 문제에서의 분석을 통해 랜드마크를 추출
반복 삭제 분석: 하나의 액션이 모든 유효 계획에 필수적인지를 반복적으로 검증

6. 랜드마크의 로봇 도메인 활용

로봇 도메인에서의 랜드마크 예시:

목표: (delivered box1 customer_loc)

랜드마크 체인:
(robot_at r1 box_loc)  →  (holding r1 box1)  →  (robot_at r1 customer_loc)  →  (delivered box1 customer_loc)

;; 로봇이 물체 위치에 도달해야 하고,
;; 물체를 집어야 하고,
;; 고객 위치에 도달해야 하고,
;; 배달을 완료해야 한다.

이 랜드마크 체인은 플래너에게 “어떤 중간 목표를 순서대로 달성해야 하는지“의 구조적 정보를 제공한다.

7. 참고 문헌

Hoffmann, J., Porteous, J., & Sebastia, L. (2004). “Ordered Landmarks in Planning.” Journal of Artificial Intelligence Research, 22, 215–278.
Helmert, M. & Domshlak, C. (2009). “Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway?” Proceedings of ICAPS, 162–169.
Richter, S. & Westphal, M. (2010). “The LAMA Planner.” Journal of Artificial Intelligence Research, 39, 127–177.