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

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

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

Трудность планирования зависит от упрощающих допущений. Можно определить несколько классов проблем планирования в зависимости от свойств, которые имеют проблемы в нескольких измерениях.

Являются ли действия детерминированными или недетерминированными? Для недетерминированных действий доступны связанные вероятности?
Являются ли переменные состояния дискретными или непрерывными? Если они дискретны, они имеют только конечное число возможных значений?
Можно ли однозначно наблюдать текущее состояние? Может быть полная наблюдаемость и частичная наблюдаемость.
Сколько начальных состояний существует, конечно или сколь угодно много?
У действий есть продолжительность?
Можно ли одновременно предпринять несколько действий или только одно действие одновременно?
Является ли цель плана достигать определенного целевого состояния или максимизировать функцию вознаграждения?
Есть ли только один агент или есть несколько агентов? Являются ли агенты совместными или эгоистичными? Разве все агенты строят свои собственные планы отдельно или планы, построенные централизованно для всех агентов?

Простейшая возможная проблема планирования, известная как проблема классического планирования, определяется:

уникальное начальное состояние,
длительные действия,
детерминированные действия,
которые могут быть приняты только по одному,
и один агент.

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

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

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

Дискретные марковские процессы принятия решений (MDP) планируют проблемы с:

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

Когда полная наблюдаемость заменяется частичной наблюдаемостью, планирование соответствует частично наблюдаемому марковскому процессу принятия решений (POMDP).

Если есть более одного агента, у нас есть многоагентное планирование, которое тесно связано с теорией игр.

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

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

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

Алгоритмы планирования
Классическое планирование
поиск пробела в пространстве цепочки, возможно, с эвристикой
поиск обратной цепочки, возможно, усиленный использованием ограничений состояния (см. STRIPS, graphplan)
планирование частичного заказа

Классическое планирование
Традиционное планирование основано на двух предположениях:

детерминизм действий. Например, действие «положить куб на таблицу» является детерминированным. Выполняя его, мы переходим из одного состояния в другое. Напротив, «бросить кубик» не является детерминированным, потому что возможны возможные значения. Действие «бросить кубик» не входит в рамки традиционного планирования.
идеальное наблюдение. Агент (робот, программа и т. Д.) Полностью знает состояние мира.

n классическое планирование, речь идет о поиске последовательности действий (например, «взять кастрюлю», «положить воду», «положить макароны», «зажечь огонь», «дотянуться», «потушить Пожар»). Алгоритм A * является типичным примером классического алгоритма планирования, часто используемого во вводных курсах для его простоты. Вот некоторые алгоритмические методы, используемые в классических планировщиках:

прямой поиск в пространстве состояний: алгоритм эвристического планирования поиска (HSP), алгоритм Fast-Forward (FF),
обратный поиск в пространстве состояний,
поиск прежде в пространстве планов, graphplan
релаксация проблемы планирования: вычисление расслабленной проблемы, для которой легче узнать, есть ли план, который помогает решить начальную проблему
превращение в задачу выполнимости формулы пропозициональной логики.

В 1994 году Биландер продемонстрировал, что обычное планирование PSPACE завершено.

Сокращение других проблем
к проблеме пропозициональной выполнимости (satplan).
переход к проверке модели — оба являются по существу проблемами пересечения пространств состояний, а классическая задача планирования соответствует подклассу проблем проверки модели.

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

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

Предпочитаемое планирование
При планировании на основе предпочтений цель заключается не только в создании плана, но и в соответствии с пользовательскими предпочтениями. Разница в более общем вознаграждении, основанном на вознаграждении, например, соответствующем МДП, предпочтения не обязательно имеют точное числовое значение.

Условное планирование
Детерминированное планирование было введено с помощью системы планирования STRIPS, которая является иерархическим планировщиком. Имена действий упорядочены в последовательности, и это план для робота. Иерархическое планирование можно сравнить с автоматически созданным деревом поведения. Недостатком является то, что дерево нормального поведения не так выразительно, как компьютерная программа. Это означает, что в графике поведения содержатся команды действий, но нет циклов или if-then-statements. Условное планирование преодолевает узкое место и вводит продуманную нотацию, аналогичную потоку управления, известную из других языков программирования, таких как Pascal. Это очень похоже на синтез программы, что означает, что планировщик генерирует исходный код, который может быть выполнен интерпретатором.

