Иллюстрированный самоучитель по введению в экспертные системы

Таблицы операторов и методика "средство – анализ завершения"

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

at(work), have(transport)

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

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

По существу, в системе STRIPS при выборе операторов выполняется поиск в пространстве состояний, как это было описано в главе 2. В результате формируется план, т.е. последовательность операторов, приводящая к достижению цели, причем за основу берется стратегия "обратного" прослеживания. Основное отличие STRIPS от других аналогичных программ состоит в том, что вместо методики "генерация – проверка" для передвижения в пространстве состояний используется другой метод, известный как "средство – анализ завершения" (means-ends analisys).

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

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

at(ящик1, комнатаА),

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

В действительности программа STRIPS считывает список целей наподобие такого:

at(ящик1, комнатаА), аt(ящик2, комнатаБ),

А затем сопоставляет эти цели и список добавления в описании каждого оператора. Так, цель at (ящик1, комнатаА) будет соответствовать элементу at(X, Z) в списке добавлений оператора push (X, Y, Z).

Схема сопоставления будет подробно рассмотрена в главах 4, 5 и 8, но сейчас, не вдаваясь в детали, просто отметим, что существует подстановка значений переменных:

Х/ящик1, Z/комнатаА,

Которая приводит к равенству выражений:

at (ящик1, комнатаА) nat(X, Z).

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

(1) Подстановкой {Х/ящик1, Z/комнатаА} означить предварительное условие, которое является производным от соответствия at (ящик1, комнатаА) nat(X, Z), и получить таким образом:

at(poбoт, Y), at(ящик1, Y).

(2) Найти в модели мира формулу, которая представляла бы текущее положение ящика а1(ящик1, комнатаБ), сравнить ее с at(ящик1, Y) и в результате этого сравнения сформулировать подстановку {Y/комнатаБ}, которую затем применить к уже частично означенному предварительному условию. В результате будет сформулирована очередная подцель:

at(робот, комнатаБ), at(ящик1, комнатаБ).

Теперь первое предварительное условие даст желаемое (целевое) положение робота, а второе предварительное условие уже выполнено.

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

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

Весь процесс решения проблемы по такой методике имеет ярко выраженный рекурсивный характер. Подцели могут, в свою очередь, приводить к формулировке подподцелей и т.д. На самом нижнем уровне окажутся подцели, которые реализуются операторами, либо не имеющими предварительных условий, либо имеющими такие предварительные условия, которые удовлетворяются тривиально. Мы рассмотрим подробно методику "средство – анализ завершения" в главах 5 и 14.

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.