Стратегия разрешения конфликтов

План решения задачи — это список всех правил, имеющих удовлетворенные условия при некотором, текущим состоянием списка фактов и объектов (и которые еще не были выполнены). Каждый модуль имеет свой собствен­ный план решения задачи. Выполнение плана подобно стеку (верхнее пра­вило плана всегда будет выполнено первым). Когда активируется новое правило, оно размещается в плане решения задачи руководствуясь следую­щими факторами:

1. Только что активированное правило помещается выше всех правил с меньшим приоритетом и ниже всех правил с большим приоритетом.

2. Среди правил с одинаковым приоритетом используется текущая страте­гия разрешения конфликтов для определения размещения среди других правил с одинаковым приоритетом.

3. Если правило активировано вместе с несколькими другими правилами, добавлением или исключением некоторого факта и с помощью шагов 1 и 2 нельзя определить порядок правила в плане решения задачи, то пра­вило произвольным образом упорядочиваются вместе с другими прави­лами, которые были активированы. Заметьте, что в этом случае порядок, в котором правила были добавлены в систему, оказывает произвольный эффект на разрешения конфликта (который в высшей степени зависит от текущей реализации правил). Старайтесь не использовать произволь­ное упорядочивание правил при решении задач, в которых требуются точные результаты или объяснения полученных решений.

CLIPS поддерживает семь различных стратегий разрешения конфликтов: стратегия глубины (depth strategy), стратегия ширины (breadth strategy), стратегия упрощения (simplicity strategy), стратегия усложнения (complexity strategy), LEX (LEX strategy), MEA (MEA strategy) и случайная стратегия (random strategy). По умолчанию в CLIPS установлена стратегия глубины. Текущая стратегия может быть установлена командой set-strategy (которая переупорядочит текущий план решения задачи, базируясь на новой страте­гии). Кроме того, пользователи Windows-версии среды CLIPS могут указать необходимую стратегию поиска с помощью диалогового окна Execution Op tions (см. рис. 6.3). Для этого выберите пункт Options в меню Execution, в появившемся диалоговом окне выберите необходимую стратегию с помощью раскрывающегося списка Strategy.

Стратегия глубины

Только что активированное правило помещается выше всех правил с таким же приоритетом. Например, допустим, что факт-А активировал правило-1 и правило-2 и факт-Б активировал правило-3 и правило-4, тогда, если факт-А добавлен перед фактом-Б, в плане решения задачи правило-3 и правило-4 будут располагаться выше, чем правило-1 и правило-2. Однако позиция правила-1 относительно правила-2 и правила-3 относительно правила-4 бу­дет произвольной.

Стратегия ширины

Только что активированное правило помещается ниже всех правил с таким же приоритетом. Например, допустим, что факт-А активировал правило-1 и правило-2 и факт-Б активировал правило-3 и правило-4, тогда, если факт-А добавлен перед фактом-В, в плане решения задачи правило-1 и правило-2 будут располагаться выше, чем правило-3 и правило-4. Однако позиция правила-1 относительно правила-2 и правила-3 относительно правила-4 бу­дет произвольной.

Стратегия упрощения

Между всеми правилами с одинаковым приоритетом только что активиро­ванные правила размещаются выше всех активированных правил с равной или большей определенностью (specificity). Определенность правила вычис­ляется по числу сопоставлений, которые нужно сделать в левой части пра­вила. Каждое сопоставление с константой или заранее связанной с фактом переменной добавляет к определенности единицу. Каждый вызов функции в левой части правила, являющийся частью условных элементов:, = или test, также добавляет к определенности единицу. Логические функции and, or и not не увеличивают определенность правила, но их аргументы могут сделать это. Вызовы функций, сделанные внутри функций, не увеличивают определенность правила.

Например, следующее правило имеет определенность, равную 5.

Пример 6.2. Вычисление определенности правила

(defrule example

(item?х?у?х)

(test (and (numberp?x) (>?х (+ 10?у)) (<?х 100)))

=>)

И сравнение заранее связанной переменной?х с константой, и вызовы функций numberp, < и > добавляют единицу к определенности правила. В итоге получаем определенность, равную 5. Вызовы функций and и + не увеличивают определенность правила.

Стратегия усложнения

Между правилами с одинаковым приоритетом, только что активированные правила размещаются выше всех активированных правил с равной или меньшей определенностью.

Стратегия LEX

