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

Проблема формального описания предметной области и задачи планирования является частным случаем задачи представления знаний интеллектуальными системами. В настоящее время разработано несколько основных способов представления знаний. Но исторически так сложилось, что в качестве формы представления знаний для систем планирования применяется только один способ — аппарат математической логики. Логика хороша тем, что может использоваться и для представления знаний и для выполнения рассуждений. Видимо поэтому ее и посчитали наиболее пригодной...

Несмотря на долгую историю, проблема разработки удобного языка описаний действий и доменов планирования остается актуальной и по сей день. С одной стороны, мы хотели бы оперировать языком, достаточно выразительным, чтобы можно было описывать множество разнообразных задач планирования, приложив к этому минимум усилий. С другой стороны, язык должен быть достаточно ограничен, чтобы можно было строить эффективные алгоритмы, с ним работающие.

Представление знаний в задачах планирования уходит корнями к работам Джона Маккарти (John McCarthy). В 1959 году он публикует статью, посвященную задаче создания интеллектуальной системы, способной к разумному поведению [McCarthy J., 1959]. Развивая идею разумной программы и пытаясь дать определение интеллекта вообще, Маккарти приходит к понятию "разумного поведения" компьютерной программы (a program that acting intelligently) в окружающей среде (мире). Он пишет: "сущность обладает интеллектом, если: 1) она имеет адекватную модель мира; 2) достаточно разумна, чтобы ответить, основываясь на этой модели, на широкий круг вопросов; 3) может получать дополнительную информацию из внешнего мира, когда это требуется; 4) может выполнять действия во внешнем мире в соответствии со своими целями и физическими возможностями". В этом высказывании мы видим требование к описанию модели мира и действий — необходимых компонентов для постановки задачи планирования.

Маккарти пишет, что, во-первых, нужно определить, какую часть мира следует рассматривать (моделировать) и как информация о мире и законах его изменения должна быть представлена в машине. Последний вопрос (как представлять информацию) приводит к дилемме: представлять информацию о мире через общие законы или через частные случаи (факты). Маккарти решает, что наиболее адекватным способом представления модели мира является множество фактов о мире, сформулированных посредством математической логики. Он пишет:

В 1963 году Маккарти публикует способ описания модели мира и ее изменений в рамках формализма математической логики [McCarthy J., 1963]. В этой работе он вводит понятие ситуационного исчисления (situational calculus) — формального аппарата для построения модели мира и выполнения рассуждений о воздействиях на мир. Такого рода формализм использовался в системе QA3 Кордела Грина. Позднее, в 1969 году Маккарти дорабатывает этот формализм [McCarthy J., 1969]. Именно эту последнюю версию мы здесь и рассмотрим.

Ситуационное исчисление (Situational Calculus)

Знакомство с формализмом начнем с введения основных понятий. Ситуация (situation) — это полное состояние мира (complete state of the universe) в некоторый момент времени. Обозначим Sit множество всех возможных ситуаций. Т.к. мир очень большой, мы никогда не сможем полностью описать ситуацию. Мы можем описать только ряд фактов о ней. Эти факты могут использоваться для вывода других фактов:

• о той же самой ситуации;
• о ситуациях, которые возникнут в будущем;
• о ситуациях, которые могут быть достигнуты из данной ситуации.

Таким образом, мы можем рассматривать не только ситуации, которые действительно случаются, но и гипотетические ситуации, которые возникли бы, если бы были выполнены некоторые действия.

Для задания частичной информации о ситуации вводится понятие флюенты. Флюента (fluent) — это функция, областью определения которой является множество всех возможных ситуаций Sit. Если областью значений флюенты является множество {истина, ложь}, то флюента называется пропозиционной (propositional). Если же областью значений является Sit, то флюента называется ситуационной (situational).

Флюенты могут быть значениями других функций. Например, функция raining(x) может возвращать флюенту. Тогда мы можем строить выражения такого вида raining(x)(s) или просто raining(x, s). Если это выражение возвращает "истина", то семантически это можно трактовать, например, как утверждение "в городе x идет дождь в ситуации s". Если же флюента raining(x)(s) возвращает "ложь", то, соответственно, получим "в городе x не идет дождь в ситуации s".

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

Переход от одной ситуации к другой также можно осуществлять при помощи флюент. Для этого используются ситуационные флюенты. Маккарти приводит пример, как можно описывать случай, когда выполнение действия влечет переход к новой ситуации. Рассмотрим этот пример.

Пусть у нас есть ситуационная флюента

result (p, a, s)

, где p — некоторое лицо, исполняющее действие; a — некоторое действие и s — ситуация. Значением флюенты result (p, a, s) является ситуация, которая получается в результате применения лицом p действия a в ситуации s.

При помощи result можно строить аксиомы, которые будут отражать результат выполнения некоторого действия. Например, формула:

Has(person, key, s) & Fits(key, safe) & At(person, safe, s) —> Open( safe, result(person, opens(safe, key), s) )

может рассматриваться как схема аксиомы, постулирующей, что "если в ситуации s лицо person обладает ключом key и этот ключ подходит к сейфу safe, то в ситуации, полученной в результате применения действия для открывания сейфа opens(safe, key), будет справедливо утверждение о том, что сейф открыт — Open(safe, ...). Т.е. мы фактически объявили, что если в некоторой ситуации справедливы какие-то утверждения, то, применив некоторое действие, мы получим другую ситуацию, в которой справедливо какое-то другое утверждение. Чтобы оперировать последовательностью действий, мы должны лишь в качестве последнего аргумента для result передавать другой result. Тогда последовательность действий определяется по правилам вычисления композиции функций. Т.е. сначала выполняется действие, соответствующее наиболее вложенному result, затем внешнее по отношению к нему и т.д.

Очевидно, что такой формализм полностью укладывается в рамки логики предикатов первого порядка.

Проблемы ситуационного исчисления

Ситуационное исчисление обладает рядом серьезных недостатков. Математическая строгость формализма и желание удержаться в рамках математической логики привело к тому, что очень сложно описывать модели мира и действия таким образом. Ознакомимся, в чем суть этих проблем.

Первая проблема получила название проблемы фрейма (frame problem).

Естественный способ сделать описание действия кратким — сконцентрироваться на описании изменений, вызываемых действием, оставляя за кадром флюенты (факты), на которые действие не влияет. Поступая так, мы столкнемся со следующей ситуацией.

