LeanPlan: LLM 생성 휴리스틱 및 허용성 증명을 활용한 최적 플래닝
LeanPlan: Optimal Planning with LLM-Generated Heuristics and Admissibility Proofs
한국어 초록
최첨단 대규모 언어 모델(LLM)은 탐색을 유도하는 휴리스틱 함수를 생성하여, 어떤 플랜이든 수용 가능한 만족 플래닝(satisficing planning)에서 최고 수준의 성능을 달성할 수 있습니다. 그러나 이러한 휴리스틱은 허용성(admissibility)이 보장되지 않아 차최적(suboptimal) 플랜으로 이어질 수 있습니다. 본 논문에서는 기계 검증된 허용성을 갖춘 LLM 생성 휴리스틱을 통해 최적 플랜을 찾는 최초의 플래닝 시스템인 LeanPlan을 소개합니다. 도메인 설명과 학습(training) 태스크가 주어지면, 에이전트 루프가 플래너의 피드백을 활용하여 재사용 가능한 도메인 특화 휴리스틱과 그 허용성 증명, 그리고 필요한 도메인 가정을 반복적으로 개선합니다. LeanPlan은 Lean 4에서 기계 검증된 그라운딩(grounding) 및 탐색 기능을 갖춘 효율적인 플래너와 함께 해당 휴리스틱 및 증명을 구현합니다. 저자들은 International Planning Competition의 10개 도메인과 3개의 신규 도메인에서 LeanPlan을 평가하였으며, 학습 태스크보다 최대 57배 많은 객체를 가진 테스트 태스크를 사용했습니다. 에이전트 루프에 GPT-5.6 Sol을 사용하여 이러한 모든 도메인에 대한 휴리스틱 및 허용성 증명을 성공적으로 생성했습니다. 그 결과 도출된 휴리스틱을 바탕으로 LeanPlan은 최첨단 Scorpion 플래너보다 대개 더 적은 상태를 확장하면서 전반적으로 더 많은 태스크를 해결합니다.
원문 초록
Frontier large language models (LLMs) can generate heuristic functions that guide search to achieve state-of-the-art performance in satisficing planning, where any plan is acceptable. However, these heuristics are not guaranteed to be admissible and can lead to suboptimal plans. We introduce LeanPlan, the first planning system that finds optimal plans with LLM-generated heuristics whose admissibility is machine-checked. Given a domain description and training tasks, an agentic loop uses planner feedback to iteratively improve a reusable domain-specific heuristic, its admissibility proof and the required domain assumptions. LeanPlan implements the heuristic, its proof and an efficient planner with machine-checked grounding and search in Lean 4. We evaluate LeanPlan on ten domains from the International Planning Competition and three new domains, using test tasks with up to 57 times as many objects as the training tasks. With GPT-5.6 Sol in the agentic loop, we successfully generate heuristics and admissibility proofs for all these domains. With the resulting heuristics, LeanPlan usually expands fewer states than the state-of-the-art Scorpion planner and solves more tasks overall.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.