====== Лабораторная работа №3: Изучение стратегий разрешения конфликтов в продукционных системах ======
===== Цель работы =====
Изучение различных стратегий разрешения конфликтов в продукционных системах.
===== Основные теоретические положения =====
При реализации прямого вывода в продукционных базах знаний машина логических выводов сопоставляет левые части (антецеденты) правил с базой данных и помещает правила, антецеденты которых удовлетворяются, в агенду (конфликтное множество). //Агенда// представляет собой список всех правил, условия которых удовлетворяются, но которые еще не были выполнены. Агенда работает аналогично стеку -- правило, которое должно быть выполнено первым является верхним правилом в агенде. Когда правило становится активным (условия в его левой части удовлетворяются), оно помещается в агенду в соответствии со следующими правилами:
  - Вновь активизируемые правила помещаются над всеми правилами с более низкой значимостью (salience) и ниже всех правил с более высокой значимостью.
  - Для определения места среди правил равной значимости используется текущая стратегия разрешения конфликта.
  - Если в результате добавления или удаления факта одновременно активизируются несколько правил и шаги 1 и 2 не позволяют выполнить упорядочение, то эти правила упорядочиваются между собой произвольно (//но не случайно//).
//Значимость// позволяет пользователю назначать правилу приоритет, который учитывается при его выборе из агенды. Первым активизируется правило с наивысшей значимостью. Значимость может принимать целое значение в диапазоне от -10000 до +10000. По умолчанию значимость правила равна 0. Для явного назначения правилу значимости используется оператор:
<code>
(declare <rule- salience>)
</code>
Этот оператор может добавляться в левую часть правила и должен размещаться перед первым условным элементом, например:
<code>
(defrule test-1
  (declare (salience 99))
  (fire test-1)
=>
  (printout t "Rule test-1 firing." crlf))
</code>
Значимости может назначаться значение в один из трех моментов: при определении правила, при активизации правила и в каждом цикле выполнения (последние два случая соответствуют //динамической значимости//). По умолчанию значение значимости назначается только при определении правила. Для изменения такого поведения может использоваться команда ''set-salience-evaluation''.
В CLIPS поддерживается семь стратегий разрешения конфликтов: <<вглубь>> (''depth''), <<вширь>> (''breadth''), <<простоты>> (''simplicity''), <<сложности>> (''complexity''), ''lex'', ''mea'' и случайного выбора (''random''). По умолчанию используется стратегия вглубь. Текущая стратегия может быть установлена командой ''set-strategy'', при этом агенда переупорядочивается на основе новой стратегии. Синтаксис команды:
<code>
(set-strategy <strategy>)
</code>
где ''<strategy> ::= depth|breadth|simplicity|complexity|lex|mea|random''. По умолчанию используется стратегия ''depth''.

**Стратегия <<вглубь>>.** Вновь активируемые правила помещаются в агенду над всеми правилами такой же значимости. Например, пусть факт f-1 активирует правила rule-1 и rule-2, а факт f-2 активирует правила rule-3 и rule-4. Тогда если f-1 устанавливается раньше, чем f-2, то rule-3 и rule-4 окажутся в агенде выше правил rule-1 и rule-2. Однако положение правила rule-1 относительно правила rule-2 и правила rule-3 относительно правила rule-4 будет произвольным.

**Стратегия <<вширь>>.** Вновь активируемые правила помещаются ниже всех правил с такой же значимостью. Например, пусть факт f-1 активирует правила rule-1 и rule-2, а факт f-2 активирует правила rule-3 и rule-4. Тогда, если f-1 устанавливается раньше, чем f-2, то rule-1 и rule-2 окажутся в агенде выше правил rule-3 и rule-4. Однако, положение правила rule-1 относительно правила rule-2 и правила rule-3 относительно правила rule-4 будет произвольным.

**Стратегия <<простоты>>.** Среди правил одинаковой значимости, вновь активируемые правила помещаются над всеми правилами с равной или большей специфичностью (specificity). Специфичность правила определяется числом сравнений, которые должны быть выполнены в левой части правила. Каждое сравнение с константой или предварительно связанной переменной увеличивает специфичность на единицу. Каждый вызов функции, сделанный из левой части правила в условном элементе с предикатным ограничением ('':''), ограничением возвращаемым значением (''<nowiki>=</nowiki>'') или УЭ-проверкой (''test'') увеличивает специфичность на единицу. Булевы функции <<и>>, <<или>>, <<не>> не увеличивают специфичность правила, но их аргументы увеличивают. Вызовы функций, выполняемые из функций не увеличивают специфичность. Например, следующее правило:
<code>
(defrule example
  (item ?x ?y ?x)
  (test (and (numberp ?x) (> ?x (+ 10 ?y)) (< ?x 100)))
=> ...)
</code>
имеет специфичность 5 (считаются операторы ''(item ?x ?y ?x)'', ''?x'', ''numberp'', ''>'', ''<'').

**Стратегия <<сложности>>.** Среди правил одинаковой значимости, вновь активируемые правила помещаются над всеми правилами с равной или меньшей специфичностью.

**Стратегия LEX.** Для определения места правила в агенде среди правил одинаковой значимости в первую очередь используется новизна образцов, активизирующих данное правило. Каждый факт и экземпляр помечаются <<временным тегом>> для указания его новизны по отношению ко всем другим фактам и экземплярам в системе. Для определения местоположения правила в агенде образцы (факты или экземпляры), связанные с активацией каждого правила сортируются по убыванию новизны. Правило с более поздним образцом помещается выше правил с более ранними образцами. Чтобы определить относительный порядок размещения двух правил, отсортированные временные теги этих образцов, активирующих эти правила, сравниваются попарно начиная с самых больших значений. Сравнение продолжается до тех пор, пока не будет обнаружено, что временной тег одной активации больше соответствующего временного тега другой активации. Правило с большим значением временного тега помещается в агенду выше другого правила.

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

**Стратегия MEA.** Для определения места правила в агенде среди правил равной значимости в первую очередь используется временной тег образца, связанного с первым условием в правиле. Правило, у которого временной тег первого образца (условного элемента) больше временных тегов первых образцов других правил, помещается в агенду выше них. Если временные теги первых образцов равны, то для определения места правила используется стратегия LEX.

**Стратегия случайного выбора (Random Strategy).** Каждой активации сопоставляется случайное число, которое используется для определения ее местоположения в агенде среди активаций равной значимости. Это случайное число сохраняется, когда стратегия изменяется, так что при возврате к случайной стратегии восстанавливается тот же порядок (среди активаций, которые находились в агенде, когда стратегия была изменена).
===== Постановка задачи =====
Исследование процесса выполнения заданного набора правил на заданном множестве фактов при различных стратегиях разрешения конфликтов.

===== Порядок выполнения работы =====
  - Cформировать с помощью конструкции ''deffacts'' исходный набор из пяти произвольных фактов (обозначаемых как ''(a)'', ''(b)'', ''<nowiki>(c)</nowiki>'', ''(d)'' и ''(e)'').
  - В соответствии с вариантом задания сформировать набор правил, где ''(n)'', ''(m)'', ''(p)'', ''<nowiki>(r)</nowiki>'', ''(s)'' и ''(t)'' -- некоторые произвольно выбранные факты (в квадратных скобках указана значимость правила). Сохранить подготовленные конструкции в файле //lab3.CLP//.
  - Загрузить среду CLIPS . Активизировать окна <<Facts Window>> и <<Agenda Window>>. С помощью команды Load Constructs меню File (или <<горячей>> комбинации ^L) загрузить факты и правила из файла //lab3.CLP//.
  - Выполнить начальную установку командой ''(reset)'' (<<горячая>> комбинация -- ^E). Зафиксировать состояние списка фактов и агенды.
  - Выполнить в пошаговом режиме обработку правил (<<горячая>> комбинация -- ^T), фиксируя после каждого шага состояние агенды и списка фактов.
  - Повторить действия п. 4 и 5 при различных стратегиях разрешения конфликтов. Для изменения стратегий спользовать пункт Options меню Execution. Зафиксировать и объяснить полученные результаты.
===== Варианты заданий =====
^  № варианта  ^  Набор правил  ^
|  1  |  (a)(b) <nowiki>=></nowiki> (m) [5000] \\ (a)<nowiki>(c)</nowiki> <nowiki>=></nowiki> (n) [6000] \\ (b)<nowiki>(c)</nowiki>(d) <nowiki>=></nowiki> (p) [5000] \\ (a)(d)<nowiki>(c)</nowiki> <nowiki>=></nowiki> <nowiki>(r)</nowiki> [6000] \\ (m)(n) <nowiki>=></nowiki> (s) [6000] \\ (n)(p)<nowiki>(r)</nowiki> <nowiki>=></nowiki> (t) [5000]  |
|  2  |  (a)(d)(e) <nowiki>=></nowiki> (m) [5000] \\ <nowiki>(c)</nowiki>(d) <nowiki>=></nowiki> (p) [5000] \\ <nowiki>(c)</nowiki>(b)(d) <nowiki>=></nowiki> <nowiki>(r)</nowiki>[6000] \\ (b)(a) <nowiki>=></nowiki> (n) [6000] \\ (p)(m) <nowiki>=></nowiki> (t) [6000] \\ <nowiki>(r)</nowiki>(p)(m) <nowiki>=></nowiki> (s) [5000]  |
|  3  |  (a)(b)<nowiki>(c)</nowiki> <nowiki>=></nowiki> <nowiki>(r)</nowiki> [5000] \\ (e)<nowiki>(c)</nowiki>(d) <nowiki>=></nowiki> (p) [5000] \\ (a)(b) <nowiki>=></nowiki> (m) [5000] \\ (a)(e) <nowiki>=></nowiki> (n) [5000] \\ (m)(n)<nowiki>(r)</nowiki> <nowiki>=></nowiki> (s) [5000] \\ (m)(p) <nowiki>=></nowiki> (t) [6000]  |
|  4  |  (e)(d)(a) <nowiki>=></nowiki> (p) [8000] \\ (b)(d) <nowiki>=></nowiki> (m) [8000] \\ (a)<nowiki>(c)</nowiki> <nowiki>=></nowiki> (n) [8000] \\ (a)(d)(b) <nowiki>=></nowiki> <nowiki>(r)</nowiki> [8000] \\ (m)(p) <nowiki>=></nowiki> (t) [6000] \\ (a)(n)<nowiki>(r)</nowiki> <nowiki>=></nowiki> (s) [6000]  |
|  5  |  (a)(d)(e) <nowiki>=></nowiki> (p) [6000] \\ (b)<nowiki>(c)</nowiki> <nowiki>=></nowiki> (m) [7000] \\ (d)(a) <nowiki>=></nowiki> (n) [7000] \\ (e)(d)<nowiki>(c)</nowiki> <nowiki>=></nowiki> <nowiki>(r)</nowiki> [6000] \\ (b)(n) <nowiki>=></nowiki> (s) [7000] \\ (n)(p)<nowiki>(r)</nowiki> <nowiki>=></nowiki> (t) [7000]  |
|  6  |  <nowiki>(c)</nowiki>(d)(a) <nowiki>=></nowiki> (m) [4000] \\ <nowiki>(c)</nowiki>(e) <nowiki>=></nowiki> (p) [4000] \\ <nowiki>(c)</nowiki>(b)(d) <nowiki>=></nowiki> <nowiki>(r)</nowiki> [4000] \\ (b)(a) <nowiki>=></nowiki> (n) [4000] \\ (p)<nowiki>(c)</nowiki> <nowiki>=></nowiki> (t) [6000] \\ (a)(p)(m) <nowiki>=></nowiki> (t) [5000]  |
|  7  |  (b)<nowiki>(c)</nowiki>(d) <nowiki>=></nowiki> <nowiki>(r)</nowiki> [3000] \\ (a)(b) <nowiki>=></nowiki> (m) [3000] \\ (e)<nowiki>(c)</nowiki>(d) <nowiki>=></nowiki> (p) [3000] \\ (a)(e) <nowiki>=></nowiki> (n) [3000] \\ (m)(e)<nowiki>(r)</nowiki> <nowiki>=></nowiki> (t) [5000] \\ (m)(b) <nowiki>=></nowiki> (s) [5000]  |
|  8  |  (a)(b)<nowiki>(c)</nowiki> <nowiki>=></nowiki> <nowiki>(r)</nowiki> [2000] \\ (e)<nowiki>(c)</nowiki>(d) <nowiki>=></nowiki> (p) [2000] \\ (a)(d) <nowiki>=></nowiki> (m) [3000] \\ (a)(e) <nowiki>=></nowiki> (n) [3000] \\ <nowiki>(c)</nowiki>(n)<nowiki>(r)</nowiki> <nowiki>=></nowiki> (t) [4000] \\ (m)(d) <nowiki>=></nowiki> (s) [5000]  |
===== Содержание отчёта =====
  * Цель работы.
  * Краткое изложение основных теоретических понятий.
  * Постановка задачи с кратким описанием порядка выполнения работы.
  * Пошаговая обработка правил, оформленная в виде таблицы для каждой стратегии, с краткими выводами по каждой из них.
  * Общий вывод по проделанной работе.
  * Код программы.