Ранним примером условного планировщика является «Warplan-C», который был представлен в середине 1970-х годов. До сих пор на вопрос не было ответа, какая разница между нормальной последовательностью и сложным планом, который содержит if-then-statements. Это связано с неопределенностью во время выполнения плана. Идея состоит в том, что план может реагировать на сигналы датчиков, которые неизвестны планировщику. Планировщик заранее генерирует два варианта. Например, если объект был обнаружен, выполняется действие A, если объект отсутствует, тогда выполняется действие B. Основным преимуществом условного планирования является способность обрабатывать частичные планы. Агент не вынужден планировать все от начала до конца, но может разделить проблему на куски. Это помогает уменьшить пространство состояний и решает гораздо более сложные проблемы.

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

Другие виды планирования
На практике он только проверяет редко предположения о классическом планировании. Вот почему многие расширения появились.

Соответствие планированию
Мы говорим о согласованном планировании (соответствующем графике), где система находится в неопределенном состоянии, но наблюдение невозможно. У агента тогда есть убеждения о реальном мире. Эти проблемы решаются методами, аналогичными методам традиционного планирования, но где пространство состояний экспоненциально зависит от размера проблемы из-за неопределенности относительно текущего состояния. Решение проблемы соответствия графика — последовательность действий.

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

В 2004 году Ринтанен продемонстрировал, что если добавление ветвления (условное планирование), проблема планирования становится EXPTIME-полной. Частный случай непрерывного планирования представлен проблемами FOND — для «полностью наблюдаемых и недетерминированных». Если цель указана в LTLf (линейная временная логика по конечной трассе), тогда проблема всегда EXPTIME-complete 16 и 2EXPTIME-complete для спецификации цели в LDLf.

Если, кроме того, добавляется неопределенность в традиционное планирование (то есть совместимое планирование), оно становится EXPSPACE-полным. Если мы добавим как ветвление, так и неопределенность (планирование как совместимого, так и условного), оно станет 2EXPTIME-полным.

Вероятностное планирование
Kushmerick et al. введено вероятностное планирование. В их работе эффект действий описывается вероятностными. Он приводит пример действия «робот берет блок», описанный следующим образом: если захват робота сух, то робот держит блок с вероятностью 0,95; если зажим влажный, то робот удерживает блок с вероятностью 0,5.

Это приводит к проблеме формирования (или стратегии) ​​политики для Марковского процесса принятия решений (MDP) или (в общем случае) частично наблюдаемого Марковского процесса принятия решений (POMDP).

Нелинейное планирование
Классическое планирование разрешает субатлеты в заданном порядке. Проблема в том, что иногда это приводит к уничтожению уже построенного. Это явление известно как аномалия Суссмана.

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

Чтобы решить эту проблему, можно перейти к частично упорядоченным планам, в которых порядок между действиями фиксируется только тогда, когда это необходимо (обязательство при последнем или минимальном планировании обязательств).

В предыдущем примере положить левый ботинок нужно, поместив носок влево. То же самое для права. С другой стороны, выполнение плана слева не зависит от исполнения для права. Таким образом, общий план частично упорядочен.

Планировщики, способные справиться с этой категорией проблемы, называются частичным порядком (POP, NOAH и т. Д.).

Иерархическое планирование
Как правило, при планировании можно иметь иерархическую информацию о действиях, то есть описание того, как сложные действия разлагаются. Например, сложное действие, такое как «подача кофе», можно разбить на последовательность двух сложных действий «приготовление кофе», а затем «приносить кофе». Таким образом, есть планировщики, такие как ABSTRIPS, которые в дополнение к описанию действий принимают в качестве входных данных иерархическое описание действий. Например, можно начинать планировать на высоком уровне, а затем, при необходимости, опускаться в деталях (как, например, ABSTRIPS). Затем цель описывается с использованием иерархической сети задач (HTN).

