최적의 고전적 계획 수립을 위한 LLM 진화형 패턴 생성기

학습된 휴리스틱 (Learned heuristics)은 최근 만족 가능한 계획 수립 (satisficing planning)을 위한 전통적인 도메인 독립적 (domain-independent) 휴리스틱의 경쟁력 있는 대안이 되었습니다. 그러나 기존의 접근 방식들은 허용성 (admissibility)을 보장하기보다는 탐색 가이드 (search guidance)를 개선하는 데 집중하고 있으며, 이는 최적의 고전적 계획 수립 (optimal classical planning)에는 부적합합니다. 본 논문에서는 설계 단계부터 허용성을 갖추어 A* 탐색의 최적성 보장을 유지하는, 도메인 의존적 (domain-dependent) 휴리스틱 학습을 위한 최초의 방법을 제시합니다. 상태 (states)에서 휴리스틱 값으로의 직접적인 매핑을 학습하는 대신, 우리는 허용 가능한 휴리스틱을 유도하는 추상화 (abstractions)를 구축하는 법을 학습합니다. 우리는 LLM 기반의 진화적 프로그램 합성 (evolutionary program-synthesis) 프레임워크를 사용하여, 각 도메인에 대해 해당 도메인의 모든 태스크에 대한 패턴 컬렉션 (pattern collection)을 생성하는 프로그램을 얻으며, 결과로 나온 패턴들을 포화 비용 분할 (saturated cost partitioning)을 통해 허용 가능하게 결합합니다. 실증적으로, 학습된 프로그램들은 해석 가능한 도메인 특화 통찰력을 인코딩하며, 테스트 시 무시할 수 있는 수준의 오버헤드로 실행됩니다. 또한 여러 도메인에서 최첨단 도메인 독립적 베이스라인 (domain-independent baselines)과 대등한 커버리지를 달성하는 동시에, 각 상태를 훨씬 더 빠르게 평가하는 휴리스틱을 생성합니다.