Прямая и обратная цепочки рассуждений
На глобальном уровне управления последовательностью применения правил можно выделить две стратегии поведения — применять правила в прямом и обратном порядке. Прямой порядок означает, что цепь рассуждений строится, отталкиваясь от данных (условий, о которых известно, что они удовлетворяются), к гипотезам (состоянию проблемы, вытекающему из этих условий). Обратная цепочка означает, что рассуждения строятся, отталкиваясь от заданной цели (гипотезы, представляющие целевое состояние системы) к условиям, при которых возможно достижение этой цели. Здесь явно чувствуется аналогия с прямой и обратной стратегиями доказательства теорем (см. об этом в главе 8).
CLIPS представляет собой систему, в которой строится прямая цепочка рассуждений, а порождающие правила в системе MYCIN используются в большинстве случаев для построения обратной цепочки рассуждений, как было показано в главе 3. В CLIPS всегда сопоставляются состояние рабочей памяти и левые части правил, а затем выполняются действия, предусмотренные правой частью выбранного правила. А в MYCIN ведущей в рассуждениях является правая часть правила. Если мы задались целью установить природу некоторого микроорганизма, то отбираются все правила, в правой части которых дается соответствующее заключение, и затем анализируется, предпосылки какого из них удовлетворяются текущими данными.
Проще всего представить отличие между прямой и обратной цепочками рассуждений в терминах грамматических правил, аналогичных представленным в разделе 5.1. Как было показано, набор правил
(Р1) $ -> а$а
(Р2) $ -> b$b
(РЗ) $ -> с$с
можно использовать двумя способами.
Во-первых, их можно использовать для формирования палиндромов. Если задаться некоторым начальным символом из имеющегося алфавита, то любая последовательность применения правил приведет к формированию палиндрома. Так, применение правил Р1, Р1, РЗ, Р2, Р3 к исходному символу с приведет к формированию строк
аса, aacaa, caacaac, bcaacaacb, cbcaacaacbc.
Это пример прямой цепочки, поскольку с и каждая последующая сформированная строка сопоставляются с левой частью правила, а затем означивается правая часть правила.
Во-вторых, можно использовать этот же набор правил не для формирования, а для распознавания палиндромов. Мы уже видели ранее, что, задавшись некоторой строкой, например ЬасаЬ, можно проследить, в какой последовательности применялись правила при построении этой строки. Строка bасаb соответствует правой части правила Р2; можно сказать, что правая часть правила Р2 "допускает" строку bacab. Означенная левая часть правила Р2 — это строка аса, которая соответствует правой части правила PI, a означенная левая часть этого правила — аксиома с. Таким образом, процесс распознавания успешно завершился — мы доказали, что bacab представляет собой палиндром. Описанный процесс распознавания — это пример применения обратной цепочки рассуждений. Начальная строка bacab и каждая очередная подстрока анализируются на соответствие с правыми частями имеющихся правил, а результатом является означивание левой части выбранного правила. Если в качестве исходной мы зададимся строкой acbcb, то для нее не удастся найти в имеющемся наборе правил такое, правая часть которого "допускала" бы эту строку, а значит, исходная строка не может быть палиндромом.
В литературе по теории доказательства теорем прямая цепочка рассуждений, как правило, ассоциируется с "восходящим" процессом, т.е. рассуждениями от фактов к целям, а обратная цепочка — с "нисходящим" процессом, рассуждением от целей к фактам. Но, строго говоря, в отношении продукционных систем эти термины не являются синонимами. Например, вполне возможно реализовать нисходящий процесс в продукционной системе с прямой цепочкой рассуждений, если должным образом настроить локальный режим управления, например задать явное указание целей.
В листинге 5.4 показана простая программа построения башни из блоков. Эта программа переключается между двумя задачами: выбором очередного блока и установкой блока в башню.
В разделе шаблонов блоки представлены объектами, обладающими такими свойствами, как цвет, размер и положение.
Если положение блока не определено, предполагается, что он находится в куче блоков (heap), еще не уложенных в башню. Шаблон on предоставляет в наше распоряжение средство, позволяющее описать размещение блоков одного (upper) на другом (lower). Информацию о текущей фазе решения проблемы (поиск или установка) несет шаблон goal.
Листинг 5.4. Набор правил для построения башни из блоков
;; СТРАТЕГИЯ РАЗРЕШЕНИЯ КОНФЛИКТОВ
(declare (strategy mea))
;; Шаблоны
;; Объект block характеризуется цветом, размером и положением,
(deftemplate block
(field color (type SYMBOL))
(field size (type INTEGER))
(field place (type SYMBOL)) )
;; Вектор 'on' указывает, что блок <upper>
;; находится на блоке <lower>. (deftemplate on
(field upper (type SYMBOL»
(field lower (type SYMBOL))
(field place (type SYMBOL) (default heap)] )
;; Текущая цель (goal) может быть либо 'найти' (find),
;; либо 'уложить' (build), (deftemplate goal
(field task (type SYMBOL)) )
;; ИНИЦИАЛИЗАЦИЯ
;; Имеются три блока разных цветов и размеров.
;; Предполагается, что они находятся в куче.
(deffacts the-facts
(block (color red) (size 10))
(block(color yellow) (size 20))
(block (color blue) (size 30))
)
;; ПРАВИЛА
;; Задать первую цель: найти первый блок,
(defrule begin
(initial-fact) =>
(assert (goal (task find))) )
;; Взять самый большой блок в куче (heap),
(defrule pick-up
?my-goal <- (goal (task find))
?my-block <- (block (size ?S1) (place heap))
(not (block (color ?C2) (size ?S2&:(>-?S2 ?S1))
(place heap))) =>
(modify ?my-block (place hand))
(modify ?my-goal (task build)) )
;; Установить первый блок в основание башни (tower).
;; Этот блок не имеет под собой никакого другого,
(defrule place-first
?my-goal <- (goal (task build))
?my-block <- (block (place hand))
(not (block (place tower)))
=>
(modify ?my-block (place tower))
(modify ?my-goal (task find)) )
;; Установить последующие блоки на тот,
;; что лежит в основании башни,
(defrule put-down
?my-goal <- (goal (task build))
?my-block <- (block (color ?C0)
(place hand))
(block (color ?C1) (place tower)))
(not (on (upper ?C2) (lower ?C1)
(place tower)))
=>
(modify ?my-block (place tower))
(assert (on (upper ?CO) (lower ?C1)
(place tower)))
(modify ?my-goal (task find)) )
;; Если в куче больше нет блоков, прекратить процесс,
(defrule stop
?my-goal <- (goal (task find))
(not (block (place heap)))
=>
(retract ?my-goal) )
Обратите внимание на то, что порядок перечисления правил в программе не имеет значения. В программе управления роботом, представленной в листинге 5.3, правило прекращения выполнения стояло в списке первым, а в этой программе оно стоит в самом конце списка. Трассировку выполнения приведенной программы и некоторые комментарии вы найдете во врезке 5.4.
5.4. Трассировка программы строительства башни
При запуске программы в режиме трассировки будет сформирована следующая карта трассировки.
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, можно говорить о том, что возможные варианты применения правил формируют пространство поиска и определяют его структуру.
Программирование, основанное на правилах (логическое программирование), не снимает с повестки дня проблему комбинаторного взрыва, поскольку для любой проблемы И/ИЛИ-дерево может ветвиться по экспоненциальному закону. Но на практике стратегия разрешения конфликтов, реализованная в интерпретаторах правил, позволяет надеяться на отыскание разумного решения.
