Войти
Язык определения домена планирования (PDDL ) является попыткой стандартизации Планирование искусственного интеллекта (AI) языков. Впервые он был разработан Дрю МакДермотт и его коллегами в 1998 году (вдохновленный, среди прочего, STRIPS и ADL ), главным образом, чтобы сделать международный журнал 1998/2000 . Планирование конкуренции (IPC) возможно, а затем эволюционировало с каждым соревнованием. «Принятие общего формализма для описания областей планирования способствует гораздо большему повторному использованию исследований и позволяет более прямое сравнение систем и подходов, и, следовательно, поддерживает более быстрый прогресс в этой области. Общий формализм - это компромисс между выразительной силой (в которой развитие в значительной степени обусловлено потенциальными приложениями) и прогрессом фундаментальных исследований (которые поощряют разработку на хорошо изученных основах). Роль общего формализма как средства коммуникации для обмена требует, чтобы он был обеспечен четкой семантикой ».
Это был официальный язык 1-го и 2-го МПК в 1998 и 2000 годах соответственно. Он разделил модель задачи планирования на две основные части: (1)описание домена и (2) соответствующее описание проблемы . Такое разделение модели позволяет интуитивно разделить те элементы, которые (1) присутствуют в каждой конкретной проблеме предметной области (эти элементы содержатся в описании предметной области), и те элементы, которые (2) определяют конкретную проблему планирования (эти элементы содержатся в описании проблемы). Таким образом, несколько описаний проблем могут быть связаны с одним и тем же описанием домена (точно так же, как могут существовать несколько экземпляров класса в ООП (объектно-ориентированное программирование) или в OWL (язык веб-онтологий) например). Таким образом, предметная область и связующее описание проблемы образуют PDDL-модель задачи планирования, и в конечном итоге это вход программного обеспечения планировщика (обычно независимого от предметной области планировщика ИИ), которое стремится решить данную задачу. проблема планирования через некоторый подходящий алгоритм планирования. Выход планировщика не указан в PDDL, но обычно это полностью или частично упорядоченный план (последовательность действий, некоторые из которых могут выполняться иногда даже параллельно). Теперь давайте посмотрим на содержимое домена PDDL1.2 и описание проблемы в целом.... (1) Описание домена состояло из определения имени домена ., определение требований (для объявления тех элементов модели планировщику, которые фактически использует PDDL-модель), определение иерархии типов объектов (точно так же, как иерархия классов в ООП ), определение постоянных объектов (которые присутствуют в каждой проблеме в домене), определение предикатов (шаблоны для логических фактов), а также определение возможных действий (оператор-схемы с параметрами, которые должны быть обоснованы / инстанциированы во время выполнения). Действия имели параметры (переменные, экземпляры которых можно создавать с помощью объектов), предварительные условия и эффекты . Последствия действий также могут быть условными (когда-эффекты) .. (2) Описание проблемы состояло из определения имя-проблемы, определения соответствующего имя-домена, определение всех возможных объектов (атомов в логической вселенной), начальных условий (начальное состояние среды планирования, соединение истинных / ложные факты) и определение целевых состояний (логическое выражение фактов, которые должны быть истинными / ложными в целевом состоянии среды планирования). Таким образом, в конечном итоге PDDL1.2 уловил «физику» детерминированной одноагентной дискретной полностью доступной среды планирования.
Это был официальный язык 3-го МПК в 2002 году. Он представил числовые потоки ( например, для моделирования небинарных ресурсов, таких как уровень топлива, время, энергия, расстояние, вес,...), план-метрики (чтобы позволить количественную оценку планов, а не только ориентированных на цели, но планирование, основанное на полезности, т.е. оптимизация, минимизация / максимизация показателей) и длительные / непрерывные действия (которые могут иметь переменную недискретную длину, условия и эффекты). В конце концов, PDDL2.1 позволил представить и решить гораздо больше реальных проблем, чем исходная версия языка.
Это был официальный язык детерминированного трека 4-го IPC в 2004 году. Он ввел производные предикаты (для моделирования зависимость данных фактов от других фактов, например, если A достижимо из B, а B доступно из C, тогда A достижимо из C (транзитивность)), и синхронизированные начальные литералы (для моделирования экзогенных событий происходящие в данный момент независимо от выполнения плана). В конечном итоге PDDL2.2 расширил язык несколькими важными элементами, но это не было радикальным развитием по сравнению с PDDL2.1 после PDDL1.2.
Это был официальный язык детерминированного трека 5-го МПК в 2006 году. Он ввел ограничения траектории состояний ( жесткие ограничения в форме модально-логических выражений, которые должны быть истинными для траектории состояния, созданной во время выполнения плана, который является решением данной задачи планирования) и предпочтений (мягкие-ограничения в форме логических выражений, подобных жестким ограничениям, но в их удовлетворении не было необходимости, хотя это могло быть включено в план-метрику, например, чтобы максимизировать количество удовлетворенных предпочтений или просто измерить качество плана) включить планирование на основе предпочтений. В конце концов, PDDL3.0 обновил выразительность языка, чтобы справиться с недавними важными изменениями в планировании.
Это был официальный язык детерминированного трека 6-го и 7-го МПК в 2008 и 2011 годах соответственно. Он представил object-fluents (т.е. диапазон функций теперь может быть не только числовым (целым или действительным), но также может быть любым типом объекта). Таким образом, PDDL3.1 адаптировал язык еще больше к современным ожиданиям с синтаксически, казалось бы, небольшим, но семантически довольно значительным изменением выразительности.
Последняя версия языка - PDDL3.1. Определение синтаксиса BNF (форма Бэкуса – Наура) для PDDL3.1 можно найти среди ресурсов домашней страницы IPC-2011 или домашней страницы IPC-2014.
Это расширение PDDL2.1 примерно 2002–2006 гг. Обеспечивает более гибкую модель непрерывного изменения за счет использования автономных процессов и события . Ключевым моментом, который предоставляет это расширение, является возможность моделировать взаимодействие между поведением агента и изменениями, инициированными средой агента. Процессы выполняются с течением времени и оказывают непрерывное влияние на числовые значения. Они инициируются и завершаются либо прямым действием агента, либо событиями, запускаемыми в среде. Эта трехчастная структура называется моделью старт-процесс-остановка. Различают логические и числовые состояния: предполагается, что переходы между логическими состояниями происходят мгновенно, в то время как занятие данного логического состояния может продолжаться с течением времени. Таким образом, в PDDL + выражения непрерывного обновления могут встречаться только в эффектах процесса. Действия и события, которые являются мгновенными, ограничиваются выражением дискретных изменений. Это вводит вышеупомянутое трехэтапное моделирование периодов непрерывного изменения: (1) действие или событие запускают период непрерывного изменения числовой переменной, выраженной посредством процесса; (2) процесс реализует непрерывное изменение числовой переменной; (3) действие или событие, наконец, останавливает выполнение процесса и прекращает его действие на числовую переменную. Комментарий: цели плана могут быть достигнуты до остановки активного процесса.
NDDL (New D omain D efinition L anguage) - это НАСА. ответ на PDDL примерно с 2002 года. Его представление отличается от PDDL в нескольких отношениях: 1) он использует представление переменной / значения (временные рамки / действия), а не пропозициональное / логика первого порядка, и 2) отсутствует концепция состояний или действий, только интервалы (действия) и ограничения между этими действиями . В этом отношении модели в NDDL больше похожи на схемы для SAT кодировок задач планирования, чем на модели PDDL. Из-за упомянутых различий планирование и выполнение планов (например, во время критических космических миссий) может быть более надежным при использовании NDDL, но соответствие стандартным представлениям задач планирования, отличным от PDDL, может быть гораздо менее интуитивным, чем в случае PDDL.
MAPL (Multi- A gent P lanning L anguage, произносится как «клен») является расширением PDDL2.1 примерно с 2003 года. Это довольно серьезная модификация исходного языка. Он вводит непропозициональные переменные состояния (которые могут быть n-арными: истина, ложь, неизвестно или что-то еще). Он вводит временную модель, заданную с помощью модальных операторов (до, после и т. Д.). Тем не менее в PDDL3.0 была дана более тщательная временная модель, которая также совместима с исходным синтаксисом PDDL (и это просто необязательное дополнение). MAPL также вводит действия, продолжительность которых будет определяться во время выполнения, и явную синхронизацию плана, которая реализуется посредством связи между агентами на основе речевого акта. Это предположение может быть искусственным, поскольку агенты, выполняющие параллельные планы, не обязательно должны взаимодействовать, чтобы иметь возможность работать в многоагентной среде. Наконец, MAPL вводит события (эндогенные и экзогенные) для обработки параллелизма действий. Таким образом, события становятся частью планов явно и назначаются агентам с помощью функции управления, которая также является частью плана.
OPT (Ontology с P олиморфными T типами) был глубоким расширением PDDL2.1, разработанным Дрю МакДермотт примерно с 2003 по 2005 год (с некоторым сходством с PDDL +). Это была попытка создать универсальную нотацию для создания онтологий, определенных как формализованные концептуальные основы для областей планирования, о которых должны рассуждать приложения планирования. Его синтаксис был основан на PDDL, но он имел гораздо более сложную систему типов, которая позволяла пользователям использовать конструкции более высокого порядка, такие как явные λ-выражения, позволяющий осуществлять эффективный вывод типа (т.е. не только объекты предметной области имели типы (типы уровня 0), но и функции / флюэнты, определенные выше этих объектов, имели типы в виде произвольных отображений (типы уровня 1), которые могут быть универсальными, поэтому их параметры (домен и диапазон общего сопоставления) могут быть определены с помощью переменных, которые могут иметь тип еще более высокого уровня (тип уровня 2), не говоря уже о том, что сопоставления могут быть произвольными, т. е. домен или диапазон функции (например, предикат, свободное владение числами) может быть любого типа уровня 0/1/2. Например, функции могут отображаться из произвольных функций в произвольные функции...). OPT в основном предназначался для (почти) восходящей совместимости с PDDL2.1. Обозначение для процессов и длительных действий было заимствовано в основном из PDDL + и PDDL2.1, но помимо этого OPT предлагал множество других значительных расширений (например, структуры данных, небулевские переменные, возвращаемые значения для действий, ссылки между действиями, иерархическое раскрытие действий, иерархия определений доменов, использование пространств имен для совместимости с семантической сетью ).
PPDDL (Probabilistic PDDL ) 1.0 был официальным языком вероятностного трека 4-го и 5-го МПК. в 2004 и 2006 годах соответственно. Он расширил PDDL2.1 с помощью вероятностных эффектов (дискретное, общее распределение вероятностей по возможным эффектам действия), плавных вознаграждений (для увеличения или уменьшения общего вознаграждения плана в эффектах действий), награды за цель (за вознаграждение за траекторию состояния, которая включает в себя хотя бы одну цель-состояние) и бегунок за достижение цели (которые были верны, если состояние -траектория включала хотя бы одну цель-состояние). В конечном итоге эти изменения позволили PPDDL1.0 реализовать планирование Марковского процесса принятия решений (MDP), где может быть неопределенность в переходах между состояниями, но среда полностью наблюдаема для планировщика / агента.
APPL (Abstract P lan P reparation L anguage) - это новый вариант NDDL с 2006 года, который является более абстрактным, чем большинство существующих языков планирования, таких как PDDL или NDDL. Целью этого языка было упростить формальный анализ и спецификацию задач планирования, которые предназначены для критически важных с точки зрения безопасности приложений, таких как управление питанием или автоматическое рандеву на будущих пилотируемых космических кораблях. APPL использовал те же концепции, что и NDDL, с расширением действий, а также некоторые другие концепции, но все же его выразительная сила намного меньше, чем у PDDL (в надежде на то, что он останется надежным и формально проверяемым).
RDDL (Rэляционный D динамическое влияние D играмма L язык) был официальным языком следа неопределенности 7-й IPC в 2011 году. Концептуально он основан на PPDDL1.0 и PDDL3.0, но практически это совершенно другой язык как синтаксически, так и семантически. Введение частичной наблюдаемости - одно из наиболее важных изменений в RDDL по сравнению с PPDDL1.0. Он позволяет эффективно описывать марковские процессы принятия решений (MDP) и частично наблюдаемые марковские процессы принятия решений (POMDP) , представляя все (текущее состояние, наблюдения, действия,...) с переменными. Таким образом, RDDL значительно отличается от PDDL. Заземленный RDDL соответствует динамическим байесовским сетям (DBN) аналогично PPDDL1.0, но RDDL более выразителен, чем PPDDL1.0.
MA-PDDL (Multi A gent PDDL ) - это минималистичное модульное расширение PDDL3.1 введено в 2012 г. (т. е. новое требование : мультиагент), которое позволяет планировать для нескольких агентов и для нескольких агентов. Дополнение совместимо со всеми функциями PDDL3.1 и решает большинство проблем MAPL. Он добавляет возможность различать возможные разные действия разных агентов (то есть разные возможности). Точно так же разные агенты могут иметь разные цели и / или показатели . Предварительные условия действий теперь могут напрямую относиться к параллельным действиям (например, действиям других агентов), и, таким образом, действия с взаимодействующими эффектами могут быть представлены в общем, гибком виде (например, предположим, что необходимы как минимум 2 агента. выполнить действие поднять, чтобы поднять тяжелый стол в воздух, иначе стол остался бы на земле (это пример конструктивной синергии, но разрушительная синергия также может быть легко представлена в MA-PDDL)). Более того, как своего рода синтаксический сахар, простой механизм наследования и полиморфизма действий, целей и показателей также был введен в MA-PDDL (при условии, что : объявлен тип). Поскольку PDDL3.1 предполагает, что среда является детерминированной и полностью наблюдаемой, то же самое верно и для MA-PDDL, т.е. каждый агент может получить доступ к значению каждого состояния в любой момент времени и наблюдать за каждым ранее выполненным действием. каждого агента, а также одновременные действия агентов однозначно определяют следующее состояние среды. Позже это было улучшено путем добавления эффектов частичной наблюдаемости и вероятностных эффектов (опять же, в форме двух новых модульных требований, : частичная наблюдаемостьи : вероятностные эффекты, соответственно, последний основан на PPDDL1.0, и оба они совместимы со всеми предыдущими функциями языка, включая : multi-agent).
Это определение домена экземпляра STRIPS для автоматизированного планирования робота с двумя захватами.
(define (domain gripper-strips) (: predicates (room? r) (ball? b) (gripper? g)) (at-robby? r) (at? b? r) (free? g) (carry? o? g)) (: action 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): предварительное условие (and (ball? obj) (room? room) (gripper? gripper) (at? obj? room) (at-robby? room) (free? gripper)): effect (and (carry? obj? gripper) ( нет (at? ob j? room)) (not (free? gripper)))) (: action drop: parameters (? obj? room? gripper): precondition (and (ball? obj) (room? room) (gripper? gripper) (переносить ? obj? gripper) (at-robby? room)): effect (and (at? obj? room) (free? gripper) (not (carry? obj? gripper)))))
И в этом проблема определение, которое воплощает предыдущее определение домена с конкретной средой с двумя комнатами и двумя шарами.
(define (problem strips-gripper2) (: domain gripper-strips) (: objects rooma roomb ball1 ball2 left right) (: init (room rooma) (room roomb) (ball ball1) (ball ball2) (gripper left) (захват справа) (at-robby rooma) (свободный левый) (свободный правый) (at ball1 rooma) (at ball2 rooma)) (: goal (at ball1 roomb)))
