1315.24 메트릭 최적화 목표의 정의

1. 메트릭의 개념

PDDL에서 메트릭(metric)은 계획의 품질을 정량적으로 평가하기 위한 목적 함수(objective function)이다. 문제 파일의 :metric 절에서 정의되며, 플래너가 계획을 생성할 때 이 목적 함수를 최소화 또는 최대화하는 방향으로 탐색을 유도한다.

2. 구문

(:metric <direction> <numeric-expression>)

여기서 <direction>은 minimize 또는 maximize이고, <numeric-expression>은 수치 플루언트 또는 산술 표현식이다.

3. 메트릭 정의의 유형

3.1 단일 함수 최적화

;; 총 비용 최소화
(:metric minimize (total_cost))

;; 총 보상 최대화
(:metric maximize (total_reward))

;; 총 이동 거리 최소화
(:metric minimize (total_distance))

3.2 복합 함수 최적화

산술 연산자를 사용하여 여러 함수를 결합한다:

;; 에너지와 시간의 가중 합 최소화
(:metric minimize (+ (* 0.7 (total_energy)) (* 0.3 (total_time))))

;; 비용에서 보상을 뺀 순비용 최소화
(:metric minimize (- (total_cost) (total_reward)))

;; 다중 페널티 합산
(:metric minimize (+ (total_distance) (* 5 (total_risk)) (* 10 (penalty_count))))

3.3 계획 길이 최소화

각 액션에서 비용을 1씩 증가시키는 패턴으로 계획 길이를 최소화한다:

(:functions (total_actions))
;; 모든 액션에서: (increase (total_actions) 1)
(:metric minimize (total_actions))

4. 메트릭의 평가 시점

메트릭의 수치 표현식은 계획 실행 완료 후의 최종 상태에서 평가된다. 즉, 초기 상태에서 계획의 모든 액션을 순차적으로 적용한 후의 수치 함수 값이 메트릭 값이 된다:

\text{metric\_value}(\pi) = \text{eval}(e, s_n)

여기서 \pi는 계획, e는 메트릭 표현식, s_n은 계획 실행 후 최종 상태이다.

5. 메트릭과 플래너의 상호 작용

5.1 최적 플래너

비용 최적 계획을 보장하는 플래너(A* 기반)는 메트릭 값이 수학적으로 최소(또는 최대)인 계획을 탐색한다. 허용 가능 휴리스틱(admissible heuristic)이 필요하다.

5.2 만족 플래너

유효한 계획을 빠르게 찾는 플래너(LAMA, FF 등)는 메트릭을 참고하여 계획 품질을 개선하지만, 최적성을 보장하지 않는다.

5.3 반복적 개선 플래너

초기 계획을 생성한 후 반복적으로 개선하여 메트릭 값을 점진적으로 향상시킨다.

6. 메트릭 미정의 시의 기본 동작

:metric 절이 문제 파일에 포함되지 않으면, 플래너에 따라 기본 동작이 다르다:

7. 메트릭 설계의 모범 사례

1. 단일 스칼라 값으로 표현: PDDL은 단일 메트릭만 지원하므로, 다중 목표는 가중 합으로 결합한다.
2. 비용 함수의 초기값을 0으로: (:init (= (total_cost) 0))
3. 양의 비용만 사용: 음의 비용은 무한 루프 가능성이 있다.
4. 모든 비용 발생 액션에서 갱신: 누락 없이 비용을 반영한다.
5. 가중치의 민감도 분석: 복합 메트릭의 가중치에 따라 계획 특성이 달라지므로, 다양한 가중치로 실험한다.

8. 참고 문헌

• Fox, M. & Long, D. (2003). “PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains.” Journal of Artificial Intelligence Research, 20, 61–124.
• Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.
• Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.