Методы поиска решений в экспертных системах

 

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

- размер, определяющий объем пространства, в котором предсто­ит искать решение;

- изменяемость области, характеризует степень изменяемости об­ласти во времени и пространстве (здесь будем выделять статические и динамические области);

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

- определенность данных о решаемой задаче, характеризует сте­пень точности (ошибочности) и полноты (неполноты) данных. Точ­ность (ошибочность) является показателем того, что предметная область с точки зрения решаемых задач описана точными или неточны­ми данными; под полнотой (неполнотой) данных понимается доста­точность (недостаточность) входных данных для однозначного реше­ния задачи.

Требования пользователя к результату задачи, решаемой с по­мощью поиска, можно характеризовать количеством решений и свойствами результата и (или) способом его получения. Параметр “количество решений” может принимать следующие основные значе­ния: одно решение, несколько решений, все решения. Параметр “свойства” задает ограничения, которым должен удовлетворять полу­ченный результат или способ его получения. Например, для си­стемы, выдающей рекомендации по лечению больных, пользователь может указать требование не использовать некоторое лекарство (в связи с его отсутствием или в связи с тем, что оно противопоказано данному пациенту). Параметр “свойства” может определять и такие особенности, как время решения (“не более чем”, “диапазон времени” и т.п.), объем памяти, используемой для получения результата, указание об обязательности (невозможности) использования каких-либо зна­ний (данных) и т.п.

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

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

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

- методы поиска в одном пространстве – предназначены для использования в следующих условиях: области небольшой раз­мерности, полнота модели, точные и полные данные;

- методы поиска в иерархических пространствах – пред­назначены для работы в областях большой размерности;

- методы поиска при неточных и неполных данных;

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

Предполагается, что перечисленные методы при необходимости должны объединяться для того, чтобы позволить решать задачи, сложность которых возрастает одновременно по нескольким пара­метрам.

 

Поиск решений в одном пространстве

 

Методы поиска решений в одном пространстве обычно делятся на поиск в пространстве состояний, поиск методом редукции, эвристиче­ский поиск и поиск методом “генерация-проверка”.

 

Поиск в пространстве состояний. Задача поиска в пространстве состояний обычно формулируется в теоретико-графовой интерпретации.

Пусть задана тройка (S0, F, Sт), где S0 – множество начальных со­стояний (условия задачи), F – множество операторов задачи, отобра­жающих одни состояния в другие; Sт – множество конечных (целевых) состояний (решений задачи).

В данном случае решить задачу – значит определить такую по­следовательность операторов, которая преобразует начальные со­стояния в конечные. Процесс решения можно представить в виде гра­фа G = (X, Y), где Х = {х0, x1,...} – множество (в общем случае бесконечное) вершин графа, каждая из которых отождествляется с одним из состояний, а Y – множество, содержащее пары вершин (xi,xj), (xi,xj)Х. Если каждая пара (xi,xj) неупорядочена, то ее называют ребром, а граф – неориентированным. Если для каждой пары (xi,xj) задан поря­док (направление), то пару (xi,xj) называют дугой (ориентированным ребром), а граф называют ориентированным (направленным). Верши­ны пары (xi,xj) называют концевыми точками ребра (дуги).

Поиск в пространстве состояний естественно представить в виде ориентированного графа. Наличие пары (xi,xj) свидетельствует о су­ществовании некоторого оператора f (fF), преобразующего состоя­ние, соответствующее вершине xi в состояние хj. С точки зрения поис­ка в пространстве состояний для некоторой вершины xi уместно выде­лить множество всех направленных пар (xi,xj)Y, т.е. множество дуг, исходящих из вершины хi (родительской вершины), и множество вер­шин (называемых дочерними вершинами), в которые эти дуги приво­дят. Множество дуг, исходящих из вершины хi, соответствует мно­жеству операторов, которые могут быть применены к состоянию, соответствующему вершине xi.

