Назад в библиотеку

Дорожная карта для руководства интеграцией LLMs в Иерархическое Планирование

Автор: Israel Puerta-Merino, Carlos Núñez-Molina, Pablo Mesejo, Juan Fernández-Olivares
Источник: A Roadmap to Guide the Integration of LLMs in Hierarchical Planning / I. Puerta-Merino, C. N´u˜nez-Molina, P. Mesejo, [et al.]. — 2025. — arXiv: 2501.08068 [cs.AI].
Перевод выполнил: М.К. Слипенко

Введение

Иерархическое Планирование (HP) — это под область внутри Автоматизированного Планирования (AP), включающая методы планирования, которые включают иерархические знания. Эти иерархические знания могут быть использованы для ускорения планирования и, также, для интеграции знаний экспертов-человеков по решению проблем. В то время как Большие Языковые Модели (LLMs) постепенно интегрируются в различные области ИИ, включая AP, их применение к HP остается недостаточно исследованным, с лишь несколькими исследованиями, косвенно затрагивающими эту тему (Yang, Zhang, and Hou 2024; Dai et al. 2024; Tse 2024; Song et al. 2023). Наш вклад в этой работе, таким образом, — это дорожная карта для заполнения этого пробела, исследуя потенциал LLMs для HP.

Мы проанализировали существующую литературу по AP с LLMs, а также текущие обзоры (Pallagani et al. 2024; Huang et al. 2024; Valmeekam et al. 2022). Наблюдая, что большинство методов в AP, которые аналогично применимы к HP, мы классифицировали эти методы, создав таксономию, чтобы приблизить HP к существующим техникам интеграции LLM. Наша таксономия классифицирует методы интеграции по двум различным измерениям: Роль в Процессе Планирования (в какой части жизненного цикла HP применяется LLM — т.е. определение проблемы, разработка плана или пост-обработка) и Стратегия Улучшения LLM (какие подходы на основе LLM используются для улучшения производительности LLM — т.е. предоставление дополнительного знания или выполнение нескольких вызовов). Учитывая, что HP является подмножеством AP, эта классификация в целом применима и к AP.

Для облегчения оценки и сравнений между методами мы предлагаем стандартизированный набор данных и фреймворк бенчмаркинга на основе треков HTN Международного Соревнования по Планированию 2023 года (IPC-2023), самого недавнего соревнования для решателей HP. В частности, мы предлагаем использовать трек total-order набора данных IPC-2023 в качестве бенчмарк-набора данных.1 В качестве базовой линии мы реализуем и оцениваем базовый Планировщик на основе LLM (прямое планирование с использованием LLM без каких-либо стратегий улучшения), самый простой метод нашей таксономии, на этом наборе данных. Мы используем Llama-3.1-Nemotron-70B-Instruct (Wang et al. 2024), одну из самых высокопроизводительных доступных LLM, и модель, которую мы планируем использовать в последующих экспериментах. Мы также предоставляем результаты от PandaDealer-agile-lama (Olz, Höller, and Bercher 2023), победителя трека Total-Order Satisficing IPC-2023 и современного решателя HP.

В итоге, эта работа предлагает дорожную карту для руководства будущими исследованиями в интеграции LLMs и HP, которая предоставлена через два основных вклада: таксономию методов интеграции LLM в HP, иллюстрирующую масштаб этого поля и раскрывающую, сколько работы еще предстоит сделать; и предложенный бенчмарк, предоставляющий инструмент для оценки и сравнения разработанных и будущих методов. Мы надеемся, что эта дорожная карта вдохновит и направит будущие исследования в этом многообещающем, но недостаточно исследованном поле.

Чтобы преодолеть разрыв между HP и существующими техниками Интеграции LLM, и исследовать это обширное поле, мы предлагаем таксономическую рамку, которая выделяет идентифицированные методы. Эта классификация в основном опирается на современное состояние AP, так что многие из этих методов также применимы к AP. Чтобы предоставить контекст для последующих разделов, мы включаем иллюстративные примеры замечательных методов Интеграции AP из текущей литературы. Каждый из методов в этой таксономии представляет подмножество техник, а не точную реализацию, и может охватывать несколько подходов. Кроме того, эти методы не являются взаимоисключающими, что означает, что агенты планирования могут быть спроектированы для исследования нескольких комбинаций, делая это огромным полем для исследования. Эта классификация предназначена быть отправной точкой, а не фиксированной рамкой, с пространством для исследования и уточнения.

