Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

В области искусственного интеллекта , описание действия языка ( 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:

  1. R представляет собой символ отношения
  2. τ 1 , ..., τ n представляет термины
  3. ψ представляет собой формулу
  4. Последовательность z 1 , ..., z k - это переменные символы, которые появляются в терминах τ 1 , ..., τ n , но не в списке параметров схемы действий.
  5. x 1 , ..., x n - символы переменных, которые отличаются от переменных z 1 , ..., z n и не появляются в τ 1 , ..., τ n , ψ или в списке параметров схема действий

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

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

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

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

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

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

Четвертое и последнее ограничение, включенное в ADL, состоит в том, что набор состояний, в которых выполняется действие, также должен быть представлен в виде формулы. Для каждого действия α, которое может быть представлено в ADL, должна существовать формула Π a со свойством 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 [ править ]

  1. Язык STRIPS допускает только положительные литералы в состояниях, в то время как ADL может поддерживать как положительные, так и отрицательные литералы. Например, допустимым предложением в STRIPS может быть Rich ∧ Beautiful. Это же предложение может быть выражено в ADL как «плохо» ¬Ugly.
  2. В STRIPS неупомянутые литералы ложны. Это называется предположением о замкнутом мире . В ADL неупомянутые литералы неизвестны. Это известно как Допущение открытого мира.
  3. В STRIPS мы можем найти только наземные литералы в целях. Например, Rich ∧ Beautiful. В ADL мы можем найти количественные переменные в целях. Например, ∃ x At (P1, x ) ∧ At (P2, x ) - это цель размещения P1 и P2 в одном месте в примере блоков.
  4. В STRIPS цели - это союзы, например, (Богатый ∧ Красивый). В ADL цели могут включать союзы и разъединения (Rich Rich (Beautiful ∧ Smart)).
  5. В STRIPS эффекты являются соединениями, но в ADL разрешены условные эффекты: когда P : E означает, что E является эффектом, только если P удовлетворяется
  6. Язык STRIPS не поддерживает равенство. В ADL встроен предикат равенства ( x = y ).
  7. У 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)ли перевозка грузов с в самолете р и является ли объект х находится в аэропорту A .

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

Действие (  Загрузка ( c : фрахт, p: самолет, A: аэропорт)  Условие: At ( c , A) ^ At ( p , A)  Эффект: ¬At ( c , A) ^ In ( c , p) )Действие (  Разгрузка ( c : фрахт, p: самолет, A: аэропорт)  Условие: In ( c , p) ^ At ( p , A)   Эффект: At ( c , A) ^ ¬In ( c , p) )Действие (  Полет ( p : Самолет, из: Аэропорт, в: Аэропорт)  Условие: В ( p , из)  Эффект: ¬At ( p , from) ^ At ( p , to) )

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

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

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