Разработка механизма вывода решений.

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

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

Наиболее часто реализуемый вариант структуры взаимодейст­вия решающих компонентов систем ИИ включает в себя БЗ, рабочую память (глобальную БД) и управляющую структуру (исходя из концепции Ньюэлла о реализации про­дукционных систем). Работа управляющей структуры в общем случае [113] заключается в анализе состояния рабочей памяти и выявлении по описанию характера и типа данных в рабочей памяти в БЗ знаний (правил, объектов или фактов), соотносимых с этим описанием. То есть в БЗ определяется некий подхо­дящий блок знаний (или набор блоков), готовый работать в со­ответствии с текущими данными рабочей памяти.

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

Системы, в основу функционирования которых положена идея обработки модулей знаний по образцам, получили название сис­тем выводов, управляемых по образцам [95]. Рассматривая систему выводов, управляемых по образцам, преимущественно имеют в виду систему, основанную на правилах, хотя возможны и иные реализации подобных систем. В системах, основанных на прави­лах, в качестве модулей, управляемых по образцам, выступают либо отдельные правила, либо блоки правил, отражающие опре­деленный уровень или тип эвристических знаний в БЗ.

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

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

На стадии сопоставления на основе сравнения с образцами активных правил и действующих данных определяются модули, для которых удовлетворяются условия выполнения. Они называ­ются означенными. В результате сопоставления всех активных модулей и данных выявляется множество таких означенных моду­лей. Это множество называется конфликтным, так как только некоторые означенные модули могут быть задействованы в текущей ситуации. Существуют различные способы и алгоритмы уско­рения работ на стадии сопоставления, поскольку активных пра­вил и данных может быть достаточно много.

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

На стадии выполнения запускаются модули, выбранные на пре­дыдущей стадии. В результате выполнения модифицируются эле­менты и структуры данных рабочей памяти, выдаются необходи­мые рекомендации или решения пользователю, возможны измене­ния в самой БЗ и т. д.

Достаточно подробное описание содержания перечисленных стадий реализации общей стратегии функционирования систем, основанных на правилах, приведено, например, в [46].

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

Процесс заканчивается либо когда определяется, что значения всех подцелей построенной цепочки истинны, либо когда БЗ ис­следована и результаты отсутствуют.

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

Наряду с рассмотренными, получившими широкое распростра­нения стратегиями существуют и другие виды стратегий управле­ния. Например, комбинированная стратегия управления, которая объединяет в себе стратегии прямых и обратных рассуждений.

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

В рассмотренных стратегиях поиска возможные переходы в пространстве состояний представляются правилами перехода. Эти правила определяют, в какие состояния из исходных разрешены переходы.

Одним из путей развития стратегий управления поискам яви­лось изменение содержания правил перехода. Во многих пред­ставлениях пространства поиска было целесообразнее описывать в активной части правила не новое состояние, а те изменения, которые должны вноситься в рабочую область при выполнении данного правила и связаны с модификацией текущих данных. Это обусловило появление нового типа структур для реализации стра­тегий управления — списков событий (или списков заявок) [75]. Указанный тип структур получил название agenda (дословно - повестка дня; используется также написание русскими буква­ми — агенда). На основе структуры агенды реализуется страте­гия управления агенда-система. Агенда-система работает с таким понятием, как источник знания. Источники знания — это модули, содержащие в правилах перехода помимо условия и действия имя и набор параметров планирования, которые определяют условия вхождения источника знания в план. План представляет собой последовательность или список модулей (источников знаний) для выполнения исходя из состояния системы и дисциплины плани­рования.

Агенда-система функционирует следующим образом. На на­чальной стадии выбираются источники знаний, которые готовы к применению, т. е. их образцы сопоставимы с текущими данными ИЛИ условные части удовлетворены. Эти источники знаний вносят­ся в агенду (т. е. в список заявок). Далее из этого списка агенда-система планирует активизацию какого-либо источника знания. Планирование осуществляется на основе соответствия значений параметров планирования дисциплине планирования. По завер­шении процесса определяют, исходя из состояния системы, акти­визацию какого следующего источника знаний следует выполнить. Реализация вывода на основе агенда-системы осуществляется до тех пор, пока вся агенда не будет исчерпана.

Дальнейшим развитием стратегий управления выводом стали системы black board (дословный перевод — системы с классной доской). Точнее отражает суть этой системы вывода название «доска объявлений».

Поднятия об укрупненных -модульных источниках знаний и ор­ганизации широких взаимосвязей посредством общей структури­рованной доски объявлений были введены для системы HEARSAY. Далее они развивались в других модификациях этой системы [97, 87]. Достаточно подробно работа систем с доской объявле­ния описана в [94, 50].

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

Системы с доской объявлений основываются на понятии гло­бально доступной структуры данных и независимых источников знаний, которые связываются при -последовательном формирова­нии гипотез на доске объявлений. Процесс поиска решений в этих системах практически представляет собой процесс планирования формирования на доске объявлений гипотез и их проверки. Фор­мирование гипотез — это выбор и активизация источников зна­ний и внесение последовательных изменений на доску объявле­ний. Следовательно, структуру данных, содержащую входные и промежуточные данные, а также окончательные результаты, можно рассматривать как структуру гипотезы. Кроме этой струк­туры, доска объявлений содержит информацию, связанную с уп­равляющими действиями. Источники знаний могут иметь доступ к управляющей информации на доске объявлений; они строятся как управляющие или планирующие.

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

Источники знаний рассматриваются как порождающие прави­ла, которые реагируют на изменения доски объявлений, вызывае­мые другими источниками знаний, и сами создают новые измене­ния. Для активизации источника знания производится операция сопоставления образца с содержимым доски объявлений. При со­поставимости создается узел записи активизации для источника знаний. Записи активизации конкурируют между собой за выпол­нение. Преодолению конфликтных требований может способство­вать процедура планирования. Она заключается в том, что в конце выполнения каждого источника знаний исходя из текущего состояния определяется, какой источник знаний реализовывать следующим. Узел записи активизации на доске объявлений в зо­не для планирования используется в качестве механизма для представления состояния активизации.

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

Краткий обзор основных стратегий управления позволяет сде­лать вывод, что в своем развитии каждая последующая система во многом базируется на предыдущей, включает ее некоторые эле­менты и отражает новый этап развития. Известны многие вари­анты прямой, обратной и комбинированной стратегий управления, агенда-систем и систем с доской объявлений. Несколько по иному строятся стратегии управления поиском решений при сетевых и фреймовых представлениях знаний. Здесь они рассматриваться не будут.

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

В качестве критерия классификации методов поиска выберем размеры и характер пространства поиска, дополняя этот крите­рий другими показателями. Ясно, что такая классификация мето­дов весьма условна, тем более что многие методы используются в пространствах поиска различного типа или при необходимости объединяются для решения существенно сложных задач. Однако подобная классификация методов поиска решений в ИС поз­воляет более системно рассматривать вопрос взаимовлияния и взаимосвязи специфики проблемной области, пространства поис­ка решений и существующих средств реализации вывода реше­ний.