Временное планирование
Планирование времени позволяет вам выражать время действия, условия в начале, конце и во время действия, а также эффекты в начале и в конце действий. PDDL 2.1 включает планирование времени. Метод TLP-GP 1 создает граф, а затем решает временные ограничения с помощью решателя SMT. Одна обратная связь в случае несогласованности. Rintanen продемонстрировал, что параллельное планирование времени (возможно несколько экземпляров одного и того же параллельного действия) завершено EXPSPACE. С другой стороны, если мы расслабляем эти условия, мы можем свести себя к традиционному планированию, и поэтому временное планирование с этими ограничениями станет полным PSPACE.

Общее планирование
Общее планирование состоит из создания плана, который работает для нескольких стартовых сред.

Планирование мультиагента
Многоагентное планирование изучает завершение задачи несколькими агентами, например несколькими роботами. Затем формирование плана и его исполнение часто распределяются / децентрализованы. Важным аспектом планов является сотрудничество между агентами. Существует также централизованный алгоритм планирования, основанный на обобщении STRIPS на мультиагентную структуру, называемую MA-STRIPS. Затем алгоритм распределял рендеринг с использованием решателя CSP, распределенного для управления координацией между агентами. Авторы, Nissim, Brafman и Domshlak экспериментально подтвердили, что их алгоритм лучше, чем централизованное планирование, когда агенты мало взаимодействуют друг с другом.

Основной сложностью в мультиагентном планировании является комбинаторный взрыв всех действий, который является экспоненциальным по количеству агентов. В 2011 году Jonsson и Rovatsos предлагают решение для противодействия этой проблеме, сводятся к классическому одноагентному планированию. Существуют также методы параллелизации параллельного использования для планирования алгоритмов масштабирования.

Эпистическое планирование
Задачей эпистемического планирования является учет знаний агентов в описании состояний и действий. Как правило, целью является формула эпистемической модальной логики, такая как «агент знает, что агент b, что блок C находится на блоке A», и действия представлены моделями действий логической динамической эпистемики. Задача планирования неразрешима во всей ее общности.

Задача :

Выше (A, B) Λ Выше (B, C)
Начальное состояние :

[Выше (A, Таблица) Λ Выше (B, Таблица) Λ Выше (C, A) Λ Блокировка (A) Λ Блокировка (B) Λ Блокировка (C) Λ Раскрытие (B) Λ Раскрытие (C)]
Доступные действия:

Переместить (b, x, y)
ПРЕДВАРИТЕЛЬНЫЕ УСЛОВИЯ: Выше (b, x) Λ Непокрытый (b) Λ Непокрытый (y) Λ Блок (b) Λ Блок (y) Λ (b ≠ x) Λ (b ≠ y) Λ (x ≠ y)
ДОПОЛНИТЕЛЬНО: выше (b, y) Λ обнаружено (x)
АННУЛИРОВАНИЕ: Выше (b, x) Λ Обнаружено (y)
Move_tool (b, x)
ПРЕДПОСЫЛКИ: Выше (b, x) Λ Непокрытый (b) Λ Непокрытый (y) Λ Блок (b) Λ (b ≠ x)
ДОПОЛНИТЕЛЬНО: выше (b, таблица) Λ Обнаружено (x)
АННУЛИРОВАНИЕ: Выше (b, x)

пример

Неофициальный пример планирования.

цель
есть фрукты и овощи в холодильнике

Начальное состояние
[пустой холодильник, дома, в тапочках]

Доступные действия (неупорядоченный список)
выйти домой,
носить обувь,
взять ключи от машины,
добраться до магазина на машине,
дойти пешком до магазина,
возвращайся домой,
размещать покупки в холодильнике,
войдите в магазин,
принимать фрукты,
принимать овощи,
платить.

Возможное решение (упорядоченный список)
[1 — носить обувь, 2 — взять ключи от машины, 3 — выйти из дома, 4 — добраться до магазина на машине, 5 — войти в магазин, 6 — принять фрукты, 7 — взять овощи, 8 — 9 — вернуться в дом, 10-местные покупки в холодильнике]

Другое возможное решение (упорядоченный список):
[1- обувь для ношения, 2 выхода, 3 — пешком до магазина, 4 — посещение магазина, 5 — овощи, 6 — фрукты, 7 — оплата, 8 — возвращение домой, 9-местное приобретение в холодильнике]

Выводы
Из примера видно, как:

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