1314.38 메트릭 기반 최적화 목표 설정

1314.38 메트릭 기반 최적화 목표 설정

1. 메트릭 구문의 정의

PDDL에서 메트릭(metric)은 문제 파일의 :metric 절을 통해 계획의 최적화 기준을 명시하는 구문이다. 이 구문이 없으면 플래너는 기본적으로 계획의 길이(액션 수)를 최소화하며, :metric 절이 명시되면 지정된 수치 표현식을 최적화 대상으로 사용한다.

기본 구문:

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

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

2. 최소화 메트릭

가장 일반적인 형태로, 지정된 수치 표현식의 최종 값을 최소화하는 계획을 탐색한다:

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

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

;; 총 에너지 소모 최소화
(:metric minimize (total_energy_consumed))

;; 계획 길이 최소화 (각 액션에서 total_cost를 1씩 증가)
(:metric minimize (total_cost))

3. 최대화 메트릭

수익, 보상, 품질 등을 최대화하는 계획을 탐색한다:

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

;; 수집 데이터량 최대화
(:metric maximize (data_collected))

4. 복합 메트릭 표현식

산술 연산자를 사용하여 여러 수치 플루언트를 결합한 복합 메트릭을 정의할 수 있다:

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

;; 비용 대비 보상 최소화
(:metric minimize (- (total_cost) (total_reward)))

;; 다중 페널티 요소의 합
(:metric minimize (+ (total_distance) (* 10 (total_risk)) (* 5 (total_delay))))

가중 합 방식은 다중 목표 최적화(multi-objective optimization)를 단일 스칼라 목표로 변환하는 표준적 방법이다. 각 가중치는 해당 목표의 상대적 중요도를 반영한다.

5. 로봇 도메인에서의 메트릭 설정 사례

5.1 물류 로봇: 총 이동 비용 최소화

(:functions
    (move_cost ?from - waypoint ?to - waypoint)
    (total_move_cost)
)

(:init (= (total_move_cost) 0))

(:metric minimize (total_move_cost))

5.2 순찰 로봇: 커버리지 최대화

(:functions (coverage_score))

(:metric maximize (coverage_score))

5.3 다중 로봇 시스템: 완료 시간 최소화

(:functions (makespan))

(:metric minimize (makespan))

5.4 에너지-시간 트레이드오프

(:functions
    (total_energy)
    (total_time)
)

;; 에너지 70%, 시간 30% 가중
(:metric minimize (+ (* 0.7 (total_energy)) (* 0.3 (total_time))))

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

6.1 만족 플래닝과 최적 플래닝

메트릭이 명시되더라도, 플래너의 유형에 따라 최적성 보장 수준이 다르다:

  • 최적 플래너: 메트릭 값이 수학적으로 최소(또는 최대)인 계획을 보장한다. 허용 가능 휴리스틱(admissible heuristic)과 A* 등의 완전 탐색이 필요하다.
  • 만족 플래너: 유효한 계획을 빠르게 찾되, 메트릭을 참고하여 품질을 개선한다. 최적성은 보장하지 않지만, 실용적인 시간 내에 합리적인 품질의 계획을 생성한다.
  • 반복적 개선 플래너: 초기 계획을 생성한 후, 반복적으로 개선하여 메트릭 값을 점진적으로 향상시킨다.

6.2 PlanSys2에서의 메트릭 처리

PlanSys2는 문제 파일에 :metric 절을 포함하여 플래너에 전달한다. POPF 플래너는 시간적 메트릭(makespan 최소화)을 기본적으로 지원하며, 사용자 정의 메트릭도 처리할 수 있다.

7. total-cost 패턴

계획 길이가 아닌 액션별 비용의 합을 최적화하기 위한 표준적 패턴이다:

;; 도메인 파일
(:functions (total-cost) - number)

(:action move
    :parameters (?r - robot ?from ?to - waypoint)
    :precondition (...)
    :effect (and
        (...)
        (increase (total-cost) (move-cost ?from ?to))
    )
)

;; 문제 파일
(:init (= (total-cost) 0))
(:metric minimize (total-cost))

이 패턴은 IPC(International Planning Competition)에서 비용 최적 플래닝 트랙의 표준으로 사용된다.

8. 설계 지침

  1. 메트릭의 단위와 범위를 문서화하라. 최적화 대상의 물리적 의미와 단위를 명확히 해야 결과의 해석이 가능하다.

  2. 메트릭 값의 초기화를 반드시 수행하라. (:init (= (total_cost) 0)) 등의 초기화가 누락되면 정의되지 않은 동작이 발생한다.

  3. 모든 관련 액션에서 메트릭을 갱신하라. 비용을 누적하는 메트릭의 경우, 비용을 발생시키는 모든 액션에서 increase를 수행해야 정확한 최적화가 이루어진다.

  4. 가중치의 민감도를 분석하라. 복합 메트릭의 가중치에 따라 생성되는 계획의 특성이 크게 달라질 수 있으므로, 다양한 가중치 조합으로 실험하여 적절한 값을 결정해야 한다.

9. 참고 문헌

  • Fox, M. & Long, D. (2003). “PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains.” Journal of Artificial Intelligence Research, 20, 61–124.
  • Hoffmann, J. (2003). “The Metric-FF Planning System: Translating ‘Ignoring Delete Lists’ to Numeric State Variables.” Journal of Artificial Intelligence Research, 20, 291–341.
  • 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.