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