Базы знаний интелл

7.1.1. Структура пилот-программ и управление выводом

В общем случае PILOT-программа содержит две основные (декларативная и процедурная) и две вспомогательные (включение файлов и переопределение строк) компоненты. Декларативная часть состоит из элементов, специфицирующих переменные, прототипы функций и/или процедур, а также необходимые базы знаний. Продукционная часть состоит из секций, которые, в свою очередь, содержат продукции. Инференциальная составляющая присутствует в ЯПЗ PILOT/2 неявным образом в виде встроенного «арбитра», алгоритм работы которого описывается ниже, и, кроме того, определяется средствами настройки и перепрограммирования такого «арбитра».

Разбиение на секции и правила и специальные условия в виде секционных и пра-виловых разрешений необходимы для того, чтобы обеспечить многоуровневое управление выполнением PILOT-программ. Как известно [Форсайт, 1987], «арбитр» продукционной системы функционирует следующим образом: сначала для всех продукций проверяются условия применимости и из тех продукций, для которых эти условия истинны, формируется конфликтное множество. Из этого множества по определенному критерию выбирается исполняемая продукция; она реализуется (то есть отрабатывается ее правая часть), и цикл управления работой «арбитра» повторяется, пока конфликтное множество на некотором шаге не станет пустым (тогда работа продукционной системы завершается естественным образом) или функционирование не будет прервано явным образом, например с помощью специального действия из правой части исполняемой продукции (в этом случае работа продукционной системы завершается принудительно).

Понятно, что работа такого «арбитра» имеет смысл лишь в тех случаях, когда продукций немного (десятки), а в конфликтном множестве продукций мало (единицы). В противном случае функционирование системы неэффективно и требуются специальные алгоритмы, чтобы «арбитр» не тратил все время только на себя. К настоящему времени разработаны и опробованы на практике различные стратегии увеличения эффективности работы «арбитра» [de Kleer, 1989], которые используются и в данном случае. Но не менее важно иметь гибкие средства описания этих стратегий с уровня входного языка. Тогда пользователь, в зависимости от требований его задачи, сможет отказаться от стандартных стратегий и описать свою собственную, которая адекватна его конкретному случаю.

Для описания стратегий управления выводом решений в ЯЦЗ PILOT/2 служат секционное и правиловое разрешения. Каждое из них является последовательностью фильтров, с помощью которых формируется и/или изменяется конфликтное множество продукций. Для понимания того, как пользоваться этими фильтрами, необходимо знать стратегию встроенного «арбитра» PILOT/2. Поэтому ниже приводится алгоритм его работы, специфицирующий схему, представленную на рис. 7.1.

Алгоритм работы встроенного «арбитра» ЯПЗ PILOT/2

while (уровень-0 ! = NULL ) {

«выбрать из «повестки-дня» секцию для выполнения»;

«сформировать на уровне-1 мн-во правил этой секции»;

«выполнить фильтрацию мн-ва правил на уровне-1 по флагу активна/ неактивна»;

«выполнить фильтрацию мн-ва оставшихся правил на основании вычисления истинности секционного разрешения»;

«сформировать на уровне-2 множество активных правил»;

for (каждого правила на уровне-2) {

«вычислить значение истинности левой части»;

if ( значение истинности правила == TRUE )

«добавить правило в конфл. мн-во на уровне-3»;

}

«выполнить фильтрацию мн-ва оставшихся на уровне-3 правил на основании вычисления истинности правиловых разрешений»;

«сформировать на уровне-4 множество готовых к выполнению правил»;

if ( на уровне-4 осталось одно правило )

«выполнить данное правило»;

else{

«выполнить случайный выбор исполняемого правила из множества правил на уровне-4»;

«выполнить данное правило»;

}

Приведенный алгоритм прозрачен и не нуждается в особых комментариях. Заметим лишь, что фильтр «активна/неактивна» реализован как встроенная проверка флагов активности продукций текущей секции. Первоначально (при запуске секции) «арбитр» считает, что все продукции секции активны, но в процессе выполнения их состояние может измениться за счет применения соответствующих действий. Фильтр секционного разрешения тоже программируется с уровня входного языка. В результате применения этих двух фильтров формируется множество продукций, которые принципиально могут войти в конфликтное множество. Этап фильтрации продукций по истинности левых частей — традиционный, в результате получается традиционное конфликтное множество (правда, уже усеченное за счет предыдущих двух фильтров). На этом множестве в ЯПЗ PILOT/2 может быть организовано дополнительное управление за счет программируемых правиловых разрешений. Если все усечения не привели к однозначному выбору исполняемой продукции, она выбирается случайным образом и цикл работы «арбитра» повторяется.

Точек «влияния» на работу «арбитра» PILOT/2 всего четыре: активность/неактивность продукций; секционное разрешение; истинность левых частей продукций; правиловое разрешение. Существует и пятая точка — алгоритм случайного выбора, но она инженеру по знаниям недоступна.

Секционные и правиловые разрешения суть последовательность операторов if-then-else и действий разрешения. При этом сами условия секционного и пра-вилового разрешений — логические формулы в базисе И-ИЛИ-НЕ с общепринятым старшинством операций. А специфика ЯЦЗ PILOT/2 состоит в том, как определяются элементарные разрешения. Семантика действий разрешений (при условии, что через КМ обозначено конфликтное множество) — следующая:

set (Rl, R2,.... Rk) KM - Rl, R2,..., Rk

insert (Rl, R2,..., Rk) КМ_н - KM_C + Rl + R2 + ... + Rk

remove (Rl, R2,..., Rk) KM_н - KM_C - Rl - R2 - ... - Rk

removeall KM = пустое множество

break Прерывает выполнение оставшихся

элементов секционного или правилового разрешения

Семантика элементарных секционных (продукционных) разрешений — определяется правилами вида:

1. Элементарное секционное разрешение active(Rl,R2,...,Rk) истинно, если все продукции Rl, R2,..., Rk имеют включенные флаги активности.

2. Элементарное секционное (продукционное) разрешение used(Rl,R2,...,Rk) истинно, если все продукции Rl, R2,..., Rk применялись ранее.

3. Элементарное продукционное разрешение ready(Rl,R2,...,Rk) истинно, если все продукции Rl, R2,..., Rk готовы к выполнению, что, в свою очередь, справедливо, если их левые части (условия) истинны.

Понятно, что практически все элементарные разрешения работают с именами продукций, так что проверка соответствующих условий выполняется «арбитром» достаточно быстро. И этих средств (в подавляющем большинстве случаев) достаточно для существенного увеличения гибкости управления продукционной системой и сохранения в то же время приемлемой эффективности ее работы.

Вместе с тем в ЯПЗ PILOT/2 инженеру по знаниям предоставлена возможность управления работой продукционной системы и на основе анализа базы знаний. Нужно лишь понимать, что это управление «дорогое», так что пользоваться им следует лишь в тех случаях, когда соответствующие условия невозможно (или нецелесообразно) проверять в левых частях продукций.

Содержание