Планирование языка определения домена - Planning Domain Definition Language

В Планирование языка определения домена (PDDL) - попытка стандартизировать Планирование искусственного интеллекта (ИИ) языков. Впервые он был разработан Дрю Макдермотт и его коллеги в 1998 г. (вдохновленные Полоски и ADL среди прочего) в основном, чтобы сделать 1998/2000 Международный конкурс планирования (IPC) возможно, а затем эволюционировали с каждым соревнованием. «Принятие общего формализма для описания областей планирования способствует гораздо большему повторному использованию исследований и позволяет более прямое сравнение систем и подходов, и, следовательно, поддерживает более быстрый прогресс в этой области. Общий формализм - это компромисс между выразительной силой (в которой развитие в значительной степени обусловлено потенциальными приложениями) и прогрессом фундаментальных исследований (которые поощряют развитие на хорошо понятых основах). Роль общего формализма как средства коммуникации для обмена требует, чтобы он был обеспечен четкой семантикой ».[1]

Де-факто официальные версии PDDL

PDDL1.2

Это был официальный язык 1-го и 2-й IPC в 1998 и 2000 годах соответственно.[2]Он разделил модель задачи планирования на две основные части: (1) описание домена и (2) связанные описание проблемы. Такое разделение модели позволяет интуитивно разделить те элементы, которые (1) присутствуют в каждой конкретной проблеме предметной области (эти элементы содержатся в описании предметной области), и те элементы, которые (2) определить конкретную проблему планирования (эти элементы содержатся в описании проблемы). Таким образом, несколько описаний проблем могут быть связаны с одним и тем же описанием домена (точно так же, как могут существовать несколько экземпляров класса в ООП (объектно-ориентированное программирование) или в OWL (язык веб-онтологий) Например). Таким образом, предметная область и связующее описание проблемы формируют PDDL-модель проблемы планирования, и в конечном итоге это Вход программного обеспечения планировщика (обычно не зависящего от предметной области ИИ-планировщика), цель которого - решить данную проблему планирования с помощью некоторого соответствующего алгоритма планирования. В вывод планировщика не указан в PDDL, но обычно полностью или частично заказанный план (последовательность действий, некоторые из которых могут выполняться иногда даже параллельно). Теперь давайте посмотрим на содержимое домена PDDL1.2 и описание проблемы в целом ...
(1) Описание домена состояло из доменное имя определение, определение требования (чтобы объявить планировщику те элементы модели, которые фактически использует PDDL-модель), определение иерархия типов объектов (точно так же, как иерархия классов в ООП ), значение постоянные объекты (которые присутствуют в каждой проблеме в предметной области), определение предикаты (шаблоны логических фактов), а также определение возможных действия (схемы операторов с параметрами, которые должны быть обоснованы / инстанциированы во время выполнения). Действия имели параметры (переменные, которые могут быть созданы с помощью объектов), предварительные условия и эффекты. Последствия действий также могут быть условный (когда-эффекты).
(2) Описание проблемы состояло из имя-проблемы определение, определение связанных доменное имя, определение всех возможных объекты (атомы в логической вселенной), первоначальные условия (начальное состояние среды планирования, сочетание истинных / ложных фактов) и определение цели-состояния (логическое выражение фактов, которые должны быть истинными / ложными в целевом состоянии среды планирования). Таким образом, в конечном итоге PDDL1.2 уловил «физику» детерминированной одноагентной дискретной полностью доступной среды планирования.

PDDL2.1

Это был официальный язык 3-й МПК в 2002 г.[3]Он представил числовой беглый (например, для моделирования небинарных ресурсов, таких как уровень топлива, время, энергия, расстояние, вес, ...), план-метрики (чтобы позволить количественную оценку планов, а не только целевое, но и ориентированное на полезность планирование, то есть оптимизацию, минимизацию / максимизацию показателей) и длительные / непрерывные действия (который может иметь переменную недискретную длину, условия и эффекты). В конце концов, PDDL2.1 позволил представить и решить гораздо больше реальных проблем, чем исходная версия языка.

PDDL2.2

Это был официальный язык детерминированного трека 4-й МПК в 2004 году.[4]Он представил производные предикаты (для моделирования зависимости данных фактов от других фактов, например, если A достижимо из B, а B достижимо из C, то A достижимо из C (транзитивность)), и синхронизированные начальные литералы (для моделирования экзогенных событий, происходящих в данный момент времени независимо от выполнения плана). В конце концов, PDDL2.2 расширил язык несколькими важными элементами, но это не было радикальным развитием по сравнению с PDDL2.1 после PDDL1.2.

