Язык описания действий

В искусственном интеллекте язык описания действий ( ADL ) — это автоматизированная система планирования и планирования, в частности для роботов. Это считается развитием STRIPS . Эдвин Педно (специалист в области абстракции данных и моделирования, который с 1996 года был научным сотрудником IBM в исследовательской группе по абстракции данных). ^[1]) предложил этот язык в 1987 году. Это пример языка действий .

Происхождение [ править ]

Педно заметил, что выразительную силу STRIPS можно улучшить, если позволить эффектам оператора быть условными. Это основная идея ADL-A, которая представляет собой примерно пропозициональный фрагмент ADL, предложенный Педно. ^[2] с ADL-B, являющимся расширением -A. В расширении -B действия могут быть описаны с косвенными эффектами путем введения нового типа предложений: «статических законов». Третьим вариантом ADL является ADL-C, который подобен -B в том смысле, что его предложения можно разделить на статические и динамические законы, но с некоторыми дополнительными особенностями. ^[3]

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

В отличие от STRIPS, в ADL применяется принцип открытого мира : все, что не встречается в условиях, неизвестно (вместо того, чтобы считаться ложным). Кроме того, в то время как в STRIPS только положительные литералы и союзы разрешены разрешены отрицательные литералы и дизъюнкции , в ADL также .

Синтаксис ADL [ править ]

Схема ADL состоит из имени действия, необязательного списка параметров и четырех необязательных групп предложений, помеченных как «Precond», «Add», «Delete» и «Update».

Группа Precond представляет собой список формул, определяющих предварительные условия выполнения действия. Если набор пуст, в группу вставляется значение «ИСТИНА», и предварительные условия всегда оцениваются как условия удержания.

Условия добавления и удаления задаются группами «Добавить» и «Удалить» соответственно. Каждая группа состоит из набора предложений формы, показанной в левом столбце рисунка 1:

R представляет собой символ отношения
τ ₁ , ..., τ _n представляет собой члены
ψ представляет собой формулу
Последовательность z ₁ , ..., z _k представляет собой переменные символы, которые появляются в терминах τ ₁ , ..., τ _n , но не в списке параметров схемы действия.
x ₁ , ..., x _n — переменные символы, которые отличаются от переменных z ₁ , ..., z _n и не появляются в τ ₁ , ..., τ _n , ψ или списке параметров схема действий

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

Семантика ADL [ править ]

Формальная семантика ADL определяется четырьмя ограничениями. Первое ограничение состоит в том, что действия не могут изменять набор объектов, существующих в мире; это означает, что для каждого действия α и каждой пары текущего состояния/следующего состояния ( s , t ) ∈ a должно быть так, что область определения t должна быть равна области определения s .

Второе ограничение заключается в том, что действия в ADL должны быть детерминированными. Если ( s , t ₁ ) и ( s , t ₂ ) являются парами действия ∃ текущее состояние/следующее состояние, то должно быть так, что t ₁ = t ₂ .

Третье ограничение, включенное в ADL, заключается в том, что введенные выше функции должны быть представлены в виде формул первого порядка. Для каждого n -арного символа отношения R должна существовать формула Φ ^а_R ( x ₁ ,... , x _n ) со свободными переменными x ₂ , ..., x _n такими, что f ^а_R ( s ) определяется как:

t(R)=f_{R}^{a}(s)=(d_{1},\ldots ,d_{n})\in \operatorname {Dom} (s)^{n}\mid s[d_{1}/x_{1},\ldots ,d_{n}/x_{n}\models \Phi _{R}^{a}(x_{1},\ldots ,x_{n})]

Следовательно, F ( n ₁ , ..., x _n ) = y будет истинным после выполнения действия |= тогда и только тогда, когда Φ ^а_R ( x ₁ , ..., x _n , y ) было истинным заранее. Обратите внимание, что это требование представимости зависит от первого ограничения (домен f должен быть равен домену s ).

Четвертое и последнее ограничение, включенное в ADL, заключается в том, что набор состояний, в которых действие может быть выполнено, также должен быть представлен в виде формулы. Для каждого действия α , которое можно представить в ADL, должна существовать формула Π ^а со свойством, что s |= Π _a тогда и только тогда, когда существует некоторое состояние t , для которого ( s , t ) ∈ α (т.е. действие α выполнимо в состоянии s )

Сложность планирования [ править ]

