GenePlan: Evolving Better Generalized PDDL Plans using Large Language Models

이 논문은 대규모 언어 모델 (LLM) 을 활용한 진화 알고리즘을 통해 PDDL 로 기술된 고전적 계획 작업에 대해 다양한 문제 인스턴스에서 최적의 해결책을 생성하는 일반화된 계획자 'GenePlan'을 제안하며, 기존 최첨단 계획자와 유사한 성능을 보이고 다른 LLM 기반 방법론보다 월등히 우수한 결과를 입증했습니다.

핵심

이 논문은 **"GenePlan(진화적 계획가)"**이라는 새로운 시스템을 소개합니다. 이 시스템은 거대한 인공지능 (LLM) 의 지능과 자연선택의 원리를 섞어서, 복잡한 문제 해결 방법을 자동으로 만들어냅니다.

일상적인 비유로 쉽게 설명해 드리겠습니다.

1. 문제: "지도 없이 길을 찾는 것"

상상해 보세요. 여러분이 낯선 도시에서 목적지까지 가는 방법을 찾아야 합니다. 하지만 여기엔 두 가지 방식이 있습니다.

• 기존 방식 (LLM 만 사용): "AI 에게 물어봐!"라고 하면, AI 가 "아, 여기가 저기야!"라고 말해줍니다. 하지만 AI 는 가끔 엉뚱한 길로 가거나, 너무 길고 비효율적인 길을 제안하기도 합니다. (논문에 따르면, AI 만으로는 계획 수립 능력이 아직 부족합니다.)
• 기존 방식 (전통적 알고리즘): 수천 년 동안 개발된 정교한 수학 공식을 써서 길을 찾습니다. 매우 정확하지만, 계산하는 데 시간이 오래 걸리고, 그 결과가 왜 그런지 사람이 이해하기 어렵습니다.

2. 해결책: "진화하는 요리사" (GenePlan)

GenePlan 은 이 두 가지의 장점을 합칩니다. 마치 수천 명의 요리사들이 모여서 '최고의 레시피'를 개발하는 과정과 같습니다.

1. 초기 아이디어 (요리사 모집): 먼저 AI 가 다양한 '요리 레시피 (코드)'를 몇 개 만들어냅니다. 처음엔 다들 엉성하고 실패할 수도 있는 레시피들입니다.
2. 시식과 평가 (시험): 이 레시피들을 실제 문제 (예: 물건을 옮기는 게임) 에 적용해 봅니다.
   • "이 레시피로 만든 요리는 너무 길게 걸려서 실패야!" (점수 낮음)
   • "이 레시피는 짧고 깔끔하게 성공했어!" (점수 높음)
3. 자연선택 (진화): 점수가 낮은 레시피는 버리고, 점수가 높은 레시피들을 '부모'로 뽑습니다.
4. 혼합과 변이 (새로운 시도): AI 는 이 좋은 레시피들을 섞어보고 (교차), 약간의 변화를 주어 (돌연변이) 더 나은 새로운 레시피를 만듭니다.
   • 예시: "A 요리사의 '재료 손질법'과 B 요리사의 '불 조절법'을 섞어보자. 그리고 소금 양을 살짝 줄여보자."
5. 반복: 이 과정을 수십 번 반복하면, 처음엔 엉망이었던 레시피들이 점점 더 짧고 효율적인 '최고의 레시피'로 진화합니다.

3. 결과: "한 번 배우면 영원한 전문가"

이 과정이 끝나면 GenePlan 은 완벽한 Python 코드 (레시피) 하나를 만들어냅니다.

• 빠름: 이 코드를 만든 후에는, 새로운 문제가 들어와도 AI 가 다시 생각할 필요 없이, 이 코드가 0.5 초 만에 해결책을 내놓습니다. (전통적인 방식은 매번 계산해야 하므로 느립니다.)
• 이해 가능: AI 가 만든 '블랙박스'가 아니라, 사람이 읽을 수 있는 Python 코드이므로 왜 그렇게 해결했는지 알 수 있습니다.
• 비효율: 이 '레시피'를 개발하는 데 드는 비용은 약 1.82 달러 (약 2,500 원) 에 불과합니다.

4. 실험 결과

연구진은 8 가지 다른 게임 (등산, 페리 배, 엘리베이터 등) 에서 이 방법을 테스트했습니다.

• 성공률: 최고의 전문가 (Fast Downward) 와 거의 비슷한 점수를 받았습니다. (91% vs 93%)
• 기존 AI 와 비교: 그냥 AI 에게 "생각해서 답해줘"라고 한 것 (Chain-of-Thought) 보다 훨씬 더 잘했습니다. (91% vs 64%)

5. 한계와 미래

물론 모든 문제에 이 방법이 좋은 것은 아닙니다.

• 예외: 어떤 문제는 (예: 소코반 게임처럼 돌을 밀어 넣는 게임) 한 번 실수하면 되돌릴 수 없는 경우가 있습니다. 이런 복잡한 문제에서는 여전히 전통적인 '계산기' 방식이 더 나을 수 있습니다.
• 미래: 앞으로는 AI 가 "이 문제는 GenePlan 이 해결하고, 저 문제는 계산기로 해결하자"라고 스스로 판단하게 만들거나, 더 좋은 해결책을 찾기 위해 '조기 종료' 기능을 추가할 계획입니다.

