심볼릭 AI 계획을 위한 LLM 진화형 도메인 독립 휴리스틱

휴리스틱 탐색 (Heuristic search)은 심볼릭 AI 계획 (Symbolic AI planning)에서 지배적인 패러다임이며, 가장 강력한 휴리스틱들은 계획 연구자들의 수십 년간의 연구 결과물입니다. 최근 연구들은 대규모 언어 모델 (LLMs)이 개별 계획 도메인을 위한 휴리스틱을 설계할 수 있음을 보여주었으나, 지금까지 LLM이 생성한 휴리스틱 중 임의의 계획 작업에서 작동하는 것은 없었습니다. 본 논문에서 우리는 진화 탐색 (Evolutionary search)을 사용하여 수작업으로 설계된 최첨단 (State of the art) 기술을 능가하는 최초의 LLM 생성 도메인 독립 휴리스틱 (Domain-independent heuristics)을 생성합니다. 우리는 LLM이 C++로 작성된 부모 휴리스틱을 변이 (Mutate)하게 하고, 후보들을 정보성 (Informedness)과 속도 (Speed)를 기준으로 한 MAP-Elites 아카이브에 저장하며, 커버리지 (Coverage)와 해결 시간 (Solving time)을 혼합하여 적합도 점수 (Fitness scores)를 계산합니다. 진화된 프로그램들을 맥락에 배치하기 위해, 우리는 추가적으로 광범위한 수작업 설계 휴리스틱 세트를 정보성-속도 트레이드오프 (Informedness-speed tradeoff) 측면에서 벤치마킹하였으며, 이는 우리가 알기로 이전에 수행된 적이 없습니다. 학습되지 않은 테스트 도메인에서 우리의 최적 진화 휴리스틱은 가장 강력한 베이스라인 (Baseline)보다 더 많은 작업을 해결하며, 우리의 전체 휴리스틱 제품군은 해당 트레이드오프의 파레토 프런티어 (Pareto frontier)에 걸쳐 있습니다. 또한 우리는 사소한 블라인드 휴리스틱 (Blind heuristic)에서 진화를 시작하는 것이 강력한 FF 휴리스틱에서 시작하는 것보다 성능이 뛰어나다는 것을 발견했습니다. 이는 결과물인 프로그램 자체가 FF 변형일 때도 마찬가지입니다. 또한 LLM의 추론 노력 (Reasoning effort)은 컴파일에 성공한 후보들의 품질보다 후보들이 얼마나 자주 컴파일되는지에 훨씬 더 큰 영향을 미칩니다. 진화된 프로그램들은 순수 C++이므로, 기존 플래너 (Planners)에 즉시 교체 가능한 형태로 삽입될 수 있으며 기초가 되는 탐색의 건전성 (Soundness) 및 완전성 (Completeness) 보장을 상속받습니다.