Наша предложенная таксономия структурирована по двум измерениям: Роль в Процессе Планирования, категоризирующая этапы жизненного цикла HP, где может применяться LLM: определение проблемы, разработка плана и пост-обработка (т.е., включая перевод плана и объяснение конечному пользователю). И Стратегия Улучшения LLM, которая охватывает общие стратегии, используемые для повышения производительности LLM, которые применимы независимо от роли, для которой они используются: улучшение знания и несколько вызовов. В этом последнем измерении, несмотря на то, что было изучено несколько Стратегий Рассуждений LLM, мы сосредоточили нашу классификацию на основных различных стратегиях, которые, как мы наблюдали, обычно используются в AP, поскольку мы считаем, что это наиболее интересные техники для первоначального исследования и оценки в HP. Эти стратегии в основном состоят в использовании дополнительного знания или увеличении числа выполнений LLM.

Роль в Процессе Планирования

LLMs могут принимать различные роли на трех общих шагах процесса планирования: (1) определение проблемы, (2) разработка плана и (3) пост-обработка. Каждый шаг далее разделен на отличительные методы интеграции LLM, наблюдаемые в литературе. Таблица 1 суммирует эту классификацию.

Определение Проблемы. Проблема HP включает те же элементы, что и проблема AP (Действия, Начальное Состояние и Цель), наряду с высокоуровневыми действиями (Задачами), которые представляют иерархическую информацию об окружении. Каждый элемент может быть сгенерирован с использованием LLM через два основных подхода: Перевод, когда вся необходимая информация явно и заранее предоставлена, и мы хотим только, чтобы LLM реструктурировал предоставленную информацию в целевой формат (Liu et al. 2023); и Генерация, когда информация предоставлена частично или неявно, так что LLM выводит или предполагает отсутствующую информацию на основе рассуждений (Gestrin, Kuhlmann, and Seipp 2024).

Разработка Плана Мы категоризируем эту группу на основе роли LLM в процессе решения проблемы:

  • Планировщик LLM. В этой базовой настройке сама LLM функционирует как планировщик (Silver et al. 2022). Хотя могут применяться стратегии улучшения LLM, здесь нет внешнего планировщика или явного процесса поиска, так что модель LLM отвечает за весь процесс планирования.
  • Поиск по Графу. LLM встроена в планировщик, который выполняется в рамках явного алгоритма поиска, где LLM может выполнять одну или несколько ролей, таких как Расширение Узла (генерация следующих возможных действий), Выбор (выбор следующего действия), Предоставление Эвристики (оценка состояний), Выявление Модели, Откат, Агрегация и Обрезка. Некоторые замечательные архитектуры: RAP (Hao et al. 2023), интегрирующая LLM в Планировщик MCTS; GoT (Besta et al. 2024), реализующая LLM в большинстве упомянутых ролей для решения задач рассуждений; и SayCan (Ahn et al. 2022), которая использует LLM как вероятностный оценщик релевантности (эвристику).
Определение проблемыГенерацияДействия
Задачи
Начальное состояние
Цель
ПереводДействия
Задачи
Начальное состояние
Цель
Разработка планаПланировщик LLM
Поиск по графуРасширение
Выбор
Извлечение
Откат
Агрегация эвристик
Обрезка
РуководствоПредпочтения
Инициализация
Пост-обработкаПеревод плана
Объяснение плана

Таблица 1: Сводка возможных ролей, которые может выполнять LLM в жизненном цикле HP. Эта классификация детализирована в разделе Роль в Процессе Планирования.

  • Руководство Планированием. Здесь LLM внешняя по отношению к планировщику, но помогает ему, предоставляя помощь. Это руководство может быть начальным планом, который планировщик может уточнить (Valmeekam et al. 2023), или предпочтениями окружения для сужения пространства поиска (Sharan et al. 2023).

Пост-Обработка После разработки плана LLM может использоваться для его уточнения путем Перевода плана в другую структуру данных или язык, обычно в исполняемый формат (например, для робота, чтобы запустить его) или естественный язык (Liu et al. 2023). Или Объяснения Плана, где LLM должна генерировать более детальную информацию, обычно на естественном языке, на основе предоставленного плана (Simon and Muise 2022).