요약

GenePlan은 AI 에게 "한 번에 정답을 외우게" 하는 게 아니라, **"수천 번의 시행착오를 통해 스스로 가장 좋은 해결책을 진화시켜서, 그 해결책을 하나의 프로그램으로 남기는 시스템"**입니다. 한 번 만들어두면 저렴하고 빠르며, 사람도 이해할 수 있는 완벽한 해결책을 제공합니다.

기술 요약

GenePlan: 대규모 언어 모델을 활용한 일반화된 PDDL 계획의 진화적 개선

이 논문은 J.P. Morgan AI Research 소속 연구진 (Andrew Murray 등) 이 제안한 GenePlan (GENeralized Evolutionary Planner) 프레임워크를 소개합니다. GenePlan 은 고전적인 계획 (Classical Planning) 문제를 PDDL(Planning Domain Definition Language) 로 표현했을 때, 다양한 문제 인스턴스에 대해 최적의 일반화된 계획자 (Generalized Planner) 를 생성하기 위해 대규모 언어 모델 (LLM) 과 진화 알고리즘 (Evolutionary Algorithms) 을 결합한 새로운 접근법입니다.

1. 문제 정의 (Problem)

• LLM 의 계획 능력 한계: 최근 LLM 의 추론 능력이 향상되었음에도 불구하고, 순차적 의사결정 작업인 계획 (Planning) 분야에서는 여전히 성능이 부족합니다. 기존 LLM 기반 접근법들은 주로 만족스러운 해 (Satisficing solutions) 를 생성하는 데 초점을 맞추었으며, 해의 품질 (예: 행동 수 최소화) 을 최적화하지 못했습니다.
• 일반화된 계획 (Generalized Planning) 의 필요성: 특정 도메인 내에서 다양한 문제 인스턴스에 적용 가능한 하나의 전략 (일반화된 계획자) 을 찾는 것은 중요합니다. 그러나 기존 LLM 기반 방법들은 도메인 지식을 활용하더라도 최적의 해를 보장하지 못하거나, 검색 알고리즘과 결합하여 비효율적인 경우가 많았습니다.
• 최적화 문제로서의 접근 부재: 기존 연구들은 주로 해를 찾는 데 그쳤으며, 해의 품질을 기준으로 진화시키는 최적화 프레임워크를 적용하지 않았습니다.

2. 방법론 (Methodology)

GenePlan 은 일반화된 계획을 최적화 문제로 재정의하고, 이를 해결하기 위해 LM 을 진화 알고리즘의 일부로 통합합니다.

핵심 아이디어

• 목표: 주어진 도메인의 여러 훈련 문제 인스턴스 (Training Tasks) 에 대해 행동 수 (Plan Length) 를 최소화하는 Python 코드로 작성된 일반화된 계획자 (Planner) 를 찾는 것.
• 적합도 함수 (Fitness Function): 생성된 계획자가 훈련 세트의 각 문제 인스턴스에서 생성한 계획의 평균 길이를 계산합니다. 계획이 실패하거나 유효하지 않으면 큰 페널티 점수를 부여합니다.

GenePlan 아키텍처 및 프로세스

GenePlan 은 Romera-Paredes 등 (2024) 의 진화적 LLM 프레임워크를 확장하여 다음과 같은 사이클을 반복합니다:

1. 초기화: PDDL 도메인 정의와 초기 계획자 (Chain-of-Thought 프롬팅 또는 제공된 코드) 로 시작합니다.
2. 선택 (Selection): 현재 모집단 (Population) 내 계획자들의 적합도 점수에 기반하여 부모 (Parent) 를 선택합니다.
   • 온도 스케줄링: 초기에는 탐색 (Exploration) 을 위해 온도를 높게, 후기에는 활용 (Exploitation) 을 위해 온도를 낮게 설정하는 역감쇠 (Inverse Decaying) 함수를 사용하여 확률적 선택을 수행합니다.
3. 프롬프트 구성 및 LLM 호출: 선택된 부모 계획자들의 코드와 실행 결과 (성공/실패 메시지, 점수) 를 포함하는 프롬프트를 LLM 에게 전달합니다.
   • LLM 은 **교차 (Crossover)**와 **변이 (Mutation)**를 수행하여 새로운 자식 (Offspring) Python 코드를 생성하도록 지시받습니다.
4. 검증 및 평가 (AST Parsing & Validation):
   • LLM 이 생성한 코드는 AST(추상 구문 트리) 파서를 통해 문법적 유효성과 허용 가능한 노드/함수만 사용했는지 검증합니다.
   • 유효한 코드는 실행되어 PDDL 계획자를 생성하고, 훈련 문제 세트에 대해 실행됩니다.
   • 생성된 계획은 PDDL 검증기 (Plan Validator) 를 거쳐 유효성 (Validity) 과 행동 수 (Length) 를 평가받습니다.
