Проблема экспоненциального роста памяти
Классические эвристические алгоритмы поиска плана (heuristic search) часто требуют хранения экспоненциального количества состояний, даже при наличии почти идеальной эвристики. Это создает узкое место в памяти для сложных задач автоматизированного планирования. Авторы работы — Доминик Дрекслер, Симон Стёльберг, Маркус Фрицше и Блай Бонет — предлагают альтернативу: обучение управляющей логики поиска (search control) с использованием индексационных политик (indexical policies).
Механика индексационных политик
Вместо перебора состояний метод использует обобщенную политику с регистрами, хранящими объекты, и режимами, упорядочивающими правила. Ключевым нововведением является правило choose (выбор), которое загружает объект в регистр и устанавливает точку бэктрекинга. В этой точке достаточно одного кандидата, тогда как все остальные правила должны работать для всех возможных исходов без дополнительного поиска. Это позволяет избежать хранения списка посещенных состояний.
Теоретические гарантии: от NP к P
Главный результат исследования — доказательство того, что структурная терминация (отсутствие бесконечных циклов) ограничивает выполнение полиномом от числа объектов. Глубинный поиск (depth-first) находит план в полиномиальном пространстве, независимо от размера пространства состояний. Временная сложность становится экспоненциальной только от глубины выбора (числа реальных решений вдоль выполнения). Таким образом, любой класс, решаемый такой политикой, лежит в NP, а при постоянной глубине выбора — в P.
Обучение через LLM и верификацию
Политики обучаются с помощью языковой модели в цикле, управляемом контрпримерами (counterexample-guided loop). Система автоматически верифицирует терминацию, проверяет обучающие задачи и поддерживает малую глубину выбора. Это обеспечивает надежность и эффективность метода на практике.
Результаты на бенчмарках IPC 2023
Метод демонстрирует выдающиеся результаты, решая 1709 из 1890 тестовых задач трека обучения IPC 2023 и набора Autoscale Agile. Большинство задач решаются менее чем за 1 секунду и потребляют до 100 МБ памяти. Ниже приведено сравнение эффективности с существующими лидерами.
| Метод | Решенные задачи (IPC 2023 Learning Track) | Потребление памяти | Время решения |
|---|---|---|---|
| Предложенный метод (LLM Policy) | 1709 / 1890 | ~100 MiB | Большинство < 1 сек |
| Меньше 1709 | Значительно выше | Выше | |
| BFWS | Меньше 1709 | Значительно выше | Выше |
| Levitron | Меньше 1709 | Значительно выше | Выше |
Работа опубликована 7 октября 2026 года в arXiv (cs.AI) и открывает путь к созданию планировщиков, способных работать с огромными пространствами состояний без ограничений по памяти.
Источник: arXiv cs.AI ↗