Планирование в искусственном интеллекте
Материал из MachineLearning.
| Статья написана с использованием LLM GPT-5.5 и проверена участником Arsenii Kolesnikov 11:43, 16 июля 2026 (MSD) |
Планирование в искусственном интеллекте — область искусственного интеллекта, изучающая построение последовательностей действий, переводящих систему из начального состояния в состояние, удовлетворяющее цели. В отличие от бытового календарного планирования, автоматическое планирование формализует действия, предусловия, эффекты, ограничения и критерии качества плана.
Планирование тесно связано с поиском, эвристическим поиском, комбинаторной оптимизацией, робототехникой и обучением с подкреплением. Классические методы предполагают известную дискретную модель мира, современные методы часто работают с неопределённостью, непрерывными состояниями и обучаемыми моделями среды.
Содержание |
Формальная постановка
Детерминированную задачу планирования можно задать пятёркой
где — множество состояний,
— множество действий,
— функция перехода,
— начальное состояние,
— множество целевых состояний.
План — последовательность действий
такая, что последовательное применение действий из приводит в состояние
. Если у действий есть стоимость
, задача может требовать минимизации суммарной стоимости:
Представление STRIPS
В STRIPS состояние описывается множеством истинных предикатов. Действие имеет:
- предусловия;
- список добавляемых фактов;
- список удаляемых фактов.
Действие применимо, если все его предусловия истинны. После применения добавляемые факты включаются в состояние, удаляемые исключаются. Такая модель проста, но позволяет формализовать широкий класс дискретных задач[1].
Поиск в пространстве состояний
Прямой поиск строит дерево состояний от к цели. Обратный поиск идёт от описания цели к состояниям, из которых цель достижима. Наивный поиск быстро сталкивается с комбинаторным взрывом, поэтому используются эвристики, оценивающие расстояние до цели.
Эвристическое планирование применяет функции , приближённо оценивающие стоимость достижения цели из состояния
. Часто эвристики строятся по релаксации задачи: например, игнорируются удаляющие эффекты действий.
Поиск в пространстве планов
План можно строить не только как путь по состояниям, но и как частичный порядок действий. В частично-упорядоченном планировании сначала задаются подцели и причинные связи, а порядок действий уточняется только при необходимости. Это уменьшает преждевременные ограничения и позволяет компактно описывать независимые действия.
Иерархическое планирование
В HTN-планировании задачи раскладываются на подзадачи. Высокоуровневое действие «организовать эксперимент» может разлагаться на «подготовить данные», «обучить модель», «проверить качество», «сохранить результат». HTN-подход удобен, когда экспертные знания о допустимых процедурах важнее полного перебора всех возможных действий[1].
SAT-планирование
SAT-планирование сводит существование плана длины к задаче выполнимости булевой формулы. Переменные кодируют факты и действия на каждом временном слое, ограничения кодируют динамику. Если формула выполнима, её модель задаёт план. Метод эффективен благодаря развитию SAT-решателей.
Планирование при неопределённости
Если действия стохастичны, задача сближается с марковскими процессами принятия решений. Если состояние частично наблюдаемо, используется POMDP. В этом случае план или политика должны учитывать не одно состояние, а распределение убеждений. Целью становится максимизация ожидаемой полезности, а не просто достижение конечного состояния.
Связь с RL и LLM-агентами
В обучении с подкреплением агент часто не имеет готовой модели переходов и должен учиться по взаимодействию со средой. Планирование применяется, когда модель известна или выучена: агент может моделировать будущие траектории и выбирать действие с лучшей ожидаемой ценностью.
В LLM-агентах термин «планирование» часто обозначает разбиение сложной инструкции на шаги. Это полезная инженерная эвристика, но строгим автоматическим планированием она становится только при наличии формальной модели действий, условий применимости, эффектов и механизма проверки плана.
Ограничения
- Пространство состояний растёт экспоненциально.
- Полная модель действий редко известна в реальных средах.
- Непрерывные переменные и физическая динамика требуют специальных методов.
- План, найденный в абстрактной модели, может оказаться невыполнимым в реальном мире.
