Методы поиска решений в экспертных системах
Методы решения задач, основанные на сведении их к поиску, зависят от особенностей предметной области, в которой решается задача, и от требований, предъявляемых пользователем к решению. Особенности предметной области с точки зрения методов решения можно характеризовать следующими параметрами:
- размер, определяющий объем пространства, в котором предстоит искать решение;
- изменяемость области, характеризует степень изменяемости области во времени и пространстве (здесь будем выделять статические и динамические области);
- полнота модели, описывающей область, характеризует адекватность модели, используемой для описания данной области. Обычно если модель не полна, то для описания области используют несколько моделей, дополняющих друг друга за счет отражения различных свойств предметной области;
- определенность данных о решаемой задаче, характеризует степень точности (ошибочности) и полноты (неполноты) данных. Точность (ошибочность) является показателем того, что предметная область с точки зрения решаемых задач описана точными или неточными данными; под полнотой (неполнотой) данных понимается достаточность (недостаточность) входных данных для однозначного решения задачи.
Требования пользователя к результату задачи, решаемой с помощью поиска, можно характеризовать количеством решений и свойствами результата и (или) способом его получения. Параметр “количество решений” может принимать следующие основные значения: одно решение, несколько решений, все решения. Параметр “свойства” задает ограничения, которым должен удовлетворять полученный результат или способ его получения. Например, для системы, выдающей рекомендации по лечению больных, пользователь может указать требование не использовать некоторое лекарство (в связи с его отсутствием или в связи с тем, что оно противопоказано данному пациенту). Параметр “свойства” может определять и такие особенности, как время решения (“не более чем”, “диапазон времени” и т.п.), объем памяти, используемой для получения результата, указание об обязательности (невозможности) использования каких-либо знаний (данных) и т.п.
|
|
Итак, сложность задачи, определяемая вышеприведенным и параметрами, варьируется от простых задач малой размерности с неизменяемыми определенными данными и отсутствием ограничений на результат и способ его получения до сложных задач большой размерности с изменяемыми, ошибочными и неполными данными и произвольными ограничениями на результат и способ его получения. Из общих соображений ясно, что каким-либо одним методом нельзя решить все задачи. Обычно одни методы превосходят другие только по некоторым из перечисленных параметров.
|
|
Рассмотренные далее методы могут работать в статических и динамических проблемных средах. Для того чтобы они работали в условиях динамики, необходимо учитывать время жизни значений переменных, источник данных для переменных, а также обеспечивать возможность хранения истории значений переменных, моделирования внешнего окружения и оперирования временными категориями в правилах.
Существующие методы решения задач, используемые в экспертных системах, можно классифицировать следующим образом:
- методы поиска в одном пространстве – предназначены для использования в следующих условиях: области небольшой размерности, полнота модели, точные и полные данные;
- методы поиска в иерархических пространствах – предназначены для работы в областях большой размерности;
- методы поиска при неточных и неполных данных;
- методы поиска, использующие несколько моделей, предназначены для работы с областями, для адекватного описания которых одной модели недостаточно.
Предполагается, что перечисленные методы при необходимости должны объединяться для того, чтобы позволить решать задачи, сложность которых возрастает одновременно по нескольким параметрам.
|
|
Поиск решений в одном пространстве
Методы поиска решений в одном пространстве обычно делятся на поиск в пространстве состояний, поиск методом редукции, эвристический поиск и поиск методом “генерация-проверка”.
Поиск в пространстве состояний. Задача поиска в пространстве состояний обычно формулируется в теоретико-графовой интерпретации.
Пусть задана тройка (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 (fF), преобразующего состояние, соответствующее вершине 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; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!