1316.48 실시간 제약에서의 고전 플래너 적용

1. 실시간 제약의 정의

로봇 시스템에서 실시간 제약(real-time constraint)은 계획 생성에 허용되는 시간이 엄격히 제한되는 상황을 의미한다. 동적 환경에서의 재계획, 인간-로봇 상호작용에서의 반응성, 안전 관련 비상 대응 등에서 실시간 제약이 발생한다. 고전적 플래너가 주어진 시간 내에 유효한 계획을 생성하지 못하면, 로봇은 행동을 결정할 수 없어 임무가 중단된다.

2. 실시간 제약의 수준

3. 실시간 대응 전략

3.1 전략 1: Anytime 플래닝

LAMA 등의 반복적 개선 플래너를 사용하여, 시간 제한에 도달하면 현재까지의 최선 계획을 반환한다:

ANYTIME_PLANNING(problem, time_limit):
    best_plan ← NULL
    start_time ← NOW()
    
    ;; 1차: 빠른 첫 해 탐색
    plan ← GREEDY_SEARCH(problem)
    IF plan ≠ NULL: best_plan ← plan
    
    ;; 반복적 개선
    WHILE NOW() - start_time < time_limit:
        improved_plan ← IMPROVE(problem, cost(best_plan))
        IF improved_plan ≠ NULL: best_plan ← improved_plan
    
    RETURN best_plan

3.2 전략 2: 계획 수리(Plan Repair)

기존 계획이 무효화되면 전체를 재계획하는 대신, 무효한 부분만 수리한다:

1. 기존 계획에서 실패한 액션을 식별
2. 실패 지점의 상태에서 목표까지 부분 재계획 수행
3. 기존 계획의 유효한 접두사와 새 부분 계획을 결합

3.3 전략 3: 휴리스틱 품질 조절

시간 압박 시 비허용 가능하지만 빠른 휴리스틱을 사용하고, 여유 시 정밀한 휴리스틱을 사용한다:

IF remaining_time < threshold:
    h ← h_add  ;; 빠르지만 부정확
ELSE:
    h ← h_FF   ;; 느리지만 정보적

3.4 전략 4: 가중 A*의 가중치 조절

시간 압박에 따라 가중치를 동적으로 조절한다:

w = \begin{cases} 10 & \text{if time\_remaining} < 1\text{s} \\ 5 & \text{if time\_remaining} < 5\text{s} \\ 2 & \text{if time\_remaining} < 30\text{s} \\ 1 & \text{otherwise (최적)} \end{cases}

3.5 전략 5: 계획 캐싱과 사전 계산

자주 발생하는 임무 패턴에 대해 계획을 사전 계산하고 캐싱하여, 실행 시 조회만으로 대응한다.

4. PlanSys2에서의 실시간 대응

PlanSys2는 다음의 메커니즘으로 실시간 제약에 대응한다:

1. 비동기 플래닝: Planner 노드가 비동기적으로 계획을 생성하여 실행 중단을 최소화
2. 재계획 트리거: 액션 실패 시 Executor가 자동으로 재계획을 요청
3. 상태 모니터링: Problem Expert가 세계 상태를 지속적으로 갱신하여 재계획의 정확성을 보장
4. 플래너 시간 제한: 외부 플래너에 시간 제한을 설정하여 무한 탐색을 방지

5. 도메인 설계를 통한 실시간 성능 향상

1. 도메인 규모 제한: 플래닝에 관련된 객체만 포함하여 상태 공간을 축소
2. 추상화 수준 조절: 시간 압박 시 더 추상적인 도메인 모델을 사용
3. 계층적 플래닝: 상위 수준에서 빠르게 개략 계획을 생성하고, 하위 수준에서 세부화

6. 참고 문헌

• Richter, S. & Westphal, M. (2010). “The LAMA Planner.” Journal of Artificial Intelligence Research, 39, 127–177.
• Nebel, B. & Koehler, J. (1995). “Plan Reuse versus Plan Generation: A Theoretical and Empirical Analysis.” Artificial Intelligence, 76(1–2), 427–454.
• Gonzalez, F., Martin, F., Matellán, V., & Rodriguez, F. J. (2021). “PlanSys2: A Planning System Framework for ROS2.” IEEE ICARSC.