Введение

Отрасль искусственного интеллекта

Автоматизированное планирование и составление расписаний, иногда обозначаемое просто как планирование в ИИ, является отраслью искусственного интеллекта, занимающейся реализацией стратегий или последовательностей действий, как правило, для выполнения интеллектуальными агентами, автономными роботами и беспилотными летательными аппаратами. В отличие от классических задач управления и классификации, решения здесь сложны и должны быть найдены и оптимизированы в многомерном пространстве. Планирование также связано с теорией принятия решений. В известных средах, где доступны модели, планирование может выполняться в автономном режиме, позволяя находить и оценивать решения до их реализации. В динамически изменяющихся и неизвестных средах стратегия часто требует пересмотра в режиме реального времени, а модели и политики должны быть адаптированы. Решения обычно основаны на итеративных процессах проб и ошибок, часто встречающихся в искусственном интеллекте, таких как динамическое программирование, обучение с подкреплением и комбинаторная оптимизация. Языки, используемые для описания планирования и составления расписаний, часто называют языками действий.

Независимое от домена планирование

В планировании с использованием ИИ, планировщики обычно принимают на вход модель домена (описание набора возможных действий, моделирующих предметную область) и конкретную задачу, определяемую начальным состоянием и целью, в отличие от планировщиков, которым не задается входной домен. Такие планировщики называются "независимыми от домена", чтобы подчеркнуть их способность решать задачи планирования в самых разных областях. Типичными примерами доменов являются задачи по складированию блоков, логистика, управление рабочими процессами и планирование задач для роботов. Таким образом, один планировщик, независимый от домена, может быть использован для решения задач планирования во всех этих различных областях. С другой стороны, планировщик маршрутов является типичным примером планировщика, ориентированного на конкретную область.

Языки моделирования области планирования

Наиболее часто используемые языки для представления областей планирования и конкретных задач планирования, такие как STRIPS и PDDL для классического планирования, основаны на переменных состояния. Каждое возможное состояние мира представляет собой набор значений переменных состояния, а действия определяют, как эти значения изменяются при выполнении действия. Поскольку набор переменных состояния определяет пространство состояний, размер которого растет экспоненциально с увеличением набора, планирование, как и многие другие вычислительные задачи, подвержено проклятию размерности и комбинаторному взрыву. Альтернативным способом описания задач планирования является использование иерархических сетей задач, в которых задается набор задач, и каждая задача может быть либо выполнена примитивным действием, либо разложена на набор других задач. Это не обязательно требует использования переменных состояния, хотя в более реалистичных приложениях переменные состояния упрощают описание сетей задач.

Снижение до других проблем

редукция к задаче выполнимости булевых формул (SATplan). Редукция к проверке моделей – обе задачи по сути являются задачами обхода пространства состояний, а классическая задача планирования соответствует подклассу задач проверки моделей.

Временное планирование

Временное планирование может быть решено методами, аналогичными классическому планированию. Основное отличие заключается в том, что из-за возможности одновременного выполнения нескольких действий с временным перекрытием и ненулевой длительностью, определение состояния должно включать информацию о текущем абсолютном времени и прогрессе выполнения каждого активного действия. Более того, при планировании с рациональным или действительным временем пространство состояний может быть бесконечным, в отличие от классического планирования или планирования с дискретным временем. Временное планирование тесно связано с задачами планирования, когда присутствует неопределенность, и может также рассматриваться с точки зрения временных автоматов. Простая временная сеть с неопределенностью (STNU) – это задача планирования, включающая управляемые действия, неопределенные события и временные ограничения. Динамическая управляемость для таких задач – это тип планирования, требующий стратегии временного планирования для реактивного запуска управляемых действий при наблюдении неопределенных событий, чтобы гарантировать выполнение всех ограничений.

Вероятностное планирование

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

План, основанный на предпочтениях

При планировании на основе предпочтений целью является не только создание плана, но и удовлетворение предпочтений, заданных пользователем. В отличие от более распространенного планирования, основанного на вознаграждении, например, как в случае с MDP, предпочтения не обязательно выражаются точными числовыми значениями.

Условный план

Детерминированное планирование было введено вместе с системой планирования STRIPS, являющейся иерархическим планировщиком. Названия действий упорядочены в последовательность, и эта последовательность представляет собой план для робота. Иерархическое планирование можно сравнить с автоматически генерируемым деревом поведения. Недостатком является то, что обычное дерево поведения менее выразительно, чем компьютерная программа. Это означает, что представление поведенческого графа содержит команды действий, но не включает циклы или операторы "если-то". Условное планирование преодолевает это ограничение и вводит более сложную нотацию, аналогичную управлению потоком выполнения, известному из других языков программирования, таких как Паскаль. Это очень похоже на синтез программ, то есть планировщик генерирует исходный код, который может быть выполнен интерпретатором. Ранним примером условного планировщика является “Warplan C”, представленный в середине 1970-х годов. В чем разница между обычной последовательностью действий и сложным планом, содержащим операторы "если-то"? Это связано с неопределенностью во время выполнения плана. Идея заключается в том, что план может реагировать на сигналы датчиков, которые неизвестны планировщику на этапе планирования. Планировщик заранее генерирует два возможных варианта действий. Например, если объект обнаружен, выполняется действие А, если объект отсутствует – выполняется действие В. Важным преимуществом условного планирования является возможность работы с частичными планами. Агент не обязан планировать все действия от начала до конца, а может разделить проблему на отдельные части. Это помогает уменьшить пространство состояний и решать более сложные задачи.

Планирование действий в чрезвычайных ситуациях

Мы говорим о "контингентном планировании", когда окружающая среда наблюдается через датчики, которые могут быть неисправны. Таким образом, это ситуация, когда агент планирования действует при неполной информации. Для задачи контингентного планирования план больше не является последовательностью действий, а деревом решений, поскольку каждый шаг плана представлен набором состояний, а не единственным полностью наблюдаемым состоянием, как в случае классического планирования. Выбранные действия зависят от состояния системы. Например, если идет дождь, агент выбирает взять зонт, а если дождя нет, то может обойтись без него. Майкл Л. Литтман в 1998 году показал, что при наличии разветвленных действий задача планирования становится NP-полной по времени (EXPTIME-полной). Частным случаем контингентного планирования являются задачи FOND – "полностью наблюдаемые и недетерминированные". Если цель задана в LTLf (линейная временная логика на конечном следе), то задача всегда EXPTIME-полна, а если цель задана с помощью LDLf, то она становится 2EXPTIME-полной.

Соответствующее планирование

Конформистское планирование — это ситуация, когда агент не знает точно текущее состояние системы и не имеет возможности проводить наблюдения. Агент формирует предположения о реальном мире, но не может подтвердить их, например, с помощью сенсорных действий. Эти задачи решаются методами, схожими с методами классического планирования, однако пространство состояний растет экспоненциально с увеличением размера задачи из-за неопределенности в отношении текущего состояния. Решением задачи конформистского планирования является последовательность действий. Хаслум и Йонссон показали, что задача конформистского планирования является EXPSPACE-полной, а при неопределенности начальной ситуации и недетерминированности исходов действий — 2EXPTIME-полной.

Развертывание систем планирования

Космический телескоп Хаббл использует систему краткосрочного планирования под названием SPSS и систему долгосрочного планирования под названием Spike.