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

В искусственный интеллект, язык описания действий (ADL) является автоматизированное планирование и составление графиков система в частности для роботов. Это считается продвижением Полоски. Эдвин Педно (специалист в области абстракции и моделирования данных, который с 1996 года работал в исследовательской группе IBM в исследовательской группе Data Abstraction Research Group).[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:

  1. В р представляет собой символ отношения
  2. τ1, ..., τп представляет условия
  3. ψ представляет собой формулу
  4. Последовательность z1, ..., zk переменные символы, которые появляются в терминах τ1, ..., τп, но не в списке параметров схемы действия
  5. Икс1, ..., Иксп символы переменных, которые отличаются от переменных z1, ..., zп и не появляются в τ1, ..., τп, ψ, или список параметров схемы действия

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

Семантика ADL

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

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

Третье ограничение, включенное в ADL, состоит в том, что введенные выше функции должны быть представлены в виде формул первого порядка. Для каждого псимвол -арное отношение р, должна существовать формула Φар(Икс1,... ,Иксп) со свободными переменными Икс2, ..., Иксп такой, что жар(s) дан кем-то:

Как следствие, F(п1, ..., Иксп) = у будет истинным после выполнения действия | = тогда и только тогда, когда Φар (Икс1, ..., Иксп,у) было верно заранее. Обратите внимание, что это требование представимости опирается на первое ограничение (область ж должен быть равен доменуs).

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

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

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

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

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

Сравнение STRIPS и ADL

  1. Язык STRIPS допускает в состояниях только положительные литералы, тогда как ADL может поддерживать как положительные, так и отрицательные литералы. Например, допустимое предложение в STRIPS может быть Rich ∧ Beautiful. Это же предложение может быть выражено в ADL как «Плохо» ¬Уродливо.
  2. В STRIPS неупомянутые литералы ложны. Это называется предположение о замкнутом мире. В ADL неупомянутые литералы неизвестны. Это известно как Допущение открытого мира.
  3. В STRIPS мы можем найти только наземные литералы в целях. Например, Rich ∧ Beautiful. В ADL мы можем найти количественные переменные в целях. Например, ∃Икс В (P1, Икс) ∧ At (P2, Икс) является целью размещения P1 и P2 в одном месте в примере блоков
  4. В STRIPS цели - это союзы, например, (Rich ∧ Beautiful). В ADL цели могут включать союзы и разъединения (Rich Rich (Beautiful ∨ Smart)).
  5. В STRIPS эффекты являются соединениями, но в ADL разрешены условные эффекты: when п:E средства E это эффект, только если п доволен
  6. Язык STRIPS не поддерживает равенство. В ADL предикат равенства (Икс = у) встроен.
  7. STRIPS не имеет поддержки типов, в то время как в ADL она поддерживается (например, переменная п : Человек).

Выразительность языка 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 без условных эффектов.

Пример

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

Необходимые действия будут загрузка, разгрузка и летающий; над дескрипторами можно было бы выразить В (c, p) и В (х, А) ли фрахт c находится в самолете п и является ли объект Икс находится в аэропорту А.

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

Действие (  Нагрузка (c: Грузовые перевозки, p: Самолет, A: Аэропорт)  Предварительное условие: при(c, А) ^ При(п, А)  Эффект: ¬At(c, А) ^ В(c, п))Действие (  Разгрузить (c: Грузовые перевозки, p: Самолет, A: Аэропорт)  Предварительное условие: В(c, р) ^ При(п, А)   Эффект: при(c, А) ^ ¬In(c, п))Действие (  Летать (п: Самолет, от: аэропорта, до: аэропорта)  Предварительное условие: при(п, из)  Эффект: ¬At(п, из) ^ В(п, к))

Смотрите также

Рекомендации

  1. ^ Эдвин Педно. "Веб-сайт IBM Research: Pednault". Получено 29 марта 2013. Cite имеет пустой неизвестный параметр: | cite = (помощь)л
  2. ^ Педно. Формулировка многоагентных задач динамического мира в рамках классического планирования. Майкл Джорджфф и Эми Лански, редакторы, Рассуждения о действиях и планах, стр. 47-82. Морган Кауфманн, Сан-Матео, Калифорния, 1987.
  3. ^ Михаил Гельфонд, Владимир Лифшиц (1998) "Языки действий В архиве 2 сентября 2011 г. Wayback Machine ", Linköping Электронные статьи по информатике и информатике, об. 3, номер 16.
  4. ^ Эдвин П. Д. Педно. ADL. «Изучение золотой середины между STRIPS и ситуационным исчислением». В Труды КР-89, 324–332.
  5. ^ Газен Б. К. и Ноблок К. А. "Сочетание выразительности UCPOP с эффективностью Graphplan". В ECP97, pp. 221233. Тулуза, Франция. 1997 г.
  6. ^ Небель Б. "О компилируемости и выразительной силе формализмов пропозиционального планирования." Журнал исследований искусственного интеллекта, 12, 271315. 2000
  7. ^ Хорхе А. Байер. "Эффективные методы поиска неклассического планирования через реформу". Кандидат наук. Диссертация, Университет Торонто, 2003.
  8. ^ Эдвинг П.Д. Педно. ADL и модель действий при переходе между состояниями
  9. ^ Х. Дж. Левеск и Р. Дж. Брахман. Фундаментальный компромисс в представлении знаний и рассуждениях. В «Чтениях в представлении знаний», Х. Дж. Левеск и Р. Дж. Брахман, редакторы, стр. 42–70. Морган Кауфманн, Сан-Матео, Калифорния, 1985.
  10. ^ Владимир Лифшиц и Аркадий Рабинов. Чудеса в формальных теориях действий. Искусственный интеллект, 626 (3): 89–116. 1986 г.