PDDL3.0

Это был официальный язык детерминированного трека 5-й IPC в 2006 году.[5][6][7]Он представил ограничения траектории состояний (жесткие ограничения в форме модально-логических выражений, которые должны быть верны для траектории состояния, созданной во время выполнения плана, который является решением данной проблемы планирования) и предпочтения (мягкие ограничения в форме логических выражений, подобные жестким ограничениям, но их удовлетворение не было обязательным, хотя оно могло быть включено в план-метрику, например, чтобы максимизировать количество удовлетворенных предпочтений или просто измерить качество план), чтобы планирование на основе предпочтений. В конце концов, PDDL3.0 обновил выразительность языка, чтобы справиться с недавними важными изменениями в планировании.

PDDL3.1

Это был официальный язык детерминированного трека Шестой и 7-е IPC в 2008 и 2011 годах соответственно.[8][9][10]Он представил объект-бегун (т.е. диапазон функций теперь может быть не только числовым (целым или действительным), но также может быть любым типом объекта). Таким образом, PDDL3.1 адаптировал язык еще больше к современным ожиданиям с синтаксически, казалось бы, небольшим, но семантически довольно значительным изменением выразительности.

Текущая ситуация

Последняя версия языка PDDL3.1. В БНФ (форма Бэкуса – Наура) определение синтаксиса PDDL3.1 можно найти среди ресурсов Домашняя страница МПК-2011 или Домашняя страница МПК-2014.

Преемники / варианты / расширения PDDL

PDDL +

Это расширение PDDL2.1 примерно с 2002 по 2006 год обеспечивает более гибкую модель непрерывных изменений за счет использования автономных процессы и События.[1][11]Ключевым моментом, который предоставляет это расширение, является возможность моделировать взаимодействие между поведением агента и изменениями, инициированными средой агента. Процессы выполняются с течением времени и оказывают непрерывное влияние на числовые значения. Они инициируются и завершаются либо прямым действием агента, либо событиями, запускаемыми в среде. Эта трехчастная структура называется модель старт-процесс-остановка. Различают логические и числовые состояния: предполагается, что переходы между логическими состояниями происходят мгновенно, в то время как занятие данного логического состояния может продолжаться с течением времени. Таким образом, в PDDL + выражения непрерывного обновления могут встречаться только в эффектах процесса. Действия и события, которые являются мгновенными, ограничиваются выражением дискретных изменений. Это вводит ранее упомянутое трехчастное моделирование периодов непрерывных изменений: (1) действие или событие запускает период непрерывного изменения числовой переменной, выраженной посредством процесса; (2) процесс реализует непрерывное изменение числовой переменной; (3) действие или событие, наконец, останавливает выполнение процесса и прекращает его действие на числовую переменную. Комментарий: цели плана могут быть достигнуты до остановки активного процесса.

NDDL

NDDL (Nфу Dдомен Dопределение Lязык) НАСА ответ на PDDL примерно с 2002 года.[12][13]Его представление отличается от PDDL в нескольких отношениях: 1) в нем используется представление переменных / значений (сроки / действия) а не пропозициональный /логика первого порядка, и 2) нет понятия состояний или действий, только интервалы (действия) и ограничения между этими действиями. В этом отношении модели в NDDL больше похожи на схемы для СИДЕЛ кодирования задач планирования, а не моделей PDDL. Из-за упомянутых различий планирование и выполнение планов (например, во время критических космических миссий) может быть более надежным при использовании NDDL, но соответствие стандартным представлениям задач планирования, отличным от PDDL, может быть гораздо менее интуитивным, чем в случае PDDL.

MAPL

MAPL (MокончательноАджентльмен плэннинг Language, произносится как «клен») является расширением PDDL2.1 примерно с 2003 года.[14]Это довольно серьезная модификация языка оригинала. Он вводит непропозициональные переменные состояния (который может быть n-арным: истина, ложь, неизвестно или что-то еще). Он вводит временную модель с модальные операторы (до, после и т. д.). Тем не менее в PDDL3.0 была дана более тщательная временная модель, которая также совместима с исходным синтаксисом PDDL (и это просто необязательное дополнение). MAPL также представляет действия, продолжительность которых будет определяться во время выполнения и явная синхронизация плана который реализуется через речевой акт общение между агентами на основе. Это предположение может быть искусственным, поскольку агенты, выполняющие параллельные планы, не обязательно должны взаимодействовать, чтобы иметь возможность работать в многоагентной среде. Наконец, MAPL представляет события (эндогенные и экзогенные) для обработки параллелизма действий. Таким образом, события становятся частью планов и назначаются агентам функция управления, что также является частью плана.

