Автоматизированное планирование и составление графиков - Automated planning and scheduling

Часть серии по
Искусственный интеллект

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

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

Обзор

Дальнейшая информация: Поиск в пространстве состояний

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Классическая планировка

Смотрите также: Аномалия Сассмана

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

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

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

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

Основные статьи: Марковский процесс принятия решений и Частично наблюдаемый марковский процесс принятия решений

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

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

Основная статья: Планирование на основе предпочтений

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

Условное планирование

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

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

Непредвиденное планирование

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

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

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

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

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

Смотрите также

Списки

Рекомендации

  1. ^ Галлаб, Малик; Nau, Dana S .; Траверсо, Паоло (2004), Автоматизированное планирование: теория и практика, Морган Кауфманн, ISBN  1-55860-856-7
  2. ^ Нойфельд, Ксения и Мостагим, Саназ и Санчо-Прадель, Дарио и Бранд, Сэнди (2017). «Создание планировщика: обзор систем планирования, используемых в коммерческих видеоиграх». IEEE Transactions по играм. IEEE.CS1 maint: несколько имен: список авторов (связь)
  3. ^ Санелли, Валерио и Кэшмор, Майкл и Магазинзени, Даниэле и Иокки, Лука (2017). Краткосрочное взаимодействие человека с роботом посредством условного планирования и исполнения. Proc. Международной конференции по автоматизированному планированию и календарному планированию (ICAPS).CS1 maint: несколько имен: список авторов (связь)
  4. ^ Пеот, Марк А. и Смит, Дэвид Э (1992). Условное нелинейное планирование (PDF). Системы планирования искусственного интеллекта. Эльзевир. С. 189–197.CS1 maint: несколько имен: список авторов (связь)
  5. ^ Карлссон, Ларс (2001). Условное прогрессивное планирование в условиях неопределенности. IJCAI. С. 431–438.
  6. ^ Лю, Дафна Хао (2008). Обзор планирования в интеллектуальных агентах: от внешне мотивированных к внутренне мотивированным системам (Технический отчет). Технический отчет TR-2008-936, Департамент компьютерных наук, Университет Рочестера.
  7. ^ Александр Альборе; Гектор Паласиос; Гектор Геффнер (2009). Подход к непредвиденному планированию, основанный на переводе. Международная объединенная конференция по искусственному интеллекту (IJCAI). Пасадена, Калифорния: AAAI.
  8. ^ Литтман, Майкл Л. (1997). Вероятностное пропозициональное планирование: представления и сложность. Четырнадцатая национальная конференция по искусственному интеллекту. MIT Press. стр. 748–754. Получено 2019-02-10.
  9. ^ а б Юсси Ринтанен (2004). Сложность планирования при частичной наблюдаемости (PDF). Int. Конф. Автоматизированное планирование и составление графиков. AAAI.
  10. ^ Де Джакомо, Джузеппе; Рубин, Саша (2018). Теоретико-автоматные основы планирования FOND для целей LTLf и LDLf. IJCAI. Получено 2018-07-17.
  11. ^ Паласиос, Гектор; Геффнер, Гектор (2009). «Компиляция неопределенности в соответствующих задачах планирования с ограниченной шириной». Журнал исследований искусственного интеллекта. 35: 623–675. Дои:10.1613 / jair.2708.
  12. ^ Альборе, Александр; Рамирес, Микель; Геффнер, Гектор (2011). Эффективная эвристика и отслеживание убеждений для планирования с неполной информацией. Двадцать первая международная конференция по автоматизированному планированию и календарному планированию (ICAPS).
  13. ^ Хаслум, Патрик; Йонссон, Питер (2000). «Некоторые результаты о сложности планирования при неполной информации». Последние достижения в планировании ИИ. Конспект лекций по информатике. Springer Berlin Heidelberg. 1809: 308–318. Дои:10.1007/10720246_24. ISBN  9783540446576.

дальнейшее чтение

внешняя ссылка