С точки зрения вычислительной эффективности ADL можно расположить между STRIPS и Ситуационным исчислением. ^[4] Любую проблему ADL можно преобразовать в экземпляр STRIPS, однако существующие методы компиляции в худшем случае экспоненциальны. ^[5] Этот худший случай нельзя улучшить, если мы хотим сохранить длину планов полиномиально: ^[6] и, таким образом, ADL является строго более кратким, чем STRIPS.

Планирование ADL по-прежнему является проблемой, полной PSPACE. Большинство алгоритмов имеют полиномиальное пространство, даже если предусловия и эффекты представляют собой сложные формулы. ^[7]

Большинство наиболее эффективных подходов к классическому планированию внутренне используют представление, подобное STRIPS. Фактически, большинство планировщиков (FF, LPG, Fast-Downward, SGPLAN5 и LAMA) сначала преобразуют экземпляр ADL в экземпляр, который по сути является экземпляром STRIPS (без условных или количественных эффектов или целей).

Сравнение STRIPS и ADL [ править ]

Язык STRIPS допускает только положительные литералы в состояниях, тогда как ADL может поддерживать как положительные, так и отрицательные литералы. Например, допустимым предложением в STRIPS может быть Rich ∧ Beautiful. То же предложение можно выразить в ADL как ¬Baor ∧ ¬Ugly.
В STRIPS неупомянутые литералы являются ложными. Это называется предположением о закрытом мире . В ADL неупомянутые литералы неизвестны. Это известно как предположение об открытом мире.
В STRIPS мы можем найти только основные литералы в целях. Например, Богатый ∧ Красивый. В ADL мы можем найти количественные переменные в целях. Например, ∃ x At (P1, x ) ∧ At(P2, x ) — это цель наличия P1 и P2 в одном и том же месте в примере блоков
В STRIPS целями являются союзы, например (Богатый ∧ Красивый). В ADL цели могут включать соединения и дизъюнкции (Богатый ∧ (Красивый ∨ Умный)).
В STRIPS эффекты представляют собой соединения, но в ADL разрешены условные эффекты: когда P : E означает, что E является эффектом, только если P удовлетворено.
Язык STRIPS не поддерживает равенство. предикат равенства ( x = y ). В ADL встроен
В STRIPS нет поддержки типов, тогда как в ADL она поддерживается (например, переменная p :Person).

Выразительность языка STRIPS ограничена типами преобразований наборов формул, которые могут быть описаны на языке. Преобразования наборов формул с использованием операторов STRIPS выполняются путем удаления некоторых формул из набора, подлежащего преобразованию, и добавления новых дополнительных формул. Для данного оператора STRIPS формулы, подлежащие добавлению и удалению, фиксированы для всех наборов преобразуемых формул. Следовательно, операторы STRIPS не могут адекватно моделировать действия, последствия которых зависят от ситуаций, в которых они выполняются. Рассмотрим ракету, которую нужно запустить в течение определенного времени. Траектория может меняться не только из-за продолжительности горения, но также из-за скорости, массы и ориентации ракеты. Его нельзя смоделировать с помощью оператора STRIPS, поскольку формулы, которые необходимо будет добавлять и удалять, будут зависеть от набора преобразуемых формул. ^[8]

Хотя эффективное рассуждение возможно при использовании языка STRIPS, общепризнано, что выразительность STRIPS не подходит для моделирования действий во многих реальных приложениях. Эта неадекватность мотивировала разработку языка ADL. ^[9]^[10] Выразительность и сложность ADL находятся между языком STRIPS и ситуационным исчислением. Его выразительная сила достаточна, чтобы позволить представить описанный выше пример ракеты, но в то же время она достаточно ограничительна, чтобы позволить разработать эффективные алгоритмы рассуждения.

В качестве примера в более сложной версии мира блоков: возможно, блок A в два раза больше блоков B и C, поэтому действие xMoveOnto(B,A) может иметь эффект отрицания Clear(A), только если On(A,C) уже истинно или создает условный эффект в зависимости от размера блоков. Такого рода условные эффекты было бы трудно выразить в нотации STRIPS без условных эффектов.

Пример [ править ]

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

Необходимыми действиями будут погрузка , разгрузка и полет ; над дескрипторы, которые можно выразить In(c, p) и At(x, A) находится ли груз c в самолете p находится ли объект x в аэропорту A. и

Тогда действия можно было бы определить следующим образом:

Action (
  Load (c: Freight, p: Airplane, A: Airport)
  Precondition: At(c, A) ^ At(p, A)
  Effect: ¬At(c, A) ^ In(c, p)
)

