LLM 생성 휴리스틱을 활용한 계층적 작업 네트워크 계획

Hierarchical Task Network Planning with LLM-Generated Heuristics

HTN(Hierarchical Task Network) 계획은 고전적인 계획 방법의 한 형태로, 선형적인 행동 순서를 찾는 대신, 알고리즘이 방법 라이브러리를 사용하여 상위 레벨의 작업을 분해하여 실행 가능한 행동만 남도록 합니다. 한편, 이는 문제에 대한 지식을 도입하여 방법 라이브러리를 통해 솔루션 검색을 가속화할 수 있도록 합니다. 다른 한편으로는, 고전적인 상태 공간 탐색에서 발생하는 문제들을 넘어선 새로운 과제를 야기합니다. 최근 연구에서 HTN 계획을 가속화하는 다양한 휴리스틱과 새로운 알고리즘이 개발되었지만, 이러한 휴리스틱은 아직 고전적인 계획 알고리즘에서 사용 가능한 휴리스틱만큼 유용하지 않습니다. 본 연구에서는 대규모 언어 모델(LLM)이 HTN 계획을 위한 효과적인 검색 휴리스틱을 생성할 수 있는지 조사하고, Corrêa, Pereira, 및 Seipp (2025)의 고전적인 계획 연구를 계층적인 계획으로 확장했습니다. Pytrich 플래너를 사용하여 6개의 표준 순서 기반 HTN 벤치마크 도메인에서 9개의 LLM이 생성한 휴리스틱을 도메인별 프롬프팅을 통해 생성하고, 이를 TDG 및 LMCount의 도메인 독립적인 기준선 및 PANDA 플래너와 비교했습니다. 그 결과, LLM이 생성한 휴리스틱은 가장 성능이 좋은 HTN 플래너의 범위를 거의 따라가면서, 공유된 문제의 83%에서 검색 노력을 크게 줄이는 것으로 나타났습니다.

HTN planning is a variation of classical planning where, instead of searching for a linear sequence of actions, an algorithm decomposes higher-level tasks using a method library until only executable actions remain. On one hand, this allows one to introduce domain knowledge that can speed up the search for a solution through the method library. On the other hand, it creates challenges that go beyond those of classical state-space search. While recent research produced a number of heuristics and novel algorithms that speed up HTN planning, these heuristics are not yet as informative as those available in classical planning algorithms. We investigate whether large language models (LLMs) can generate effective search heuristics for HTN planning, extending the methodology of Corrêa, Pereira, and Seipp (2025) from classical to hierarchical planning. Using the Pytrich planner on six standard total-order HTN benchmark domains, we evaluate heuristics generated by nine LLMs under domain-specific prompting and compare them against the TDG and LMCount domain-independent baselines and the PANDA planner. Our results show that LLM-generated heuristics nearly match the coverage of the best available HTN planner, while substantially reducing search effort on 83% of shared problems.