Сеть иерархических задач - Википедия - Hierarchical task network

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

Задачи планирования определяются в сетевом подходе с иерархическими задачами путем предоставления набора задач, которые могут быть:

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

Тогда решение проблемы HTN - это исполняемая последовательность примитивных задач, которая может быть получена из исходной сети задач путем декомпозиции составных задач на их набор более простых задач и путем вставки ограничений упорядочения.

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

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

Некоторые из наиболее известных систем планирования HTN, не зависящих от предметной области:

  • Nonlin, одна из первых систем планирования HTN.[1]
  • СИПЭ-2[2]
  • O-Plan, Открытая планировочная архитектура[3]
  • UMCP, первая надежная и полная система планирования HTN.[4]
  • I-X / I-Plan[5]
  • SHOP2, HTN-планировщик, разработанный в Университет Мэриленда, Колледж-Парк.[6]
  • PANDA, система, разработанная для гибридного планирования, расширение HTN-планирования, разработанная в Университете Ульма, Германия. [7]
  • HTNPlan-P, г. на основе предпочтений Планирование HTN.[8]

Планирование HTN строго более выразительно, чем Полоски, вплоть до неразрешимости в общем случае.[9] Однако многие синтаксические ограничения планирования HTN разрешимы, с известными сложностями в диапазоне от НП-полный к 2-EXPSPACE-полный,[10] и некоторые проблемы HTN могут быть эффективно скомпилированы в PDDL, язык, похожий на полоски.[11]

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

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

  1. ^ Нелин
  2. ^ Дэвид Э. Уилкинс. «СИПЭ-2: Система интерактивного планирования и исполнения». Центр Искусственного Интеллекта. SRI International. Получено 2013-06-13.
  3. ^ O-план
  4. ^ UMCP
  5. ^ I-X / I-Plan
  6. ^ МАГАЗИН2
  7. ^ ПАНДА
  8. ^ HTNPlan-P
  9. ^ Эрол, Кутлухан; Хендлер, Джеймс; Нау, Дана С. (1996). «Результаты сложности для планирования сети» (PDF). Анналы математики и искусственного интеллекта. Springer. 18: 69–93. Получено 8 февраля 2015.
  10. ^ Алфорд, Рон; Беркер, Паскаль; Ага, Дэвид (июнь 2015). Жесткие границы для планирования HTN (PDF). Материалы 25-й Международной конференции по автоматизированному планированию и календарному планированию (ICAPS). Получено 8 февраля 2015.
  11. ^ Алфорд, Рон; Кутер, Угур; Нау, Дана С. (июль 2009 г.). Перевод HTN в PDDL: небольшое знание предметной области может иметь большое значение (PDF). Двадцать первая международная совместная конференция по искусственному интеллекту (IJCAI). Получено 8 февраля 2015.