Иерархическая сеть задач
В области искусственного интеллекта планирование иерархической сети задач (HTN) — это подход к автоматизированному планированию , при котором зависимость между действиями может быть задана в форме иерархически структурированных сетей.
Проблемы планирования определяются в подходе иерархической сети задач с помощьюпредоставление набора задач, которые могут быть:
- примитивные (начальное состояние) задачи, которые примерно соответствуют действиям STRIPS ;
- сложные задачи (промежуточное состояние), которые можно рассматривать как составленные из набора более простых задач;
- целевые задачи (целевое состояние), что примерно соответствует целям STRIPS , но носит более общий характер.
В таком случае решением проблемы HTN является исполняемая последовательность примитивных задач, которую можно получить из исходной сети задач путем разложения составных задач на набор более простых задач и путем введения ограничений порядка.
Примитивная задача — это действие, которое может быть выполнено непосредственно при условии, что состояние, в котором оно выполняется, поддерживает его предварительное условие. Составная задача — это сложная задача, состоящая из частично упорядоченного набора дополнительных задач, которые могут быть примитивными или абстрактными. Целевая задача – это задача удовлетворения условия. Отличие примитивных задач от других состоит в том, что примитивные действия могут выполняться напрямую. И сложные, и целевые задачи требуют выполнения последовательности примитивных действий; однако целевые задачи определяются с точки зрения условий, которые должны быть выполнены, в то время как составные задачи могут быть определены только с точки зрения других задач через сеть задач, описанную ниже.
Ограничения между задачами выражаются в виде сетей, называемых (иерархическими) сетями задач. Сеть задач — это набор задач и ограничений между ними. Такую сеть можно использовать в качестве предварительного условия для выполнимости другой сложной или целевой задачи. Таким образом, можно выразить, что данная задача выполнима только в том случае, если выполняется набор других действий (упомянутых в сети), и они выполняются таким образом, что ограничения между ними (заданные сетью) выполняются. . Одним из конкретных формализмов представления иерархических сетей задач, который довольно широко используется, является TAEMS .
Некоторые из наиболее известных доменно-независимых систем планирования HTN:
- НОА, Сети иерархий действий. [1]
- Nonlin, одна из первых систем планирования HTN. [2]
- СИПЭ-2 [3]
- O-Plan, архитектура открытой планировки [4]
- UMCP, вероятно, первая надежная и полноценная система планирования HTN. [5]
- IX/I-План [6]
- SHOP2 — HTN-планировщик, разработанный в Университете Мэриленда, Колледж-Парк . [7]
- PANDA, система, предназначенная для гибридного планирования, расширение планирования HTN, разработанное в Ульмском университете, Германия. [8]
- HTNPlan-P, на основе предпочтений . планирование HTN [9]
Планирование HTN строго более выразительно, чем STRIPS , вплоть до неразрешимости в общем случае. [10] Однако многие синтаксические ограничения планирования HTN разрешимы, при этом известные сложности варьируются от NP-полных до 2-EXPSPACE-полных . [11] а некоторые проблемы HTN можно эффективно скомпилировать в PDDL , язык, похожий на STRIPS. [12]
См. также [ править ]
- ПОЛОСКИ
- Иерархическая система управления – система управления с обратной связью, хорошо подходящая для планирования HTN.
Ссылки [ править ]
- ^ НОА
- ^ Нонлин
- ^ Дэвид Э. Уилкинс. «SIPE-2: Система интерактивного планирования и исполнения» . Центр искусственного интеллекта . НИИ Интернешнл . Проверено 13 июня 2013 г.
- ^ О-План
- ^ UMCP
- ^ IX/I-План
- ^ МАГАЗИН2
- ^ ПАНДА
- ^ ХТНПлан-П
- ^ Эрол, Кутлухан; Хендлер, Джеймс; Нау, Дана С. (1996). «Результаты сложности планирования htn» (PDF) . Анналы математики и искусственного интеллекта . 18 . Спрингер: 69–93 . Проверено 8 февраля 2015 г.
- ^ Алфорд, Рон; Бершер, Паскаль; Ага, Дэвид (июнь 2015 г.). Жесткие границы для планирования HTN (PDF) . Материалы 25-й Международной конференции по автоматизированному планированию и составлению графиков (ICAPS) . Проверено 8 февраля 2015 г.
- ^ Алфорд, Рон; Кутер, Угур; Нау, Дана С. (июль 2009 г.). Перевод HTN в PDDL: небольшой объем знаний предметной области может иметь большое значение (PDF) . Двадцать первая международная совместная конференция по искусственному интеллекту (IJCAI) . Проверено 8 февраля 2015 г.