OPT

OPT (Онтология с полиморфный Тypes) был глубоким расширением PDDL2.1 за счет Дрю Макдермотт примерно с 2003 по 2005 год (с некоторым сходством с PDDL +).[15]Это была попытка создать универсальную нотацию для создания онтологии, определяемые как формализованные концептуальные основы для областей планирования, о которых должны рассуждать приложения планирования. Его синтаксис был основан на PDDL, но он имел гораздо больше сложная система шрифтов, что позволило пользователям использовать конструкции более высокого порядка, такие как явные λ-выражения позволяя эффективно вывод типа (т.е. не только объекты домена имели типы (типы 0 уровня), но также функции / флюенты, определенные выше этих объектов, имели типы в виде произвольных отображений (типы 1 уровня), которые могут быть универсальными, поэтому их параметры (домен и диапазон общего сопоставления) могут быть определены с помощью переменных, которые могут иметь тип еще более высокого уровня (уровень 2 типа), не говоря уже о том, что сопоставления могут быть произвольными, то есть домен или диапазон функции (например, предикат, числовой беглый) может быть любого типа уровня 0/1/2. Например, функции могут отображаться из произвольных функций в произвольные функции ...). OPT в основном предназначался для (почти) восходящей совместимости с PDDL2.1. Обозначение для процессы и длительные действия был заимствован в основном из PDDL + и PDDL2.1, но помимо этого OPT предлагал множество других значительных расширений (например, структуры данных, небулевские беглые языки, возвращаемые значения для действий, ссылки между действиями, иерархическое расширение действия, иерархия определений домена, использование пространства имен для совместимости с семантическая сеть ).

PPDDL

PPDDL (пробабилистический PDDL) 1.0 был официальным языком вероятностного трека 4-й и 5-й IPC в 2004 и 2006 годах соответственно.[16]Он расширил PDDL2.1 с вероятностные эффекты (дискретные, общие распределения вероятностей возможных эффектов действия), вознаграждать беглых (для увеличения или уменьшения общей награды за план в результате действий), награды за цель (для вознаграждения за траекторию состояния, которая включает как минимум одно целевое состояние), и бегло к цели (что было правдой, если траектория состояния включала хотя бы одну цель-состояние). В конце концов эти изменения позволили PPDDL1.0 реализовать Марковский процесс принятия решений (MDP) планирования, где может быть неопределенность в переходах между состояниями, но среда полностью наблюдаема для планировщика / агента.

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ (Ареферат план пвозмещение Language) - это новый вариант NDDL с 2006 года, который является более абстрактным, чем большинство существующих языков планирования, таких как PDDL или NDDL.[17]Целью этого языка было упростить формальный анализ и спецификацию задач планирования, которые предназначены для критически важных с точки зрения безопасности приложений, таких как управление питанием или автоматическое рандеву на будущих пилотируемых космических кораблях. APPL использовал те же концепции, что и NDDL с продление действия, а также некоторые другие концепции, но все же его выразительная сила намного меньше, чем у PDDL (в надежде на то, что он останется надежным и формально проверяемым).

RDDL

RDDL (рвосторженный Dдинамическое влияние Dиаграмма Lязык) был официальным языком трека неопределенности 7-е IPC в 2011 году.[18]Концептуально он основан на PPDDL1.0 и PDDL3.0, но практически это совершенно другой язык как синтаксически, так и семантически. Вступление к частичная наблюдаемость является одним из наиболее важных изменений в RDDL по сравнению с PPDDL1.0. Это позволяет оперативно описывать Марковские процессы принятия решений (MDP) и Частично наблюдаемые марковские процессы принятия решений (POMDP) представляя все (текущее состояние, наблюдения, действия, ...) переменными. Таким образом, RDDL значительно отличается от PDDL. Заземленный RDDL соответствует Динамические байесовские сети (DBN) аналогичен PPDDL1.0, но RDDL более выразителен, чем PPDDL1.0.

MA-PDDL