Стратегии Улучшения LLM

При выполнении любой задачи с использованием LLM ее можно напрямую выполнить для получения вывода. Однако их результаты часто субоптимальны. Чтобы решить это, существуют некоторые стратегии для повышения производительности LLM, которые использовались в нескольких областях, связанных с рассуждениями, таких как математика, ответы на вопросы или AP. Опираясь на эту основу, мы идентифицировали стратегии, обычно используемые в AP, и расширили их на конкретный случай HP. В этом разделе мы предлагаем классификацию стратегий, которые могут быть использованы в HP для улучшения производительности LLM, независимо от роли, для которой они используются.

Производительность LLM может быть повышена либо путем предоставления большего знания о проблеме, либо увеличением числа вызовов LLM, используемых во время решения проблемы. Каждый из этих подходов также категоризирован на отличительные стратегии. Эта классификация детализирована в следующих подразделах и суммирована в Таблице 2. Обратите внимание, что эти стратегии ни обязательны, ни взаимоисключающи, что означает, что возможно использовать ни одну, некоторые или все из них одновременно.

Улучшение Знания Мы можем разделить стратегии улучшения знания LLM на две основные перспективы: с предыдущим знанием (предоставление дополнительной информации, релевантной проблеме, перед началом ее решения) или через обратную связь (модель итеративно предоставляется дополнительная информация на основе ее предыдущих выводов, во время решения задачи). Обе перспективы, кроме того, могут иметь разные подходы в зависимости от места, где применяется знание:

  • Предыдущее. Этот подход включает предоставление дополнительной информации LLM перед ее выполнением. Тонкая настройка — это традиционный метод в области глубокого обучения, который включает корректировку внутренних весов модели с дополнительными данными (Pallagani et al. 2022). Альтернативно, знание может быть напрямую предоставлено через промпт модели, что является более гибким и доступным вариантом, чем тонкая настройка, поскольку не требует процесса обучения. Предоставление дополнительной информации достигается через примеры ввода-вывода (shots), которые улучшают сгенерированные ответы (Song et al. 2023). Если shots предоставляют полезную информацию об окружении (например, информацию о домене), это называется in-context prompting; если они предназначены только для вызова конкретной структуры вывода, это называется out-of-context prompting. Кроме того, мы можем также предоставить знание о том, как рассуждать, о самой проблеме. Chain of Thoughts (CoT) (Wei et al. 2022) — лучший пример этого, другая стратегия промптинга, которая побуждает LLM генерировать процесс рассуждений перед предоставлением окончательного ответа. Это обычно достигается с использованием few-shot prompting с примерами рассуждений, хотя рассуждения могут также вызываться без примеров, известных как Zero-shot CoT (Kojima et al. 2022).
  • Обратная связь. В отличие от предыдущей парадигмы, здесь дополнительная информация предоставляется во время процесса решения задачи: вместо простого принятия вывода выполнения LLM мы можем итеративно улучшать результат LLM, предоставляя ей обратную связь на основе ее предыдущих выводов. Эта обратная связь может поступать из различных источников (люди, окружение, внешний модуль, другая LLM и т.д.). Усиленное Обучение — это классический метод обучения на основе обратной связи в машинном обучении, где знание применяется путем модификации внутренних весов модели на основе оценки вознаграждения (Yao et al. 2020). Альтернативно, обратная связь может использоваться для динамической корректировки и улучшения промпта (Коррекция Промпта), где заметные примеры в литературе - Self-Refine (Madaan et al. 2024) и Reflexion (Shinn et al. 2024). Наконец, обучение модели может также представляться через внешний Модуль Памяти, причем Voyager — заметная архитектура, использующая этот подход (Wang et al. 2023).
ЗнаниеПредыдущееТонкая настройка
Промптинг
Цепочка Мыслей
Обратная связьУсиленное обучение
Коррекция промпта
Память
Множественные вызовыДекомпозицияПоследовательные вызовы
Параллельные вызовы
РевизияПоследовательные вызовы
Параллельные вызовы

