On Sample-Efficient Generalized Planning via Learned Transition Models

이 논문은 직접적인 행동 시퀀스 예측 대신 학습된 전이 모델을 통해 중간 세계 상태를 autoregressively 예측하는 방식을 제안함으로써, 더 적은 데이터와 작은 모델로도 분포 외 (out-of-distribution) 일반화 성능을 크게 향상시킨다고 주장합니다.

핵심

이 논문은 **"로봇이나 AI 가 새로운 문제를 만났을 때, 이전에 배운 작은 경험만으로도 큰 문제를 해결할 수 있게 하는 방법"**에 대한 연구입니다.

기존의 AI 는 방대한 양의 데이터를 외워서 정답을 맞추는 방식 (암기) 에 가까웠는데, 이 연구는 "세상이 어떻게 움직이는지 원리 (물리 법칙) 를 이해하게" 하는 새로운 방식을 제안합니다.

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

---

1. 기존 방식 vs. 새로운 방식: "레시피 암기" vs. "요리 원리 이해"

기존의 AI (기존 방식: 행동 중심)

• 비유: 요리사에게 "감자 10 개를 넣으면 감자 11 개가 나오는 요리"를 100 번 시켰습니다. AI 는 "아, 감자 10 개면 11 개가 나오네!"라고 암기했습니다.
• 문제점: 이제 감자가 100 개가 나오면 어떻게 할까요? AI 는 "감자 100 개면 101 개가 나오겠지?"라고 추측하다가 엉뚱한 결과를 내놓습니다. (데이터가 너무 많아야 하고, 상황이 조금만 달라져도 망가집니다.)
• 논문에서 지적한 점: 최신 AI(트랜스포머 등) 는 방대한 데이터로 행동을 외우지만, 세상의 변화를 직접 계산하지 않기 때문에 긴 시간 동안 계획을 세우면 엉뚱한 길로 빠집니다.

이 연구의 방식 (새로운 방식: 상태 중심)

• 비유: 이 연구는 AI 에게 "감자 10 개를 넣으면 11 개가 나오는 게 아니라, 감자를 하나 더 넣으면 개수가 하나 늘어난다"는 원리를 가르칩니다.
• 핵심: AI 가 "다음에 무슨 행동을 할지"를 외우는 대신, **"지금 이 상태에서 행동을 하면 세상이 어떻게 변할지"**를 예측하는 모델을 만듭니다.
• 효과: 감자가 1,000 개가 되어도 "하나씩 늘어난다"는 원리만 알면 해결할 수 있습니다. 데이터가 적어도, 모델이 작아도 큰 문제를 해결할 수 있습니다.

---

2. 핵심 기술: "세상의 지도를 그리는 AI"

이 연구는 AI 가 **세상의 변화 (Transition Model)**를 학습하도록 만들었습니다.

• 상상해 보세요: AI 는 마치 내비게이션처럼 작동합니다.
  • 기존 AI: "A 지점에서 B 지점으로 가려면 '우회전'을 해"라고 외웁니다. (경로만 외움)
  • 이 연구의 AI: "A 지점에서 우회전하면 B 지점에 도착하고, B 지점에서 좌회전하면 C 지점에 간다"는 지도와 규칙을 학습합니다.
• 왜 중요한가요?
  • AI 가 "다음 상태"를 예측하면, 그 예측이 맞는지 기존의 논리 (기호) 로 검증할 수 있습니다.
  • 만약 AI 가 "우회전하면 하늘로 날아갈 거야"라고 잘못 예측해도, 논리 검증기가 "아니야, 우회전하면 도로로 가"라고 바로 잡아줍니다. 이를 신경 - 기호 (Neuro-Symbolic) 방식이라고 합니다.

---

3. 크기 불변성: "레고 블록의 법칙"

연구의 가장 큰 성과는 **크기 (Size Invariance)**를 다루는 방법입니다.

• 비유:
  • 기존 방식: 4 개의 레고 블록으로 만든 성을 배웠다면, 100 개의 블록으로 만든 성을 보면 "내 배운 게 4 개까지인데, 100 개는 모르겠다"고 당황합니다.
  • 이 연구의 방식: "레고 블록은 어떻게 끼워지는지"라는 구조적 규칙을 배웁니다. 블록이 4 개든 100 개든, 끼우는 원리는 똑같습니다.
• 기술적 용어 (WL 임베딩): 연구팀은 복잡한 상황을 **그래프 (그림)**로 변환하고, 블록의 개수가 달라져도 원칙만 추출해내는 특수한 수학적 도구 (Weisfeiler-Leman) 를 사용했습니다. 덕분에 아주 작은 데이터로 큰 문제를 해결할 수 있었습니다.

---

4. 실험 결과: "작은 두뇌로 큰 문제 해결"

