Язык определения домена планирования
Язык программирования планирования

Язык определения области планирования ( PDDL ) — это попытка стандартизировать языки планирования искусственного интеллекта (ИИ) . [1] Впервые он был разработан Дрю Макдермоттом и его коллегами в 1998 году, в основном для того, чтобы сделать возможным проведение Международного конкурса по планированию (IPC) 1998/2000 годов, а затем развивался с каждым конкурсом. Стандартизация, предоставляемая PDDL, имеет то преимущество, что делает исследования более пригодными для повторного использования и легко сопоставимыми, хотя и за счет некоторой выразительной силы по сравнению с системами, ориентированными на определенную область. [2]

Обзор

PDDL — это понятный человеку формат для задач автоматизированного планирования, который дает описание возможных состояний мира, описание набора возможных действий, определенное начальное состояние мира и определенный набор желаемых целей. Описания действий включают предпосылки действия и последствия действия. PDDL разделяет модель задачи планирования на две основные части: (1) описание домена тех элементов, которые присутствуют в каждой задаче проблемной области, и (2) описание проблемы, которое определяет конкретную задачу планирования. Описание проблемы включает начальное состояние и цели, которые должны быть достигнуты. В примере ниже дано определение домена и пример описания проблемы для автоматизированного планирования робота с двумя захватными руками.

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

Язык PDDL был вдохновлен, среди прочего, Stanford Research Institute Problem Solver (STRIPS) и Action description language (ADL). Язык PDDL использует принципы языков представления знаний , которые используются для создания онтологий , примером является Web Ontology Language (OWL). Онтологии — это формальный способ описания таксономий и сетей классификации, по сути определяющий структуру знаний для различных доменов: существительные, представляющие классы объектов, и глаголы, представляющие отношения между объектами.

Последняя версия PDDL описана в определении синтаксиса BNF (форма Бэкуса–Наура) PDDL 3.1. [3] Доступно несколько онлайн-ресурсов по использованию PDDL, [1] [4] [5] [6] [7] а также книга. [8]

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

PDDL1.2

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

PDDL2.1

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

PDDL2.2

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

PDDL3.0

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

PDDL3.1

Это был официальный язык детерминированного направления 6-го и 7-го МПК в 2008 и 2011 годах соответственно. [15] [16] [17] Он ввел объектно-флюентные (т.е. диапазон функций теперь мог быть не только числовым (целым или вещественным), но и любым объектным типом). Таким образом, PDDL3.1 еще больше адаптировал язык к современным ожиданиям с синтаксически, казалось бы, небольшим, но семантически весьма существенным изменением в выразительности.

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

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

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

ПДДЛ+

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

НДДЛ

NDDL ( New Domain Definition Language ) — это ответ NASA на PDDL примерно с 2002 года. [ 19] [20] Его представление отличается от PDDL в нескольких отношениях: 1) он использует представление переменных/значений (временные шкалы/действия), а не пропозициональную / первопорядковую логику , и 2) нет концепции состояний или действий, только интервалы (действия) и ограничения между этими действиями . В этом отношении модели в NDDL больше похожи на схемы для кодирования SAT задач планирования, чем на модели PDDL. Из-за упомянутых различий планирование и выполнение планов (например, во время критических космических миссий) могут быть более надежными при использовании NDDL, но соответствие стандартным представлениям задач планирования, отличным от PDDL, может быть гораздо менее интуитивным, чем в случае PDDL.

МАПЛ

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

ОПТ

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

ПППДЛ

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

АППЛ

APPL ( Abstract Plan P reparation Language ) — это новый вариант NDDL от 2006 года, который более абстрактен, чем большинство существующих языков планирования, таких как PDDL или NDDL. [ 24 ] Целью этого языка было упрощение формального анализа и спецификации задач планирования, которые предназначены для критически важных для безопасности приложений, таких как управление питанием или автоматизированное рандеву в будущих пилотируемых космических кораблях. APPL использовал те же концепции, что и NDDL, с расширением действий , а также некоторые другие концепции, но все же его выразительная сила намного меньше, чем у PDDL (в надежде остаться надежным и формально проверяемым).

РДЛ

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

MA-PDDL