Между правилами с одинаковым приоритетом только что активированные правила размещаются с использованием одноименной стратегии, впервые использованной в системе OPS5. Для определения места активированного правила в плане решения задачи используется "новизна" образца, который активировал правило. CLIPS маркирует каждый факт или объект временным тегом для отображения относительной новизны каждого факта или объекта в системе. Образцы, ассоциированные с каждой активацией прави­ла, сортируются по убыванию тегов для определения местоположения пра­вила. Активация правила, выполненная более новыми образцами, распола­гается перед активацией, осуществленной более поздними образцами. Для определения порядка размещения двух активаций правил, поодиночке срав­ниваются отсортированные временные теги для этих двух активаций, начи­ная с наибольшего временного тега. Сравнение продолжается до тех пор, пока не останется одна активация с наибольшим временным тегом. Эта активация размещается выше всех остальных в плане решения задачи.

Если активация некоторого правила выполнена большим числом образцов, чем активация другого правила и все сравниваемые временные теги одина­ковы, то активация с большим числом временных тегов помещает перед активацией с меньшим. Если две активации имеют одинаковое количество временных тегов и их значения равны, то правило с большей определен­ностью (см. разд. 6.4.3) помещается перед активацией с меньшей. В отличие от системы OPS5, условный элемент not в CLIPS имеет псевдовременной тег, который также используется в данной стратегии разрешения конфлик­тов. Временной тег условного элемента not всегда меньше, чем временной тег образца.

В качестве примера рассмотрим следующие шесть активаций правил, при­веденные в LEX-порядке (запятая в конце строки активации означает нали­чие логического элемента not). Учтите, что временные теги фактов не обя­зательно равны индексу, но если индекс факта больше, то больше и его временной тег. Для данного примера примем, что временные теги равны индексам.

 

Пример 6.3. Правила, отсортированные стратегией LEX

 

rule-б:           f-l,f-4

rule-5:           f-l,f-2,f-3,

rule-1:           f-l,f-2,f-3

rule-2:           f-3, f-1

rule-4:           f-l,f-2

rule-3:           f-2, f-1

 

В примере 6.4 показаны те же активации с индексами фактов в том поряд­ке, в котором они сравниваются стратегией LEX.

Пример 6.4. Порядок сравнения стратегией LEX

 

rule-6:       f-4,f-l

rule-5:       f-3,f-2,f-1,

rule-1:       f-3,f-2,f-1

rule-2:       f-3,f-1

rule-4:       f-2,f-1,

rule-3:       f-2,f-1

Стратегия МЕА

 

Между правилами с одинаковым приоритетом только что активированные правила размещаются с использованием одноименной стратегии, впервые использованной в системе OPS5. Основное отличие стратегии МЕА от LEX в том, что в стратегии МЕА не производится сортировка образцов, активи­ровавших правило. Сравниваются только временные теги первых образцов двух активаций. Активация с большим тегом помещается в план решения задачи перед активацией с меньшим. Если обе активации имеют одинако­вые временные теги, ассоциированные с первым образцом, то для опреде­ления размещения активации в плане решения задачи используется стратегия LEX. Так же, как и в стратегии LEX, условный элемент not имеет псевдовременной тег.

В качестве примера рассмотрим следующие шесть активаций, приведенные в МЕА-порядке (запятая на конце активации означает наличие логического элемента not).

Пример 6.5. Правила, отсортированные стратегией МЕА

 

rule-2:       f-3,f-l

rule-3:       f-2,f-l

rule-6:       f-l,f-4

rule-5:       f-1,f-2,f-3,

rule-1:       f-1,f-2,f-3

rule-4:       f-1, f-2,

Случайная стратегия

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

 

Синтаксис LHS правила

Этот раздел описывает синтаксис, используемый в левой части правил. Ле­вая часть правил содержит список условных элементов (conditional elements или CEs), которые должны удовлетворяться, для того чтобы правило было помещено в план решения задачи. Существует восемь типов условных эле­ментов, используемых в левой части правил: CEs-образцы, test CEs, and CEs, or CEs, not CEs, exists CEs, forall CEs и logical CEs. Образцы — наиболее часто используемый условный элемент. Он содержит ограничения, которые слу­жат для определения, удовлетворяет ли какой-нибудь элемент данных (факт или объект) образцу. Условие test используется для оценки выражения, как части процесса сопоставления образов. Условие and применяется для опре­деления группы условий, каждое из которой должно быть удовлетворено. Условие or — для определения одного условия из некоторой группы, кото­рое должно быть удовлетворено. Условие not — для определения условия, которое не должно быть удовлетворено. Условие exists — для проверки наличия, по крайней мере одного, совпадения факта (или объекта) с некото­рым заданным образцом. И наконец, условие logical позволяет выполнить добавление фактов и создание объектов в правой части правила, связанных с фактами и объектами, совпавшими с заданным образцом в левой часта правила (поддержка достоверности фактов в базе знаний).

Синтаксис условного элемента можно формализовать следующим образом: