1. Выше было отмечено, что стереотипы - это образцы, содержащие переменные, тогда как прецеденты являются конкретными решениями, в которых фигурируют константы. Это обстоятельство не позволяет использовать при ассоциативном планировании методы поиска прецедентов (такие как метод разделяемой сети свойств [Kolodner, 1993]).
2. Применение стереотипов при ассоциативном планировании организовано в виде итерационного цикла - последовательности шагов, приводящих к решению. Прецедент обычно является приближенным вариантом полного решения, и план строится на основе только одного прецедента.
1.2 Критерии отбора стереотипов для получения эффективного плана
Обычные алгоритмы сопоставления с образцом неприменимы для поиска близких ситуаций, поскольку предназначены для полного, а не частичного сопоставления. Такие алгоритмы пригодны только для нахождения полностью распознанных ситуаций. Для решателя разработан алгоритм поиска близких ситуаций, подробное изложение которого содержится во второй главе работы. Входными данными алгоритма являются факты из базы задачи решателя. Результатом его работы является список четверок вида: (имя стереотипа, ситуация, строка сопоставления, набор недостающих фактов). На основании этих данных производится адаптация стереотипов и применение их действий, но предварительно производится отбор среди стереотипов с близкими ситуациями. Цель этого отбора - получение эффективного плана.
Критерии отбора стереотипов следующие:
· условие «полезности»;
· условие «доступности»;
· комбинированный критерий.
Условие «полезности» заключается в том, что трудность действия стереотипа, не должна превышать установленного предела. Выполнение данного условия гарантирует, что действие рассматриваемого стереотипа не слишком сложно, то есть применение данного действия не повлечет излишнего усложнения плана.
Условие «доступности» накладывает ограничения, связанные с адаптацией стереотипа. При адаптации стереотипа его действие усложняется - добавляются операторы, связанные с недостающими фактами. Возникает добавленная трудность стереотипа, которую можно охарактеризовать суммарной трудностью целей, необходимых для вывода недостающих фактов. «Доступность» стереотипа означает, что вывод недостающих фактов представляется достаточно простым, другими словами, трудность действий, добавленных при адаптации стереотипа, невелика. При проверке данного условия учитывается тип недостающих фактов, поскольку для вывода фактов разных типов ставятся цели различной трудности (как правило, найти площадь треугольника труднее, чем величину его стороны). Например, «доступным» может оказаться стереотип, адаптация которого требует вывода нескольких несложных фактов, а стереотип с одним недостающим «трудным» фактом может быть отвергнут.
Комбинированный критерий позволяет совместно оценить «полезность» и «доступность» стереотипа. При отборе стереотипа по данному критерию осуществляется проверка: лежит ли значение функции взвешивания в априорно заданных пределах. Функция взвешивания представляет собой функцию от двух переменных - основной трудности стереотипа и его добавленной трудности. С помощью комбинированного критерия исключаются из рассмотрения стереотипы, для которых значения обеих характеристик близки к предельным. В настоящее время в РГЗ используется следующая функция взвешивания: f(x, y) = = x + y (где x - основная трудность, а y - добавленная трудность).
Конкретные значения пределов трудности, используемые в критериях, устанавливаются априорно - независимо от текущей цели и текущего состояния предметной области. Они определяются классом решаемых задач и являются параметрами, с помощью которых можно управлять работой РГЗ, сужая или расширяя рассмотрение близких ситуаций.
Можно провести некоторые параллели с продукционными системами, в которых отбор применяемых продукций является основным способом управления эффективностью их работы. В таких системах каждый раз запускается не более одной активной продукции, а случае, когда одновременно есть несколько активных продукций, производит отбор лучшей - той, которую выгоднее всего запустить Существуют также параллельные реализации продукционных систем, в которых продукции запускаются параллельно без предварительного отбора.. Для ряда продукционных систем использование специальных способов отбора продукций позволило повысить их эффективность. Например, одним из таких способов является правило MEA, предложенное разработчиками экспертной системы R1/XCON [McDermott, 1982].
2. Сопоставитель ситуаций
Распознавание ситуаций стереотипов осуществляется в решателе сопоставителем ситуаций. В основу его реализации положен Rete-алгоритм, использованный в продукционной системе R1/XCON (см. [Forgy, 1982]). Этот алгоритм, как и еще один алгоритм сопоставления с образцом - Treat алгоритм, предложенный Миранкером для продукционных систем (см. [Miranker and Lofaso, 1991]), осуществляет полное сопоставление. Оба они не пригодны для нахождения близких ситуаций стереотипов. Нахождение неполных означивающих наборов фактов для ситуаций в них не реализовано, поскольку при их создании не ставилось такой задачи. Тем не менее, данные, получаемые при работе алгоритмов полного сопоставления, можно использовать для поиска близких ситуаций. Предлагаемый далее алгоритм поиска близких ситуаций использует данные, накопленные в ходе распознавания ситуаций стереотипов РГЗ. Поэтому начнем рассмотрение с того, как осуществляется распознавание ситуаций.
2.1 Идея Rete-алгоритма
Распознавание ситуаций происходит каждый раз при записи новых фактов в базу задачи. Факты (объекты, отношения между объектами, величины объектов) подаются на вход Rete-алгоритма. Его задачей является определение изменений во множестве распознанных ситуаций, вызванных поступившими фактами. Во избежание неэффективного рассмотрения всех ситуаций, они организуются в сеть - разновидность классификационной сети (сеть строится перед сеансом работы решателя). В узлах сети происходит обработка поступивших фактов, во время которой проверяются условия из описания ситуаций. В зависимости от результата проверок факты задерживаются в узлах или передаются дальше по сети. Если в результате обработки какие-либо факты оказываются в концевых узлах сети, это означает, что распознаны ситуации, связанные с данными концевыми узлами.
В ходе распознавания интерпретатор сети проверяет различные условия для фактов базы задачи. Их можно разделить на два класса: внутренние условия (проверяются для одного факта) и внешние (определяют взаимосвязь между несколькими фактами).
При прохождении факта через сеть он сначала попадает в корневую вершину, которая передает его своим преемникам - одновходовым узлам. Это узлы, осуществляющие проверку внутренних условий. Если условие выполнено для поступившего факта, то он передается дальше. Среди преемников одновходовых узлов могут быть двухвходовые узлы, с которыми связаны внешние условия. В таких узлах факты объединяются, а затем проверяется внешнее условие, в зависимости от выполнения которого объединенный факт будет пропущен дальше или остановлен в данном узле. С каждым входом двухвходового узла связан список-память, в котором хранятся копии фактов, пришедших на данный вход. Это необходимо для сопоставления с фактами, которые позднее придут на другой вход узла. Пропуск факта через сеть заканчивается, если не будет выполнена проверка в каком-либо узле, или если факт попадет в концевой (терминальный) узел. Концевой узел завершает последовательность узлов для некоторой ситуации. Факт, попадающий на его вход, сигнализирует об успешном распознавании ситуации и содержит означивание переменных из описания ситуации - строку сопоставления.
Для эффективной работы Rete-алгоритма необходимо, чтобы выполнялись следующие условия:
· Множество ситуаций должно быть статично.
· Анализируемые факты не должны содержать переменных.
· Множество фактов должно изменяться достаточно медленно.
Все эти условия соблюдены в РГЗ, так как набор ситуаций не меняется в ходе решения задачи, и множество записываемых фактов невелико. Это позволило использовать Rete-алгоритм как основу при реализации сопоставителя ситуаций решателя.
2.2 Структура используемой в решателе Rete-сети
При модернизации Rete-алгоритма для нужд РГЗ основные изменения были внесены в структуру Rete-сети. В решателе факты, приходящие на вход сопоставителя ситуаций делятся на два класса - факты-объекты и факты отношения. Факт-объект поступает при анализе текущего контекста, в случае создания нового фрейма-экземпляра какого-либо геометрического объекта или записи нового значения слота в ранее порожденный фрейм. Факт отношение обрабатывается сопоставителем ситуаций при записи нового проблемного отношения в базу задачи. Каждый факт в базе задачи имеет опору - пустую в случае безусловно истинного факта или список условных фактов, при условии истинности которых факт считается истинным. Опора факта учитывается при его обработке в сети решателя, что позволяет учитывать текущий контекст при распознавании ситуаций.
Как и в Rete-сети, в сети решателя каждый узел проверяет некоторое свойство факта, и если оно выполнено в момент проверки, то передает факт своим преемникам, иначе факт отбрасывается. Узлы сети решателя можно разделить на пять классов:
1) начальный узел - не имеет входов, выполняет служебные функции, в сети присутствует один такой узел;
2) одновходовые проверяющие узлы - имеют один вход, один или более выходов, проверяют некоторое свойство факта;
3) одновходовые запоминающие узлы - имеют один вход, один и более выходов, запоминают попавшие на вход факты и без проверок передают дальше по сети;
4) двухвходовые узлы - имеют два входа (правый и левый), один или более выходов, объединяют факты, пришедшие на один вход, с фактами из другого входа, выполняют сложные проверки над объединенными фактами;
5) терминальные узлы - имеют один вход и ни одного выхода, запоминают строки сопоставления ситуаций.
Узлу, как правило, соответствует условие из описания ситуации, исключение составляют служебные (начальный и терминальный) узлы и одновходовые запоминающие узлы, введенные специально для реализации поиска близких ситуаций.
Рассмотрим структуру сети на примере, ранее использованной ситуации fsit242 (описание см. на странице 7). Соответствующий данному описанию фрагмент сети изображен на рис.1.
Условиям ситуации соответствуют десять узлов:
1) проверка факта-объекта на тип „треугольник“;
2) проверка факта-объекта на тип „отрезок“;
3) проверка факта-объекта на тип „окружность“;
4) проверка факта-отношения на тип „равны отрезки“;
5) проверка факта-отношения на тип „диаметр“;
6) проверка факта-отношения на тип „описана около треугольника“;
7) получение имени элемента объекта по роли „сторона“;
8) проверка проблемного отношения „равны отрезки“;
9) проверка проблемного отношения „диаметр“;
10) проверка проблемного отношения “описана около треугольника”.
Кроме того, ситуации соответствует один терминальный узел, один одновходовый запоминающий узел для проверки, является ли близкой ситуация fsit242, и два объединяющих узла join.
В сети могут быть узлы 18 типов. С каждым типом узлов связана определенная функция, выполняемая при интерпретации сети сопоставителем ситуаций.
Узел типа start:
1. Начальный узел сети (start). Присутствует в сети в единственном экземпляре. Определяет тип информации, поступающий на вход сети (объект или отношение) и в зависимости от результата записывает факт в одну из частей сети - для объектов или для отношений.
Одновходовые проверочные узлы:
2. Проверка совпадения типа объекта с указанным (oequ). Является начальным узлом для части сети, предназначенной для объектов. Узел проверяет совпадение типа факта-объекта с заданным значением. В случае успеха передает объект своим преемникам. Например, изображенные на рис. 1 вершины типа oequ проверяют типы геометрических объектов.
3. Проверка совпадения типа отношения с указанным (requ). Узлы этого типа являются начальными для части сети, предназначенной для отношений. В узле осуществляется сравнение типа записываемого факта-отношения с указанным типом (например, типом «диаметр», см. рис.1).
4, 5. Получение имени элемента по имени слота или по роли (slot и role). Узел осуществляет сопоставление элемента, заданного именем слота (ролью), с реальным именем элемента, определенным в задаче. При этом полученное соответствие абстрактного имени элемента из описания ситуации с реальным именем добавляется к факту как часть строки сопоставления. Иногда возможны несколько сопоставлений (например, в треугольнике можно получить три различных имени стороны или угла). Каждое из них передается дальше по сети независимо от других, как новый факт. В рассматриваемом примере узел типа role служит для получения имени стороны треугольника (см. рис.1).
6, 7. Проверка отношения конфигурации между элементами одного или нескольких геометрических объектов (econf и conf). По реальным именам элементов определяется, выполнено отношение или нет. Примером отношения конфигурации может служить отношение «противолежат» между стороной и углом треугольника. В нашем примере узлы данных типов отсутствуют.