MA-PDDL (Multi Аджентльмен PDDL) является минималистичным модульным расширением PDDL3.1 введен в 2012 г. (т.е. новый : мультиагент требование), что позволяет планирование и для несколько агентов.[19] Дополнение совместимо со всеми функциями PDDL3.1 и решает большинство вопросов MAPL. Это добавляет возможность различать возможные разные действия разных агентов (т.е. разные возможности). Подобным образом разные агенты могут иметь разные цели и / или показатели. Предварительные условия действий теперь могут напрямую относиться к параллельным действиям (например, действиям других агентов) и, таким образом, действия с взаимодействующими эффектами могут быть представлены в общем, гибком виде (например, предположим, что для выполнения поднимать действие, чтобы поднять тяжелый стол в воздух, иначе стол остался бы на земле (это пример конструктивной синергии, но разрушительная синергия также может быть легко представлена ​​в MA-PDDL)). Более того, как своего рода синтаксический сахар, простой механизм для наследование и полиморфизм действий, целей и метрик также был введен в MA-PDDL (при условии : typing заявлен). поскольку PDDL3.1 предполагает, что среда детерминирована и полностью наблюдаема, то же самое верно и для MA-PDDL, то есть каждый агент может получить доступ к значению каждого состояния в каждый момент времени и наблюдать за каждым ранее выполненным действием каждого агента, а также за параллельными действиями агенты однозначно определяют следующее состояние среды. Позже это было улучшено путем добавления эффектов частичной наблюдаемости и вероятностных эффектов (опять же, в форме двух новых модульных требований: : частичная наблюдаемость и : вероятностные эффектысоответственно, последние вдохновлены PPDDL1.0, и оба совместимы со всеми предыдущими функциями языка, включая : мультиагент).[20]

Пример

Это определение домена Полоски Пример для автоматизированного планирования робота с двумя захватными руками.[21]

(определять (домен захваты)  (: предикаты (комната ?р) (мяч ? б) (захват ?грамм) (Ат-Робби ?р)               (в ? б ?р) (свободный ?грамм) (нести ? o ?грамм))  (:действие двигаться   : параметры (?из ?к)   : предварительное условие (и (комната ?из)                      (комната ?к)                      (Ат-Робби ?из))   :эффект (и (Ат-Робби ?к)                (не (Ат-Робби ?из))))  (:действие выбирать   : параметры (? obj ?комната ? захват)   : предварительное условие (и (мяч ? obj)                      (комната ?комната)                      (захват ? захват)                      (в ? obj ?комната)                      (Ат-Робби ?комната)                      (свободный ? захват))   :эффект (и (нести ? obj ? захват)                (не (в ? obj ?комната))                (не (свободный ? захват))))  (:действие уронить   : параметры (? obj ?комната ? захват)   : предварительное условие (и (мяч ? obj)                      (комната ?комната)                      (захват ? захват)                      (нести ? obj ? захват)                      (Ат-Робби ?комната))   :эффект (и (в ? obj ?комната)                (свободный ? захват)                (не (нести ? obj ? захват)))))

И это определение проблемы, которое инстанцирует предыдущее определение домена с конкретной средой с двумя комнатами и двумя шарами.