MA-PDDL ( M ulti A gent PDDL ) — это минималистичное модульное расширение PDDL3.1, представленное в 2012 году (т. е. новое :multi-agentтребование), которое позволяет осуществлять планирование несколькими агентами и для них. [26] Дополнение совместимо со всеми функциями PDDL3.1 и решает большинство проблем MAPL. Оно добавляет возможность различать возможные различные действия разных агентов (т. е. разные возможности). Аналогично разные агенты могут иметь разные цели и/или метрики . Предпосылки действий теперь могут напрямую ссылаться на параллельные действия (например, действия других агентов), и, таким образом, действия с взаимодействующими эффектами могут быть представлены общим, гибким способом (например, предположим, что для выполнения liftдействия по подъему тяжелого стола в воздух требуется не менее 2 агентов, иначе стол останется на земле (это пример конструктивной синергии, но деструктивную синергию также можно легко представить в MA-PDDL)). Более того, как своего рода синтаксический сахар, в MA-PDDL также был введен простой механизм наследования и полиморфизма действий, целей и метрик:typing (предполагая , что объявлено). Поскольку PDDL3.1 предполагает, что среда детерминирована и полностью наблюдаема, то же самое справедливо и для MA-PDDL, т. е. каждый агент может получить доступ к значению каждого состояния, текущего в любой момент времени, и наблюдать каждое ранее выполненное действие каждого агента, а также одновременные действия агентов однозначно определяют следующее состояние среды. Это было улучшено позже путем добавления частичной наблюдаемости и вероятностных эффектов (опять же, в виде двух новых модульных требований :partial-observabilityи :probabilistic-effects, соответственно, последнее было вдохновлено PPDDL1.0, и оба они совместимы со всеми предыдущими функциями языка, включая :multi-agent). [27]

Пример

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

