8, 9. Проверка известности (или неизвестности) значения элемента (valknown и valnknown). Узлы данного типа проверяют известность слота геометрического объекта. Если имя слота не указано, то по умолчанию у объекта проверяется слот «величина» (value). В узлах типа valknown, если значение слота известно, то опора обрабатываемого факта объединяется с опорой проверяемого слота (поскольку его значение может быть известно условно), и факт с объединенной опорой пропускается дальше по сети. Если требуется, чтобы значение не было известно, опора слота объединяется с отрицанием опоры пришедшего факта. Факт с новой опорой передается потомкам узла. Узлы типа valnknown пропускают факт дальше и при неизвестном значении слота, но в этом случае меняют его опоры. На рис.1 узлов типа valknown нет, так как в описании ситуации fsit242 нет соответствующих условий.
10, 11. Проверка равенства (или неравенства) значения слота заданной константе (valequ и valnoequ). Узлы данного типа проверяют совпадение значения слота геометрического объекта со значением, записанным в узле. Преобразование опоры факта осуществляется аналогично вышеописанным преобразованиям в узлах типа valknown/valnknown с поправкой на проверяемое условие.
Одновходовые запоминающие узлы:
12. Узлы типа store. С каждым из них связан список-память, в который заносятся все приходящие на вход узла факты. После запоминания факт без проверок и изменений передается потомкам узла. (Здесь описана функция узла только при распознавании ситуаций. Обработка фактов в узлах такого типа при поиске близких ситуаций будет описана ниже.)
Двухвходовые вершины:
13. Объединение фактов без проверок (join). Узел служит для получения всех различных парных объединений всех приходящих в нее фактов. Никаких проверок в узле не выполняется. Для запоминания фактов, как и все двухвходовые узлы, он имеет две памяти - левую для левого входа и правую для правого. Пришедший факт объединяется с фактами из памяти противоположной вершины, опоры которых включены в текущий контекст. Полученные объединенные факты пропускаются дальше по сети. На рис.1 узлов данного типа два.
14, 15. Проверка наличия (отсутствия) проблемного отношения в базе задачи (prob или nprob). Узел проверяет проблемное отношение между объектами или элементами объектов. Он также имеет две памяти для запоминания фактов. Входы узла не являются симметричными. На левый вход приходит факт-объект (возможно, несколько объединенных фактов-объектов), а на правый - факт-отношение. Для пришедшего отношения поверяется наличие в левой памяти факта-объекта, у которого в строке сопоставления аргументы отношения имеют такое же означивание, что и в факте-отношении. Опора каждого такого факта (отрицание опоры в узлах типа nprob) объединяется с опорой отношения, после чего факт передается потомкам узла. В случае, когда в узел пришел факт-объект, производится поиск соответствующих отношений в правой памяти. Если в узле типа nprob не найдено ни одного соответствия между объектами и отношениями, факт объект пропускается дальше по сети без изменения опоры. В узлах типа prob такие факты отвергаются, как не прошедшие проверку. На рис.1 узлы данного типа проверяют проблемные отношения, «диаметр» и «описана около треугольника».
16, 17. Проверка наличия (отсутствия) симметричного отношения (sprob или nsprob). Этот тип узлов отличается от предыдущего тем, что предназначен для проверки симметричных проблемных отношений. В узлах учитывается то, что порядок аргументов симметричного отношения значения не имеет, в отличие от обычных проблемных отношений. Обработка фактов в узлах данного типа производится аналогично обработке в узлах типа prob/nprob, но с поправкой на указанное обстоятельство. Узел данного типа в сети для ситуации fsit242 проверяет симметричное проблемное отношение «равны отрезки».
Узел типа end:
18. Терминальный узел сети (end). Узлы данного типа являются заключительными узлами фрагментов сети, соответствующих описаниям ситуаций из базы знаний. Они запоминают все пришедшие к ним объединенные факты в своей памяти (вместе со строкой сопоставления). Если факт приходит с ложной в текущем контексте опорой, то он не запоминается, более того из памяти удаляются все тождественные ему факты, имеющие другие опоры.
Результатом обработки фактов в узлах сети решателя является множество ситуаций, распознанных в текущем контексте. Для поиска близких ситуаций сопоставитель решателя в том виде, котором он описан выше, не пригоден. Неполные означивающие наборы фактов для близких ситуаций будут остановлены в промежуточных узлах сети, поскольку по определению часть условий близких ситуаций не выполнена. Тем не менее, при интерпретации сети решателя в памяти узлов запоминаются данные, которые полезны при поиске близких ситуаций. Использование этих данных при поиске близких ситуаций описано ниже.
2.3 Использование Rete-сети при поиске близких ситуаций
При ассоциативном планировании стереотип должен быть пригодным для уточнения текущей цели. Поэтому первым этапом поиска близких стереотипов является определение множества стереотипов, уточняющих цели того же типа, что и текущая. Абстрактное описание уточняемой стереотипом цели сравнивается с текущей целью, и если цель подходит по типу, то стереотип считается пригодным и с ним связывается частичная строка сопоставления абстрактных объектов из описания стереотипа с реальными объектами из текущей уточняемой цели.
На втором этапе поиска происходит проверка является ли близкой ситуация стереотипа, то есть, существует ли для нее неполный означивающий набор фактов, который можно достроить для полного распознавания ситуации. Если набор существует (а их может быть несколько, как показано в 1.1.), то определяются недостающие факты (для каждого из наборов). Этот этап занимает большую часть времени, поскольку требует проверки условий из описания ситуации. Существенно сократить число проверок позволяет использование данных, накопленных сопоставителем ситуаций.
В каждом фрагменте Rete-сети, соответствующем ситуации, узлы осуществляющие проверки фактов, вывод которых невозможен при работе решателя, расположены выше узлов, проверяющих условия, которые можно удовлетворить выводом новых фактов (см. Рис. 2). Во время работы сопоставителя ситуаций на выход верхней части Rete-сети попадают все строки сопоставления для данной ситуации, возможные в данном состоянии базы задачи. Они запоминаются в памяти узла store, чтобы затем быть использованными при поиске близких ситуаций. Это полные строки сопоставления, поскольку узлов, в которых происходит означивание в нижней части Rete-сети нет. Некоторые из этих строк проходят нижнюю часть сети и попадают в терминальный узел (узел end) - они соответствуют распознанным ситуациям. Эти строки запоминаются в памяти терминального узла и в дальнейшем выдаются в ответ на запросы к сопоставителю ситуаций. Остальные строки сопоставления соответствуют близким ситуациям, поскольку для каждой из них невыполненые условия в описании ситуации можно удовлетворить добавлением новых фактов (условия на значения слотов объектов и проблемные отношения). То есть, каждая из строк соответствует неполному означивающему набору фактов, который можно достроить. Остается определить недостающие факты, чтобы можно было применить найденную близкую ситуацию при планировании.
Узел store специально предназначен для поиска близких ситуаций. Это одновходовый узел с памятью, в которой запоминаются все входящие строки сопоставления. При обычной работе сопоставителя, функция этого узла ограничивается только запоминанием и передачей строк сопоставления потомкам узла. В режиме поиска близких ситуаций строки сопоставления из памяти узла store (те из них, которые включают в себя частичные строки, полученные при сопоставлении текущей цели с целью из описания стереотипа, и которые не содержатся в памяти узла end) передаются для проверок потомкам узла store. При этом проход фактов по сети отличается от прохода в режиме распознавания ситуаций. Попадая в какой-либо узел, строка сопоставления обрабатывается в соответствии с типом данного узла, но если проверка, связанная с узлом неуспешна, то строка передается потомкам узла с пометкой о невыполненном условии. Если же проверка успешна, строка передается дальше без пометок. Таким образом, дойдя до узла end, каждая строка сопоставления для близкой ситуации будет иметь одну или более пометок о невыполненных условиях, по которым будет построены недостающие факты.
Перечень шагов алгоритма поиска близких стереотипов:
1. Положить пустым множество близких стереотипов S.
2. Для всех стереотипов из базы знаний повторять шаги 3-12.
3. Если тип уточняемой стереотипом цели совпадает с типом текущей цели, то запомнить частичную строку сопоставления объектов из описания уточняемой стереотипом цели с реальными объектами из текущей цели, иначе перейти к обработке другого стереотипа (шаг 2).
4. Для ситуации стереотипа найти соответствующие узлы Rete-сети типа store и end.
5. Для всех строк сопоставления из памяти узла store повторять шаги 6-11.
6. Если строка сопоставления содержит частичную строку, запомненную на шаге 3, и отсутствует в памяти вершины end, то передать строку узлу, который является потомком вершины store, иначе перейти к обработке другой строки (шаг 5).
7. Если тип узла-потомка end, то выполнить проверку, соответствующую узлу, иначе перейти на шаг 10.
8. Если проверка неуспешна, то сделать пометку о невыполненном условии.
9. Передать строку потомку текущего узла и перейти на шаг 7.
10. Если строка сопоставления имеет пометки о невыполненных условиях, то стереотип считать близким, построить набор недостающих фактов по пометкам строки, занести четверку (имя стереотипа, ситуация, строка сопоставления, список недостающих фактов) в множество S.
11. Если есть еще строки в памяти узла store, перейти на шаг 5.
12. Если в базе знаний остались нерассмотренные стереотипы, то перейти на шаг 1.
Запись алгоритма на псевдокоде:
Set:= Ш {Set - множество близких стереотипов}
FOR Ster:= Ster1 TO SterN DO {Ster1, …, SterN - все стереотипы в базе знаний}
IF тип цели Ster совпадает с типом текущей цели THEN
Match1:= частичная строка сопоставления объектов из описания уточняемой
стереотипом цели с реальными объектами из текущей цели
FOR Str:= Str1 TO StrM DO
{Str1, …, StrM - строки сопоставления из памяти узла Store ситуации стереотипа Ster, которых нет в памяти узла End}
IF Match1 является подстрокой Str THEN
Node:= узел-потомок узла Store
WHILE тип Node End DO
Выполнить проверку в узле Node
IF проверка неуспешна THEN приписать к Str пометку о невыполненном условии
END IF
Node:= узел-потомок Node
END WHILE
построить список недостающих фактов Facts по пометкам Str
Set:= Set + (Ster, ситуация Ster, Str, Facts)
END IF
END FOR
END IF
END FOR
Приведенный алгоритм поиска близких стереотипов можно сравнить с другим алгоритмом, в котором поиск ситуаций близких стереотипов происходит одновременно с сопоставлением ситуаций. Во втором алгоритме не требуется специальных запоминающих узлов, а факты, обрабатываемые в сети решателя, проходят от узла к узлу с пометками о выполнении или невыполнении проверяемых в узлах условий. Попадая в концевую вершину, факты, не имеющие пометок о неудачных проверках, сигнализируют о распознавании ситуаций, а факты с пометками о нарушенных условиях - о близких ситуациях.
Недостатком сопоставителя ситуаций, выполняющего одновременно полное распознавание и поиск близких ситуаций, является его меньшая эффективность по сравнению с алгоритмом, который был рассмотрен ранее. Во-первых, значительно увеличивается время распознавания ситуаций, поскольку факты не задерживаются в промежуточных узлах сети, тогда как именно отбрасывание фактов, не прошедших проверок, обеспечивает сравнительно быстрое распознавании ситуаций в Rete-алгоритме (оценки эффективности Rete-алгоритма приведены в работе [Forgy, 1982]). Во-вторых, лишь малую часть найденных по второму алгоритму близких ситуаций удается использовать для уточнения текущей цели, так как не все стереотипы, связанные с ними, будут пригодны для уточнения текущей цели. Это означает, что большая часть времени работы сопоставителя ситуаций будет затрачена впустую.
Необходимо заметить, что алгоритм поиска близких ситуаций является достаточно универсальным. Его можно применять в тех предметных областях, которые отвечают требованиям, необходимым для применения Rete-алгоритма.
3. Построение уточнения цели при ассоциативном планировании
Уточнение текущей цели, получаемое при ассоциативном планировании, представляет собой подграф графа целей, имеющий параллельно-последовательную структуру - такую же что и структура уточнения, получаемого методом обратной цепочки рассуждений (будем далее называть такое уточнение дедуктивным). Разница между этими двумя видами уточнений заключается в способе их построения.
Дедуктивное уточнение состоит из параллельно объединенных цепочек целей, добавление каждой из которых предписано действиями стереотипа, уточняющего текущую цель. Процесс построения ассоциативного уточнения плана (уточнения на основе близких ситуаций) сложнее, чем построение дедуктивного уточнения. Ассоциативное уточнение тоже состоит из параллельно объединенных цепочек целей, каждая из которых построена на основе стереотипа с близкой ситуацией. Такие цепочки составляются из двух частей - подцепочки целей для вывода недостающих фактов и целей, добавляемых в действии стереотипа. Подцепочка целей для вывода недостающих фактов строится следующим образом:
1) для каждого недостающего факта конструируется цель в соответствии с его типом, реальными объектами и их слотами, указанными в факте;
2) сконструированные цели объединяются последовательно без указания их порядка, так как все они должны лежать в графе на одном пути, а порядок их достижения не важен.