Compiling Temporal Numeric Planning into Discrete PDDL+: Extended Version

이 논문은 PDDL+의 의미론을 완전히 포착하고 실험적으로도 검증된 다항식 시간 복잡도의 실용적인 컴파일 기법을 통해, 지속적 행동을 포함하는 시계열 수치 계획 문제를 PDDL+로 변환하는 방법을 제시합니다.

핵심

이 논문은 복잡한 시간 관리 문제를 해결하는 두 가지 서로 다른 '언어'를 연결하는 다리를 놓는 방법에 대해 이야기합니다.

간단히 말해, **"시간이 걸리는 작업 (Durative Actions)"을 어떻게 하면 컴퓨터가 더 잘 이해하고 처리할 수 있는 새로운 방식으로 변환할 수 있을까?**에 대한 해답을 제시한 연구입니다.

이 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

1. 배경: 두 가지 다른 언어, 같은 문제

상상해 보세요. 여러분이 **거대한 공사 현장 (계획 문제)**을 관리해야 한다고 가정해 봅시다.

• PDDL 2.1 (기존 언어): 여기서는 작업자들이 "이 작업은 3 시간 걸려요"라고 말합니다. 하지만 이 언어는 작업이 시작하고 끝나는 순간, 그리고 그 사이 동안 무슨 일이 일어나야 하는지 세세하게 설명하는 데 약간의 한계가 있습니다. 마치 "3 시간 동안 벽을 칠하세요"라고만 지시하는 것과 비슷하죠.
• PDDL+ (새로운 언어): 이 언어는 조금 더 정교합니다. "벽을 칠하는 동안 (프로세스), 페인트가 마르는 속도가 변하고, 3 시간이 되면 (이벤트) 작업이 끝납니다"라고 시간이 흐르는 과정 자체를 수학적으로 묘사할 수 있습니다.

문제: 예전부터 PDDL 2.1 로 만든 문제를 PDDL+ 로 바꿀 수 있다는 이론은 있었지만, 실제로 어떻게 변환할지 구체적인 방법 (레시피) 이 없었습니다. 그래서 많은 전문가들이 이 변환을 시도하지 못했죠.

2. 이 연구의 핵심: "자물쇠와 시계"를 이용한 변환법

저자들은 이 두 언어를 완벽하게 연결하는 실용적인 변환 도구를 개발했습니다. 이 도구의 원리는 다음과 같은 두 가지 비유로 이해할 수 있습니다.

비유 1: "자물쇠 (Lock) 시스템"으로 혼란 방지

공사 현장에 여러 대의 크레인이 동시에 움직인다고 상상해 보세요. 만약 두 대의 크레인이 같은 물건을 동시에 들어 올리려고 하면 충돌이 일어납니다.

• 기존 방식: "너는 3 시간 동안 일해"라고만 하면, 컴퓨터는 3 시간 동안 무슨 일이 일어날지 모호하게 처리할 수 있습니다.
• 이 연구의 방식: 각 작업이 시작할 때 **자물쇠 (Lock)**를 채웁니다.
  • "나는 이 물건을 건드리고 있어!"라고 자물쇠를 잠그면, 다른 작업은 그 물건을 건드릴 수 없습니다.
  • 작업이 끝나면 자물쇠를 풉니다.
  • 이 '자물쇠' 시스템을 통해 동시에 일어나는 작업들이 서로 간섭하지 않도록 PDDL+ 가 정확히 통제할 수 있게 만들었습니다.

비유 2: "시계 (Clock) 와 타이머"로 시간 관리

작업이 3 시간 걸린다고 했을 때, PDDL+ 는 "3 시간이 지났을 때 자동으로 작업이 끝난다"는 신호를 보내야 합니다.

• 연구자들은 각 작업에 **작은 시계 (Timer)**를 달아줍니다.
• 작업이 시작되면 시계가 0 에서 1 초, 2 초... 하며 카운트합니다.
• 시계가 정해진 시간 (예: 3 시간) 에 도달하면, 자동으로 "작업 종료 (이벤트)" 신호가 울립니다.
• 이렇게 하면 "3 시간 동안 계속되는 상태"를 PDDL+ 가 자연스럽게 이해할 수 있게 됩니다.

3. 왜 이것이 중요한가요? (실험 결과)

저자들은 이 변환 방법을 실제로 테스트해 보았습니다. 결과는 놀라웠습니다.

