Автоматизированное планирование и составление графиков

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

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

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

Обзор [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

Планирование, не зависящее от домена [ править ]

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

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

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

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

Алгоритмы планирования [ править ]

Классическая планировка [ править ]

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

Сведение к другим проблемам [ править ]

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

Временное планирование [ править ]

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

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

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

Планирование на основе предпочтений [ править ]

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

Условное планирование [ править ]

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

Ранним примером условного планировщика является «Warplan-C», который был представлен в середине 1970-х годов. ^{[4] В} чем разница между нормальной последовательностью и сложным планом, который содержит «если-то-утверждения»? Это связано с неопределенностью во время выполнения плана. Идея состоит в том, что план может реагировать на сигналы датчиков, которые неизвестны планировщику. Планировщик заранее создает два варианта. Например, если объект был обнаружен, то выполняется действие A, если объект отсутствует, то выполняется действие B. ^[5] Основным преимуществом условного планирования является возможность работать с частичными планами . ^[6]Агент не обязан планировать все от начала до конца , но может разделить проблему на куски . Это помогает уменьшить пространство состояний и решает гораздо более сложные проблемы.

Непредвиденное планирование [ править ]

Мы говорим о «непредвиденном планировании», когда за окружающей средой можно наблюдать с помощью датчиков, которые могут быть неисправными. Таким образом, возникает ситуация, когда агент планирования действует в условиях неполной информации. Для задачи условного планирования план больше не является последовательностью действий, а деревом решений, потому что каждый шаг плана представлен набором состояний, а не одним совершенно наблюдаемым состоянием, как в случае классического планирования. ^[7] Выбранные действия зависят от состояния системы. Например, если идет дождь, агент решает взять зонт, а если нет, он может его не брать.

Майкл Л. Литтман показал в 1998 году, что с ветвлением действий задача планирования становится EXPTIME- полной. ^{[8] [9]} Частный случай непрерывного планирования представлен проблемами FOND - для «полностью наблюдаемых и недетерминированных». Если цель указана в LTLf (логика линейного времени на конечной трассе), тогда проблема всегда будет завершена EXPTIME ^[10] и 2EXPTIME-завершена, если цель указана с помощью LDLf.

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

Конформное планирование - это когда агент не уверен в состоянии системы и не может делать никаких наблюдений. Тогда агент имеет представления о реальном мире, но не может проверить их, например, с помощью сенсорных действий. Эти проблемы решаются методами, аналогичными методам классического планирования ^{[11] [12],} но где пространство состояний экспоненциально зависит от размера проблемы из-за неопределенности текущего состояния. Решение проблемы согласованного планирования - это последовательность действий. Хаслум и Йонссон продемонстрировали, что проблема согласованного планирования является EXPSPACE -полной , ^[13] и 2EXPTIME-полной, когда исходная ситуация неопределенная, и есть недетерминизм в результатах действий. ^[9]

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

• Космический телескоп Хаббл использует краткосрочную систему под названием SPSS и долгосрочная система планирования под названием Spike ^{[ править ]} .

См. Также [ править ]

• Язык описания действия
• Актерская модель
• Приложения искусственного интеллекта
• Проблема удовлетворения ограничений
• Реактивное планирование
• Планирование (вычисления)
• Стратегия (теория игр)

Списки

• Список решателей SMT
• Список языков программирования ограничений
• Список новых технологий
• Схема искусственного интеллекта

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Влахавас, И. "Планирование и составление графиков" . EETN . Архивировано из оригинала на 2013-12-22.

Внешние ссылки [ править ]

• Международная конференция по автоматизированному планированию и календарному планированию