Анализ методов интеллектуального планирования.

Идея алгоритма STRIPS заимствована из системы GPS (General Problem Solver), разработанной для доказательства теорем [41]. Метод, использованный в GPS, назывался «анализ средств и целей» (Cneans-ends analysis). Он подразумевает рассмотрение тех действий в текущем состоянии, которые имеют отношение к цели. Однако при таком подходе возникает следующая проблема: применять ли действия связанные с целью сразу же, как только они найдены или же приостановить применение действия пока не будут найдены все действия имеющие отношение к цели. STRIPS применяет действия сразу, достигая каждой цели по отдельности.

МакДермот Д. [38] показал, что эффективность планирования с

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

Для решения проблемы фрейма STRIPS допускает следующее: в состоянии, к которому применяется правило, изменяется выполнимость лишь тех формул, которые описаны в эффекте действия, а все остальные остаются неизменными.

Рассмотрим постановку задачи планирования при классических допущениях в терминах STRIPS.

Пусть L - язык исчисления предикатов 1-го порядка (ИППП). Факт f некоторая правильно построенная замкнутая формула L. Состояние s - некоторое множество фактов.

По сути, состояние s - это эрбрановская интерпретация множества фактов. Таким образом, каждый факт из s выполним или невыполним в s, в соответствии с обычным определением понятия выполнимости в ИППП.

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

Приведём пример описания среды в терминах STRIPS:

s = {ATR(a), AT(B,b), АТ(С,с), "u"x"y ((AT(u,x) Ù (x ¹ у)) ® ⌝ AT(u,y)) }

Здесь, ATR(a) означает, что "робот находится в комнате а", АТ(В,Ь) -"ящик В находится в комнате b", АТ(С,с) - "ящик С находится в комнате с", последняя сложная формула - "один объект не может находиться в разных местах", х, у, и - переменные в области значений, охватывающей доступное множество объектов. Имена конкретных объектов из этого множества: 'а', b', 'с' - соответственно 'комната а’, 'комната b', 'комната с'; 'А', 'В', 'С -соответственно 'ящик А',' ящик В', 'ящик С.

Действия агента описываются с помощью правил.

Правило R-это <C,A,D>, где С - предусловие правила, А -список добавлений, D - список удалений.

Предусловие С описывает множество фактов, которые должны быть выполнимы в состоянии s перед применением правила R. Список удалений D описывает множество фактов удаляемых из s при применении правила R. Список добавлений А описывает множество фактов, добавляемых в s при применении правила R.

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

Во-первых, при описании правила R затруднительно или невозможно явно выразить все удаляемые факты в различных случаях применения R. Поэтому в STRIPS принято такое ограничение, что в списке удалений выражаются лишь атомарные факты. При этом после применения правила контролируется выполнимость сложных фактов из s, которые содержат в своём описании удалённые атомарные формулы. Однако, как показано в [35] это не уберегло STRIPS от некорректностей. Оказывается, для списка добавлений А также необходимо было ввести подобное ограничение. Вместе с тем, в предусловии сложные факты могут фигурировать.

Во-вторых, если в описании- домена планирования допустимы функциональные символы, то это приводит к полуразрешимой задаче планирования, так как в множество фактов в s может быть добавлено потенциально бесконечное количество формул [20].

Для обхода подобных трудностей, при описании STRIPS-задачи планирования общепринято использовать лишь элементарные термы без функциональных символов.

Пример правила.

Имя правила: Push (х, у, z);

Предусловие: C(R) = {ATR (у), АТ(х, у)};

Список добавлений: A(R) = {ATR (у), АТ(х, у)};

Список удалений: D(R) = {ATR (z), АТ(х, z)};

В приведённом примере, STRIPS-правило Push (х, у, z) описывает действие робота по перемещению ящика х из комнаты у в комнату z. Здесь, х, у, z - переменные.

Выполнение агентом действия сводится к применению правила. Применение правила модифицирует состояние s. Дадим формальное определение применения правила STRIPS.

Правило R q-применимо в состоянии s, если Сq выполнимо в s, где С - предусловие правила R, q - подстановка на место каждой переменной в правиле R некоторых констант.