Model Space Reasoning as Search in Feedback Space for Planning Domain Generation

이 논문은 자연어 설명에 최소한의 심볼릭 정보를 추가하고 랜드마크나 VAL 계획 검증기 출력과 같은 다양한 심볼릭 피드백을 활용하여 휴리스틱 탐색을 수행함으로써, 에이전트 언어 모델 피드백 프레임워크를 통해 고품질의 계획 도메인을 생성하는 방법을 연구합니다.

핵심

이 논문은 **"인공지능이 자연어로 된 설명을 읽고, 정확한 '계획 수립 규칙 (PDDL)'을 스스로 만들어내는 방법"**에 대한 연구입니다.

쉽게 비유하자면, 인공지능이 "주방에서 요리를 하라"는 말만 듣고, 요리사들이 따라야 할 정확한 레시피와 도구 사용법을 스스로 작성하는 과정이라고 생각하시면 됩니다. 하지만 AI 가 처음에 만든 레시피는 종종 "설탕을 넣으라"고 쓰여 있는데 실제로는 "소금"을 넣는 식으로 엉뚱한 오류를 범하곤 합니다.

이 논문은 이 오류를 어떻게 고쳐서 완벽한 레시피를 만들 수 있는지, 그리고 어떤 '피드백 (교정)' 방식이 가장 효과적인지를 실험했습니다.

---

🍳 핵심 비유: "요리 레시피 교정 프로젝트"

1. 문제 상황: AI 의 첫 번째 시도는 엉망입니다

AI 가 "주방에서 요리를 하라"는 말 (자연어) 을 듣고 규칙을 만들면, 문법적으로는 맞지만 논리적으로는 틀린 경우가 많습니다.

• 예시: "냄비에 물을 넣고 끓여라"라고 썼는데, 실제 냄비가 없거나 물이 끓는 조건이 누락된 경우입니다.
• 기존 연구: AI 가 만든 레시피를 사람이 직접 하나하나 읽어보며 고쳐주거나, 아주 단순한 오류만 찾아주는 방식이었습니다. 하지만 사람이 직접 고쳐주는 건 시간이 너무 오래 걸립니다.

2. 이 연구의 해결책: "스스로 고쳐주는 AI 팀"

연구진은 AI 가 만든 레시피를 스스로 검증하고 고칠 수 있는 시스템을 만들었습니다. 여기서 핵심은 **'피드백 (Feedback)'**입니다. 마치 요리사가 실패한 요리를 보고 "아, 소금 대신 설탕을 넣었구나"라고 알려주는 것과 같습니다.

이 논문은 두 가지 종류의 '교정 메시지'를 실험했습니다.

• A. 랜드마크 피드백 (Landmark Feedback) = "필수 단계 체크리스트"

  • 비유: "요리할 때 반드시 거쳐야 하는 단계가 있어. 예를 들어 '양파를 먼저 볶아야 해' 또는 '마지막에 후추를 뿌려야 해' 같은 거야."
  • 효과: 전체적인 흐름을 놓치지 않도록 중요한 핵심 단계들을 알려줍니다.

• B. 계획 검증 피드백 (Plan Validation) = "실제 요리 시연"

  • 비유: "이 레시피대로 따라 해보니까, 불을 켜기 전에 냄비가 없어서 실패했어. 혹은 마지막에 요리를 다 했는데 맛이 없었어."
  • 효과: 구체적인 행동 순서에서 어떤 단계가 잘못되었는지, 왜 실패했는지 상세하게 알려줍니다.

3. 새로운 아이디어: "우연히 고치는 게 아니라, 전략적으로 고치는 것"

기존 방식은 "실수한 것 중 하나를 무작위로 골라 고쳐봐"라고 했습니다. 하지만 이 논문은 **"어떤 교정 메시지를 주면 가장 빨리 완벽해질까?"**를 계산해서 고르는 지능적인 탐색 (Heuristic Search) 방식을 도입했습니다.

• 비유:
  • 무작위 고치기 (Random Walk): "어디가 잘못됐을지 모르니, 일단 이 부분부터 고쳐봐. 안 되면 저 부분." (비효율적)
  • 전략적 고치기 (Heuristic Search): "이 레시피를 보면 '불 조절' 부분이 가장 치명적인 것 같아. 일단 이 부분부터 집중해서 고쳐보자. 그다음에 '재료 순서'를 보자." (효율적)

📊 실험 결과: 무엇이 가장 잘됐을까?

연구진은 다양한 AI 모델 (GPT-5 시리즈 등) 과 다양한 요리 상황 (블록 쌓기, 미로 찾기, 파크맨 게임 등) 에서 실험을 했습니다.

