Планирование языка определения предметной области

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

Обзор

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

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

Язык PDDL был создан, среди прочего, на основе решения проблем Стэнфордского исследовательского института (STRIPS) и языка описания действий (ADL). Язык PDDL использует принципы языков представления знаний , которые используются для создания онтологий , примером является язык веб-онтологий (OWL). Онтологии — это формальный способ описания таксономий и классификационных сетей, по существу определяющий структуру знаний для различных областей: существительные, представляющие классы объектов, и глаголы, представляющие отношения между объектами.

Последняя версия PDDL описана в определении синтаксиса BNF (форма Бэкуса – Наура) PDDL 3.1. Доступно несколько онлайн-ресурсов о том, как использовать PDDL. а еще книга.

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

PDDL1.2

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

PDDL2.1

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

PDDL2.2

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

PDDL3.0

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

PDDL3.1

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

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

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

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

ПДДЛ+

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

НДДЛ

NDDL ( — это ) язык определения нового домена НАСА появившийся примерно PDDL , ответ на в 2002 году. Его представление отличается от PDDL в нескольких отношениях: 1) оно использует представление переменных/значений (временные шкалы/действия), а не пропозициональную логику / логику первого порядка , и 2) нет концепции состояний или действий, есть только интервалы (действия). ) и ограничения между этими видами деятельности . В этом отношении модели в NDDL больше похожи на схемы SAT- кодирования задач планирования, чем на модели PDDL. Из-за упомянутых различий планирование и выполнение планов (например, во время критических космических полетов) могут быть более надежными при использовании NDDL, но соответствие стандартным представлениям задач планирования, отличным от PDDL, может быть гораздо менее интуитивным, чем в случае PDDL.

МАПЛ

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

ОПТ

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

ППДДЛ

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

ПРИЛОЖЕНИЕ

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

РДДЛ

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

МА-ПДДЛ

MA-PDDL ) — это в 2012 году (т . представленное (MultiAgent PDDL минималистичное модульное расширение PDDL3.1, е. новый :multi-agent требование), что позволяет осуществлять планирование несколькими агентами и для них . Дополнение совместимо со всеми функциями PDDL3.1 и решает большинство проблем MAPL . Это добавляет возможность различать возможные разные действия разных агентов (т.е. разные возможности). Аналогично, разные агенты могут иметь разные цели и/или показатели . Предварительные условия действий теперь могут напрямую относиться к одновременным действиям (например, действиям других агентов), и, таким образом, действия с взаимодействующими эффектами могут быть представлены в общем и гибком виде (например, предположим, что для выполнения некоторого действия необходимы как минимум 2 агента). lift действие по поднятию тяжелого стола в воздух, иначе стол остался бы на земле (это пример конструктивной синергии, но деструктивную синергию также можно легко представить в MA-PDDL)). простой механизм наследования и полиморфизма действий, целей и метрик (при условии, что Более того, в качестве своего рода синтаксического сахара в MA-PDDL также был введен :typing объявлено). Поскольку PDDL3.1 предполагает, что среда детерминирована и полностью наблюдаема, то же самое справедливо и для MA-PDDL, т.е. каждый агент может свободно получать доступ к значению каждого состояния в любой момент времени и наблюдать за каждым ранее выполненным действием каждого агента, а также совпадающие действия агентов однозначно определяют следующее состояние среды. Позже это было улучшено за счет добавления эффектов частичной наблюдаемости и вероятностных эффектов (опять же в форме двух новых модульных требований: :partial-observability и :probabilistic-effectsсоответственно, последний вдохновлен 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))))
  (:action pick
   :parameters (?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))))
  (:action drop
   :parameters (?obj ?room ?gripper)
   :precondition (and (ball ?obj)
                      (room ?room)
                      (gripper ?gripper)
                      (carry ?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)
           (gripper right)
           (at-robby rooma)
           (free left)
           (free right)
           (at ball1 rooma)
           (at ball2 rooma))
    (:goal (at ball1 roomb)))