(определить (полосы захвата домена) (:предикаты (комната ?r) (мяч ?b) (захват ?g) (at-robby ?r) (в ?b ?r) (свободный ?g) (нести ?o ?g)) (:действие переместить :параметры (?от ?до) :предусловие (и (комната ?из) (комната ?в) (at-robby ?из)) :эффект (и (at-robby ?to) (не (at-robby ?from)))) (:действие выбрать :параметры (?объект ?комната ?захват) :предусловие (и (мяч ?объект) (комната ?комната) (захват ?захват) (в ?объекте ?комнате) (at-robby ?room) (бесплатно ?захват)) :эффект (и (перенести ?объект ?захват) (не (в ?объекте ?комнате)) (не (свободный ?захватчик)))) (:действие падение :параметры (?объект ?комната ?захват) :предусловие (и (мяч ?объект) (комната ?комната) (захват ?захват) (переносить ?объект ?захват) (at-robby ?room)) :эффект (и (в ?объекте ?комнате) (свободный ?захват) (не (нести ?объект ?захват))))

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

(определить (проблемные полоски-захват2) (:domain gripper-strips) (:объекты комнатаа комнатаб мяч1 мяч2 лево право) (:init (комната rooma) (комната) (мяч мяч1) (мяч мяч2) (захват левый) (захват правый) (at-robby rooma) (свободно слева) (свободное право) (в комнате ball1) (в комнате ball2a)) (:цель (в комнате ball1b)))

Ссылки

  1. ^ ab Haslum, Patrik. «Writing Planning Domains and Problems in PDDL». Австралийский национальный университет . Получено 5 февраля 2024 г.
  2. ^ ab Fox, M.; Long, D. (2002). "PDDL+: Моделирование непрерывных эффектов, зависящих от времени". Труды 3-го Международного семинара NASA по планированию и составлению расписаний для космоса . CiteSeerX 10.1.1.15.5965 . 
  3. ^ Ковач, Дэниел Л. (2011). "BNF-определение PDDL 3.1" (PDF) . Университет Хаддерсфилда .
  4. ^ "Справочное руководство по PDDL". GitHub . Получено 5 февраля 2024 г.
  5. ^ Грин, Адам. «Что такое Planning Domain Definition Language (PDDL)?». Planning.wiki . Получено 5 февраля 2024 г.
  6. ^ "Planning Domain Definition Language (PDDL)". GitHub . Получено 5 февраля 2024 г.
  7. ^ Хельмерт, Мальте (16 октября 2014 г.). «Введение в PDDL» (PDF) . Университет Торонто .
  8. ^ Хаслум, Патрик; Липовецкий, Нир; Магацзени, Даниэле; Муиз, Кристиан (апрель 2019 г.). Введение в язык определения предметной области планирования. Спрингер Чам . дои : 10.1007/978-3-031-01584-7. ISBN 978-3-031-00456-8.
  9. ^ Макдермотт, Дрю; Галлаб, Малик; Хоу, Адель ; Ноблок, Крейг; Рам, Эшвин; Велосо, Мануэла; Уэлд, Дэниел; Уилкинс, Дэвид (1998). "PDDL — язык определения области планирования" (PDF) . Технический отчет CVC TR98003/DCS TR1165 . Нью-Хейвен, Коннектикут: Йельский центр вычислительного зрения и управления. CiteSeerX 10.1.1.51.9941 . 
  10. ^ Фокс, М.; Лонг, Д. (2003). "PDDL2.1: Расширение PDDL для выражения доменов временного планирования" (PDF) . Журнал исследований искусственного интеллекта . 20 : 61–124 . doi :10.1613/jair.1129. S2CID  1397894.
  11. ^ Эделькамп, С.; Хоффманн, Дж. (2003). "PDDL2.2: Язык для классической части 4-го Международного конкурса по планированию" (PDF) . Технический отчет № 195. Institut für Informatik. Архивировано из оригинала (PDF) 2016-10-12.
  12. ^ Gerevini, A.; Long, D. (2006). «Предпочтения и мягкие ограничения в PDDL3» (PDF) . Труды семинара ICAPS-2006 по предпочтениям и мягким ограничениям в планировании . стр.  46–54 .
  13. ^ Геревини, А.; Лонг, Д. (2005). «Планирование ограничений и предпочтений в PDDL3» (PDF) . Технический отчет RT 47.08.2005 . Отделение электроники для автоматизации, Университет дельи Студи ди Брешиа.
  14. ^ Gerevini, A.; Long, D. (2005). "BNF Description of PDDL3.0" (PDF) . Неопубликованная рукопись, ссылка на которую находится на веб-сайте IPC-5 .
  15. ^ Хельмерт, М. (2008). «Изменения в PDDL 3.1». Неопубликованное резюме с веб-сайта IPC-2008 .
  16. ^ Kovacs, DL (2011). "BNF Definition of PDDL3.1: totally corrected, without comments" (PDF) . Неопубликованная рукопись с веб-сайта IPC-2011 .
  17. ^ Kovacs, DL (2011). "BNF Definition of PDDL3.1: partial corrected, with comments/explainments" (PDF) . Неопубликованная рукопись с веб-сайта IPC-2011 .
  18. ^ Фокс, М.; Лонг, Д. (2006). «Моделирование смешанных дискретно-непрерывных доменов для планирования» (PDF) . Журнал исследований искусственного интеллекта . 27 : 235–297 . arXiv : 1110.2200 . CiteSeerX 10.1.1.75.6792 . doi : 10.1613/jair.2044. S2CID  5730335. 
  19. ^ Фрэнк, Дж.; Йонссон, А. (2002). "Атрибутное и интервальное планирование на основе ограничений" (PDF) . Технический отчет . Моффетт-Филд, Калифорния: Исследовательский центр имени Эймса в НАСА.
  20. ^ Бернардини, С.; Смит, Д.Э. (2007). "Разработка доменно-независимого управления поиском для EUROPA2" (PDF) . Труды семинара по эвристике для доменно-независимого планирования: прогресс, идеи, ограничения, проблемы . 17-я Международная конференция по автоматизированному планированию и составлению расписаний (ICAPS-2007). Род-Айленд, США.
  21. ^ Бреннер, М. (2003). "Язык многоагентного планирования" (PDF) . Труды семинара по PDDL . 13-я Международная конференция по автоматизированному планированию и составлению расписаний (ICAPS-2003). Тренто, Италия.
  22. ^ Макдермотт, Д. (2005). "OPT Manual Version 1.7.3 (Reflects Opt Version 1.6.11) * DRAFT **" (PDF) . Неопубликованная рукопись с веб-сайта Дрю Макдермотта .
  23. ^ Younes, HLS; Littman, ML (2004). "PPDDL 1.0: расширение PDDL для выражения областей планирования с вероятностными эффектами" (PDF) . Технический отчет CMU-CS-04-167 . Питтсбург: Университет Карнеги-Меллона.
  24. ^ Батлер, Р.; Муньос, К. (2006). "Язык подготовки абстрактного плана" (PDF) . Технический отчет НАСА NASA/TM-2006-214518 .
  25. ^ Саннер, С. (2010). «Язык реляционных динамических диаграмм влияния (RDDL): описание языка» (PDF) . Неопубликованная рукопись с веб-сайта IPC-2011 .
  26. ^ Kovacs, DL (2012). "Мультиагентное расширение PDDL3.1" (PDF) . Труды 3-го семинара по Международному конкурсу планирования (IPC) . 22-я Международная конференция по автоматизированному планированию и составлению расписаний (ICAPS-2012). Атибая, Сан-Паулу, Бразилия. С.  19–27 .
  27. ^ Kovacs, DL; Dobrowiecki, TP (2013). «Преобразование MA-PDDL в игры в расширенной форме» (PDF) . Acta Polytechnica Hungarica . 10 (8): 27– 47. doi : 10.12700/APH.10.08.2013.8.2 .
  28. ^ Велосо, Мануэла. "PDDL на примере" (PDF) . Университет Карнеги-Меллона . Получено 28.11.2015 .
Взято с "https://en.wikipedia.org/w/index.php?title=Planning_Domain_Definition_Language&oldid=1267846847"