В множестве вершин Х выделяют подмножество вершин Х0Х, соответствующее множеству начальных состояний (S0), и подмноже­ство вершин ХтХ, соответствующее множеству конечных (целевых) состояний (Sт). Множество Хт может быть задано как явно, так и не­явно, т.е. через свойства, которыми должны обладать целевые со­стояния.

Отметим, что граф G может быть задан явно и неявно. Неявное задание графа G состоит в определении множества Х0Х (соответствующего множеству начальных состояний) и множества операторов, которые, будучи применимы к некоторой вершине графа, дают все ее дочерние вершины.

Итак, граф G задает пространство состояний, т.е. пространство, в котором осуществляется поиск решения. Построение пространства осуществляется с помощью следующего процесса. Берется некая вер­шина x0Х0, к ней применяются все возможные операторы, порож­дающие все дочерние вершины. Этот процесс называют процессом раскрытия вершин. Если получена целевая вершина, то она не раскры­вается. Процесс построения пространства состояний заканчивается, когда все нераскрытые вершины являются целевыми, или терминаль­ными (т.е. вершинами, к которым нельзя применить никаких операто­ров). В связи с тем, что пространство состояний может содержать бес­конечное количество вершин, на практике процесс порождения про­странства ограничивают либо временем, либо объемом памяти.

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

- глубина начальной вершины равна нулю;

- глубина “неначальной” вершины равна единице плюс глубина наи­более близкой родительской вершины.

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

- при достижении целевой вершины;

- при достижении терминальной вершины;

- при построении в ходе поиска вершины, глубина которой превышает некоторую граничную глубину.

При поиске в ширину вершины раскрываются в том же порядке, в котором они порождаются.

Если в пространство состояний ввести операторы, переводящие состояние Si в предшествующее состояние Si-1, то поиск можно осу­ществлять не только в направлении от начального состояния к целе­вому, но и в обратном направлении. Поиск первого типа называют поиском от данных, или прямым поиском, а поиск второго типа – поис­ком от цели, или обратным поиском. Можно организовать поиск в двух направлениях одновременно. Такой поиск называют двунаправленным (или бинаправленным).

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

Рис. 3.3. Пространство состояний, построенное поиском в глубину (а) и в ширину (б)

 

Поиск методом редукции. При поиске методом редукции решение задачи сводится к реше­нию совокупности образующих ее подзадач. Этот процесс повторя­ется для каждой подзадачи до тех пор, пока каждая из полученного набора подзадач, образующих решение исходной задачи, не будет иметь очевидное решение. Подзадача считается очевидной, если ее решение общеизвестно или получено ранее. Процесс решения задачи разбиением ее на подзадачи можно представить в виде специального направленного графа G, называемого И/ИЛИ-графом. Каждой вер­шине этого графа ставится в соответствие описание некоторой задачи (подзадачи). В графе выделяют два типа вершин: конъюнктивные вершины и дизъюнктивные вершины. Конъюнктивные вершины, или вершины типа “И”, вместе со своими дочерними вершинами интер­претируются так: решение задачи сводится к решению всех ее подза­дач, соответствующих дочерним вершинам конъюнктивной вершины. Дизъюнктивные вершины, или вершины типа “ИЛИ”, вместе со своими дочерними вершинами интерпретируются так: решение задачи сво­дится к решению любой из ее подзадач, соответствующих дочерним вершинам дизъюнктивной вершины.

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

