When both Grounding and not Grounding are Bad -- A Partially Grounded Encoding of Planning into SAT (Extended Version)

Each language version is independently generated for its own context, not a direct translation.

1. 문제 상황: 도서관의 혼란 (기존 방식의 한계)

상상해 보세요. AI 가 어떤 일을 하려고 할 때, 모든 가능한 상황을 하나하나 종이에 적어서 계획을 세운다고 가정해 봅시다.

완전 바닥화 (Full Grounding): 모든 사물 (책, 사람, 장소) 의 이름을 다 적어서 "A 라는 사람이 B 라는 책방에 가자", "C 라는 사람이 D 라는 책방에 가자" 식으로 모든 경우의 수를 일일이 나열하는 방식입니다.
- 문제: 사물과 장소가 조금만 많아져도 종이의 양이 기하급수적으로 불어납니다. 마치 도서관의 모든 책 제목을 적어내려다 도서관 자체가 책으로 가득 차서 사람이 들어갈 수 없게 되는 것과 같습니다.
완전 추상화 (Full Lifting): "사람이 책방에 간다"라는 원칙만 적어두는 방식입니다. 구체적인 이름은 적지 않습니다.
- 장점: 종이가 아주 적게 듭니다.
- 문제: AI 가 "어떤 사람이 어느 책방에 갔는지"를 추론할 때, 모든 연결고리를 일일이 찾아야 해서 연산 속도가 느려집니다. 특히 계획이 길어질수록 시간이 기하급수적으로 늘어납니다.

지금까지의 최첨단 기술 (LiSAT) 은 이 '완전 추상화' 방식을 썼는데, 계획이 길어질수록 종이 양이 2 배, 3 배가 아니라 4 배, 9 배로 폭증하는 치명적인 약점이 있었습니다.

2. 이 논문의 해결책: "반쪽짜리 지도" (부분적 바닥화)

이 연구팀은 "완전히 나열하지도, 완전히 추상화하지도 않는" 중간 지점을 찾았습니다. 바로 **"부분적으로만 구체적인 지도"**를 그리는 것입니다.

아이디어: "사람"과 "책방" 같은 행동 자체는 추상적으로 유지하되, "어떤 책방에 있는가?" 같은 상태 (위치) 는 부분적으로 구체화합니다.
비유:
- 기존 방식: 도서관 전체를 1:1 로 다 찍은 고해상도 사진 (데이터가 너무 큼).
- 새로운 방식: 도서관의 주요 구역 (책장) 만은 구체적인 사진으로 찍고, 그 사이를 연결하는 길은 간단한 화살표로만 표시한 지도.
- 효과: 지도의 크기는 커지지 않으면서도, AI 가 길을 찾을 때 필요한 정보는 빠르고 정확하게 얻을 수 있습니다.

3. 핵심 기술: "잠금 장치" (Mutex Groups) 활용

이 방법이 어떻게 가능한 걸까요? 바로 **'잠금 장치 (Mutex Groups)'**라는 개념을 썼기 때문입니다.

비유: "한 사람이 동시에 두 개의 책방에 있을 수 없다"는 상식입니다.
적용: AI 는 "A 가 책방 1 에 있다"면 "A 가 책방 2 에는 없다"는 것을 자동으로 알 수 있습니다. 그래서 모든 책방의 상태를 다 적을 필요 없이, **"누가 어디에 있는가?"**를 나타내는 하나의 변수만으로도 전체 상태를 표현할 수 있습니다.
결과: 데이터 양이 압도적으로 줄어들고, 계획이 길어지더라도 데이터 양이 선형적으로 (직선처럼)만 증가합니다. 기존 방식처럼 폭증하지 않는 것입니다.

4. 실험 결과: 더 빠르고 강력해지다

연구팀은 이 새로운 방식을 여러 가지 복잡한 문제 (물류, 로봇 이동, 미로 찾기 등) 에 적용해 보았습니다.

결과: 기존에 가장 잘하던 기술 (LiSAT) 보다 더 많은 문제를 더 빠르게 해결했습니다. 특히 사물이 많고 계획이 길어야 하는 어려운 문제에서 압도적인 성능을 보였습니다.
의미: 마치 고속도로를 새로 뚫어서 교통 체증이 심한 구간을 순식간에 통과하게 만든 것과 같습니다.

5. 요약: 왜 이것이 중요한가요?