Таблица 2: Сводка возможных стратегий, которые могут быть использованы для улучшения производительности LLM в жизненном цикле HP, независимо от конкретной роли. Эта классификация детализирована в разделе Стратегии Улучшения LLM.

Несколько Вызовов Чтобы улучшить производительность LLM через несколько вызовов, существуют две основные перспективы: проблема может быть разделена на более простые подзадачи, которые LLM решает на каждом вызове (Декомпозиция); или LLM решает всю проблему несколько раз, и мы используем преимущество разнообразной информации, сгенерированной несколькими выводами (Ревизия). Обе перспективы также могут решаться через два разных подхода, в зависимости от того, используется ли вывод для следующего вызова или нет (Последовательные или Параллельные вызовы).

  • Декомпозиция. Проблема может быть последовательно декомпозирована: вывод каждого вызова LLM генерирует промежуточный шаг, который используется для ввода следующего вызова. Например, для генерации плана мы могли бы итеративно просить LLM генерировать только следующее действие частичного плана, вместо попытки сгенерировать весь план в одном вызове (Huang et al. 2022). В противном случае проблема может быть декомпозирована параллельно: каждый вызов LLM может возвращать список более простых подзадач, которые могут решаться независимо (т.е. классическая стратегия Divide and Conquer). Это иллюстративно используется в Generative Agents (Park et al. 2023).
  • Ревизия. Мы можем выполнять несколько вызовов для последовательного уточнения вывода LLM: мы просим LLM первоначально дать нам полный, но простой (общий) решение, которое итеративно становится более детализированным через вызовы (Liu et al. 2024). В противном случае мы можем выполнять параллельный подход, спрашивая LLM полностью решить проблему несколько раз и затем объединяя разные результаты в окончательный вывод. Self-consistency (Wang et al. 2022) — заметный подход, который объединяет несколько выводов, выбирая наиболее распространенный ответ, но могут использоваться различные критерии для выбора окончательного вывода.

Бенчмарк

Иерархические Сети Задач (HTN) Планирование (Nau et al. 2003) — это наиболее широко используемый и изученный подход в поле HP, что делает его подходящей точкой отсчета для экспериментов с различными методами интеграции LLM и их оценки. Мы предлагаем использовать трек total-order из IPC-2023, который содержит 22 домена, каждый с десятками проблем. Детальный разбор этой информации, наряду с суммой экспериментальных результатов, предоставлен в Таблице 3.

Чтобы оценить и сравнить производительность будущих реализаций, мы устанавливаем две точки отсчета. Во-первых, мы рассматриваем победителя трека Total-Order Satisficing IPC-2023, PandaDealer-agile-lama (Olz, Höller, and Bercher 2023) как верхнюю границу, поскольку он представляет текущее состояние искусства в решателях HP. Во-вторых, мы включаем в качестве базовой линии базовый Планировщик LLM (т.е. использование LLM напрямую для планирования без предоставления какой-либо Стратегии Улучшения LLM), представляющий нижнюю границу для Интеграции LLM. Этот подход, будучи самым простым методом в нашей таксономии, служит фундаментальной точкой сравнения и отправной точкой для дорожной карты.

Соображения по Выполнению и Экспериментированию

Оценка PandaDealer в наборе данных взята из опубликованных результатов IPC-2023. Эта оценка представляет соотношение C∗/C между стоимостью эталонного плана (C∗) и лучшим полученным планом (C). Из-за недоступности этих эталонных планов мы не смогли вычислить ту же оценку для Планировщика LLM. Тем не менее, эта оценка служит надежной ссылкой для оценки качества производительности PandaDealer. Для генеративных планов, однако, нужно оценивать дополнительные свойства, такие как семантическая coherentность в плане (которая не нуждается в измерении в символьных планировщиках). Чтобы решить это, мы приняли альтернативные метрики, более подходящие для анализа качества генеративных планов: Физибилити Плана (план синтаксически правильный), Корректность Плана (он исполняемый и достигает состояния цели), Физибилити Декомпозиции (иерархическая декомпозиция плана синтаксически правильная) и Корректность Декомпозиции (декомпозиция соответствует сгенерированному плану).