Action (
  Unload (c: Freight, p: Airplane, A: Airport)
  Precondition: In(c, p) ^ At(p, A) 
  Effect: At(c, A) ^ ¬In(c, p)
)

Action (
  Fly (p: Airplane, from: Airport, to: Airport)
  Precondition: At(p, from)
  Effect: ¬At(p, from) ^ At(p, to)
)

См. также [ править ]

Ссылки [ править ]

^ Эдвин Педно. «Исследовательский веб-сайт IBM: Педно» . Проверено 29 марта 2013 г. л
^ Педно. Формулирование многоагентных задач динамического мира в рамках классического планирования. В книге Майкла Джорджеффа и Эми Лански, редакторов, «Рассуждения о действиях и планах», стр. 47–82. Морган Кауфманн, Сан-Матео, Калифорния, 1987 год.
^ Майкл Гельфонд , Владимир Лифшиц (1998) « Языки действий. Архивировано 2 сентября 2011 года в Wayback Machine », Linköping Electronic Articles in Computer and Information Science , vol 3 , nr 16 .
^ Эдвин П.Д. Педно. АДЛ. «Изучение золотой середины между STRIPS и ситуационным исчислением». В Трудах КР -89, 324–332.
^ Газен, Британская Колумбия и Ноблок, Калифорния, «Сочетание выразительности UCPOP с эффективностью Graphplan». В ECP9 7, стр. 221–233. Тулуза, Франция. 1997 г.
^ Небель, Б., « О компилируемости и выразительной силе формализмов пропозиционального планирования ». Журнал исследований искусственного интеллекта , 12, 271315. 2000 г.
^ Хорхе А. Байер, «Эффективные методы поиска для неклассического планирования посредством переформулировки». доктор философии диссертация, Университет Торонто, 2003 г.
^ Эдвинг П.Д. Пено. ADL и модель действий по переходу государства
^ Х. Дж. Левеск и Р. Дж. Брахман. Фундаментальный компромисс в представлении знаний и рассуждениях. В «Чтениях по представлению знаний», Х. Дж. Левеск и Р. Дж. Брахман, ред., стр. 42–70. Морган Кауфманн, Сан-Матео, Калифорния, 1985 год.
^ Владимир Лифшиц и Аркадий Рабинов. Чудеса в формальных теориях действий. Искусственный интеллект , 626(3):89–116. 1986 год

[1] Эдвин Педно. «Исследовательский веб-сайт IBM: Педно» . Проверено 29 марта 2013 г. л

[2] Педно. Формулирование многоагентных задач динамического мира в рамках классического планирования. В книге Майкла Джорджеффа и Эми Лански, редакторов, «Рассуждения о действиях и планах», стр. 47–82. Морган Кауфманн, Сан-Матео, Калифорния, 1987 год.

[3] Майкл Гельфонд , Владимир Лифшиц (1998) « Языки действий. Архивировано 2 сентября 2011 года в Wayback Machine », Linköping Electronic Articles in Computer and Information Science , vol 3 , nr 16 .

[4] Эдвин П.Д. Педно. АДЛ. «Изучение золотой середины между STRIPS и ситуационным исчислением». В Трудах КР -89, 324–332.

[5] Газен, Британская Колумбия и Ноблок, Калифорния, «Сочетание выразительности UCPOP с эффективностью Graphplan». В ECP9 7, стр. 221–233. Тулуза, Франция. 1997 г.

[6] Небель, Б., « О компилируемости и выразительной силе формализмов пропозиционального планирования ». Журнал исследований искусственного интеллекта , 12, 271315. 2000 г.

[7] Хорхе А. Байер, «Эффективные методы поиска для неклассического планирования посредством переформулировки». доктор философии диссертация, Университет Торонто, 2003 г.

[8] Эдвинг П.Д. Пено. ADL и модель действий по переходу государства

[9] Х. Дж. Левеск и Р. Дж. Брахман. Фундаментальный компромисс в представлении знаний и рассуждениях. В «Чтениях по представлению знаний», Х. Дж. Левеск и Р. Дж. Брахман, ред., стр. 42–70. Морган Кауфманн, Сан-Матео, Калифорния, 1985 год.

[10] Владимир Лифшиц и Аркадий Рабинов. Чудеса в формальных теориях действий. Искусственный интеллект , 626(3):89–116. 1986 год

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]