이 논문은 **"AI 가 복잡한 문제를 해결할 때, 모든 것을 다 기억할 필요도, 모든 것을 다 추상화할 필요도 없다"**는 것을 증명했습니다.

핵심 메시지: "적당히 구체화 (Partial Grounding)"가 가장 효율적인 방법입니다.
일상적 비유: 집을 정리할 때, 모든 옷을 하나하나 세어 적는 것도 아니고, "옷장 안에 옷이 있다"고만 적는 것도 아닙니다. **"옷장 A 에는 겨울옷, 옷장 B 에는 여름옷"**이라고 핵심만 구체화하는 것이 가장 효율적인 정리법인 것과 같습니다.

이 기술은 앞으로 더 크고 복잡한 AI 시스템이 더 적은 컴퓨터 자원으로 더 먼 미래까지 계획을 세울 수 있게 해줄 것입니다.

Each language version is independently generated for its own context, not a direct translation.

1. 문제 제기 (Problem)

자동 계획 수립 문제는 일반적으로 들 수 있는 (lifted) 1 차 논리 표현으로 정의되며, 이는 컴팩트함과 일반성을 제공합니다. 그러나 대부분의 계획기는 추론을 단순화하기 위해 이 표현을 **완전히 Grounding(구체화)**하여 모든 객체와 술어에 대한 인스턴스를 생성합니다.

완전 Grounding 의 문제: 객체 수가 많거나 술어의 차수 (arity) 가 높을 경우, 상태 공간의 크기가 기하급수적으로 증가하여 (Exponential blowup) 확장성 (Scalability) 문제가 발생합니다.
완전 Lifted (LiSAT) 의 문제: 최근의 접근법인 LiSAT (Höller & Behnke, 2022) 는 완전한 리프팅을 유지하여 Grounding 문제를 피하지만, 계획 길이에 따라 인코딩 크기가 2 차 (Quadratic) 로 증가하는 치명적인 단점이 있습니다. 이는 긴 계획을 필요로 하는 문제에서 성능 저하를 초래합니다.

핵심 질문: Grounding 과 비-Grounding 사이의 중간 지점 (Middle ground) 을 찾아, 행위는 리프팅된 채로 유지하면서 상태 설명만 부분적으로 구체화하여 2 차 증가를 1 차 증가로 줄일 수 있는가?

2. 방법론 (Methodology)

저자들은 행위는 완전히 리프팅 (Lifted) 된 상태로 유지하되, 상태 설명 (Predicates) 에 대해 부분적인 Grounding을 수행하는 세 가지 새로운 SAT 인코딩을 제안합니다.

2.1. 핵심 아이디어: 부분 리프트된 뮤텍스 그룹 (PLMGs)

리프트된 뮤텍스 그룹 (LMGs): 특정 사실 집합 중 reachable state 에서는 최대 하나만 참일 수 있다는 불변량 (Invariant) 을 리프트된 형태로 정의합니다 (예: 한 패키지는 동시에 두 곳에 있을 수 없음).
부분 리프트된 뮤텍스 그룹 (PLMGs): 고정된 변수 (fixed variables) 가 이미 인스턴스화된 LMG 의 하위 집합입니다.
접근 방식:
1. 행위 (Actions): LiSAT 와 동일한 'Unified Arguments' 방식을 사용하여 완전히 리프팅된 상태로 인코딩합니다.
2. 상태 (State):
  - Fully Grounded: 모든 술어를 구체화 (기저선).
  - Partially Grounded (One-hot): PLMG 를 사용하여 상태 표현을 부분 구체화합니다. PLMG 내의 counted variables(세어지는 변수) 를 사용하여 어떤 사실이 참인지 암시적으로 나타냅니다.
  - Partially Grounded (Binary): PLMG 변수를 이진 비트 (bit-representation) 로 인코딩하여 변수 수를 $\lceil \log_2(|O|) \rceil$ 로 줄입니다.

2.2. 인코딩 구조 및 선형 확장성

기존 LiSAT 는 원인 - 결과 링크 (Causal links) 를 명시적으로 추적하기 위해 계획 길이 $\ell$ 에 대해 2 차적으로 증가하는 제약 조건을 생성했습니다.

새로운 접근: 상태를 명시적으로 추적 (Explicitly track state) 하여 원인 - 결과 링크를 제거합니다.
결과: 인코딩 크기가 계획 길이 $\ell$ 에 대해 **선형 (Linear)**으로만 증가합니다.
프레임 공리 (Frame Axioms): 상태가 행동의 효과에 의해 변경되지 않는 한 변하지 않음을 보장하는 새로운 변수와 제약 조건을 도입했습니다.