1. 피드백은 필수입니다: 아무 말 없이 AI 가 처음에 쓴 레시피보다, 피드백을 주고 고친 레시피가 훨씬 정확했습니다.
2. 두 가지 피드백을 섞으면 더 좋습니다: '필수 단계 체크리스트'와 '실제 시연 오류'를 모두 활용하면, 어느 한 가지만 쓸 때보다 더 좋은 결과를 냅니다.
3. 전략이 중요합니다: 무작위로 고치는 것보다, "어떤 교정이 가장 효과적인지" 계산해서 고르는 방식이 전반적으로 더 좋았습니다.
   • 다만: 모든 경우에 전략이 무조건 좋은 건 아니었습니다. 어떤 복잡한 상황에서는 오히려 무작위로 고치는 게 더 빠르거나 잘 맞는 경우도 있었습니다. (마치 요리 종류에 따라 '전문가 조언'이 필요할 때도 있고, '직관'이 더 필요할 때가 있는 것과 비슷합니다.)

💡 결론 및 의의

이 연구는 **"AI 가 복잡한 규칙을 스스로 배우고 고칠 수 있다"**는 것을 증명했습니다.

• 전문가 없이도 가능: 이제 복잡한 계획 수립 규칙을 만들 때, 인간 전문가가 일일이 코드를 짜거나 고칠 필요가 줄어듭니다. AI 가 자연어로 된 설명만 받아서, 스스로 피드백을 주고받으며 완벽한 규칙을 만들어냅니다.
• 미래: 이 기술이 발전하면, 우리가 "자율주행차가 비 오는 날에 어떻게 운전해야 해?"라고 말만 해도, AI 가 그 상황을 위한 완벽한 안전 규칙과 행동 지침을 자동으로 만들어낼 수 있게 될 것입니다.

한 줄 요약:

"AI 가 만든 엉뚱한 규칙을, **'필수 체크리스트'**와 **'실제 시연 오류'**라는 두 가지 교정 도구로, 가장 효과적인 순서대로 고쳐주니 완벽한 규칙이 만들어졌다!"

기술 요약

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

• 배경: 인공지능 계획 (AI Planning) 분야에서는 목표 상태를 달성하는 계획을 생성하기 위해 정확한 '계획 도메인 모델 (Planning Domain Model)'이 필요합니다. 이 모델은 자연어 기술에서 자동으로 생성되면 계획 기술의 접근성이 크게 향상될 수 있습니다. 최근 대규모 언어 모델 (LLM) 이 자연어 설명을 기반으로 PDDL(Planning Domain Definition Language) 도메인을 생성하는 데 유망한 성과를 보이고 있습니다.
• 문제점: 그러나 현재 LLM 이 생성한 도메인은 문법적으로 올바를지라도 의미론적 (semantic) 결함이 많아 실제 계획기에 적용하기 어렵습니다. 기존 연구들은 주로 단일 피드백 유형 (예: 계획 검증 도구 VAL 의 출력) 이나 인간 개입에 의존하거나, 제한된 벤치마크 도메인에서만 평가되었습니다. 또한, 생성된 도메인과 실제 도메인 간의 품질을 자동으로 정량화하는 데 한계가 있었습니다.
• 연구 목표: 자연어 설명에서 고품질의 계획 도메인을 생성하기 위해, **상징적 피드백 (Symbolic Feedback)**을 활용하고 이를 **휴리스틱 탐색 (Heuristic Search)**을 통해 최적화하는 에이전트 기반 프레임워크를 제안하는 것입니다.

2. 방법론 (Methodology)

저자들은 자연어 설명 ($D_{NL}$) 과 보조 정보 (문제, 계획, 랜드마크) 를 입력받아 고품질 PDDL 도메인 ($D'$) 을 생성하고 자동 평가하는 파이프라인을 설계했습니다.

2.1. 파이프라인 개요

프로세스는 크게 두 단계로 나뉩니다:

1. 초기 도메인 구성 (Initial Domain Construction):
   • LLM 에게 자연어 동작 설명을 PDDL 동작으로 변환하도록 프롬프트합니다.
   • 생성된 PDDL 코드를 구문 분석기 (Parser) 로 검증하여 문법 오류가 있을 경우 수정 요청을 반복합니다.
   • 모든 동작이 생성되면 초기 도메인 $D'$을 구성합니다.
2. 도메인 정제 (Domain Refinement via Feedback):
   • 생성된 도메인에 다양한 피드백 메커니즘을 적용하여 반복적으로 개선합니다.
   • 피드백 소스:
     • 랜드마크 (Landmarks): 모든 계획에서 반드시 거쳐야 하는 상태나 동작의 집합 (Hoffmann et al., 2004).
     • 계획 검증 (Plan Validation, VAL): 지상 진실 (Ground Truth) 도메인에서 유효한 계획이 생성된 도메인에서 실행 가능한지 확인 (VAL 도구 사용).
   • 피드백 전략:
     • 무작위 단일 피드백 (Random Single): 유효하지 않은 계획이나 랜드마크에 대한 피드백 중 하나를 무작위 선택하여 LLM 에게 재요청.
     • 휴리스틱 탐색 (Heuristic Search): 가능한 피드백 메시지 공간에서 휴리스틱 함수 (노드 깊이 $G$와 유효하지 않은 계획 수 $H$ 기반) 를 사용하여 가장 유망한 피드백을 선택하고 탐색 트리를 확장합니다.

2.2. 품질 평가 지표 (Evaluation Metric)

• 휴리스틱 도메인 동등성 (Heuristic Domain Equivalence, HDE):
  • 생성된 도메인 $D'$과 지상 진실 도메인 $D$의 동등성을 자동으로 평가합니다.
  • 지상 진실 도메인의 문제들에 대해 생성된 도메인에서 계획을 생성하고, 그 역으로 검증합니다.
  • HDE 점수 공식:
    $$HDE(\Pi, \Pi') = \frac{1}{2} \left( \frac{|P \cap P_{\Pi'}|}{|P|} + \frac{|P' \cap P_{\Pi}|}{|P'|} \right)$$
    • 첫 번째 항: 지상 진실 계획이 생성된 도메인에서 유효한 비율 (Forward).
    • 두 번째 항: 생성된 계획이 지상 진실 도메인에서 유효한 비율 (Backward).
  • 이 지표를 통해 생성된 도메인이 지나치게 일반화되었는지 (Over-generalized) 또는 과도하게 제한적인지 (Over-restrictive) 를 파악할 수 있습니다.

