Трассировка программы строительства башни

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

CLIPS> (reset)

==> f-0 (initial-fact)

==> f-1 (block (color red) (size 10) (place heap))

==>f-2 (block (color yellow) (size 20) (place heap))

==> f-3 (block (color blue) (size 30) (place heap))

CLIPS> (run)

TIRE 1 begin: f-0

==> f-4 (goal (task find))

FIRE 2 pick-up: f-4, f-3,

<== f-3 (block (color blue) (size 30) (place heap))

==> f-5 (block (color blue) (size 30) (place hand))

<== f-4 (goal (task find))

==> f-6 (goal (task build))

FIRE 3 place-first: f-6, f-5,

<== f-5 (block (color blue) (size 30) (place hand))

==> f-7 (block (color blue) (size 30) (place tower))

<== f-6 (goal (task build))

==> f-8 (goal (task find))

FIRE 4 pick-up: f-8, f-2,

<== f-2 (block (color yellow) (size 20) (place heap))

==> f-5 (block (color yellow) (size 20) (place hand))

<== f-8 (goal (task find))

==> f-10 (goal (task build))

FIRE 5 put-down: f-10, f-9, f-7,

<== f-9 (block (color yellow) (size 20) (place hand))

==>. f-11 (block (color yellow) (size 20) (place tower))

==> f-12 (on (upper yellow) (lower blue) (place tower))

<== f-10 (goal (task build))

==> f-13 (goal (task find))

FIRE 6 pick-up: f-13, f-1,

<== f-1 (block (color red) (size 10) (place heap))

==> f-5 (block (color red) (size 10) (place hand))

<== f-13 (goal (task find))

==> f-15 (goal (task build))

FIRE 7 put-down: f-15, f-14, f-11,

<== f-14 (block (color red) (size 10) (place hand))

==> f-16 (block (color red) (size 10) (place tower))

==> f-17 (on (upper red) (lower yellow) (place tower))

<== f-15 (goal (task build))

==> f-18 (goal (task find))

FIRE 8 stop: f-18,

<== f-18 (goal (task find))

CLIPS> (reset)

<== f-0 (initial-fact)

<== f-7 (block (color blue) (size 30) (place tower))

<== f-11 (block (color yellow) (size 20) (place tower))

<== f-12 (on (upper yellow) (lower blue) (place tower))

<== f-16 (block (color red) (size 10) (place tower))

<== f-17 (on (upper red) (lower yellow) (place tower))

Обратите внимание на манипулирование лексемой цели в ходе выполнения программы. Конечное состояние представлено при очистке рабочей памяти. Блоки в башне расположились в таком порядке: красный (red) — самый верхний, он стоит на желтом (yellow), который стоит на синем (blue).

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

(goal (task find)

и

(goal (task build)).

Когда оказывается, что в куче больше нет блоков, главная цель достигнута. Мы делаем это в определенной степени неформально, используя (initial-fact) для упрощения программного кода, но принцип, тем не менее, соблюдается.

Иногда необходимо провести четкую границу между направленностью цепочки и направленностью действительных рассуждений. Эти две операции представляют разные уровни анализа. Очевидно, что цепочка является реализацией рассуждений, а не наоборот, но стратегия рассуждений управляет процессом построения цепочки, что в данном случае выполняется манипулированием лексемами цели. В главе 14 будет продемонстрирован гораздо более сложный пример использования этого метода в системе R1/XCON.

Это разделение высвечивает проблему, с которой очень часто приходится сталкиваться при обсуждении функционирования программ искусственного интеллекта. Большинство сложных систем, независимо от того, являются ли они программными системами, или физическими устройствами, или комбинацией тех и других, могут быть описаны на разных уровнях [Newell, 1982]. В соответствии с терминологией Ньюэлла, построение цепочки — это свойство символического уровня, где нас интересуют только левые и правые части правил, а рассуждение— это нечто, возникающее на уровне знаний, где можно провести разделение между фактами и задачами.

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

В главе 3 мы рассказывали о представлении пространства поиска, связанного с набором порождающих правил, с помощью И/ИЛИ-дерева. Узлы такого дерева соответствуют состояниям рабочей памяти, а дуги — правилам, которые при этом возможно применить. Древовидная схема очень хорошо согласуется с методикой обратной цепочки рассуждений, если считать, что корень дерева соответствует целевому состоянию, промежуточные узлы — подцелям, а терминальные узлы (листья) — данным.

В И/ИЛИ-дереве корень представляет исходное состояние проблемы, а листья — возможные варианты ее решения. Нетерминальные узлы могут быть двух видов: И-узлы и ИЛИ-узлы. И-узлы соответствуют применению нескольких правил, которые в совокупности формируют цель как объединение нескольких подцелей, а ИЛИ-узлы соответствуют наличию альтернативы при выборе возможных правил. Таким образом, используя терминологию главы 2, можно говорить о том, что возможные варианты применения правил формируют пространство поиска и определяют его структуру.

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

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

Код каждого порождающего правила является самодостаточным, т.е. весь необходимый контекст активизации правила содержится только в его предпосылках. Не существует способа, который позволял бы одному правилу вызывать другое, как если бы правила были процедурами. Правило R, которое активизируется в цикле С_i, может облегчить последующую активизацию правила R' в цикле C_i+1, но единственный способ сделать это — изменить состояние рабочей памяти.

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

Метаправила, таким образом, существенно отличаются от обычных правил, поскольку они направляют ход рассуждений, а не принимают непосредственное участие в процессе формирования суждений. Часто это отличие формулируется в терминах разграничения уровней функционирования правил — метауровня и объектного уровня.

Например, в системе MYCIN набор порождающих правил индексирован по клиническим параметрам, которые упоминаются в его правой части (заключение правила). В результате появляется предпосылка для значительного ускорения процедуры извлечения правил, которые можно использовать для определения величины определенного параметра (лекарственного препарата). Эта информация используется метаправилами, которые применяются по отношению к правилам, с помощью которых достигается определенная подцель. Пусть, например, сформулирована очередная подцель G, скажем, классифицировать микроорганизм. Для достижения этой подцели в системе при данном состоянии рабочей памяти можно применить множество, например порядка 30 правил. Метаправила позволяют значительно сузить круг кандидатов на основании какого-либо критерия, заложенного программистом в формулировку этого правила.

Ниже представлено простое метаправило сокращения количества кандидатов в системе MYCIN, заимствованное из книги Бучанана и Шортлиффа [Buchanan and Shortliffe, 1984, Chapter 28].

МЕТАПРАВИЛO001

ЕСЛИ