Пусть, например, мы обладаем описанием некоторой ситуации (естественно частичным описанием, т.е. множеством фактов). Назовем ее начальной ситуацией — s₀. Пусть в описание ситуации входят следующие факты, выраженные флюентами:
1. Has (person1, phoneBook, s₀)
2. AtHome (person2, s₀)
и пусть имеются следующие аксиомы:
a1. (" p1, p2, s) [ Has (p1, phoneBook, s) —> KnowNumber (p1, p2, result (p1, seekNumber(p2, phoneBook), s)) ]
a2. (" p1, p2, s) [ KnowNumber (p1, p2, s) & AtHome (p2, s) —> Talking (p1, p2, result (p1, call(p2), s))

Первые две флюенты говорят о том, что в начальной ситуации у некоторого лица person1 есть телефонная книга, и некоторое лицо person2 находится дома. Аксиома a1 утверждает, что если у некоторого лица есть телефонная книга, то он может найти телефонный номер любого другого лица (действие seekNumber). Аксиома a2 утверждает, что если у некоторого лица есть телефонный номер другого лица, и это другое лицо находится дома, то можно с ним поговорить, выполнив звонок (действие call).

Полагаясь на здравый смысл, мы можем сделать следующее умозаключение. Если в начальной ситуации от лица person1 выполнить последовательность действий [ seekNumber(person2, phoneBook), call(person2) ], то мы достигнем ситуации, в которой происходит разговор между двумя персонами ( Talking(person1, person2, s_x) ). Однако ситуационное исчисление ставит препятствие в достижении этого простого умозаключения.

Выполнив первое действие, находясь в начальной ситуации, мы окажемся в новой ситуации — result(person1, seekNumber(person2, phoneBook), s₀). Будем обозначать ее s₁. Эта ситуация может быть вовсе не той же самой ситуацией, что и s₀. Считать так даже правильно, т.к. ситуация изменилась, и мы теперь знаем нужный нам телефонный номер. А это значит, что у нас есть пара фактов KnowNumber(person1, person2, s₁) и AtHome(person2, s₀), но они не являются посылкой для аксиомы a2, т.к. в них речь идет о различных ситуациях. Значит того, что мы описали, недостаточно. Чтобы последовательность действий сработала, необходимо переписать первую аксиому следующим образом:
a1*. (" p1, p2, s) [ Has (p1, phoneBook, s) & AtHome (p2, s) —>
           AtHome (p2, result (p1, seekNumber(p2, phoneBook), s)) & KnowNumber (p1, p2, result (p1, seekNumber(p2, phoneBook), s)) ]

Т.е. мы должны явно указать, что пока мы ищем телефонный номер person2, этот person2 свой дом не покинет. Используя такой подход, мы на чуть более крупных задачах получаем колоссальное количество аксиом. В этом случае и описание задачи планирования, и выполнение логического вывода становится значительной проблемой, которая получила название проблемы фрейма.

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

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

Вторая проблема ситуационного исчисления называется проблемой косвенных эффектов (ramification problem), смысл которой заключается в том, что очень сложно описать все эффекты действия. Так, например, перемещение шкафа роботом из одной комнаты в другую повлечет за собой перемещение и всех книг внутри шкафа, и освобождение места в комнате, и изменение внешнего вида комнаты, и многие другие изменения. Отсюда вытекает вопрос, какой способ является наиболее адекватным для описания таких изменений? Описание всех эффектов в аксиомах перехода к новой ситуации потребует очень большого количества таких аксиом.

В ситуационном исчислении мы можем кроме аксиом, отвечающих за переход к новой ситуации посредством действий, задавать еще и любые другие аксиомы. Вывод с использованием этих аксиом может отражаться на ситуации. Т.е. при помощи этих аксиом могут быть обнаружены дополнительные факты о ситуации.

Вообще все аксиомы в ситуационном исчислении можно разделить на два класса. К первому классу относятся аксиомы, которые осуществляют переход от одной ситуации к другой (посредством действий). Ко второму — относятся аксиомы, которые используются для вывода каких-то фактов в рамках одной и той же ситуации. Т.е. они добавляют пропозиционные флюенты, описывающие ту же самую ситуацию.

Когда мы выполняем действие, мы осуществляем переход к новой ситуации. При этом сама аксиома, реализующая действие, постулирует ряд фактов о новой ситуации. Но на основании этих фактов (выведенных из аксиомы, реализующей действие) могут быть выведены другие факты об этой новой ситуации посредством других аксиом. Можно сказать, что этот дополнительный вывод представляет собой косвенный эффект действия, приведшего к новой ситуации. Таково решение проблемы косвенных эффектов, предлагаемое ситуационным исчислением.

Теперь взглянем на эти вещи с позиций задачи планирования. Когда мы хотим достичь какую-то цель (используя рассуждения, а не перебор), мы должны подобрать такое действие, которое эту цель сделает истинной в некоторой модели мира (ситуации). Но из-за косвенных эффектов мы должны будем рассматривать не только описания действий (аксиом, реализующих действия), но и все остальные аксиомы!

Третья проблема носит названия проблемы ограничительных условий (qualification problem). Суть ее состоит в том, что очень трудно перечислить все условия, которые могут препятствовать выполнению действия. Например, пусть робот должен выполнить действие переместить шкаф из северного угла комнаты в южный. Выполнению такой задачи может препятствовать множество вещей. Шкаф может оказаться слишком тяжелым; пол в южном углу может оказаться слишком хрупким; конфигурация мебели в комнате может быть такой, что нет возможности протащить шкаф из северной части комнаты в южную; может случиться пожар; и множество других причин. При этом описание некоторых причин может быть весьма сложным (как, например, конфигурация мебели). Таким образом, может потребоваться очень сложное описание предусловия действия (аксиомы, реализующей действие).

Последние две проблемы актуальны и по сей день. Особенно это важно при неполном описании модели мира. Эффективный способ их решения пока не найден.

С появлением планировщика STRIPS, которой, по сути, является родоначальником всех современных планировщиков, появился и новый формализм для описания действий и доменов планирования. Рассмотрим его подробнее.

STRIPS-формализм

Именно планировщику STRIPS мы обязаны современной терминологией в языках описания действий и доменов [Fikes, Nilsson, 1971]. Файкс и Нильсон (авторы STRIPS) отходят от ситуационного исчисления и модели, основанной исключительно на математической логике. Они вводят структурное понятие для описания мира, а именно, понятие состояния (в первоисточнике используется термин "модель мира"). Таким образом, они предложили моделировать изменения в мире, как переходы мира из одного состояния в другое.

Итак, в любой момент времени мир находится в некотором состоянии. Действия могут переводить мир в другие состояния. Состояние (state) в STRIPS представляет собой множество фактов о конкретном моменте эволюции мира, записанных при помощи формул исчисления предикатов первого порядка. Все, что постулируют эти формулы, а также все, что выводимо из этих формул, считается истинным в данном состоянии мира (в данный момент эволюции мира). Все прочие утверждения считаются ложными. Это последнее допущение в литературе называют допущением замкнутости мира (closed-world assumption). Все атомарные формулы во множестве формул, описывающих состояние, не должны иметь свободных переменных.

Изменение мира происходит вследствие применения действий. Действие преобразует состояние мира. Или же можно сказать, что мир переходит в новое состояние, а действие являет собой правило перехода. Можно также подойти к понятию действия, как к функции. Тогда действие принимает в качестве параметра текущее состояние мира и выдает в качестве результата новое состояние.

Действия описываются при помощи специальных конструкций, состоящих из трех элементов: имени, предусловия и эффекта. Предусловие позволяет определить, возможно ли применение действия в некотором состоянии и задается означенной формулой логики предикатов первого порядка. Если эта формула выводима из формул, входящих в описание состояния, то действие считается применимым в данном состоянии. Эффект описывается двумя списками, содержащими означенные формулы логики предикатов первого порядка. Один из списков называется списком удаления (delete list). Он состоит из формул, которые станут гарантированно ложными в новом состоянии (полученном вследствие применения действия). Другой список, называемый списком добавления (add list), содержит формулы, которые станут гарантированно истинными в новом состоянии. Все формулы, которые содержатся в состоянии, в котором действие применяется, но не упоминающиеся в эффекте действия, будут содержаться и в результирующем состоянии действия. Это последнее утверждение в литературе называют STRIPS-допущением (STRIPS assumption). STRIPS-допущение разрешает проблему фрейма, детерминируя, что изменится после выполнения действия, а что останется неизменным.

Действия группируются в классы действий, называемые схемами действий (action schema). Именно схемы действий использовались в STRIPS для описания домена. Схема действия — это абстракция действия, в которой константы в описании предусловия и эффекта заменены (частично или полностью) параметрами. Подстановка в схему действия конкретных значений вместо параметров являет собой обратный переход (от схемы к действию). Параметризация дает нам сжатое описание целой группы действий.

Рассмотрим пример того, как схемы действий описываются в STRIPS. Пусть мы, например, хотим описать перемещения робота между двумя комнатами. Мы можем описать это при помощи следующей схемы действия.

GoToAnOtherRoom (door, room₁, room₂)
precondition = InRoom(ROBOT, room₁) & Connects(door, room₁, room₂)
delete list = { InRoom(ROBOT, room₁) }
add list = { InRoom(ROBOT, room₂) }

В этом примере схема действия GoToAnOtherRoom (пойти в какую-либо другую комнату) имеет три параметра: door (дверь), room₁ (комната 1), room₂ (комната 2). Формула предусловия является параметризованной конъюнкцией литералов. Первый литерал InRoom(...), говорит о том, что действие выполнимо, только если робот находится в комнате, обозначенной параметром room₁. Здесь константа ROBOT не заменена параметром. В этом нет смысла, если в предметной области есть только один робот. Второй литерал предусловия Connects(...) требует, чтобы комнаты, между которыми выполняется перемещение, соединялись дверью. Список удаления состоит из одной формулы, которая утверждает, что после выполнения действия (полученного из этой схемы) робот больше не будет находиться в комнате, из которой он ушел. В списке добавления, наоборот, присутствует формула, указывающая, что робот появится в комнате, в которую он совершает перемещение. Подставив вместо параметров конкретные константы, мы получим конкретное действие перемещения робота (из вполне определенной комнаты в другую вполне определенную комнату через конкретную дверь).

Список удалений требует аккуратного с собой обращения. Например, когда некоторая формула X в описании состояния выведена из предикатов A и B, то при удалении (действием) предиката A или предиката B, должна удалиться и формула X. В STRIPS такой механизм реализуется посредством установления связей между зависимыми формулами.

Кроме этих базовых вещей, авторами STRIPS был предложен дополнительный механизм, делающих язык более гибким. Они вводят специальный метасимвол "$", который может быть указан в качестве аргумента предиката. Этот метасимвол обозначает произвольное значение аргумента и может использоваться в списках удаления схем действий. Например, допустима запись RobotIn($) в списке удалений, обозначающая, что все предикаты RobotIn(...) должны быть удалены из текущей модели мира.

Еще один момент, на который стоит обратить внимание, это то, что авторы допускают применение функциональных символов в качестве параметров предикатов (в формулах списков добавления и удаления). Потенциально, это означает, что возможно бесконечное количество состояний, порождаемых действиями. Такое допущение выводит нас за рамки классического планирования (мир должен быть конечен). Поэтому следует аккуратно пользоваться этой возможность.

Несмотря на то, что STRIPS-подход решает проблему фрейма, в нем имеется ряд недостатков, как выразительного, так и формального характера. Авторы STRIPS ставили перед собой конкретную практическую задачу (управление роботом) и мало заботились о формальной стороне вопроса. В частности о недостаточной формализации языка STRIPS писал в 1987 году Владимир Лифшиц [Lifschitz V., 1987], хотя и не он первый заострил на этом внимание.

Критика STRIPS

Лифшиц отмечает сразу два недостатка STRIPS-языка. Первый момент обусловлен необходимостью удалять неатомарные формулы. Второй связан с использованием метасимвола "$" в симметричных предикатах.

Рассмотрим подробнее проблему с неатомарными формулами. Пусть у нас есть мир, в котором существует комната с несколькими выключателями. Пусть также в начальном состоянии все выключатели находятся в состоянии "выкл". Это начальное состояние можно описать двумя способами в рамках STRIPS-языка. Во-первых, можно перечислить множество атомарных формул

Status (switch_i, OFF)

для каждого (i-ого) выключателя. Во-вторых, можно написать одну квантифицированную формулу:

(" x) [ Type (x, LIGHT_SWITCH) —> Status (x, OFF) ]

Предположим теперь, что у нас есть действие, которое включает один выключатель: TurnOnLight. Это действие должно содержать в списке удаления формулу Status (switch_i, OFF). Т.е. после включения выключателя, состояние этого выключателя перестает быть "выкл".

Если мы имеем описание начального состояния в виде квантифицированной формулы, то действие TurnOnLight не сможет корректно отработать список удаления. Из состояния в STRIPS удаляются только те формулы, которые явно перечислены в списке удаления, или были выведены при их помощи. Наша квантифицированная формула не была получена в результате вывода и не содержится в списке удаления. Значит она не будет удалена. Даже если бы она была связана с формулой Status (switch_i, OFF), как результат вывода, то ее удаление не было бы корректной операцией, т.к. это приводило бы к потере информации. Мы бы утратили информацию о состоянии всех других выключателей.

Т.е. использовать такие неатомарные формулы нужно очень аккуратно. Наличие их в начальном состоянии или списке добавления действия может привести к некорректной модели рассуждений. Для того, чтобы STRIPS-язык был формально корректным, необходимо, чтобы все неатомарные формулы были бы истинными во всех состояниях мира. Т.е. их нельзя было бы удалять или добавлять. Примером такой формулы может послужить формула, описывающая то, что если дверь соединяет комнаты 1 и 2, то она соединяет и комнаты 2 и 1. Это утверждение (если мы говорим о нашем мире) всегда справедливо, является аксиомой и не может измениться от какого-либо воздействия.

Второй недостаток, который выделил Лифшиц в STRIPS-языке, это необходимость с большой осторожностью пользоваться метасимволом "$". Опасность возникает при использовании симметричных (по смыслу) предикатов. Например, СОСЕДИ($, Предмет1) по смыслу эквивалентен записи СОСЕДИ(Предмет1, $). Однако, если в списке удалений мы укажем только один из вариантов, система может прийти в противоречивое состояние. Лифшиц предложил во избежание таких проблем предварительно производить унификацию симметричных предикатов (т.е. выбирать единую форму записи для всей системы).

ADL (Action Definition Language)

Как упоминалось выше, STRIPS, кроме формальной несостоятельности, оказался еще и недостаточно выразительным, чтобы кратко описывать сложные проблемы. В ответ на этот недостаток появился новый язык ADL, предложенный в 1989 году Эдвином Педнолтом (Edwin Pednault) [Pednault E.P.D., 1989].

ADL большей частью унаследовал идеологию и терминологию STRIPS. Но формализация и выразительные способности этого языка оказались значительно выше. Мы рассмотрим только отличительные особенности этого языка по отношению к STRIPS.

1. В ADL предлагается представлять состояния при помощи множества позитивных и негативных литералов. Т.е. здесь явно указывается, какие свойства мира истинны, а какие ложны. Если в STRIPS мы считали, что все что не упомянуто в состоянии считается ложным, то здесь мы полагаем, что неупомянутые литералы имеют неопределенное значение истинности. Т.е. в ADL мы отходим от допущения о замкнутости мира.

2. Эффект не разделяется на список добавления и удаления. Литералы, на которые производится воздействие, представляются в эффекте конъюнкцией литералов.. Если в эффекте записана формула (P & ¬Q), то это значит, что в новое состояние будут добавлены литералы P и ¬Q, а также будут удалены ¬P & Q.

3. К числу достоинств ADL причисляют также возможность использовать в описании цели квантифицированные и дизъюнктивные формулы. В STRIPS явно не указывается, что их использование запрещено, тем не менее, мы отметим и этот момент.

4. В ADL появилась возможность задавать условные эффекты действий. Это можно сделать при помощи конструкции when P: E, которую можно трактовать так. Если P истинно в текущем состоянии, то эффект E будет произведен действием. Наряду с условным эффектом, могут быть другие эффекты действия, которые будут иметь место в любом случае, если действие будет применено.

5. Предложено считать предикат (x = y) элементом языка.

6. Переменные и параметры в формулах могут быть типизированы. Это может существенно сократить множество возможных подстановок и здорово сказаться на эффективности.

Некоторое время ADL пользовался популярностью, хотя наряду с ним разрабатывались и другие языки. Но уже через 9 лет появился новый, еще более мощный язык, который является и по сей день стандартом для описания задач планирования. Речь идет о языке PDDL. Именно ему мы и посвятим оставшуюся часть этой главы.

PDDL (Planning Domain Definition Language)

Язык PDDL появился в 1998 году в ответ на потребность разработки единого языка для всех видов планировщиков. Потребность такая возникла в связи с предложением проводить соревнования планировщиков, чтобы эмпирически оценить производительность и эффективность тех или иных методов планирования. К тому же, единая нотация позволила бы разработчикам планировщиков легко обмениваться описаниями задач планирования. PDDL был разработан группой авторов [McDermott D., et al., 1998] и впервые представлен на первых международных соревнованиях планировщиков (IPC — International Planning Competition).

К настоящему моменту вышло несколько версий языка. Это обусловлено увеличением сложности задач и выходом за рамки классического планирования. Следом за PDDL v1.2 (от 1998 года) в 2003 году появился PDDL v2.1 для доменов с действиями, имеющими длительность [Fox, Long, 2003]. В 2004 году произошло разделение языка на две ветви: для планирования c детерминированными эффектами действий (PDDL v2.2) [Edelkamp, Hoffmann, 2004] и для вероятностных эффектов (PPDDL v1.0) [Younes, Littman, 2004]. В 2005 году опубликована третья версия языка (PDDL v3.0) [Gerevini, Long, 2005], в которой появилась возможность задания более жестких ограничений на структуру плана, а также возможность описания желательных (но не обязательных) целей и ограничений. Традиционно, выход новой версии языка приурочен к очередному соревнованию IPC.

Здесь мы рассмотрим основные концептуальные положения первой версии языка PDDL и наиболее важные и интересные изменения в последующих его версиях.

PDDL предназначен для описания "физики" домена (physics), т.е. того, какие предикаты бывают, какие действия возможны, какова структура составных действий и каковы эффекты действий. Кроме этого, большинство современных планировщиков требуют некоторого рода "подсказок" (advice), таких как, аннотации о том, какие действия для удовлетворения каких целей использовать, или при каких условиях какие составные действия выполнять. Авторы PDDL не стремились обеспечить поддержку таких дополнений-подсказок как часть языка. Почти все планировщики потребовали бы расширения нотации, но каждый планировщик захотел бы расширить ее своим индивидуальным способом. Вместо этого был предложен общий механизм для решения этого вопроса. Определенными синтаксическими конструкциями можно вводить любые дополнения в язык, но не каждый планировщик обязан эти конструкции рассматривать.

Таким образом, главным девизом языка PDDL стала фраза "physics, not advice", которая говорит, что во главу угла ставится описание физики предметной области вообще, а не специфичных для разных методов планирования параметров.

PDDL version 1.2

При помощи PDDL можно описывать домены планирования и задачи планирования (привязанные к определенным доменам). Каждое такое описание оформляется отдельным файлом. Т.е. описание домена физически отделено от описания задачи. Следовательно, легко можно описать несколько задач для одного и того же домена. Домен планирования декларирует:

• объекты каких типов могут фигурировать в описании задачи планирования;
• виды отношений между объектами и виды свойств объектов;
• константные сущности предметной области;
• определения схем действий;
• определения схем аксиом.

Задача планирования декларирует:

• к какому домену относится эта задача;
• множество рассматриваемых объектов;
• начальное состояние (отношения между объектами и их свойства);
• цель.

Разработчики языка хотели, чтобы PDDL мог использоваться любым планировщиком. Но каждый планировщик умеет работать только с конструкциями определенной сложности (для которых он спроектирован). Например, STRIPS-планировщик не может работать с условными эффектами, т.к. не рассчитан на них. Чтобы планировщик мог быстро определить, может ли он работать с предложенным ему описанием домена, каждое такое описание объявляет требования (requirements) к способностям планировщика. Так, если у некоторого описания домена в PDDL указано требование :conditional-effects (условные эффекты), то STRIPS-планировщику нет смысла работать с такой декларацией. В этом случае необходимо найти (или составить) описание, пригодное для STRIPS-планировщика (если это возможно).

Для описания языка мы будем использовать синтаксис БНФ. Наклонным шрифтом будем выделять ключевые слова. Угловые скобки заключают имя синтаксического элемента (нетерминальный символ). Квадратные скобки окружают необязательные элементы. Звездочка (*) означает "ноль или более"; плюс (+) означает "один или более".

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

Из этой декларации видно, что описание домена состоит из имени домена (<name>), множества требований к планировщику (requirements), множества типов объектов (types), множества констант (constants), множества видов отношений между объектами и видов свойств объектов (predicates), множества возможных схем действий (<action-def>^*) и множества схем аксиом домена (<axiom-def>^*).

Имя домена — <name> — это некоторое символьное наименование для домена.

Поле :requirements предназначено для формализации требований к планировщику. Требования задаются при помощи флагов-требований, начинающихся с символа двоеточие. В качестве примеров таких флагов можно привести следующие:
    :typing (допустима типизация объектов),
    :equality (предикат равенства считается встроенным в язык),
    :conditional-effects (допустимы условные эффекты),
    :domain-axiom (допустимы аксиомы).
Если требования опущены, то это поле по умолчанию имеет значение :strips. Это означает, что описание домена (и задач к нему) ограничено выразительными способностями STRIPS-языка (естественно с иными синтаксическими конструкциями). В PDDL :strips обозначает подмножество (по выразительным способностям) STRIPS языка с более жесткими ограничениями на допустимые формулы. Предусловия, эффекты и цели в этом случае должны быть конъюнкциями литералов.

Поле :types допустимо только в том случае, если среди требований указан флаг :typing, и служит для перечисления допустимых типов объектов. Вообще, в PDDL есть два встроенных типа: object и number. Кроме этого, можно создавать произвольное количество типов, производных от данных. Именно эти производные типы и задаются в поле :types. Конструкция <types-definition> может быть описана так:

Здесь <type_name> и <base_type_name> являются символьными именами типов. В первом случае базовым типом будет считаться object, во втором — тот тип, который соответствует записи <base_type_name>.

Поле :constants имеет тот же синтаксис, что и :types, но семантика этого поля иная. Здесь имена рассматриваются как новые константы в рамках домена, которые могут быть типизированы. Формально <constants-definition> можно задать так

Поле :predicates состоит из списка деклараций предикатов. Для объявления аргументов каждого предиката вновь используется синтаксис типизированных списков (как и для констант).

В отличие от имен типов и констант, имена параметров начинаются со знака вопроса.

Схема действия в PDDL описывается следующей конструкцией.

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

Список :parameters является типизированным списком имен параметров схемы действия, т.е. аргументы схемы действия. Используется синтаксис аналогичный синтаксису описания аргументов предиката, приведенному выше.

:precondition — некое описание цели (goal-definition), которая должна быть удовлетворена до применения действия. Если не определены предусловия, то действие всегда выполнимо. Описание цели определяется следующим образом

Таким образом, предусловие задается формулой исчисления предикатов первого порядка с рядом ограничений (например, недопустимы функциональные символы). Используется префиксная форма записи операций. Ключевое слово exists заменяет квантор существования, а forall — квантор всеобщности. Последние четыре определения допустимы только при наличии определенных требований к планировщику (не будем здесь рассматривать это подробно). Все предикаты, которые упоминаются в атомарных формулах и литералах должны быть объявлены в домене в поле :predicates.

:effect — описание эффекта действия, которое также задается формулой. Но ограничения на формулу еще более жесткие. Не допустимы or- и not-формулы (однако, отрицательные литералы допустимы). Недопустимо использовать квантор существования. Как и в STRIPS, значения истинности атомарных формул сохраняются с течением времени (STRIPS-допущение). В отличие от STRIPS PDDL-определение схемы действия не имеет списка удалений — вместо удаления (on a b) декларируется (not (on a b)).

Чтобы продемонстрировать, как в PDDL описываются схемы действий, вернемся к примеру с перемещением робота между комнатами.

(:action GoToAnOtherRoom
   :parameters (?door - doorType ?room1 ?room2 - roomType)
   :precondition (and (inroom ROBOT ?room1) (connects ?door ?room1 ?room2))
   :effect (and (not (inroom ROBOT ?room1)) (inroom ROBOT ?room2) )

Кроме схем действий в описании домена могут фигурировать схемы аксиом. Это корректно, если указано требование :domain-axiom. Аксиомы, по сути, являются логическими формулами, которые декларируют связь между высказываниями в рамках состояния модели мира (в отличие от действий, которые определяют связь между последовательными состояниями). Аксиома определяется следующей конструкцией.

Фактически эта запись сводится к следующей логической формуле

(" :vars) [ :context —> :implies ]

Т.е. в поле :vars перечисляются (типизированные) переменные, которые стоят под квантором всеобщности. :context определяет посылку аксиомы-импликации, а :implies определяет заключение импликации. В посылке и заключении могут фигурировать переменные из :vars.

В качестве примера можно привести аксиому, постулирующую, что если один объект лежит на другом, то он находится выше другого. Это можно записать так.

(:axiom
   :vars (?x ?y - object)
   :context (on ?x ?y)
   :implies (above ?x ?y)
)

Второй важной частью PDDL являются конструкции для описания задачи планирования. Рассмотрим структуру, при помощи которой описывают задачи (опять же упрощенный вариант).

Как и домен, задача обладает именем.

Каждая задача планирования имеет связь с доменом планирования, для которого эта задача составлена. Имя домена указывается в поле :domain.

Поле :objects позволяет задать множество типизированных объектов в дополнение к тем, что указаны в поле :constants домена.

Поле :init содержит описание начального состояния в виде множества означенных литералов. Как правило, начальное состояние задается при помощи множества положительных литералов, которые считаются истинными утверждениями о состоянии мира. Не упомянутые отношения (предикаты) считаются ложными в начальном состоянии. Т.е. работает допущение о закрытости мира. Это справедливо, если явно не указано требование домена :open-world.

Цель :goal имеет тот же формат, что и ранее описанное предусловие схемы действия.

Кроме упомянутых синтаксических конструкций, PDDL версии 1.2 имеет средства для описания:

• флюент;
• вычисляемых выражений;
• условных эффектов действий;
• иерархических структур действий (для иерархических планировщиков);
• ограничений сохранности (Своего рода дополнительных целей, которые должны быть истинны в целевом состоянии, если они были истины в начальном состоянии. Если ограничение сохранности нарушается где-то в процессе планирования, то оно должно быть восстановлено в дальнейшем.);
• ограничений на длину целевого плана.

Подробнее с этими механизмами можно ознакомиться в работе-первоисточнике [McDermott D., et al., 1998].

PDDL version 2.1

В версии 2.1 появляется ряд расширений, направленных на работу с числовыми выражениями (для моделирования работы с ресурсами), метриками плана (для поиска оптимального плана) и действиями, имеющими длительность. Чтобы ликвидировать разрыв между исследованиями и практическим применением теории планирования, планировщики должны быть способны работать с такими важными категориями как время и количество. PDDL v2.1 расширяет возможности предыдущей версии языка как раз в этом направлении. Версия 2.1 обратно совместима с наиболее активно использовавшимся фрагментом версии 1.2 (однако некоторые вещи исчезли из языка, например, аксиомы), т.е.:

• практически все существовавшие PDDL домены являются корректными доменами в PDDL v2.1;
• корректные планы являются корректными с точки зрения PDDL v2.1.

К числу основных нововведений и доработок языка относятся:

• более развитые средства для работы с числовыми выражениями (доменные функции);
• метрики качества плана;
• действия, имеющие длительность (дискретные и непрерывные);
• параллелизм действий, имеющих длительность.

Кратко опишем эти языковые средства.

Доменные функции (domain functions) ставят в соответствие некоторому множеству объектов домена числовую величину. Значение этой величины может изменяться посредством применения действий. Из доменных функций и математических операций можно строить числовые выражения (numeric expressions). Числовые выражения могут использоваться для описания условий и эффектов. Условие с использованием числовых выражений — это всегда сравнение двух числовых выражений. В эффекте может использоваться операция присваивания (assign) для изменения величины доменной функции. Можно выполнять относительное присваивание: увеличение (increase) или уменьшение (decrease) на заданную величину. Числовые выражения не могут выступать в качестве термов (параметров предикатов и действий), т.к. это приведет к бесконечному количеству инстанциаций схем действий (множество чисел бесконечно), а значит к бесконечному дереву поиска. Фактически, доменные функции и числовые выражения с их использованием являются более формальной заменой числовым флюентам (numeric fluents), которые могли появляться в качестве термов.

Для демонстрации того, как можно применять доменные функции опишем домен с действием "переливание воды из одного кувшина в другой".

(define (domain jug-pouring)
   (:requirements :typing :fluents)
   (:types jug)
   (:functions
       (amount ?j - jug)
       (capacity ?j - jug) )
   (:action pour
       :parameters (?jug1 ?jug2 - jug)
       :precondition (>= (- (capacity ?jug2) (amount (?jug2)) (amount ?jug1))
       :effect (and (assign (amount ?jug1) 0 ) (increase (amount ?jug2) (amount ?jug1)) ) )
)

Для того, чтобы пользоваться доменными функциями, необходимо, чтобы планировщик умел обращаться с флюентами (требование :fluents). В поле :functions мы определяем две доменные функции amount (количество воды в кувшине) и capacity (емкость кувшина). Далее описано действие pour (наливать) с двумя параметрами ?jug1 (из какого кувшина выливать) и ?jug2 (в какой кувшин лить). Предусловие декларирует, что если оставшегося места в целевом кувшине достаточно для вмещения всей воды из первого кувшина, то действие применимо. Эффект состоит из конъюнкции двух выражений. Первое выражение устанавливает (assign) количество воды в первом кувшине равным нулю. Второе выражение увеличивает (increase) объем воды во втором кувшине на количество воды, находившейся в первом кувшине до выполнения действия.

Для практического использования планировщиков важно обладать богатыми описательными средствами оценки качества плана. Количество действий в плане не всегда является адекватным критерием пригодности плана. Метрики плана расширяют описательные возможности PDDL в этом направлении. Метрика плана (plan metric) — это новое опциональное поле в описании задачи, которое определяет директиву для получения оптимального плана. Примерами таких директив могут служить: "минимизировать расход топлива", "минимизировать время выполнения плана", "максимизировать уровень качества продукции" и т.д. В одной задаче можно указать несколько различных (непротиворечивых) метрик.

Для того чтобы определить метрику в терминах определенной величины (quantity), необходимо обеспечить поддержку этой величины в домене планирования. Например, если метрика определяется через "величину расхода топлива", то эта величина должна быть установлена в ноль в начальном состоянии и изменяться каждый раз, когда происходит расход топлива.

В качестве примера, приведем описание метрики "минимизировать расход топлива". Синтаксически это будет строка (в рамках описания задачи) следующего вида:

(:metric minimize (fuel-used))

Использование метрик довольно сложный вопрос, скрывающий ряд подводных камней, и пользоваться ими нужно аккуратно. Довольно часто встречаются домены, которые содержат действия как увеличивающие, так и уменьшающие количественную величину, фигурирующую в метрике. Например, пусть есть домен, содержащий действия "движение автомобиля" и его "перезаправка". Тогда метрика "минимизировать расход топлива" при перемещении из одного города в другой вовсе не означает поиск оптимального пути, т.к. автомобиль может проехать по любой дороге и потом заправиться. Более того, планировщик может добавить довольно большое число действий по дозаправке, т.к. они улучшают качество плана, хотя и не являются необходимыми в таком количестве.

Таким образом, метрики — это простой инструмент для оценки качества готового плана. Но каким образом метрики могут направлять процесс поиска, пока открытый вопрос.

Следующим ключевым новшеством PDDL v2.1 являются длительные действия (durative actions) и параллелизм их исполнения. Предложены две формы таких действий: дискретные длительные действия (discretised durative actions) и непрерывные длительные действия (continuous durative actions).

Моделирование временных зависимостей в дискретных длительных действиях осуществляется посредством временных меток для предусловий и эффектов. Аннотация предусловия определяет, когда данное условие должно соблюдаться, чтобы действие было выполнимо: перед началом выполнения действия (at start), перед применением конечного эффекта действия (at end) или в открытом интервале между at start и at end (over all). Аннотация эффекта определяет, является ли эффект немедленным (at start) или отложенным (at end).

Рассмотрим пример дискретного длительного действия, осуществляющего погрузку объекта на грузовик при помощи крана. Действие имеет следующее описание.

(:durative-action load-truck
   :parameters (?t - truck ?l - location ?o - cargo ?c - crane)
   :duration (= ?duration 5)
   :condition (and
      (at start (at ?t ?l))
      (at start (at ?o ?l))
      (at start (empty ?c))
      (over all (at ?t ?l))
      (at end (holding ?c ?o)) )
   :effect (and
      (at start (holding ?c ?o))
      (at start (not (at ?o ?l)))
      (at end (in ?o ?t))
      (at end (not (holding ?c ?o))) )
)

В этом примере вместо ключевого слова :action мы видим его аналог для длительных действий :durative-action. Появляется новое поле :duration, где указывается длительность действий в некоторых условных единицах, которая может быть задана константно или числовым выражением (можно использовать неравенства). Ключевое слово :precondition заменено на :condition. В качестве условий указано, что в состоянии, к которому будет применено действие, должно выполняться следующее: грузовик находится в указанном месте (at ?t ?l), объект транспортировки находится там же (at ?o ?l) и кран не занят (empty ?c). Эти три условия описаны с временной меткой at start, которая говорит, что они должны быть соблюдены в момент начала применения действия. Если эти условия выполняются, то может быть произведен немедленный (at start) эффект, который заключается в поднятии краном объекта (holding ?c ?o) & (not (at ?o ?l)). После этого наступает интервал выполнения действия, для которого должны выполняться все условия, помеченные over all. Т.е. в нашем случае, грузовик не должен никуда уезжать, пока идет погрузка (at ?t ?l). При этом ничего не говориться о том, что кран должен по-прежнему держать груз. Важно лишь, чтобы к моменту применения отложенного эффекта этот груз был поднят краном — условие (at end (holding ?c ?o)). Т.е. в процессе выполнения действия (между его стартовой и конечной временными метками) другие действия могут пользоваться краном. Отложенное действие (с меткой at end) выполняет окончательную погрузку объекта в грузовик (in ?o ?t) & (not (holding ?c ?o)).

Дискретные длительные действия при определенных ограничениях можно использовать и для описания изменений числовых величин. Мы не будем здесь это рассматривать в деталях.

Изменение истинности логических формул всегда происходит моментально, что не всегда справедливо для числовых величин. Непрерывные длительные действия описывают изменения числовых величин в процессе выполнения действия (а не только в моменты at start и at end). Т.е. непрерывные эффекты действия не помечены временными метками. Они могут быть вычислены в любой момент интервала выполнения действия.

Для ссылки на непрерывно изменяющееся время в рамках длительности действия используется символ #t. Например, для отражения того факта, что уровень топлива самолета ?p уменьшается непрерывно, как функция от скорости потребления самолета, можно написать.

(:durative-action fly
   :parameters (?p - plane ?a ?b - airport)
   :duration (= ?duration (flight-time ?a ?b))
   :condition (and
      (at start (at ?p ?a))
      (over all (inflight ?p))
      (over all (>= (fuel-level ?p) 0)) )
   :effect (and
      (at start (inflight ?p))
      (at start (not (at ?p ?a)))
      (at end (at ?p ?b))
      (at end (not (inflight ?p)))
      (decrease (fuel-level ?p) (* #t (fuel-consumption-rate ?p))) )
)

Таким образом, в зависимости от времени полета и скорости потребления топлива мы получаем различные значения для количества оставшегося топлива. Мы можем узнать значение этой величины в любой момент выполнения действия. Этот механизм позволяет выражать более сложные зависимости между параллельно исполняющимися действиями.

В PDDL шкалу времени можно рассматривать, как множество интервалов (соответствующих состояниям), разделенных точками, в которых осуществляется деятельность по изменению состояния. Всякое изменение логических (в отличие от числовых) составляющих происходит мгновенно (в точках at start или at end длительного действия). Логическое высказывание истинно на полуоткрытом интервале, который закрыт слева и открыт справа (временная ось идет слева направо). Деятельность может изменять логическое состояние или значения доменных функций.

На параллелизм выполнения длительных действий (как дискретных, так и непрерывных) накладывается ряд ограничений. В корректном плане недопустимо, чтобы логическое высказывание было утверждено (как истинное) и опровергнуто в один и тот же момент времени. Более того, недопустимо, чтобы логическое условие было запрошено и утверждено в один и тот же момент. То же касается и числовых величин. Последние два утверждения сводятся к правилу, которое называется правило неподвижных целей (no moving targets rule). Оно гласит, что недопустима ситуация, когда в один и тот же момент времени, одно действие запрашивает значение некоторой величины, а другое — изменяет эту величину. В отличие от моментов времени (точек at start и at end), с интервалами деятельности дело обстоит иначе. В случае дискретных длительных действий числовые величины могут запрашиваться и изменяться на протяжении выполнения действия при условии, что всякое изменение не будет противоречить условиям с меткой over all. В случае непрерывных длительных действий числовые величины также могут одновременно запрашиваться и изменяться во время непрерывного процесса их изменения между метками at start и at end. Допустимы множественные одновременные изменения.

PDDL version 2.2

В PDDL версии 2.2 появились два новых элемента: выводимые предикаты (derived predicates) и отложенные начальные литералы (timed initial literals).

Выводимые предикаты по существу являются другим названием аксиом (которые были убраны из языка в версии 2.1). Домены, содержащие описания выводимых предикатов, помечены требованием :derived-predicates. Выводимые предикаты описываются в файле домена там, где раньше описывались аксиомы. Формально декларации выводимых предикатов должны соответствовать следующей БНФ.

Здесь atomic-formula соответствует заключению аксиомы, а goal-definition — посылке аксиомы. Отметим, что в версии языка 1.2 в качестве заключения выступал литерал. Здесь выразительность сузили до позитивного литерала. В качестве примера выводимого предиката можно привести описание аксиомы для отношения above.

(:derived
   (above ?x ?y)
   (or (on ?x ?y)
        (exists (?z) (and (on ?x ?z) (above ?z ?y)))
   )
)

Второе нововведение — отложенные начальные литералы — средство для декларации внешних событий, то есть фактов, которые в заранее известный планировщику момент времени станут истинными или ложными (не зависимо от того, какие действия будут исполняться). Такие события очень часто встречаются на практике. Например, события открытия и закрытия магазина в строго определенные часы. Признаком наличия отложенных литералов является требование домена :timed-initial-literals. Отложенные литералы могут использоваться только в доменах с длительными действиями (т.е. с отсчетом времени).

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

Наличие такой конструкции говорит о том, что в момент времени number в модели мира актуализируется литерал ground-literal. В качестве примера рассмотрим, как можно описать знания о том, что магазин работает с 8 до 20 часов.

(:init
   (at 8 (shop-open))
   (at 20 (not (shop-open)))
)

PDDL version 3.0

В PDDL v3.0 развитие языка пошло по двум важным (с практической точки зрения) направлениям.

• Во-первых, появились средства описания дополнительных ограничений на структуру плана. Сюда относятся ограничения на допустимость или необходимость присутствия тех или иных действий в плане, а также ограничения на промежуточные состояния в плане. Авторы предложили называть это ограничениями на траекторию плана (plan trajectory).
• Во-вторых, были добавлены средства описания предпочтений (preference) — желательных, но не необходимых целей и ограничений. При помощи весовых коэффициентов можно выражать значимость желательных целей и ограничений по отношению друг к другу. Эти средства позволяют сравнивать планы на качественном уровне. Чем больше наиболее значимых желательных целей (ограничений) мы достигнем, тем лучше (качественнее) считается план. С практической точки зрения, качественная оценка плана является очень важным вопросом. Во многих предметных областях мы сталкиваемся с задачами, имеющими большое количество решений. И тогда приходится выбирать лучшее. Более того, часто встречаются задачи, в которых не могут быть достигнуты все цели. В этом случае желательно найти план, достигающий хотя бы некоторые из них.

В языке появилось новое понятие — ограничение (constraint). Ограничение может быть жестким (strong) или слабым (soft). Жесткие ограничения на план должны быть выполнены, слабые — желательно, чтобы были выполнены (выражаются предпочтениями). Цель планирования (goal) является частным случаем ограничения; это ограничение на целевое состояние. Следовательно, цель также может быть жесткой (обязательной) или слабой (желательной).

Рассмотрим подробнее появившиеся нововведения. Сначала остановимся на ограничениях на траекторию. Ограничения на траекторию по состояниям (state trajectory constraints) — это условия, которые должны быть достигнуты где-то в последовательности состояний, которые будут посещены в процессе выполнения плана. Они выражаются посредством темпоральных модальных операторов (temporal modal operator), применяемых к формулам, описывающим требование. Авторами предлагается следующий набор модальных операторов:

• always — выполнение ограничения во всех (начальном, целевом и промежуточных) состояниях плана.
• sometime — выполнение ограничения хотя бы в одном из состояний плана.
• at-most-once — выполнение ограничения не более чем в одном состоянии плана.
• at end — выполнение ограничения в конечном состоянии (цель).
• within — выполнение ограничения не позднее, чем некоторый заданный момент времени (deadline).
• sometime-before — выполнение ограничения когда-либо до актуализации некоторого заданного факта (отношения или свойства).
• somtime-after — аналогично, но после актуализации заданного факта.
• always-within — выполнение ограничения в течение некоторого заданного интервала времени, причем сразу после актуализации заданного факта.
• hold-during — выполнение ограничения на заданном временном интервале.
• hold-after — выполнение ограничения после заданной временной метки.

Ограничения на траекторию задаются в новом поле :constraints в файле описания задачи. Кроме того, если задача планирования содержит ограничения на траекторию, то описание домена должно быть помечено требованием :constraints. В качестве примера рассмотрим запись следующего ограничения: "на хрупком (fragile) кубике не должно ничего находиться".

(:constraints
   (and   (always (forall (?b - block) (implies (fragile ?b) (clear ?b))))
   ...
   )
)

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

Синтаксис декларирования слабого ограничения описывается следующей схемой.

Отметим, что слабые ограничения — это частный случай ограничений, следовательно, в goal-definition могут фигурировать упоминавшиеся выше темпоральные модальные операторы. Имя предпочтения используется для его идентификации при расчете качественной оценки плана в дальнейшем. Несколько деклараций могут иметь одно и то же имя. Домены с предпочтениями помечаются требованием :preferences.

Качество плана рассчитывается путем начисления штрафов за нарушение слабого ограничения. Штраф рассчитывается при помощи выражения (is-violated <preference-name>). Значение этого выражения определяет, сколько слабых ограничений с таким именем не было выполнено в плане. Кроме того, выражения (is-violated ...), как правило, умножаются на некоторый весовой коэффициент, чтобы подчеркнуть значимость нарушения данного вида ограничения. Таким образом, именование слабых ограничений позволяет разным ограничениям задать разные штрафы. План считается тем качественнее, чем меньше его штраф по слабым ограничениям (при прочих равных условиях). Для декларации условия, оценивающего качество плана, используется механизм метрики плана (metric). При этом метрика может также содержать и обычные для этой конструкции составляющие (оптимизирующие условия) в некоторой комбинации со штрафами.

Рассмотрим следующий пример. Пусть наша цель планирования, попасть в Мадрид. При этом, мы хотели бы также побывать в Париже (желательная цель) и Праге (желательная цель). Причем, если бы пришлось выбирать между Прагой и Парижем, то мы выбрали бы Прагу. При всем этом, мы хотели бы потратить как можно меньше топлива (пусть для нас это играет гораздо большую роль, чем посещения упомянутых европейских столиц). В этом случае наши предпочтения можно было бы описать следующими целями.

(preference VisitParis (sometime (at Paris)))
(preference VisitPrague (sometime (at Prague)))

А оптимизирующее условие (дающее оценку качества плана) задать следующим образом.

(:metric minimize (+ (* 10 (fuel-used)) (* 2 (is-violated VisitPrague)) (is-violated VisitParis)))

Таким образом, задача планировщика минимизировать функцию, которая увеличивается на двойку, если мы не посетим Прагу, увеличивается на единицу, если мы не посетим Париж, и увеличивается на десять при использовании очередной единицы топлива.

Анонимные (имя в preference является опциональным элементом) слабые ограничения неявно включаются в метрику как слагаемые и имеют вес, равный 1, если метрика минимизирующая, или -1, если метрика максимизирующая.

В данном обзоре возможности PDDL v3.0 рассмотрены лишь частично. За подробной информацией обращайтесь к первоисточнику [Gerevini, Long, 2005].

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

Библиография.

Трофимов И.В.

апрель 2005
последнее обновление 10 мая 2006