• 결과: 이 연구팀은 거대한 AI(수억 개의 파라미터) 를 쓰지 않고, **아주 작은 모델 (수백만 개 이하)**로도 기존 거대 AI 들이 실패했던 '완전히 새로운 상황 (Extrapolation)'에서 더 좋은 성적을 냈습니다.
• 비유: 거대한 슈퍼컴퓨터로 암기 시험을 치는 대신, 작은 두뇌로 수학 공식을 적용해 문제를 푼 것과 같습니다.
• 한계: 모든 문제가 해결된 것은 아닙니다. 물류 (Logistics) 같은 아주 복잡하게 얽힌 문제에서는 아직 한계가 있지만, 블록 쌓기나 그리드 이동 같은 문제에서는 압도적인 효율을 보였습니다.

---

5. 요약: 이 연구가 우리에게 주는 메시지

이 논문은 **"AI 에게 정답을 외우게 하지 말고, 세상이 어떻게 변하는지 원리를 가르쳐라"**라고 말합니다.

• 데이터가 적어도 됩니다. (원리를 알면 데이터가 적어도 됨)
• 모델이 작아도 됩니다. (복잡한 암기가 필요 없으므로)
• 새로운 상황에도 강합니다. (원리를 알면 크기가 커져도 해결 가능)

마치 아이에게 "1+1=2"라고 외우게 하는 대신, "숫자가 어떻게 더해지는지"를 가르쳐주는 것과 같습니다. 이렇게 하면 아이는 100+100 같은 큰 숫자도 스스로 계산할 수 있게 되죠. 이 연구는 AI 에게도 똑같은 '수학 원리'를 가르쳐서, 더 똑똑하고 효율적인 AI 를 만드는 길을 제시했습니다.

기술 요약

1. 연구 배경 및 문제 정의 (Problem)

• 일반화 계획 (Generalized Planning): 공통된 도메인 모델 (전이 함수 $\gamma$) 을 공유하는 계획 문제들의 가족 (families) 에 대해 해결 전략을 구축하는 것을 목표로 합니다.
• 기존 접근법의 한계: 최근 Transformer 기반의 계획기 (PlanGPT, Plansformer 등) 는 문제를 직접적인 행동 시퀀스 예측 ($p(\pi|\Pi)$) 으로 간주합니다.
  • 문제점: 명시적인 상태 전이 모델링을 생략하여, 긴 시간 범위 (long-horizon) 에서 **상태 드리프트 (State Drift)**가 발생합니다. 즉, 예측된 행동이 실제 세계 상태의 진화와 일치하지 않아 분포 외 (Out-of-Distribution, OOD) 인스턴스, 특히 객체 수가 훈련 데이터보다 훨씬 큰 경우에서 성능이 급격히 저하됩니다.
  • 데이터 비효율성: 이러한 모델들은 대규모 데이터셋과 거대한 모델 크기 (수억 개 파라미터) 를 요구합니다.

2. 제안된 방법론 (Methodology)

저자들은 일반화 계획을 전이 모델 학습 문제로 재정의했습니다. 행동 대신 **다음 상태 (Successor State)**를 예측하는 상태 중심 (State-Centric) 접근법을 사용합니다.

A. 핵심 아키텍처: 상태 중심 계획 파이프라인

1. 크기 불변 상태 표현 (Size-Invariant State Representation):

   • 객체 수가 변해도 일정한 차원의 벡터로 상태를 인코딩하기 위해 weisfeiler-Leman (WL) 그래프 임베딩을 사용합니다.
   • 이는 상태 - 목표 쌍 $(s, g)$을 관계형 그래프로 변환하고, WL 색칠 정제 (Color Refinement) 를 통해 고정된 차원의 특징 벡터 $\phi(s, g)$를 생성합니다.
   • 의의: 객체 수 ($|O|$) 에 의존하지 않는 치환 불변 (Permutation-invariant) 표현을 제공하여, 훈련 데이터보다 큰 객체 수를 가진 테스트 인스턴스로의 외삽 (Extrapolation) 을 가능하게 합니다.
   • 비교 대상: 고정 크기 팩터링 (Fixed-Size Factored, FSF) 인코딩은 객체 수 증가 시 실패함을 확인했습니다.

2. 전이 모델 학습 (Transition-Model Learning):

   • 행동 $a_t$를 예측하는 대신, 현재 상태 $s_t$와 목표 $g$를 입력받아 다음 상태 $s_{t+1}$의 임베딩을 예측하는 신경망 $f_\theta$를 학습합니다.
   • 잔차 (Residual) 모델링: STRIPS 전이 함수의 희소성 (대부분의 술어는 변하지 않음) 을 활용하여, 전체 상태 임베딩 대신 **상태 변화량 ($\Delta_t = \phi(s_{t+1}) - \phi(s_t)$)**을 예측하도록 설계했습니다. 이는 프레임 공리 (Frame Axioms) 를 명시적으로 인코딩하고 학습 효율성을 높입니다.
   • 모델 종류: 순차적 기억이 필요한지 확인하기 위해 LSTM(매개변수 모델) 과 XGBoost(비매개변수 트리 기반 회귀) 를 비교 평가했습니다.