3. 주요 기여 (Key Contributions)

1. 상징적 피드백과 탐색의 통합: 랜드마크와 계획 검증 (VAL) 피드백을 결합하고, 이를 무작위 선택이 아닌 **휴리스틱 탐색 (Model Space Reasoning as Search)**을 통해 최적화하는 새로운 프레임워크를 제안했습니다.
2. 자동화된 정량적 평가: 인간 평가자 없이 HDE 지표를 사용하여 생성된 도메인의 의미론적 정확성을 자동으로 측정하는 방법을 적용했습니다.
3. 다양한 도메인에서의 검증: 잘 알려진 고전 도메인 (Blocks, Miconic) 뿐만 아니라, LLM 학습 데이터에 포함되지 않았거나 덜 알려진 새로운 도메인 (Hiking, Pacman 변형 등) 에서도 실험을 수행하여 일반화 능력을 입증했습니다.
4. 최적의 피드백 전략 발견: 단일 피드백 유형보다 피드백을 탐색하는 방식이 더 효과적일 수 있음을 보였으며, 특히 랜드마크 피드백이 복잡한 계획 검증 피드백만큼 효과적일 수 있음을 발견했습니다.

4. 실험 결과 (Results)

• 실험 설정: 3 가지 LLM (gpt-5-nano, gpt-5-mini, deepseek-chat) 과 7 가지 피드백 파이프라인 (무피드백, 랜드마크/계획 피드백의 무작위/탐색 버전 등) 을 다양한 도메인에서 20 회 반복 실험했습니다.
• 주요 발견:
  • 피드백의 효과 (R1): 무피드백 베이스라인에 비해 모든 피드백 메커니즘이 도메인 품질 (HDE 점수) 을 유의미하게 향상시켰습니다.
  • 피드백 유형의 비교 (R2): 단일 피드백 유형이 모든 도메인에서 우월하지는 않았습니다. 랜드마크와 계획 피드백은 상호 보완적인 강점을 가졌습니다.
  • 탐색 vs 무작위 (R4): 일반적으로 휴리스틱 탐색 (Search) 기반 접근법이 무작위 선택 (Random Walk) 보다 더 좋은 결과를 보였습니다.
    • 예외: 특정 도메인 (Flow, Hiking 등) 에서는 무작위 선택이 탐색보다 더 높은 HDE 점수나 100% 정확도 달성 횟수를 보인 경우도 있어, 피드백 전략이 도메인과 모델에 따라 다르게 작용함을 시사합니다.
  • 성공 사례: gpt-5-mini 모델을 사용한 랜드마크 + 계획 피드백 탐색 (LVS) 전략은 테스트된 모든 도메인에서 최소 1 회 이상 100% HDE 점수를 달성했습니다. 이는 생성된 도메인이 지상 진실과 완전히 일치함을 의미합니다.

5. 의의 및 결론 (Significance)

• 실용성: 이 연구는 LLM 을 이용한 계획 도메인 생성의 정확도를 획기적으로 높여, 비전문가도 자연어 설명만으로 신뢰할 수 있는 계획 시스템을 구축할 수 있는 가능성을 열었습니다.
• 효율성: 복잡한 계획 검증 (Plan Validation) 피드백 대신 상대적으로 계산 비용이 적게 드는 랜드마크 피드백만으로도 높은 품질의 도메인을 생성할 수 있음을 보여주었습니다.
• 미래 전망: 향후 invariant 기반 피드백 확장, 사용자 연구, 그리고 실제 세계 계획 시나리오 적용 등을 통해 이 프레임워크의 범위를 넓힐 계획입니다.

요약하자면, 이 논문은 **"모델 공간 추론을 피드백 공간 탐색으로 간주"**하여, 자연어에서 PDDL 도메인 생성의 정확도를 높이기 위해 상징적 피드백 (랜드마크, 계획 검증) 과 휴리스틱 탐색을 결합한 혁신적인 접근법을 제시하고 실험적으로 검증했습니다.