5. 대체 (Replacement):
   • 새로운 자식 계획자들이 모집단에 추가됩니다.
   • 세대 (Generation) 가 완료되면, 가장 낮은 점수 (최악의 성능) 를 가진 계획자를 제거하고 상위 성능의 계획자들만 다음 세대로 유지하는 **엘리트 대체 전략 (Elitist Replacement)**을 사용합니다.
6. 수렴: 정해진 세대 수 (G) 또는 수렴 조건에 도달할 때까지 이 과정을 반복하며, 최종적으로 가장 우수한 Python 계획자를 추출합니다.

3. 주요 기여 (Key Contributions)

1. 최적화 중심의 일반화된 계획 프레임워크: LLM 을 단순히 해를 생성하는 도구가 아닌, 진화 알고리즘을 통해 해의 품질을 지속적으로 개선하는 최적화 엔진으로 활용했습니다.
2. 해석 가능한 고품질 Python 계획자 생성: 생성된 계획자는 블랙박스 모델이 아닌, 인간이 이해하고 수정할 수 있는 Python 코드 형태로 출력됩니다.
3. LLM 기반 방법론의 성능 한계 극복: 기존 Chain-of-Thought (CoT) 프롬팅 방식보다 훨씬 우수한 성능을 보여주며, 전통적인 고전적 계획 솔버 (Fast Downward) 와 비교해도 경쟁력 있는 결과를 달성했습니다.
4. 비용 효율성: 고비용의 검색 기반 솔버와 달리, 한 번 계획자를 생성한 후에는 매우 낮은 비용과 빠른 속도로 새로운 문제를 해결할 수 있습니다.

4. 실험 결과 (Results)

8 개의 PDDL 도메인 (기존 벤치마크 6 개 + 새로 생성된 2 개) 에서 10 가지 베이스라인과 비교 평가되었습니다.

• 성능 (SAT Score):
  • GenePlan (evo) 은 평균 0.91의 SAT 점수를 기록했습니다.
  • 이는 30 분 시간 제한을 둔 최첨단 솔버인 Fast Downward (fd_1800, 점수 0.93) 와 거의 동급의 성능입니다.
  • 기존 LLM 기반 베이스라인인 Chain-of-Thought (CoT, GPT-4o) 의 평균 점수 (0.64) 보다 0.27 포인트 크게 향상되었습니다.
• 실행 시간 및 비용:
  • 생성 시간: 계획자 생성에 약 10~15 분 (평균 645 초) 이 소요되지만, 이는 일회성 비용입니다.
  • 추론 시간: 생성된 계획자는 새로운 문제를 해결하는 데 평균 0.49 초가 소요되어 Fast Downward 보다 훨씬 빠릅니다.
  • 비용: GPT-4o 를 사용한 경우 도메인당 평균 $1.82의 비용으로 고품질 계획자를 생성할 수 있었습니다.
• 통계적 유의성: Nemenyi 사후 검정을 통해 GenePlan 이 CoT 기반 방법론보다 통계적으로 유의미하게 우월함을 입증했습니다.
• 도메인별 특징:
  • 단순한 전략이 존재하는 도메인 (예: Trapnewspapers, Hiking) 에서는 1 세대 만에 최적해에 수렴하기도 했습니다.
  • Sokoban 과 같이 국소 최적해에 빠지기 쉽거나 복잡한 도메인에서는 GenePlan 이 검색 알고리즘을 모방하려다 실패하는 경향이 있어, 이러한 도메인에서는 전통적인 검색 기반 솔버가 여전히 필요함을 확인했습니다.

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

GenePlan 은 LLM 을 활용한 계획 분야에서 다음과 같은 중요한 의의를 가집니다:

• 실용성: 생성된 Python 계획자는 해석 가능하고, 재사용 가능하며, 실시간으로 빠른 추론이 가능합니다. 이는 반복적인 계획이 필요한 실제 응용 분야 (예: 물류, 로봇 제어) 에 매우 적합합니다.
• 비용 효율성: 고가의 검색 알고리즘을 매번 실행하는 대신, 한 번의 진화 과정을 통해 최적의 휴리스틱을 학습하여 장기적으로 비용을 절감할 수 있습니다.
• 미래 방향:
  • 수렴 시 조기 종료 (Early Stopping) 기준을 도입하여 생성 비용을 더 줄일 수 있습니다.
  • 단순한 계획 길이 최적화를 넘어 다양한 최적화 지표를 연구할 수 있습니다.
  • LLM 을 오케스트레이션 인터페이스로 사용하여, 문제의 복잡도에 따라 GenePlan 생성 계획자와 전통적 검색 솔버를 동적으로 선택하는 하이브리드 시스템 구축이 가능합니다.

결론적으로, GenePlan 은 LLM 의 생성 능력과 진화 알고리즘의 최적화 능력을 결합하여, 기존 LLM 기반 방법론의 한계를 극복하고 전통적 계획 솔버와 경쟁할 수 있는 고품질 일반화 계획자를 생성하는 유효한 프레임워크임을 입증했습니다.