Разрешение конфликтов
Как мы видели, в алгоритме функционирования продукционной системы введен специальный шаг принятия решения между шагами анализа ситуации и применения правила. В результате анализа соответствия текущих данных и предпосылок различных правил в имеющемся наборе можно сформировать список правил, которые могут быть применимы в данной ситуации. Такой набор иногда называют конфликтующий множеством (conflict set). В терминологии языка CLIPS этот список называется agenda – список заявок.
Цель процедуры разрешения конфликтов – выбрать из сформированного списка заявок единственное правило, которое должно быть применено в текущей ситуации. Поскольку стратегия разрешения конфликтов оказывает существенное влияние на производительность системы в целом, в большинстве программных систем предусматриваются определенные опции для подстройки этого механизма.
При выработке стратегии разрешения конфликтов обычно используется комбинация разных базовых механизмов, каждый из которых обладает свойственными только ему характеристиками. Производительность экспертной системы зависит от таких ключевых характеристик режима управления, как чувствительность и стабильность. Чувствительность характеризует, как быстро система будет реагировать на изменение среды, которое отражается в рабочей памяти, а стабильность характеризует степень консерватизма в поведении системы ([McDermott andForgy, 1978], [Brownston et al., 1985, Chapter 7]).
Свойства механизмов разрешения конфликтов, которые реально применяются в системах, при всем их разнообразии можно разделить на три довольно компактные группы.
- Разнообразие. Не следует применять к одним и тем же данным правило, которое уже было к ним применено ранее. Самый простой вариант реализации этого механизма – удалять из списка заявок примененное ранее правило. Иногда используется другой вариант – из списка удаляется правило, активизированное в предыдущем цикле, – это предотвращает зацикливание, но если желательно именно повторять процедуру, то в распоряжение программиста предоставляется функция refresh, которая позволяет временно подавить механизм, действующий по умолчанию.
- Новизна. Элементы в рабочей памяти в таких инструментальных системах, как CLIPS, снабжены специальным атрибутом времени порождения. Это позволяет системе ранжировать элементы в списке заявок соответственно тому, как давно введены в рабочую память данные, которые использовались при сопоставлении, а затем приоритет отдается правилам, "реагирующим" на более свежие данные. Идея состоит в том, чтобы следовать за "текущей волной" и меньше внимания уделять тем данным, которые были давно сформированы. К ним можно будет вернуться в дальнейшем, если текущая цепочка рассуждения натолкнется на какое-либо препятствие.
- Специфика. Более специфичные правила, которые включают большее количество компонентов в предпосылках и соответственно труднее удовлетворяются, имеют приоритет перед более общими. Идея состоит в том, что использование таких правил должно принести больше "пользы", поскольку они принимают во внимание больше информации. Эту стратегию можно эффективно использовать при работе с исключениями из общих правил.
Не располагая механизмом разрешения конфликтов, продукционная система будет не в состоянии эффективно справляться с отсутствием детерминизма в наборе правил, обработкой исключений и переключением внимания на определенный стиль рассуждений. Другими словами, представление будет страдать отсутствием эвристических способностей, а управлять функционированием такой системы будет довольно трудно, даже если знания представлены вполне корректно.
В системе интерпретации CLIPS использованы все три описанные выше механизма, что дает хороший эффект. Кроме того, интерпретатор позволяет пользователю связать с любым правилом свойство salience (выпуклость), которое используется для того, чтобы отсортировать список заявок по классам выпуклости. В первом приближении можно считать, что список заявок сортируется сначала по классам выпуклости, а затем правила, имеющие одинаковую "выпуклость", отсортировываются по другим характеристикам механизма разрешения конфликтов.
Разрешение конфликтов в CUPS
В этой врезке будут описаны те стратегии разрешения конфликтов, которые используются в исполнительной системе языка CLIPS. Для краткости мы будем говорить о сортировке правил, хотя в действительности сортируются означивания правил, которые образуются в результате подстановки значений переменных и таким образом отражают соответствие между образцом, специфицированным в предпосылке правила, и действительными данными.
Стратегия глубины. Это воплощение стратегии новизны данных по отношению к правилам, имеющим одинаковый класс выпуклости. Правила, выбранные в список заявок на основании данных, которые были включены в рабочую память сравнительно недавно, располагаются в этом списке раньше правил, при выборе которых использованы более старые данные. Таким образом, предпочтение отдается принципу поиска в глубину в пространстве состояний проблемы, т.е. правила, которые являются следствием более поздних изменений состояния системы, имеют определенный приоритет. В системе CLIPS 6.0 эта стратегия реализуется по умолчанию.
Стратегия ширины. Эта стратегия обратна рассмотренной выше стратегии глубины и предназначается для реализации поиска в ширину в пространстве состояний проблемы. Правила, выбранные в список заявок на основании данных, которые были включены в рабочую память сравнительно давно, располагаются в этом, списке раньше правил, при выборе которых использованы более свежие данные.
Стратегия простоты. Сложность правила определяется количеством операций проверки, которые нужно выполнить при анализе условий данного правила. Более верхнее положение в списке заявок при реализации этой стратегии отдается тем правилам, сложность которых ниже.
Стратегия сложности. Использует тот же критерий, что и стратегия простоты, но располагает правила в обратном порядке – более сложные занимают более приоритетное место в списке.
LEX-стратегия. Предполагает сначала удаление из списка заявок всех правил, которые уже были ранее использованы. Оставшиеся правила с равным значением выпуклости затем отсортировываются по "новизне" используемых данных. Если окажется, что два правила используют данные одинаковой "свежести", то предпочтение отдается тому, которое вовлекает в анализ предпосылок больше данных.
МЕА-стратегия. Во многом аналогична предшествующей, но при анализе новизны принимаются во внимание только первые условия в предпосылках правил. Если окажется, что в списке заявок оказались два претендента с равными показателями, то для выбора между ними применяется механизм LEX-стратегии.
МЕА – это аббревиатура от наименования одной из первых методик решения задач искусственного интеллекта путем построения обратной цепочки рассуждений Mean-Ends Analysis (средство – анализ результата). Идея состоит в том, что стратегия должна быть использована вместе со специальными лексемами цели в рабочей памяти, которые направляют процесс рассуждений и которым соответствуют первые условия в предпосылках правил. Пример использования такой методики представлен в главе 14.
В системе OPS5, многие черты которой унаследовали более поздние программные средства построения экспертных систем, использовались только две последние из перечисленных стратегий – LEX и МЕА. Стратегия LEX показала себя как хорошая стратегия общего применения, в то время как МЕА является эффективной стратегией при решении более специфических задач, таких как планирование. Тривиальный пример использования этой стратегии в программе на языке CLIPS представлен в листинге 5.4.