• **기존의 시간 관리 전문가들 (기존 PDDL 2.1 솔버)**은 복잡한 숫자 계산이 포함된 시간 문제에서 종종 막혔습니다.
• 하지만 이 변환 방법을 통해 PDDL+ 언어로 문제를 바꾸고, PDDL+ 전용 솔버 (ENHSP) 로 풀게 하니, 오히려 더 빠르고 정확하게 문제를 해결했습니다.

비유하자면:
기존에는 "3 시간 동안 요리해"라고만 해서 요리사가 혼란을 겪었는데, 이 연구는 "냄비 위에 타이머를 두고, 3 시간이 되면 자동으로 불을 끄는 장치를 설치"해 준 것입니다. 그 결과 요리사 (컴퓨터) 는 훨씬 더 효율적으로 요리를 할 수 있게 된 것입니다.

4. 결론: 무엇을 얻었나요?

이 논문은 단순히 이론적인 증명만 한 것이 아니라, 실제로 복잡한 시간과 숫자 문제를 해결하는 데 쓸모 있는 도구를 만들었습니다.

• 완벽한 번역: PDDL 2.1 의 모든 규칙을 PDDL+ 로 완벽하게 옮길 수 있는 방법을 처음 제시했습니다.
• 실용성: 이 변환을 통해 기존에 풀기 어려웠던 복잡한 문제들도 쉽게 풀 수 있게 되었습니다.
• 미래: 이 기술은 더 나아가 연속적인 시간 변화 (예: 물이 서서히 차오르는 것) 까지 다루는 미래의 계획 시스템의 기초가 될 것입니다.

한 줄 요약:

"시간이 걸리는 복잡한 작업을 컴퓨터가 더 잘 이해하도록, '자물쇠'와 '시계'를 달아주는 새로운 번역 기술을 개발했고, 이 기술이 기존 방법보다 훨씬 효과적임을 증명했습니다."

기술 요약

1. 문제 정의 (Problem)

• 배경: 자동 계획 (Automated Planning) 분야에서 PDDL 2.1 은 시간적 계획 (Temporal Planning) 과 지속적 행동 (Durative Actions) 을 모델링하는 표준 언어로 널리 사용되어 왔습니다. PDDL+ 는 시간과 하이브리드 시스템을 표현하기 위해 프로세스 (Processes), 이벤트 (Events), 즉각적 행동 (Instantaneous Actions) 을 도입한 더 표현력 있는 언어입니다.
• 현황: PDDL 2.1 의 지속적 행동을 PDDL+ 로 변환 (컴파일) 하는 것이 이론적으로 가능하다는 것은 알려져 있었으나, 실제 적용 가능한 구체적인 컴파일 방법이 문헌에 제시된 바 없었습니다.
• 핵심 과제: PDDL 2.1 (레벨 3) 으로 정의된 시간적 계획 문제를 PDDL+ 로 변환하되, 의미론 (Semantics) 을 완전히 보존하고, 특히 행동의 중첩 방지 (Non-self-overlapping) 및 상호 배제 (Non-interference) 조건을 정확히 구현하는 실용적인 컴파일러를 개발하는 것입니다.

2. 방법론 (Methodology)

저자들은 PDDL 2.1 의 지속적 행동을 PDDL+ 의 프로세스, 이벤트, 즉각적 행동의 조합으로 매핑하는 새로운 컴파일 기법을 제안합니다.

2.1 핵심 아이디어

• 행동 변환:
  • 고정 지속 시간 행동 (Fixed Duration): 시작 행동 (Action) + 프로세스 (Process) + 이벤트 (Event) 의 3 단계로 구성됩니다.
  • 가변 지속 시간 행동 (Variable Duration): 시작 행동 (Action) + 프로세스 (Process) + 종료 행동 (Action) 의 3 단계로 구성됩니다.
• 잠금 메커니즘 (Lock Mechanism):
  • PDDL+ 의 초밀집 시간 (Superdense time) 모델에서 발생하는 동시성 충돌을 방지하기 위해 **잠금 상태 변수 (Lock Predicates: rlf, alf, ilf)**를 도입했습니다.
  • 이 잠금 변수들은 변수를 읽거나 (Read), 할당 (Assign), 증가 (Increment) 할 때 상호 배제를 강제합니다.
  • gc (Global Counter) 와 ok 변수: 시간의 경과를 감지하고 잠금 변수를 초기화하기 위해 gc 변수를 사용하며, 계획의 유효성을 검증하기 위해 ok 변수를 사용합니다. gc 가 0 이 아닌 값으로 증가하면 다음 시간 단계에서 gc 가 0 으로 리셋되고 모든 잠금 변수가 해제되는 구조를 가집니다.