Графически для различения дизъюнктивной и конъюнктивной вершин дуги, исходящие из конъюнктивной вершины, соединяются дужкой при вершине. Пример графического представления разбиения задачи на подзадачи приведен на рис 3.4. Здесь S0 – исходная задача, для решения которой требуется решить подзадачу S3 или подзадачи S1 и S2. Решение задачи S1 сводится к решению либо подзадачи S4, либо подзадачи S5. Решение подзадачи S3 сводится к решению подзадач S6 и S7. Решение задач S2, S5, S7 предполагается известным, решение задач S4 и S6 неизвестно. В приведенном примере задача S0 может быть ре­шена либо путем решения задачи S3, либо путем решения задач S1 и S2. В связи с тем, что в И/ИЛИ-графе каждая вершина относится только к одному типу (либо И, либо ИЛИ), то для записи графа, изображенно­го на рис. 3.4 в виде И/ИЛИ-графа, надо ввести дополнительную вер­шину (вершина R1 (рис. 3.5). Двойными линиями выделен решающий граф задачи S0, а конечные вершины обозначены зачер­ненными квадратами.

 

Риc. 3.4. Графическое представление процесса разбиения задачи на подзадачи

Рис.3.5. Пример И/ИЛИ-графа

 

Цель процесса поиска в И/ИЛИ-графе – показать, что начальная вершина разрешима, т.е. для этой вершины существует решающий граф. Определение разрешимой вершины в И/ИЛИ-графе можно сфор­мулировать рекурсивно следующим образом:

1. Конечные (целевые) вершины разрешимы, так как их решение известно по исходному предположению.

2. Вершина ИЛИ разрешима тогда и только тогда, когда разре­шима по крайней мере одна из ее дочерних вершин.

3. Вершина И разрешима тогда и только тогда, когда разрешима каждая из ее дочерних вершин.

Итак, решающий граф определяется как подграф из разрешимых вершин, который показывает, что начальная вершина разрешима (в соответствии с приведенным выше определением). На рис. 3.5 разре­шимые вершины – темные, а неразрешимые оставлены светлыми.

Для графа И/ИЛИ, как и для поиска в пространстве состоя­ний, можно определить поиск в глубину и в ширину как в пря­мом, так и в обратном направлении. На рис. 3.6 приведен пример по­иска в ширину и поиска в глубину. Вершины пронумерованы в том порядке, в котором они раскрыва­лись; конечные вершины обозначены квадратами, разрешимые вер­шины зачернены, дуги решающего графа выделены двойными ли­ниями.

Рис.3.6. Пример разбиения задач на подзадачи при поиске в ширину (а) и при поиске в глубину (б)

 

Эвристический поиск. Методы поиска в глубину и ширину называют слепым поиском, поскольку в этих методах порядок раскрытия вершин предопределен и никак не зависит от расположения цели. При увеличении пространства поиска методы слепого поиска требуют чрезмерных затрат времени и (или) памяти. Стремление сократить время поиска привело к созданию эвристических методов поиска, т.е. методов, использую­щих некоторую информацию о предметной области для рассмотрения не всего пространства поиска, а таких путей в нем, которые с наи­большей вероятностью приводят к цели. Один способ сокращения перебора состоит в выборе более “информированного” оператора, который не строит так много вершин, не относящихся к делу. Другой способ состоит в использовании эвристической информации для определения на каждом шаге дальнейшего направления перебора. Для этого необходимо ввести меру “перспективности” вершины в виде некоторой оценочной функции. В некоторых случаях удается ввести такую оценочную функцию, которая, сокращая перебор, не теряет свойства полноты. Чаще используемые эвристики, существенно сокращая перебор, влекут за собой потерю свойства полноты. Как правило, оценочные функции пытаются количественно оценить рас­стояние от текущей вершины до конечной. Из двух вершин при оди­наковой глубине перспективней та, от которой меньше расстояние до цели. Для многих приложений, в частности для экспертных систем, применение количественных оценок не позволяет эффективно направ­лять процесс поиска.

 

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

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

Можно выделить важную форму метода “генерация-проверка”, называемую “иерархическая генерация-проверка”. В этом случае на верхнем уровне генератор вырабатывает не полное, а частично опре­деленное решение (будем для краткости называть такие решения час­тичными). Каждое частичное решение описывает не все состояние, а только его некоторую часть, определяя таким образом класс возмож­ных состояний. Идея состоит в том, что устройство проверки может уже по виду частичного решения определить, что оно (а следователь­но, и все полные решения, которые могут быть получены из него) не ведет к успеху. Если же проверка не отвергает частичное решение, то на следующем уровне генератор продолжает вырабатывать из данно­го частичного решения все полные решения, а устройство проверки определяет, являются ли они целевыми.

 

Поиск в иерархии пространств

 

Методы поиска в одном пространстве не позволяют решать слож­ные задачи, так как с увеличением размера пространства время поиска экспоненциально растет. При большом размере пространства поиска можно попробовать разбить общее пространство на подпространства и осуществлять поиск сначала в них. Можно сказать, что в данном случае пространство поиска представлено иерархией пространств. Важность иерархических методов при работе с большими про­странствами понята давно. Еще в 1963 г. М.Минский писал, что вве­дение “островков планирования” уменьшает время поиска по экспо­ненте: “В графе с 10 ребрами, исходящими из каждой вершины, 20–шаговый поиск может потребовать 1020 попыток, что нереально реа­лизовать, в то время как введение четырех лемм или последователь­ных подцелей может уменьшить поиск до 5х104 попыток, которые машина может выполнить. Поэтому имеет смысл приложить даже огромные усилия, чтобы выявить такие “островки” при решении сложных задач”. Идею М.Минского о иерархии пространств мож­но развить, допустив в иерархии не только конкретные, но и абстрактные пространства, т.е. пространства которые имеют описание только наиболее важных сущностей. В качестве классического приме­ра использования абстрактных пространств можно привести задачу определения кратчайшего пути на карте. Пусть требуется переехать из центра города А в центр города В. Если осуществлять поиск требуе­мого пути на детальной карте, содержащей все улицы во всех городах, встретившихся по дороге, то задача может стать практически нераз­решимой. При определении пути из города А в город В целесообразно спланировать маршрут по крупномасштабной карте (т.е. осуществить поиск в абстрактном пространстве), а затем по детальной карте спла­нировать выезд из города А и въезд в город В. В данном разделе будут рассмотрены методы, использующие общую идею иерархии про­странств, но отличающиеся природой пространств.

Методы поиска решения в иерархических пространствах обычно делятся на поиск в факторизованном пространстве, поиск в фиксиро­ванном и изменяющемся множестве пространств.

 

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

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

 

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

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

 

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

Система ABSTRIPS – один из первых примеров ис­пользования метода нисходящего уточнения. ABSTRIPS является программой, составляющей план перемещения роботом объектов (ящиков) между комнатами. Получив задачу, система составляет по­следовательность действий робота, которая решает эту задачу. Робот действует в мире, содержащем описание комнат, расположение дверей в комнатах, состояние дверей (открыты, закрыты), местонахождение объектов, местонахождение робота. Робот умеет выполнять ряд дей­ствий: перемещаться по комнате, переходить из одной комнаты в дру­гую, открывать дверь, толкать объекты и т.п. Возможным действиям робота соответствуют определенные операторы. Каждый оператор представлен наименованием со списком параметров, условиями при­менимости оператора и преобразованиями, которые он совершает, изменяя пространство. Пространство поиска (конкретное простран­ство), в котором ищется решение, состоит из возможных состояний мира, получаемых преобразованием исходного состояния путем при­менения к нему всех возможных операторов. Для того чтобы упрос­тить процесс решения задачи, ABSTRIPS формирует из конкретного пространства иерархию абстрактных пространств. Абстрактные про­странства образуются путем упрощения условий применимости опе­раторов, т.е. чем выше уровень абстракции, тем меньше литер (слов) содержит условие применимости каждого оператора. Такой подход позволяет при формировании абстрактного пространства не вычер­кивать несущественные детали из описания мира и операторов, а просто не учитывать их при решении. Уровень детальности указы­вается с помощью веса, связанного с каждой литерой в условии при­менимости оператора. Основанием для назначения веса служат сле­дующие эвристические соображения. Существование предметов и их свойств (т.е. наличие комнат, дверей, ящиков) является с точки зрения построения плана более важным фактом, чем положение предметов, которые могут передвигаться роботом, и тем более чем положение робота. Поэтому только эти наиболее важные факты должны учиты­ваться в абстрактном пространстве. После построения приблизитель­ного плана его детали уточняются в более конкретных про­странствах.

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

- возможно осуществить частичное упорядочение понятий облас­ти, приемлемое для всех решаемых задач;

- решения, принимаемые на верхних уровнях, нет необходимости отменять на более нижних.

 

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

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

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

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

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

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

- определить, когда накопилось достаточно информации для при­нятия решения;

- приостанавливать работу над некоторой подзадачей, когда для решения нет достаточной информации;

- переходить с одной подзадачи на другую, возобновляя выполнение приостановленной подзадачи при появлении недостающей информации;

- объединять информацию, полученную различными подза­дачами.

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

Распространение ограничений – механизм для передачи информа­ции между подзадачами. Ограничения, выставленные одной подзада­чей, могут существенно сузить набор альтернатив другой подзадачи. MOLGEN строит планы в ответ на распространение ограничений.

Чередование в MOLGEN подхода наименьших свершений и эври­стических стратегий иллюстрирует ограниченность принципа наи­меньших свершений. В связи с тем, что любой решатель имеет непол­ные знания о проблеме, в процессе использования принципа наи­меньших свершений может возникнуть следующая ситуация. Необхо­димо делать выбор, но нет оснований предпочесть одну альтернативу другим. Эта ситуация приводит к остановке процесса и называется тупиком, потому что все подзадачи перешли в состояние “ожидание ограничений”. Когда MOLGEN распознает эту ситуацию, она пере­ключается на эвристическую стратегию и делает предположение (угадывание). Во многих случаях угадывание позволяет продолжить процесс поиска решения и довести его до конечного результата. Иногда угадывание приводит к конфликтам, требующим но­вых попыток по угадыванию. Конфликт может возникнуть и при ра­боте по принципу наименьших свершений, а именно в том случае, когда цели принципиально недостижимы.

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

 

Метапространства в иерархии пространств. При решении любой задачи многократно возникает вопрос: “Что делать на следующем шаге?”. В простейшем случае решение предоп­ределено методом поиска решения. При поиске в абстрактных и кон­кретных пространствах на каждом шаге решался вопрос о том, какой из операторов, существующих в проблемной области, применить к ее текущему состоянию. Вопрос о том, как ре­шающая программа это сделает, не обсуждался. Можно оказывать не явное, а косвенное влияние на определение того, “что делается на сле­дующем шаге в проблемной области” путем выбора того или иного метода, известного решателю. Подобный подход требует явного раз­граничения знаний о процессе решения и знаний о проблемной об­ласти. Для этого необходимы знания на метауровне. Решатель в метапространстве содержит явное описание процесса организации поиска, т.е. описание состояний, операторов, условий применимости операто­ров, описание доступных методов (стратегий) поиска и способов их взаимодействия. Получить решение в метапространстве – это значит определить, какой метод (программа) будет применен на следующем шаге, т.е. составить метаплан решения задачи. Заметим, что метаплан, в отличие от абстрактного плана, выражается не в терминах операто­ров проблемной области, а в терминах методов (программ), из­вестных решателю. Не существует причин ограничивать метазнания одним уровнем.

По аналогии с факторизацией абстрактного пространства можно говорить о разбиении метапространства на метазадачи (методы, про­граммы). Разбиение на метазадачи является полезным методом орга­низации знаний в ЭС, однако в настоящее время еще далеко до общего теоретического осмысления данного вопроса.

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

---

Дата добавления: 2019-07-15; просмотров: 1847; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!