(определять (проблема полосы-захват2)    (:домен захваты)    (:объекты комната комнатаb мяч1 мяч2 оставили верно)    (:в этом (комната комната)           (комната комнатаb)           (мяч мяч1)           (мяч мяч2)           (захват оставили)           (захват верно)           (Ат-Робби комната)           (свободный оставили)           (свободный верно)           (в мяч1 комната)           (в мяч2 комната))    (:Цель (в мяч1 комнатаb)))

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

  1. ^ а б Fox, M .; Лонг, Д. (2002). «PDDL +: Моделирование непрерывных эффектов, зависящих от времени». Труды 3-го Международного семинара НАСА по планированию и составлению расписания для космоса. CiteSeerX  10.1.1.15.5965.
  2. ^ Макдермотт, Дрю; Галлаб, Малик; Хау, Адель; Ноблок, Крейг; Рам, Ашвин; Велозу, Мануэла; Weld, Дэниел; Уилкинс, Дэвид (1998). «PDDL - язык определения предметной области» (PDF). Технический отчет CVC TR98003 / DCS TR1165. Нью-Хейвен, Коннектикут: Йельский центр вычислительного зрения и управления. CiteSeerX  10.1.1.51.9941.
  3. ^ Fox, M .; Лонг, Д. (2003). «PDDL2.1: расширение PDDL для выражения доменов временного планирования» (PDF). Журнал исследований искусственного интеллекта. 20: 61–124.
  4. ^ Edelkamp, ​​S .; Хоффманн, Дж. (2003). «PDDL2.2: Язык классической части 4-го Международного конкурса планирования» (PDF). Технический отчет № 195. Institut für Informatik.
  5. ^ Геревини, А .; Лонг, Д. (2006). «Предпочтения и мягкие ограничения в PDDL3» (PDF). Материалы семинара ICAPS-2006 по предпочтениям и мягким ограничениям в планировании. С. 46–54.
  6. ^ Геревини, А .; Лонг, Д. (2005). «Планируйте ограничения и предпочтения в PDDL3» (PDF). Технический отчет R. T. 2005-08-47. Dipartimento di Elettronica per l'Automazione, Università degli Studi di Brescia.
  7. ^ Геревини, А .; Лонг, Д. (2005). "Описание BNF PDDL3.0" (PDF). Неопубликованная рукопись, ссылка на которую имеется на сайте IPC-5.
  8. ^ Хельмерт, М. (2008). «Изменения в PDDL 3.1». Неопубликованное резюме с сайта IPC-2008.
  9. ^ Ковач, Д. Л. (2011). «Определение PDDL3.1 BNF: полностью исправлено, без комментариев» (PDF). Неопубликованная рукопись с сайта МПК-2011.
  10. ^ Ковач, Д. Л. (2011). «Определение PDDL3.1 BNF: частично исправлено, с комментариями / пояснениями» (PDF). Неопубликованная рукопись с сайта МПК-2011.
  11. ^ Fox, M .; Лонг, Д. (2006). «Моделирование смешанных дискретно-непрерывных областей для планирования» (PDF). Журнал исследований искусственного интеллекта. 27: 235–297. arXiv:1110.2200. CiteSeerX  10.1.1.75.6792. Дои:10.1613 / jair.2044.
  12. ^ Франк, Дж .; Йонссон, А. (2002). «Планирование атрибутов и интервалов на основе ограничений» (PDF). Технический отчет. Моффетт Филд, Калифорния: Исследовательский центр Эймса НАСА.
  13. ^ Bernardini, S .; Смит, Д. Э. (2007). «Разработка независимого от домена управления поиском для EUROPA2» (PDF). Материалы семинара по эвристике для независимого от предметной области планирования: прогресс, идеи, ограничения, вызовы. 17-я Международная конференция по автоматизированному планированию и календарному планированию (ICAPS-2007). Род-Айленд, США.
  14. ^ Бреннер, М. (2003). «Многоагентный язык планирования» (PDF). Материалы семинара по PDDL. 13-я Международная конференция по автоматизированному планированию и календарному планированию (ICAPS-2003). Тренто, Италия.
  15. ^ Макдермотт, Д. (2005). "Руководство OPT версии 1.7.3 (отражает версию 1.6.11 Opt) * ПРОЕКТ **" (PDF). Неопубликованная рукопись с веб-сайта Дрю Макдермотта.
  16. ^ Юнес, Х. Л. С .; Литтман, М. Л. (2004). «PPDDL 1.0: расширение PDDL для выражения областей планирования с вероятностными эффектами» (PDF). Технический отчет CMU-CS-04-167. Питтсбург: Университет Карнеги-Меллона.
  17. ^ Батлер, Р .; Муньос, К. (2006). "Язык подготовки абстрактного плана" (PDF). Технический отчет НАСА NASA / TM-2006-214518.
  18. ^ Саннер, С. (2010). «Язык диаграмм реляционного динамического влияния (RDDL): описание языка» (PDF). Неопубликованная рукопись с сайта МПК-2011.
  19. ^ Ковач, Д. Л. (2012). «Мультиагентное расширение PDDL3.1» (PDF). Материалы 3-го семинара по международному конкурсу планирования (IPC). 22-я Международная конференция по автоматизированному планированию и календарному планированию (ICAPS-2012). Атибая, Сан-Паулу, Бразилия. С. 19–27.
  20. ^ Ковач, Д. Л .; Добровецкий, Т. П. (2013). Преобразование MA-PDDL в игры с расширенной формой (PDF). Acta Polytechnica Hungarica. 10 (8). С. 27–47. Дои:10.12700 / APH.10.08.2013.8.2.
  21. ^ Велозу, Мануэла. «PDDL на примере» (pdf). Университет Карнеги Меллон. Получено 2015-11-28.