Мы используем Llama-3.1-Nemotron-70B-Instruct, одну из самых высокопроизводительных доступных LLM (Wang et al. 2024), в качестве Планировщика LLM. Мы используем официальный верификатор IPC для оценки сгенерированных планов по различным предложенным метрикам. Исходные коды выполнения и валидации, а также сгенерированные планы и полученные результаты размещены на GitHub. URL: https://github.com/Corkiray/HTN-LLM.

Обсуждение Результатов

В этой предварительной работе мы получили результаты для 15 из 23 доменов в наборе данных, не полный набор, из-за временных и вычислительных ограничений. Тем не менее, эти результаты достаточны, чтобы иллюстрировать notably низкую производительность Планировщика LLM, которая ожидаема, учитывая простоту метода и отсутствие каких-либо Стратегий Улучшения LLM. Как показано в Таблице 3, Планировщик LLM не может генерировать физибильные планы в почти 70% проблем, подчеркивая ограниченную способность LLM интерпретировать и придерживаться конкретного формата. Еще более замечательна доля правильных планов: с только 4% (т.е. 13% от физибильных планов), это показывает трудность, с которой сталкивается базовый LLM в правильном планировании. Аналогичная тенденция наблюдается в числе физибильных декомпозиций, которые с только 3% правильными указывают на значительное падение производительности при обработке конкретного формата с увеличением сложности. Интересно, что правильные планы и физибильные декомпозиции часто disjoint (т.е. LLM достигает либо одного результата, либо другого, но не обоих). Следовательно, LLM не смогла произвести правильную иерархическую декомпозицию ни для одной проблемы. Это наблюдение объяснимо, учитывая inherent архитектуру LLM как трансформера, который работает в статической вычислительной мощности. LLM не может динамически корректировать время обработки на основе сложности проблемы, и в результате ее способность одновременно решать несколько demanding требований (т.е. корректность плана и физибилити декомпозиции) ограничена.

ДоменNОценкаFPCPFDCD
Assembly300.8915300
Barman200.784100
Blocks300.779010
Depots300.904000
Factories200.676000
Freecell600.13381800
Hiking300.830000
lamps300.485110
Logistics800.9814110
Multiarm740.9530020
Robot200.9213150
Satellite200.9211020
Towers200.655000
Transport400.7310040
Woodwork300.6926000
Итого61414.4219025160
Среднее:0.800.310.040.030

Таблица 3: Сводка информации, предоставленной бенчмарком, с указанием количества задач в каждом домене набора данных и производительности, сообщаемой каждым планировщиком. Оценка PandaDealer — это та, что предоставлена результатами IPC-2023. Оценки, используемые для Планировщика LLM, объяснены в разделе Бенчмарк, представляя количество физибильных планов (FP), правильных планов (CP), физибильных декомпозиций (FD) и правильных декомпозиций (CD).

Заключение

В этой работе мы предлагаем дорожную карту для руководства будущими исследованиями в интеграции LLMs и HP, поскольку это остается в значительной степени неисследованным полем. Эта дорожная карта центрирована на двух ключевых вкладах: таксономии и бенчмарке. Таксономия категоризирует основные методы интеграции, структурированные по двум измерениям: первое учитывает различные роли, которые LLM может выполнять в жизненном цикле HP. Второе фокусируется на стратегиях повышения производительности LLM, независимо от конкретной роли, в которой они применяются. Бенчмарк вводит набор данных и предоставляет начальные результаты, которые служат ссылкой в последующих экспериментах. Эти результаты включают производительность современного решателя HP и Планировщика LLM с использованием одной из самых высокопроизводительных доступных LLM, но без использования какой-либо стратегии улучшения. Как и ожидалось, результаты раскрывают ограниченную производительность LLM в решении проблем HP, но они устанавливают базовую линию для оценки последующих улучшений. Многообещающие будущие направления включают исследование возможностей планирования Планировщика LLM, augmented с Стратегиями Улучшения, чтобы преодолеть ограничения, идентифицированные в этом исследовании. Кроме того, исследование интеграции в дополнительные аспекты жизненного цикла HP, такие как Мониторинг Плана или Управление Исключениями, полезно для расширения границ предложенной таксономии. Наконец, разработка новых архитектур в рамках очерченных Ролей Процесса Планирования предлагает путь для систематического исследования и продвижения этого неисследованного поля.

Ссылки