5.2. Системы порождающих правил для решения проблем
Хотя в приложении к экспертным системам порождающие правила и отличаются от тех правил переписывания, о которых шла речь выше, фундаментальные принципы и формальные свойства их остаются теми же. Но при этом нас интересует не столько сама по се-
бе грамматика символических структур, как в примере с палиндромами, сколько способы представления некоторой проблемы и преобразования этого представления, которое должно привести ее к виду, о котором можно сказать: "Это решение данной проблемы".
5.2.1. Синтаксис представления правил
В настоящее время порождающие правила обычно реализуются в форме правил, манипулирующих с символическими структурами типа списка векторов, а не строк символов. В этом сказывается влияние языков программирования вроде LISP и тех структур данных, которые они поддерживают. (В ранних реализациях использовались языки манипулирования символами, например SNOBOL.)
В результате алфавит канонической символьной системы заменяется словарем символов или атомов и довольно простой грамматикой формирования символических структур. Словарь, как правило, состоит из трех подмножеств:
подмножества N имен объектов предметной области;
подмножества Р имен свойств, которые рассматриваются в качестве атрибутов объектов;
подмножества V допустимых значений атрибутов.
На практике подмножества N и V перекрываются.
Используемая грамматика, как правило, имеет вид триад объект-атрибут-значение. Триада (v, л, w) существует, если v принадлежит N и л принадлежит Р, w принадлежит V. Например, триада
(ОРГАНИЗМ-1, морфология, палочка)
представляет определенный микроорганизм, имеющий форму палочки.
Представленная синтаксическая форма обобщается в том случае, когда нужно для некоторого объекта v представить « вариантов пар атрибут-значение (л1,w1) ..., (лn,wn). В таком случае они объединяются в вектор в форме
(v, л1, w1,..., лn, wn).
На языке CLIPS тот факт, что определенный микроорганизм имеет форму палочки и активно развивается в воздушной среде, будет представлен вектором
В дальнейшем мы будем повсеместно использовать именно такой синтаксис, поскольку CLIPS будет нашим основным программным инструментом.
Имея в своем распоряжении словарь символов и грамматику, регламентирующую порождение символических структур, можно представить в машинном виде исходное состояние интересующих нас проблем. Эти представления соответствуют аксиомам канонической системы — они представляют собой некоторую символическую структуру, которую нужно преобразовывать, применяя имеющиеся правила в определенном порядке.
Теперь перейдем к самим правилам. В этих правилах антецеденты должны соответствовать допустимым символическим структурам, а консеквенты — содержать специальные операторы манипулирования такими структурами. Детали этого процесса станут вам понятны после изучения следующего раздела, где будет описан вычислительный механизм применения таких правил.
Продукционная система (production system) состоит из множества правил (иногда этот набор правил называют продукционной памятью — production memory), интерпретатора правил, который решает, когда надлежит применить каждое из них, и рабочей памяти, содержащей данные, описание цели и промежуточные результаты, в совокупности определяющие текущее состояние проблемы. Именно структуры данных в рабочей памяти анализируются и преобразуются порождающими правилами. Обращение к правилам синхронизируется текущими данными, а интерпретатор правил управляет выбором и активизацией определенных правил в каждом цикле.
Схематически правила в продукционной системе имеют такую обобщенную форму:
P1,..., Pm,->Q1,..., Qn
которая читается следующим образом:
если предпосылки Р1 и ... и Рт верны, то выполнить действия Q1 и ... и Qn.
Предпосылки часто называются условиями, а действия — заключениями, поскольку один из видов действий — сделать заключение, если встретилось такое сочетание условий, которое делает истинным или вероятным определенное порождающее правило, как это было показано в главе 3. Иногда используется и другая терминология, согласно которой предпосылки называются левой частью правила, а действия — правой.
Предпосылки обычно бывают представлены в форме вектора объект-атрибут— значение, как, например:
В данном случае предпосылка состоит в том, что определенный микроорганизм имеет форму палочки и размножается в воздушной среде.
Правило, которое включает такую предпосылку, на языке CLIPS имеет вид, показанный в листинге 5.1.
Листинг 5.1. Оргправило системы MYCIN, записанное на языке CLIPS
(defrule diagnosis
(patient (name Jones)
(organism organism-1))
(organism (name organism-1)
(morphology rod)
(aerobicity aerobic)) => (assert
(organism
(name organism-1)
(identify enterobacteriaceae)
(confidence 0.8)))
На языке CLIPS представление правила имеет следующий формат:
(defrule <наименование правила> <предпосылка1>
<предпосылка m > =>
<действие 1>
<действие n>
Перечень предпосылок в таком правиле представляет собой образец вектора, которому должно соответствовать состояние рабочей памяти. Действия, такие как (assert ...) в приведенном выше примере, задают изменения, которые должны быть внесены в состояние рабочей памяти. Например, специфицированное в приведенном выше правиле действие добавит в рабочую память новый вектор
(organism (name organism-1)
(identify enterobacteriaceae)
(confidence 0.8)).
Таким образом, правило diagnosis означает следующее: если у определенного пациента обнаружена связь с определенным микроорганизмом, который имеет перечисленные в правиле свойства, то мы можем с определенным шансом на успех предполагать, что этот микроорганизм принадлежит такому-то классу. Это правило не является общим, поскольку применимо только к конкретному пациенту (Jones) и конкретному микроорганизму (organism-1). Гораздо чаще нам придется применять правила, которые пригодны для любого пациента и любого микроорганизма. В такие правила поле имени пациента вовсе не включается.
Желание сформировать общие правила требует включения в него переменных, которые играют роль местодержателя. В правиле, представленном в листинге 5.2, такие переменные отличаются от прочих членов наличием префикса ? перед именем. Обратите внимание на то, что переменная ?pat не появляется в заключительной части правила, а значит, использование поля имени пациента в предпосылках правила действительно является избыточным.
Листинг 5.2. Правило, в котором используются переменные
(defrule diagnosis
(patient (name ?pat)
(organism ?org))
(organism (name ?org)
(morphology rod)
(aerobicity aerobic)) => (assert
(organism
(name ?org)
(identify enterobacteriaceae) (confidence 0.8)))
При использовании правила интерпретатором вместо всех одноименных переменных подставляется одно и то же значение.
5.2.2. Рабочая память
Основная функция рабочей памяти — хранить данные в формате векторов объект-атрибут-значение. Эти данные используются интерпретатором, который в случае присутствия (или отсутствия) определенного элемента данных в рабочей памяти активизирует те правила, предпосылки в которых удовлетворяются наличными данными. Как это делается, рассмотрим на примере.
Пусть в рабочей памяти содержатся векторы
(patient (name Jones) (age 40)
(organism organism-1))
(organism (name organism-1)
(morphology rod) (aerobicity .aerobic)).
В очередном цикле интерпретатор просмотрит имеющийся список правил и отыщет в нем то, которое содержит условия, удовлетворяющиеся этими векторами.
Если предпосылка в правиле не содержит переменных, она удовлетворяется при точном совпадении выражений в правиле и в рабочей памяти. Если же предпосылка в правиле содержит переменные, т.е. является образцом, то она удовлетворяется, если в рабочей памяти содержится вектор, включающий такую пару атрибут-значение, которая остается постоянной при удовлетворении всех остальных условий в том же правиле.
В самом простом случае соответствие проверяется присвоением постоянных значений переменным, которые делают предпосылку совпадающей с вектором в рабочей памяти. Так, вектор состояния в рабочей памяти
(patient (name Jones) (age 40)
(organism organism-1))
удовлетворяет предпосылку в правиле
(patient (name ?pat) (organism ?org))
подстановкой Jones вместо ?pat и Organism-1 вместо ?org.
Обратите внимание на то, что мы опускаем при анализе соответствия пары, которые отсутствуют в предпосылке правила. Поскольку другая предпосылка в этом же правиле также удовлетворяется при указанной подстановке, то новый вектор
(organism (name organism-1)
(identify enterobacteriaceae) (confidence 0.8))
добавляется интерпретатором в рабочую память.
Поскольку для заключения правила значение ?pat безразлично, поле имени пациента можно в условии вообще игнорировать.
Теперь рассмотрим набор правил, представленный в листинге 5.3, вместе с множеством векторов в рабочей памяти. Этот пример основан на планировщике STRIPS, о котором шла речь в главе 3. Программа состоит из выражений трех типов:
деклараций (или шаблонов), которые определяют формат векторов в рабочей памяти;
определений фактов, которыми задается начальное состояние проблемы;
порождающих правил, которые определяют возможные трансформации состояния проблемы.
Строки, которые начинаются символами ";;", являются комментариями.
Листинг 5.3. Набор правил для проблемы в системе STRIPS
;; Шаблоны
;; Цель (goal) представляет собой вектор, состоящий из
;; четырех компонентов:
;; действие, которое нужно выполнить,
;; объект, над которым должно быть выполнено действие;
;; исходное положение;
;; положение, в которое нужно перейти.
(deftemplate goal
(field action (type SYMBOL))
(field object (type SYMBOL))
(field from (type SYMBOL))
(field to (type SYMBOL))
)
;; Вектор 'in' указывает, где находится объект, (deftemplate in
(field object (type SYMBOL))
(field location (type SYMBOL)) )
ФАКТЫ
;;Функция 'deffacts' вводит в рабочую память
;;описание исходного состояния.
;;Функция вызывается при перезапуске системы.
;;Исходное состояние объектов следующее.
;;Робот находится в комнате А,
;;ящик находится в комнате В,
;;цель - вытолкнуть ящик в комнату А.
(deffacts world
(in (object robot)
(location RoomA))
(in (object box)
(location RoomB))
(goal (action push)
(object box)
(from RoomB) (to RoomA))
)
;; ПРАВИЛА
;; Это правило утверждает:
;; Прекратить процесс, когда цель будет достигнута.
(defrule stop
(goal (object ?X) (to ?Y))
(in (object ?X) (location ?Y)) =>
(halt) )
;; Если робот отсутствует в том месте, где находится
;; объект, который нужно передвинуть,
;; переместить туда робот.
(defrule move
(goal (object ?X) (from ?Y))
(in (object ?X) (location ?Y))
?robot-position <- (in (object robot)
(location ?Z&~?Y)) =>
(modify ?robot-position (location ?Y))
;; Если робот и объект не в том помещении,
;; которое указано в цепи,
;; переместить туда робот и объект.
(defrule push
(goal (object ?X) (from ?Y) (to ?Z))
(in (object ?X) (location ?Y))
?object-position <- (in (object ?X) (location ?Y))
?robot-position <- (in (object robot) (location ?Y))
=>
(modify ?robot-position (location ?Z))
(modify ?object-position (location ?Z))
Это законченная программа на языке CLIPS, которую можно запустить на выполнение в среде разработки ^ CLIPS 6.O. В этой программе не нужно было специально предусматривать какие-либо варианты разрешения конфликтных ситуаций, поскольку стратегия, предложенная по умолчанию, всегда обеспечит решение задачи (см. раздел 5.3). Введите в систему текст этой программы и запустите на выполнение:
введите (reset),
затем введите (run).
С помощью команды watch посмотрите, в каком порядке будут использоваться специфицированные в программе правила. Во врезке 5.2 представлены трассировка выполнения этой программы и краткие пояснения.
5.2. Трассировка программы управления роботом
Представленная ниже карта трассировки будет сформирована при запуске про-граммы в режиме трассировки.
Команда reset обеспечит перезагрузку описания исходного состояния в рабочую память, а команда run запустит программу на выполнение.
В карте трассировки каждая строка, которая начинается с символов ==>, представляет добавление вектора в рабочую память, а строка, которая начинается с символов, <==, — удаление вектора из рабочей памяти. Строки, которые начинаются с 'FIRE', представляют активизацию какого-либо правила. Остальные строки пока ,что игнорируйте.
(reset)
==> f-0 (initial-fact)
=> f-1 (in (object robot) (location RoomA))
==> f-2 (in (object box) (location RoomB))
==> f-3 (goal (action push) {object box)
(from RoomB) (to RoomA)) CLIPS>
(run) FIRE 1 move: f-3, f-2, f-1
<== f-1 (in (object robot) (location RoomA))
==> f-4 (in (object robot) (location RoomB))
FIRE 2 push: f-3, f-2, f-4 <== f_4
(in (object robot) (location RoomB))
==> f-5 (in (object robot) (location RoomA))
<== f-2 (in (object box) (location RoomB))
==> f-6 (in (object box) (location RoomA))
FIRE 3 stop: f-3, f-6
[PRCCODE4] Execution halted during the actions of defrule stop.
CLIPS> (reset)
<== f-0 (initial-fact)
<== f-3 (goal {action push)
(object box) (from RoomB) (to RoomA))
<== f-5 (in (object robot) (location RoomA))
<== f-6 (in (object box) (location RoomA))
CLIPS>
Обратите внимание на то, что выполнение программы останавливается правилом 'stop'.
