Improved Generalized Planning with LLMs through Strategy Refinement and Reflection

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

• 일반화 계획 (Generalized Planning): PDDL(Planning Domain Definition Language) 도메인 내의 모든 작업 (tasks) 에 대해 적용 가능한 일반적인 계획 (일반적으로 Python 프로그램으로 표현됨) 을 생성하는 문제입니다. 이는 개별 작업마다 계획을 생성하는 것보다 확장성과 비용 효율성이 뛰어납니다.
• 기존 접근법의 한계 (Silver et al., 2024):
  • 이전 연구는 LLM 에게 도메인 요약을 생성하게 한 후, 이를 자연어 (NL) 전략으로 변환하고, 이를 바로 Python 코드로 구현하게 했습니다.
  • 핵심 병목 현상: 생성된 자연어 전략이 잘못되면, 이를 구현한 Python 코드도 당연히 오류를 포함하게 됩니다. 기존 방식은 전략 단계에서 오류를 검증하거나 수정할 수 없었으며, 오직 코드 실행 단계의 피드백만 활용했습니다.
  • 이로 인해 전략이 부정확할 경우, 전체 일반화 계획 생성이 실패하거나 품질이 낮아지는 문제가 발생했습니다.

2. 제안된 방법론 (Methodology)

저자들은 전략 생성 (Strategy Generation) 을 코드 생성과 분리된 독립적인 하위 작업으로 취급하고, 이를 의사코드 (Pseudocode) 형태로 생성하여 자동 디버깅 및 정제하는 새로운 파이프라인을 제안합니다.

주요 구성 요소:

1. 의사코드 전략 생성 및 검증 (Strategy Generation & Validation):

   • LLM 에게 자연어 요약 대신 구조화된 의사코드 (Pseudocode) 형태의 전략을 생성하도록 지시합니다.
   • 자동 검증: 생성된 의사코드를 기반으로 LLM 이 디버깅용 작업 (debugging tasks) 에 대한 PDDL 계획을 생성하게 합니다.
   • 심볼릭 검증기 (VAL) 활용: 생성된 PDDL 계획을 심볼릭 플래너 검증기 (VAL) 로 검증하여 정합성을 확인합니다.
   • 반성 (Reflection) 단계: 검증 실패 시, LLM 에게 "어떤 전략 부분이 오류를 유발했는지"와 "왜 그 부분이 부적절한지"를 분석하도록 요청합니다. 이를 통해 LLM 은 의사코드를 수정하고 재검증합니다.

2. 코드 디버깅 및 반성 (Code Debugging with Reflection):

   • 의사코드가 검증된 후 Python 코드로 변환됩니다.
   • 기존 디버깅 과정에 반성 단계를 추가합니다. 코드 실패 시, 단순히 오류 메시지를 주는 것을 넘어, LLM 이 오류의 원인과 위치를 분석하고 수정하도록 유도합니다.
   • 또한, 성공한 작업들의 결과도 피드백에 포함시켜 컨텍스트를 풍부하게 합니다.

3. 다중 코드 변이 생성 (Multiple Code Variants):

   • LLM 기반 코드 생성의 불확실성을 줄이기 위해, 동일한 전략을 기반으로 여러 개의 초기 프로그램 버전을 생성합니다.
   • 입력 데이터 (객체 및 사실) 의 순서를 무작위로 변경하여 다양한 초기 코드를 생성한 후, 디버깅 성능이 가장 좋은 프로그램을 최종 선택합니다.

3. 주요 기여 (Key Contributions)

1. 전략 수준의 자동 디버깅: 자연어 전략이 아닌 의사코드를 생성하고, 이를 심볼릭 플래너와 LLM 을 통해 자동 검증 및 정제하는 프레임워크를 도입했습니다. 이는 오류를 코드 구현 단계 이전인 전략 단계에서 발견하고 수정할 수 있게 합니다.
2. 반성 (Reflection) 메커니즘의 통합: 전략 및 코드 디버깅 단계 모두에서 LLM 이 오류의 원인을 스스로 분석하고 설명하도록 하는 반성 단계를 도입하여 수정의 정확도를 높였습니다.
3. 다중 후보 생성 및 선택: 단일 코드 생성이 아닌, 입력 순서 변이를 통한 다중 프로그램 생성 및 성능 기반 선택 방식을 적용하여 안정성을 높였습니다.
4. 광범위한 실험 및 검증: 17 개의 벤치마크 도메인에서 4 가지 LLM(GPT-4o, Llama3.3, DeepSeek-V3.2, Qwen3-Thinking) 을 사용하여 실험을 수행하고, 기존 방법론 (Silver et al.) 및 심볼릭 플래너와 비교했습니다.

4. 실험 결과 (Results)

• 성능 향상: 제안된 방법 (F5-3 구성) 은 17 개 도메인에서 평균 82% 의 커버리지를 달성했습니다.
  • 기존 방법 (Silver et al.) 대비 GPT-4o 기준 23%p, DeepSeek 기준 14%p 등 모든 모델에서 유의미한 성능 향상을 보였습니다.
  • 특히 DeepSeek 모델과 결합 시, 14 개 도메인에서 3 번의 실행 중 1 번 이상 100% 커버리지를 달성했습니다.
• 일반화 능력: 100% 커버리지를 달성한 프로그램들은 평가 데이터셋을 넘어, 해당 도메인 생성기로 생성 가능한 모든 크기 및 형태의 작업에 대해 일반화되는 것을 수동 분석을 통해 확인했습니다.
• 비용 효율성 및 속도:
  • 일반화 계획은 도메인당 한 번만 생성하면 되므로, 개별 작업별 계획 생성에 비해 LLM 호출 비용이 현저히 낮습니다.
  • 생성된 Python 프로그램의 실행 속도는 심볼릭 플래너 (FF, LM-cut) 보다 대부분의 작업에서 훨씬 빠릅니다 (약 97% 의 작업에서 더 빠름).
  • 계획의 길이는 심볼릭 플래너보다 약간 길 수 있지만 (평균 1.1~1.5 배), 실행 시간의 이점이 이를 상쇄합니다.
• 강건성 (Robustness): "Costumed" (의미론적 이름 변경) 벤치마크에서도 좋은 성능을 보여, LLM 이 단순한 훈련 데이터 암기가 아닌 실제 도메인 논리를 추론하고 있음을 입증했습니다.

5. 의의 및 결론 (Significance)

• LLM 과 심볼릭 AI 의 융합: 이 연구는 LLM 의 추론 능력을 활용하면서도 심볼릭 검증기 (VAL) 를 통해 논리적 정확성을 보장하는 하이브리드 접근법의 가능성을 보여주었습니다.
• 확장성 해결: 개별 작업별 계획 생성의 비효율성과 확장성 한계를 극복하고, 도메인 단위의 일반화 계획을 통해 대규모 문제 해결을 가능하게 합니다.
• 실용적 가치: 생성된 프로그램은 매우 빠른 실행 속도를 가지며, 이는 실제 로봇 제어나 복잡한 의사결정 시스템에서 LLM 기반 플래너의 실용성을 높이는 중요한 기여입니다.

결론적으로, 이 논문은 LLM 을 이용한 일반화 계획의 핵심 병목인 "전략의 정확성" 문제를 의사코드 기반 검증과 반성 메커니즘으로 해결함으로써, 기존 방법론보다 훨씬 신뢰성 있고 효율적인 일반화 계획 생성을 가능하게 했습니다.