1314.37 액션 비용 모델링과 최적화

1. 액션 비용의 개념

자동화된 플래닝에서 액션 비용(action cost)은 각 액션의 실행에 수반되는 정량적 비용을 나타내며, 플래너가 비용 최적 계획을 탐색하는 데 사용된다. PDDL 2.1에서는 수치 플루언트와 메트릭(metric) 구문을 통해 액션 비용을 모델링하고 최적화 목표를 설정할 수 있다.

2. 액션 비용의 모델링 방법

2.1 단일 비용 함수 사용

도메인 전체에서 단일 수치 플루언트를 비용 누적기로 사용하는 방법이다:

(:functions (total_cost))

(:action move
    :parameters (?r - robot ?from - waypoint ?to - waypoint)
    :precondition (and (robot_at ?r ?from) (connected ?from ?to))
    :effect (and
        (not (robot_at ?r ?from))
        (robot_at ?r ?to)
        (increase (total_cost) (distance ?from ?to))
    )
)

(:action pick_up
    :parameters (?r - robot ?obj - object ?loc - waypoint)
    :precondition (...)
    :effect (and
        (holding ?r ?obj)
        (not (object_at ?obj ?loc))
        (increase (total_cost) 1)
    )
)

2.2 다중 비용 요소의 결합

여러 비용 요소를 가중 합산하여 복합 비용을 모델링한다:

(:functions
    (total_energy)
    (total_time)
    (total_risk)
)

(:action move
    :parameters (?r - robot ?from - waypoint ?to - waypoint)
    :effect (and
        (not (robot_at ?r ?from))
        (robot_at ?r ?to)
        (increase (total_energy) (energy_cost ?from ?to))
        (increase (total_time) (travel_time ?from ?to))
        (increase (total_risk) (risk_level ?from ?to))
    )
)

3. 최적화 목표의 설정

PDDL에서 최적화 목표는 문제 파일의 :metric 절에서 정의한다:

3.1 최소화 (minimize)

(:metric minimize (total_cost))

이는 total_cost의 최종 값이 최소가 되는 계획을 찾으라는 지시이다. 가장 빈번하게 사용되는 최적화 방향이다.

3.2 최대화 (maximize)

(:metric maximize (total_reward))

보상이나 수익을 최대화하는 계획을 찾는다.

3.3 복합 메트릭

산술 표현식을 사용하여 복합 최적화 목표를 설정할 수 있다:

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

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

4. 로봇 도메인의 비용 모델링 사례

4.1 에너지 최적 경로 계획

(:functions
    (energy_cost ?from - waypoint ?to - waypoint)
    (total_energy_consumed)
)

(:action navigate
    :parameters (?r - robot ?from - waypoint ?to - waypoint)
    :precondition (and
        (robot_at ?r ?from)
        (connected ?from ?to)
        (>= (battery_level ?r) (energy_cost ?from ?to))
    )
    :effect (and
        (not (robot_at ?r ?from))
        (robot_at ?r ?to)
        (decrease (battery_level ?r) (energy_cost ?from ?to))
        (increase (total_energy_consumed) (energy_cost ?from ?to))
    )
)

;; 문제 파일에서의 메트릭
(:metric minimize (total_energy_consumed))

4.2 시간 최적 임무 수행

(:functions
    (travel_time ?from - waypoint ?to - waypoint)
    (task_duration ?t - task)
    (makespan)
)

;; 메트릭: 총 소요 시간 최소화
(:metric minimize (makespan))

4.3 비용-품질 트레이드오프

(:functions
    (total_cost)
    (quality_score)
)

;; 비용 최소화와 품질 최대화의 균형
(:metric minimize (- (total_cost) (* 0.5 (quality_score))))

5. 비용 최적 플래너

비용 최적 계획을 보장하는 플래너와 비용을 고려하되 최적성을 보장하지 않는 플래너를 구분해야 한다:

6. 설계 지침

1. 비용 함수의 단위를 일관되게 유지하라. 에너지(kWh), 시간(초), 거리(미터) 등의 단위가 혼재하면 가중 합산에서 왜곡이 발생한다.

2. 비용 함수를 단순하게 유지하라. 과도하게 복잡한 비용 함수는 플래너의 최적화 능력을 저하시킬 수 있다.

3. 비용이 항상 양수임을 보장하라. 음의 비용은 일부 플래너에서 무한 루프를 유발할 수 있다.

4. 최적성 요구 수준에 맞는 플래너를 선택하라. 비용 최적 계획이 필요하면 A* 기반 플래너를, 빠른 계획 생성이 우선이면 만족 플래너를 사용한다.

7. 참고 문헌

• 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.