2.3. 술어 가지치기 (Predicate Pruning)

계획에 영향을 미치지 않는 불필요한 사실 (Goal 이나 전제 조건에 등장하지 않는 사실) 을 사전에 제거하여 인코딩 크기를 추가로 줄이는 최적화 기법을 적용했습니다.

3. 주요 기여 (Key Contributions)

새로운 SAT 인코딩 제안: 행위는 리프팅, 상태는 부분 구체화 (PLMG 기반) 하는 세 가지 인코딩 (Fully Grounded, Partially One-hot, Partially Binary) 을 개발했습니다.
복잡도 개선: 기존 LiSAT 의 2 차 ( $O(\ell^2)$ ) 확장성을 **선형 ( $O(\ell)$ )**으로 개선하여 긴 계획을 다루는 능력을 획기적으로 향상시켰습니다.
PLMG 활용: Lifted Fact Altering Mutex Groups 알고리즘을 활용하여 문제의 내재적 구조를 포착하고, 이를 통해 상태 표현을 압축했습니다.
이진 인코딩 (Binary Encoding): 객체 인덱스를 이진 비트로 표현하여 변수 수를 대폭 줄이고 정보 밀도를 높였습니다.

4. 실험 결과 (Experimental Results)

저자들은 표준 벤치마크 (lifted planning benchmarks) 를 사용하여 LiSAT, Powerlifted (PWL), CPDDL, Madagascar, Fast Downward 등 최신 계획기와 비교 실험을 수행했습니다.

최적 길이 계획 (Length-Optimal Planning):
- 제안된 인코딩 (특히 Binary + Predicate Pruning) 은 9 개 도메인 중 5 개에서 LiSAT 보다 우수한 성능을 보였습니다.
- Logistics, Pipesworld, Rover 도메인에서는 해결된 인스턴스 수가 LiSAT 대비 20% 이상 증가했습니다.
- 전체 점수 (Score) 에서 LiSAT 를 능가하거나 경쟁력 있는 결과를 보였습니다.
충분한 계획 (Satisficing Planning):
- LiSAT 와 제안된 방법은 검색 기반 계획기 (PWL 등) 와 상호 보완적인 능력을 보여주었습니다. 특정 도메인 (Blocksworld, Visitall 등) 에서 다른 계획기보다 우수한 성능을 발휘했습니다.
인코딩 크기 분석:
- 변수 수: 제안된 방법은 LiSAT 대비 변수 수가 1~2 차수 (orders of magnitude) 적게 생성되었습니다.
- 절 (Clause) 수: PLMG 의미론 인코딩의 복잡도로 인해 절 수는 LiSAT 보다 다소 많았으나, 계획 길이에 따른 성장은 선형적으로 유지되었습니다.
- 확장성: LiSAT 는 문제 난이도와 계획 길이에 따라 급격히 증가하는 반면, 제안된 방법은 도메인 간 변동성이 적고 선형적으로 증가하는 것을 확인했습니다.

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

이론적 의의: 완전한 리프팅과 완전한 구체화 사이의 균형을 찾는 새로운 패러다임을 제시했습니다. 특히, 상태 추적 방식을 변경하여 SAT 기반 계획 수립의 복잡도 한계를 2 차에서 1 차로 낮춘 것은 중요한 이론적 진전입니다.
실용적 의의: 긴 계획을 필요로 하거나 객체 수가 많은 복잡한 도메인에서 기존 LiSAT 의 한계를 극복하고, 더 많은 문제를 해결할 수 있게 했습니다.
미래 작업: 현재 순차적 계획 (Sequential plans) 에 초점을 맞추고 있으나, 향후 행동 병렬화 (Action parallelism) 지원, 부정적 전제 조건 (Negative preconditions), 조건부 효과 (Conditional effects) 지원 등을 통해 적용 범위를 확장할 수 있습니다.

요약하자면, 이 논문은 "Grounding 과 비-Grounding 모두 단점이 있다"는 전제 하에, 부분적으로 구체화된 상태 표현과 완전히 리프팅된 행위를 결합하여 SAT 기반 계획 수립의 확장성 문제를 해결하고, 특히 긴 계획 수립에서 기존 최첨단 기법 (LiSAT) 을 능가하는 성능을 입증했습니다.