Язык определения предметной области планирования ( PDDL ) - это попытка стандартизировать языки планирования искусственного интеллекта (ИИ) . Впервые он был разработан Дрю Макдермоттом и его коллегами в 1998 году (вдохновленный, среди прочего, STRIPS и ADL ) в основном для того, чтобы сделать возможным Международный конкурс планирования (IPC) 1998/2000 годов , а затем развивался с каждым соревнованием. Стандартизация, обеспечиваемая PDDL, позволяет сделать исследования более пригодными для повторного использования и легко сопоставимыми, хотя и за счет некоторой выразительной силы, по сравнению с системами, ориентированными на конкретную предметную область. [1]
Де-факто официальные версии PDDL
PDDL1.2
Это был официальный язык 1-го и 2-го МПК в 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- го IPC в 2004 году. [4] Он ввел производные предикаты (для моделирования зависимости данных фактов от других фактов, например, если A достижимо из B, а B достижимо из C, тогда A достижимо из C (транзитивность)) и синхронизированными начальными литералами (для моделирования экзогенных событий, происходящих в данный момент времени независимо от выполнения плана). В конечном итоге PDDL2.2 расширил язык несколькими важными элементами, но это не было радикальным развитием по сравнению с PDDL2.1 после PDDL1.2.
PDDL3.0
Это был официальный язык детерминированного трека 5-го МПК в 2006 году. [5] [6] [7] Он ввел ограничения траектории состояния (жесткие ограничения в форме модально-логических выражений, которые должны быть верными для состояния -траектория, созданная во время выполнения плана, который является решением данной задачи планирования) и предпочтений (мягкие ограничения в форме логических выражений, аналогичные жестким ограничениям, но их выполнение не было необходимым, хотя это могло быть включены в план-метрику, например, чтобы максимизировать количество удовлетворенных предпочтений или просто измерить качество плана), чтобы обеспечить планирование на основе предпочтений . В конце концов PDDL3.0 обновил выразительность языка, чтобы быть в состоянии справиться с недавними важными изменениями в планировании.
PDDL3.1
Это был официальный язык детерминированного трека 6-го и 7-го МПК в 2008 и 2011 годах соответственно. [8] [9] [10] Он ввел объектные флюенты (т.е. диапазон функций теперь может быть не только числовым (целым или действительным), но также может быть любым типом объекта). Таким образом, PDDL3.1 адаптировал язык еще больше к современным ожиданиям с синтаксически, казалось бы, небольшим, но семантически довольно значительным изменением выразительности.
Текущая ситуация
Последняя версия языка - PDDL3.1 . BNF (Бэкус-Наур) определение синтаксиса PDDL3.1 можно найти среди ресурсов страницы IPC-2011 или домашней страницы IPC-2014 .
Преемники / варианты / расширения PDDL
PDDL +
Это расширение PDDL2.1 примерно с 2002 по 2006 год обеспечивает более гибкую модель непрерывного изменения за счет использования автономных процессов и событий . [1] [11] Ключ, который предоставляет это расширение, - это способность моделировать взаимодействие между поведением агента и изменениями, инициированными средой агента. Процессы выполняются с течением времени и оказывают непрерывное влияние на числовые значения. Они инициируются и завершаются либо прямым действием агента, либо событиями, запускаемыми в среде. Эта трехчастная структура называется моделью старт-процесс-остановка . Различают логические и числовые состояния: предполагается, что переходы между логическими состояниями происходят мгновенно, в то время как занятие данного логического состояния может продолжаться с течением времени. Таким образом, в PDDL + выражения непрерывного обновления могут встречаться только в эффектах процесса. Действия и события, которые являются мгновенными, ограничиваются выражением дискретных изменений. Это вводит вышеупомянутое трехэтапное моделирование периодов непрерывного изменения: (1) действие или событие запускает период непрерывного изменения числовой переменной, выраженной посредством процесса; (2) процесс реализует непрерывное изменение числовой переменной; (3) действие или событие, наконец, останавливает выполнение процесса и прекращает свое действие на числовую переменную. Комментарий: цели плана могут быть достигнуты до остановки активного процесса.
NDDL
NDDL ( N EW D omain D efinition L anguage) является НАСА ответ «с до PDDL из около 2002. [12] [13] Его представление отличается от PDDL в нескольких аспектах: 1) он использует представление переменной / значение (временные рамки деятельности / ), а не пропозициональная логика / логика первого порядка , и 2) нет концепции состояний или действий, только интервалы (действия) и ограничения между этими действиями . В этом отношении модели в NDDL больше похожи на схемы для SAT- кодирования задач планирования, чем на модели PDDL. Из-за упомянутых различий планирование и выполнение планов (например, во время критических космических полетов) может быть более надежным при использовании NDDL, но соответствие стандартным представлениям задач планирования, отличным от PDDL, может быть гораздо менее интуитивным, чем в случае PDDL.
MAPL
MAPL ( М конечном Gent Р Лэннинг л anguage, объявленный «клен») является расширением PDDL2.1 со всего 2003. [14] Это довольно серьезное изменение первоначального языка. Он вводит непропозициональные переменные состояния (которые могут быть n-арными: истина, ложь, неизвестно или что-то еще). Он вводит временную модель, заданную модальными операторами (до, после и т. Д.). Тем не менее в PDDL3.0 была дана более тщательная временная модель, которая также совместима с исходным синтаксисом PDDL (и это просто необязательное дополнение). MAPL также вводит действия, продолжительность которых будет определяться во время выполнения, и явную синхронизацию плана, которая реализуется посредством коммуникации между агентами на основе речевых актов . Это предположение может быть искусственным, поскольку агенты, выполняющие параллельные планы, не обязательно должны взаимодействовать, чтобы иметь возможность работать в многоагентной среде. Наконец, MAPL вводит события (эндогенные и экзогенные) для обработки параллелизма действий. Таким образом, события явно становятся частью планов и назначаются агентам функцией управления , которая также является частью плана.
OPT
OPT ( O ntology с Р olymorphic Т ypes) был глубокое продолжение PDDL2.1 по Drew McDermott со всего 2003-2005 (с некоторым сходством с PDDL +). [15] Это была попытка создать универсальную нотацию для создания онтологий , определяемую как формализованные концептуальные основы для областей планирования, о которых должны рассуждать приложения планирования. Его синтаксис был основан на PDDL, но имел гораздо более сложную систему типов , которая позволяла пользователям использовать конструкции более высокого порядка, такие как явные λ-выражения, обеспечивающие эффективный вывод типов (т.е. не только объекты предметной области имели типы ( уровень 0 типы ), но также функции / флюенты, определенные выше этих объектов, имели типы в виде произвольных отображений ( типы уровня 1 ), которые могли быть универсальными, поэтому их параметры (домен и диапазон общего отображения) могли быть определены с помощью переменных , который может иметь тип даже более высокого уровня (тип уровня 2 ), не говоря уже о том, что сопоставления могут быть произвольными, то есть домен или диапазон функции (например, предикат, числовой беглый) может быть любым типом уровня 0/1/2 . Например, функции могут отображаться из произвольных функций в произвольные функции ...). OPT в основном предназначался для (почти) восходящей совместимости с PDDL2.1. Обозначения для процессов и длительных действий были заимствованы в основном из PDDL + и PDDL2.1, но помимо этого OPT предлагал множество других значительных расширений (например, структуры данных , небулевские флюенты , возвращаемые значения для действий, связи между действиями, иерархическое расширение действий. , иерархия определений домена , использование пространств имен для совместимости с семантической сетью ).
PPDDL
PPDDL ( P robabilistic PDDL ) 1,0 был официальным языком вероятностного дорожки 4 и 5 IPC в 2004 и 2006 годах соответственно. [16] Он расширил PDDL2.1 с помощью вероятностных эффектов (дискретных, общих распределений вероятностей для возможных эффектов действия), плавных вознаграждений (для увеличения или уменьшения общего вознаграждения плана в эффектах действий), целевых вознаграждений (для вознаграждение за траекторию состояния, которая включает, по крайней мере, одну цель-состояние), и беглости достигнутых целей (которые были верны, если траектория состояния включала хотя бы одну цель-состояние). В конечном итоге эти изменения позволили PPDDL1.0 реализовать планирование Марковского процесса принятия решений (MDP) , при котором может быть неопределенность в переходах между состояниями, но среда полностью наблюдаема для планировщика / агента.
ПРИЛОЖЕНИЕ
APPL ( A bstract P lan P reparation L anguage) - это новый вариант NDDL с 2006 года, который является более абстрактным, чем большинство существующих языков планирования, таких как PDDL или NDDL. [17] Целью этого языка было упростить формальный анализ и спецификацию задач планирования, которые предназначены для критически важных с точки зрения безопасности приложений, таких как управление питанием или автоматическое рандеву на будущих пилотируемых космических кораблях. APPL использовал те же концепции, что и NDDL, с расширением действий , а также некоторые другие концепции, но все же его выразительная сила намного меньше, чем у PDDL (в надежде остаться надежным и формально проверяемым).
RDDL
RDDL ( R elational D инамического влияния D iagram L anguage) был официальным языком неопределенности дорожки 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 ( M ульта барин PDDL ) является минималистичный, модульное расширение PDDL3.1 введена в 2012 году (то есть новое требование) , что позволяет планировать и в интересах нескольких агентов. [19] Дополнение совместимо со всеми функциями PDDL3.1 и решает большинство проблем MAPL . Это добавляет возможность различать, возможно, разные действия разных агентов (то есть разные возможности). Точно так же разные агенты могут иметь разные цели и / или показатели . Предварительные условия действий теперь могут напрямую относиться к параллельным действиям (например, действиям других агентов), и, таким образом, действия с взаимодействующими эффектами могут быть представлены в общем, гибком виде (например, предположим, что для выполнения действия по поднятию тяжелый стол в воздух, иначе стол остался бы на земле (это пример конструктивной синергии, но деструктивная синергия также может быть легко представлена в MA-PDDL)). Более того, как своего рода синтаксический сахар, простой механизм наследования и полиморфизма действий, целей и показателей также был введен в MA-PDDL (при условии, что объявлено). Поскольку PDDL3.1 предполагает, что среда является детерминированной и полностью наблюдаемой, то же самое верно и для MA-PDDL, то есть каждый агент может получить доступ к значению каждого текущего состояния в каждый момент времени и наблюдать за каждым ранее выполненным действием каждого агента, а также одновременные действия агентов однозначно определяют следующее состояние среды. Позже это было улучшено добавлением эффектов частичной наблюдаемости и вероятностных эффектов (опять же, в форме двух новых модульных требований, и , соответственно, последнее было вдохновлено PPDDL1.0 , и оба были совместимы со всеми предыдущими функциями языка. , в том числе ). [20]:multi-agent
lift
:typing
:partial-observability
:probabilistic-effects
:multi-agent
Пример
Это определение предметной области экземпляра STRIPS для автоматического планирования робота с двумя захватными руками. [21]
( Определяет ( доменную захватную-полоску ) ( : предикат ( номер г? ) ( Шар б? ) ( Захватный г? ) ( По-Robby г? ) ( При б? Г? ) ( Свободный г? ) ( Перенос O? ? g )) ( : действие move : parameters ( ? from ? to ) : precondition ( and ( room ? from ) ( room ? to ) ( at-robby ? from )) : effect ( and ( at-robby ? to ) ( not ( at-robby ? from )))) ( : действие выбрать : параметры ( ? obj ? room ? gripper ) : precondition ( and ( ball ? obj ) ( room ? room ) ( gripper ? gripper ) ( at ? obj ? room ) ( at-robby ? room ) ( free ? gripper )) : effect ( and ( carry ? obj ? gripper ) ( not ( at ? obj ? room )) ( not ( free ? gripper )))) ( : действие drop : параметры ( OBJ? номер? рапиры? ) : предварительное условие ( и ( мяч ? OBJ ) ( номер комнаты? ) ( захватное рапиры? ) ( кэрри OBJ? рапиры? ) ( в-Robby номер? )) : эффект ( и ( в ? OBJ ? комната ) ( свободный ? захват ) ( не ( нести ? obj ? захват )))))
И это определение проблемы, которое инстанцирует предыдущее определение домена с конкретной средой с двумя комнатами и двумя шарами.
( Определить ( проблемные полоски-gripper2 ) ( : домен захватной-полоска ) ( : объекты Rooma roomb ball1 ball2 влево вправо ) ( : INIT ( номер Rooma ) ( номер roomb ) ( мяч ball1 ) ( мяч ball2 ) ( захват влево ) ( эспандер right ) ( at-robby rooma ) ( свободный слева ) ( свободный справа ) ( at ball1 rooma ) ( at ball2 rooma )) ( : goal ( at ball1 roomb )))
Рекомендации
- ^ a b Fox, M .; Лонг, Д. (2002). «PDDL +: Моделирование непрерывных эффектов, зависящих от времени». Труды 3-го Международного семинара НАСА по планированию и диспетчеризации космоса . CiteSeerX 10.1.1.15.5965 .
- ^ Макдермотт, Дрю; Галлаб, Малик; Хау, Адель; Ноблок, Крейг; Рам, Ашвин; Велозу, Мануэла; Weld, Дэниел; Уилкинс, Дэвид (1998). «PDDL - язык определения предметной области» (PDF) . Технический отчет CVC TR98003 / DCS TR1165 . Нью-Хейвен, Коннектикут: Йельский центр вычислительного зрения и управления. CiteSeerX 10.1.1.51.9941 .
- ^ Fox, M .; Лонг, Д. (2003). «PDDL2.1: расширение PDDL для выражения доменов временного планирования» (PDF) . Журнал исследований искусственного интеллекта . 20 : 61–124. DOI : 10.1613 / jair.1129 .
- ^ Edelkamp, S .; Хоффманн, Дж. (2003). «PDDL2.2: Язык классической части 4-го Международного конкурса планирования» (PDF) . Технический отчет № 195 . Institut für Informatik .
- ^ Геревини, А .; Лонг, Д. (2006). «Предпочтения и мягкие ограничения в PDDL3» (PDF) . Материалы семинара ICAPS-2006 по предпочтениям и мягким ограничениям в планировании . С. 46–54.
- ^ Геревини, А .; Лонг, Д. (2005). «Планируйте ограничения и предпочтения в PDDL3» (PDF) . Технический отчет RT 2005-08-47 . Dipartimento di Elettronica per l'Automazione, Università degli Studi di Brescia.
- ^ Геревини, А .; Лонг, Д. (2005). "Описание BNF PDDL3.0" (PDF) . Неопубликованная рукопись, связанная с веб-сайтом IPC-5 .
- ^ Хельмерт, М. (2008). «Изменения в PDDL 3.1» . Неопубликованное резюме с веб-сайта IPC-2008 .
- ^ Ковач, Д.Л. (2011). «Определение PDDL3.1 в BNF: полностью исправлено, без комментариев» (PDF) . Неопубликованная рукопись с веб-сайта МПК-2011 .
- ^ Ковач, Д.Л. (2011). «Определение PDDL3.1 BNF: частично исправлено, с комментариями / пояснениями» (PDF) . Неопубликованная рукопись с веб-сайта МПК-2011 .
- ^ Fox, M .; Лонг, Д. (2006). «Моделирование смешанных дискретно-непрерывных областей для планирования» (PDF) . Журнал исследований искусственного интеллекта . 27 : 235–297. arXiv : 1110.2200 . CiteSeerX 10.1.1.75.6792 . DOI : 10.1613 / jair.2044 .
- ^ Франк, Дж .; Йонссон, А. (2002). «Планирование атрибутов и интервалов на основе ограничений» (PDF) . Технический отчет . Моффетт Филд, Калифорния: Исследовательский центр Эймса НАСА.
- ^ Bernardini, S .; Смит, DE (2007). «Разработка независимого от домена управления поиском для EUROPA2» (PDF) . Труды семинара по эвристике для независимого от предметной области планирования: прогресс, идеи, ограничения, проблемы . 17-я Международная конференция по автоматизированному планированию и календарному планированию (ICAPS-2007). Род-Айленд, США.
- ^ Бреннер, М. (2003). «Многоагентный язык планирования» (PDF) . Материалы семинара по PDDL . 13-я Международная конференция по автоматизированному планированию и календарному планированию (ICAPS-2003). Тренто, Италия.
- ^ Макдермотт, Д. (2005). «Руководство по OPT версии 1.7.3 (отражает версию 1.6.11 Opt) * ПРОЕКТ **» (PDF) . Неопубликованная рукопись с веб-сайта Дрю Макдермотта .
- ^ Юнес, HLS; Литтман, ML (2004). «PPDDL 1.0: расширение PDDL для выражения областей планирования с вероятностными эффектами» (PDF) . Технический отчет CMU-CS-04-167 . Питтсбург: Университет Карнеги-Меллона.
- ^ Батлер, Р .; Муньос, К. (2006). "Язык подготовки абстрактных планов" (PDF) . Технический отчет НАСА NASA / TM-2006-214518 .
- ^ Саннер, С. (2010). «Язык диаграмм реляционного динамического влияния (RDDL): описание языка» (PDF) . Неопубликованная рукопись с веб-сайта МПК-2011 .
- ^ Ковач Д.Л. (2012). «Мультиагентное расширение PDDL3.1» (PDF) . Труды 3-го семинара по международному конкурсу планирования (IPC) . 22-я Международная конференция по автоматизированному планированию и календарному планированию (ICAPS-2012). Атибая, Сан-Паулу, Бразилия. С. 19–27.
- ^ Ковач, DL; Добровецкий Т.П. (2013). Преобразование MA-PDDL в игры расширенной формы (PDF) . Acta Polytechnica Hungarica . 10 (8). С. 27–47. DOI : 10.12700 / APH.10.08.2013.8.2 .
- ^ Велозу, Мануэла. «PDDL на примере» (PDF) . Университет Карнеги-Меллона . Проверено 28 ноября 2015 .