1315.26 총 비용 최적화 전략

1. 총 비용 최적화의 개요

총 비용 최적화(total cost optimization)는 계획에 포함된 모든 액션의 비용 합계를 최소화하는 플래닝 전략이다. 이는 IPC(International Planning Competition)의 비용 최적 트랙에서 표준적으로 사용되는 최적화 형태이며, 실제 로봇 시스템에서 자원 효율성을 극대화하는 데 핵심적인 역할을 한다.

2. total-cost 패턴

비용 최적 플래닝의 표준 패턴은 total-cost(또는 total_cost)라는 전역 함수를 정의하고, 모든 비용 발생 액션에서 이 함수를 증가시키는 것이다:

;; 도메인
(:functions (total-cost))

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

(:action pick_up
    :parameters (?r - robot ?obj - object ?loc - waypoint)
    :effect (and
        (holding ?r ?obj)
        (not (object_at ?obj ?loc))
        (not (gripper_free ?r))
        (increase (total-cost) (pick-cost ?r))
    )
)

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

3. 최적 플래너의 비용 탐색 전략

3.1 A* 기반 탐색

비용 최적 계획을 보장하기 위해 A* 알고리즘을 사용하는 플래너는 다음의 평가 함수를 사용한다:

$f(n) = g(n) + h(n)$

여기서 $g(n)$ 은 초기 상태에서 노드 $n$ 까지의 실제 비용, $h(n)$ 은 $n$ 에서 목표까지의 추정 비용(휴리스틱)이다. 허용 가능 휴리스틱(admissible heuristic) 하에서 A*는 비용 최적 계획을 보장한다.

3.2 비용 고려 휴리스틱

비용 최적 플래닝에서 사용되는 대표적 허용 가능 휴리스틱:

휴리스틱	특성	비용 고려
$h^{\max}$	최대 달성 비용	비용 반영
$h^{\text{LM-cut}}$	랜드마크 기반	비용 반영
$h^{\text{merge-and-shrink}}$	추상화 기반	비용 반영
$h^{\text{blind}}$ ( $h = 0$ )	무정보	비용 미반영 (Dijkstra 탐색)

3.3 만족 플래닝과 비용 개선

최적성이 필요하지 않은 경우, 만족 플래너(LAMA 등)를 사용하여 빠르게 유효한 계획을 생성한 후, 반복적 개선(anytime improvement)을 통해 비용을 점진적으로 감소시킬 수 있다. LAMA는 초기 계획 생성 후 비용 제한(cost bound)을 점차 줄여가며 더 나은 계획을 탐색한다.

4. 비용 최적화 전략의 유형

4.1 균일 비용 전략

모든 액션에 동일한 비용(일반적으로 1)을 부여하여 계획 길이를 최소화한다. 이는 “최소 액션 수“로 목표를 달성하는 전략이다.

4.2 가중 비용 전략

액션 유형별로 다른 비용을 부여하여, 비용이 높은 액션의 사용을 억제한다:

;; 이동보다 충전이 더 비용이 높도록 설정
(:action move :effect (... (increase (total-cost) 1)))
(:action charge :effect (... (increase (total-cost) 5)))
;; 플래너는 충전을 최소화하는 계획을 선호

4.3 자원 기반 비용 전략

실제 자원 소모량을 비용으로 사용하여 자원 효율적인 계획을 생성한다:

(:action move
    :effect (...
        (increase (total-cost) (* (distance ?from ?to) (energy_per_meter ?r)))
    )
)

5. 로봇 도메인에서의 비용 최적화 고려사항

비용 요소의 선택: 에너지, 시간, 거리, 마모 중 어떤 요소를 비용으로 사용할지 결정한다.
비용 스케일의 정규화: 서로 다른 단위의 비용 요소를 결합할 때 스케일을 맞춘다.
계산 시간과 최적성의 트레이드오프: 최적 계획 탐색은 계산 비용이 높으므로, 실시간 요구사항에 따라 만족 플래닝을 선택할 수 있다.
재계획 시의 비용 연속성: 재계획 시 이미 수행된 액션의 비용이 반영되도록 상태를 갱신한다.

6. 참고 문헌

Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.
Richter, S. & Westphal, M. (2010). “The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks.” Journal of Artificial Intelligence Research, 39, 127–177.
Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.