• 보안성 (Safety) 및 무결성:
  • 전체 조건 (Overall Conditions): 행동이 실행되는 동안 조건이 위배되면 ok 변수를 False 로 설정하여 해당 계획 경로를 무효화합니다.
  • 중첩 방지: 행동이 시작될 때 ra (Running Action) 변수를 True 로 설정하고, 행동이 실행 중일 때는 새로운 시작을 막는 전제 조건을 추가하여 자기 중첩 (Self-overlapping) 을 방지합니다.

2.2 컴파일 결과물

• 입력: PDDL 2.1 문제 ($F, X, I, A_i, A_d, G$)
• 출력: PDDL+ 문제 ($\bar{F}, \bar{X}, \bar{I}, \bar{G}, \bar{A}, \bar{E}, \bar{P}$)
• 변환된 문제는 **다항식 크기 (Polynomial size)**를 가지며, 계획 길이는 상수 배수 내에서 유지됩니다.

3. 주요 기여 (Key Contributions)

1. 최초의 완전한 형식적 기술: PDDL 2.1 의 지속적 행동을 PDDL+ 로 변환하는 첫 번째 완전하고 엄밀한 형식적 설명 (Formal Account) 을 제공합니다.
2. 의미론적 정확성: PDDL 2.1 의 복잡한 의미론 (특히 '움직이는 목표 규칙'과 상호 배제 조건) 을 PDDL+ 의 이산 시간 (Discrete Time) 모델에서 정확히 구현했습니다.
3. 이론적 증명: 제안된 컴파일 방법이 **정합성 (Soundness)**과 **완전성 (Completeness)**을 가진다는 것을 수학적으로 증명했습니다.
   • 정합성: 변환된 PDDL+ 문제를 해결하면 원래 PDDL 2.1 문제의 유효한 해를 얻습니다.
   • 완전성: 원래 PDDL 2.1 문제의 해가 존재하면, 충분히 작은 시간 간격 ($\delta$) 을 선택하여 변환된 PDDL+ 문제의 해가 존재합니다.
4. 실용적 확장성: 지연 효과 (Delayed Effects) 와 타이밍 초기 리터럴 (Timed Initial Literals) 과 같은 고급 기능을 PDDL+ 에서 자연스럽게 처리할 수 있음을 보여줍니다.

4. 실험 결과 (Results)

저자들은 다양한 시간적 수치 계획 (Temporal Numeric Planning) 도메인에서 실험을 수행했습니다.

• 사용된 도메인: MatchCellar, MAJSP, T-Sailing, T-Plant-Watering 등.
• 비교 대상:
  • 변환 후: PDDL+ 플랜너 ENHSP (Lazy Greedy 및 WA* 엔진 사용).
  • 네이티브: ARIES, NextFLAP, TFLAP, OPTIC, TAMER, Patty 등 최신 시간적 플랜너.
• 성과:
  • ENHSP-WA가 가장 높은 커버리지 (해결된 인스턴스 수) 를 기록했습니다.
  • 순수 시간적 도메인에서는 네이티브 플랜너가 더 빠르지만, **수치적 요소가 포함된 복잡한 도메인 (Temporal Numeric)**에서는 변환된 PDDL+ 접근법 (ENHSP) 이 기존 최첨단 플랜너들보다 우수한 성능을 보였습니다.
  • 특히 MAJSP 와 같은 복잡한 도메인에서 ENHSP-WA 가 압도적인 우위를 점했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 이론과 실용의 연결: PDDL+ 가 시간적 계획 문제를 표현할 수 있다는 이론적 사실을 넘어, 이를 실제로 적용 가능한 컴파일러로 구현하고 그 유효성을 입증했습니다.
• 플랜너 선택의 유연성: 시간적 계획 문제를 PDDL+ 로 변환함으로써, PDDL+ 를 지원하는 강력한 플랜너 (예: ENHSP) 를 시간적 계획 문제에 활용할 수 있게 되었습니다. 이는 수치적 제약이 복잡한 문제 해결에 특히 효과적입니다.
• 향후 작업:
  • PDDL 2.1 레벨 4 (연속적 변화, Continuous Change) 로의 확장.
  • 연속 시간 (Continuous Time) 의미론을 가진 PDDL+ 를 대상으로 한 대체 컴파일 연구.

요약하자면, 이 논문은 PDDL 2.1 기반의 시간적 계획 문제를 PDDL+ 로 변환하는 정합적이고 완전한 방법을 제시하며, 수치적 복잡성이 높은 시간적 계획 문제 해결에 있어 기존 전용 플랜너보다 강력한 성능을 발휘할 수 있음을 실험을 통해 입증했습니다.