3. 뉴로 - 심볼릭 계획 디코딩 (Neuro-Symbolic Plan Decoding):

   • 학습된 모델이 예측한 다음 상태 임베딩 $\hat{\phi}(s_{t+1})$을 생성합니다.
   • 실제 심볼릭 연산자 (Operators) 를 사용하여 현재 상태에서 적용 가능한 모든 유효한 심볼릭 후속 상태 $Succ(s_t)$를 나열합니다.
   • 예측된 임베딩과 가장 거리가 가까운 유효한 심볼릭 후속 상태를 선택하여 실행 가능한 행동을 복원합니다.
   • 장점: 이 과정은 각 단계에서 심볼릭 유효성을 보장하며, 신경망 예측 오류를 실시간으로 수정 (Online Correction) 합니다.

3. 주요 기여 (Key Contributions)

1. 새로운 공식화: 목표 조건화된 후속 상태 예측을 통한 일반화 계획의 전이 모델 기반 공식화 제시.
2. 체계적 평가: 크기 불변 및 샘플 효율적인 일반화를 위한 다양한 상태 표현 (WL vs FSF) 과 신경 아키텍처 (LSTM vs XGBoost) 의 체계적 비교.
3. 실증적 성과: Transformer 기반 계획기보다 훨씬 적은 파라미터 (약 100 만 개 vs 2 억 개 이상) 와 데이터로 동등하거나 더 나은 OOD 일반화 성능을 달성함을 입증.

4. 실험 결과 (Results)

4 가지 IPC 벤치마크 도메인 (Blocksworld, Gripper, Logistics, VisitAll) 에서 평가되었습니다.

• OOD 일반화 성능:
  • 기존 행동 중심 모델 (Plansformer, PlanGPT, SymT) 은 엄격한 외삽 (Extrapolation, 훈련보다 훨씬 큰 객체 수) 에서 대부분 0% 에 가까운 성공률을 보였습니다.
  • 제안된 WL 기반 상태 중심 모델은 Blocksworld 와 VisitAll 도메인에서 SymT 보다 높은 성공률 (예: VisitAll 에서 0.87 vs 0.64) 을 기록했습니다.
  • Logistics 도메인: 모든 학습 기반 모델이 실패했습니다. 이는 계층적 인과 결합 (Hierarchical Causal Coupling) 이 강한 도메인에서는 1 단계 전이 예측만으로는 부족함을 시사합니다.
• 표현의 중요성:
  • WL 임베딩을 사용한 모델만 외삽이 가능했고, FSF 인코딩을 사용한 모델은 모든 도메인에서 실패했습니다. 이는 크기 불변 표현이 필수적임을 증명합니다.
• 모델 효율성:
  • 제안된 모델 (LSTM: 1M 파라미터, XGBoost: ~115K 노드) 은 SymT(25-35M), PlanGPT(125M), Plansformer(220M) 보다 수백 배 작은 규모로 훈련되었습니다.
  • 데이터 증강 (SymT 의 경우) 없이 원본 소규모 데이터셋만으로도 우수한 성능을 냈습니다.
• 잔차 모델링의 효과:
  • XGBoost 의 경우 잔차 (Delta) 예측 모드가 상태 직접 예측 모드보다 외삽 성능을 크게 향상시켰습니다 (예: Blocksworld 0.25 → 0.45).

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

• 인덕티브 바이어스 (Inductive Bias) 의 우위: 거대한 모델 크기와 데이터 양보다는 명시적인 전이 모델 학습과 **적절한 관계형 추상화 (Relational Abstraction)**가 일반화 계획에서 더 강력한 인덕티브 바이어스임을 입증했습니다.
• 샘플 효율성: 대규모 LLM 이나 Transformer 에 의존하지 않고도, 컴팩트한 모델로 효율적인 일반화 계획을 수행할 수 있음을 보였습니다.
• 한계 및 향후 과제: Logistics 와 같은 복잡한 계층적 도메인에서는 1 단계 전이 예측의 한계가 드러났습니다. 향후 연구에서는 다단계 전이 또는 추상적 전이를 포함한 확장된 프레임워크를 제안할 예정입니다.

요약: 이 논문은 "행동을 예측하는 것" 대신 "상태의 변화를 예측하는 것"으로 접근하고, 이를 WL 그래프 임베딩과 심볼릭 검증으로 결합함으로써, 적은 데이터와 작은 모델로도 강력한 일반화 능력을 갖춘 계획기를 개발할 수 있음을 증명했습니다.