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

В главе 5 были упомянуты стратегии разрешения конфликтов LEX и МЕА, реализованные в языке CLIPS. Ниже будет в общих чертах рассмотрена реализация стратегии МЕА, которая использована в системе R1/XCON.

Как было показано в главе 3, анализ "средство — анализ результата" является абстрактным режимом формирования цепочки обратного логического вывода в случае, когда определена некоторая цель. Этот режим позволяет выбрать операторы или правила, которые способны сократить "расстояние" между текущим и заданным целевым состоянием проблемы. Несложно показать, как этот режим можно использовать в контексте порождающей системы с обратной стратегией логического вывода, например MYCIN, когда весь процесс начинается с цели самого верхнего уровня общности (см. главу 3). В системах, использующих прямой логический вывод, которые строятся на основе языковых средств OPS5 или CLIPS, применяется стратегия разрешения конфликтов МЕА. Основанный на ней режим управления позволяет программе "продвигаться" по неявно заданному дереву целей, которые представлены специальными лексемами в рабочей памяти экспертной системы.

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

(1) Исключить из конфликтующего множества те правила, которые уже были применены в предыдущем цикле. Если после этого множество стало пустым, прекратить процесс.

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

Равным приоритетом, они сохраняются в конфликтующем множестве, а прочие из него удаляются. Далее выполняется переход к шагу (3).

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

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

(5) Применяется правило, выбранное произвольным образом из оставшихся в конфликтующем множестве, и процесс прекращается.

Таким образом, стратегия МЕА объединяет в едином алгоритме анализ таких показателей, как повторяемость, новизна и специфика. Алгоритм LEX практически идентичен алгоритму МЕА за одним исключением — в нем отсутствует шаг 2), а на шаге 3) сравниваются все элементы условий конкретизированных правил и связанных с ними элементов рабочей памяти. Первые элементы условий, которые использовались на шаге 2), являются, как правило, лексемами задач в рабочей памяти (в главе 5 приведен пример программы, которая манипулирует такими лексемами).

Формирование суждений с учетом ограничений: метод Match

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

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

В контексте подзадачи 3) существует ряд ограничений, которые можно использовать для унификации поиска решения.

Каждый модуль UNIBUS требует размещения на генплате ответного разъема подходящего типа.

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

Выходная мощность каждого блока питания ограничена и не зависит от количества слотов на генплате.

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

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

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

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

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

Для основной проблемы в том способе решения проблемы, который использован в системе R1, разработчики выбрали наименование "Match" (сопоставление), которое вносит некоторую путаницу в смысл проблемы. Любые системы, основанные на применении правил, в той или иной мере используют сопоставление, но разработчики системы R1 придали термину Match (начинающемуся с прописной буквы "М") несколько иной смысл. Вместо того чтобы формировать набор решений-кандидатов и затем выбирать из них подходящий, как это делается в системе DENDRAL (см. главу 20), программа, использующая метод Match, на каждой стадии процесса "распознает", что ей делать дальше.

Метод Match можно рассматривать как метод поиска экземпляра, который означивал бы (конкретизировал) определенную "форму", — символическое выражение, содержащее переменные. Примером такой формы может служить левая часть выражения порождающего правила. Таким образом, пространством поиска для метода Match является "пространство всех означиваний переменных в форме" [McDermott, 1982, а, р. 54]. Каждое состояние в этом пространстве соответствует частично означенной форме.

Существуют формы, которые заключают в себе знания, специфические для данной предметной области, касающиеся удовлетворения ограничений. Именно с ними при решении данной частной проблемы и имеет дело метод Match. Мак-Дермот указал на два условия, которые нужно удовлетворить для того, чтобы можно было использовать для отыскания решения этот довольно "слабый" метод поиска.

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

Однонаправленное распространение условий. Применение какого-либо оператора должно сказываться только на тех компонентах решения, которые до сих пор не были определены. Другими словами, применение какого-либо оператора не должно давать никаких побочных эффектов, которые могли бы повлиять на уже сформированные компоненты решения. Само название условия говорит о том, что последствия применения операторов должны распространяться только в одном направлении — от текущего контекста к "дочерним" и еще не проанализированным "соседним", но не в обратном направлении, — к "родительским" контекстам.