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

Методы поиска решений в ЭС.

Лекция.9.

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

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

-размер пространства в котором решается задача;

-изменяемость области;

-полнота модели описывающей область;

-определенность данных о решаемой задаче.

Параметр "размер" характеризует размер пространства, в котором предстоит искать решение. Параметр "изменяемость" характеризует степень изменяемости области во времени и пространстве. Различают статические и динамические области. Параметр "полнота модели" характеризует адекватность модели используемой для описания данной проблемной области. Если модель не полна, то для описания данной области используют несколько моделей дополняющих друг друга. Параметр "определенность данных" характеризует степень точности-ошибочности и полноты-неполноты данных. Ошибочность означает, что данные о проблемной области неточны. Неполнота означает недостаточность входных данных для однозначного решения задачи.

Требования пользователя к результату задачи определяются: количеством решений; свойствами результата и способами его получения.

Параметр "свойство результата" включает время решения, объем памяти, указание об обязательности использования каких-либо знаний и т.п.

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

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

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

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

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

-методы поиска в динамической проблемной области - это методы, предназначенные для работы с областями, изменяемыми во времени и (или) в пространстве.

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

Задача в поиске в пространстве состояний может быть сформулирована следующим образом.

Пусть задана тройка (S0,F,St), где S0 - множество начальных состояний (условия задачи), F - множество операторов задачи, отображающих одни состояния в другие, St - множество конечных состояний (решения задачи). Решить задачу значит определить такую последовательность операторов, которая преобразует начальные состояния в конечные. Процесс решения можно представить в виде графа G=(X,Y), X={x₀,x₁,...} - множество вершин графа, каждая из которых отождествляется с одним из состояний, Y - множество, содержащее пары вершин (x_i,x_j), где x_i,x_j принадлежат X. Итак, граф G задает пространство состояний, т.е. пространство, в котором осуществляется поиск решения. Построение пространства осуществляется следующим образом. Берется некая вершина х₀ из области начальных состояний Х0, к ней применяются все возможные операторы, порождающие все дочерние вершины. Этот процесс называется процессом раскрытия вершин. Если получена целевая вершина, то она не раскрывается. Процесс построения пространства состояний заканчивается, когда все нераскрытые вершины являются целевыми или терминальными. Терминальными называются вершины, к которым нельзя применить никаких операторов.

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

В зависимости от порядка, в котором перебираются вершины различают: поиск в глубину; поиск в ширину.

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

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

Более того, можно организовать поиск в обоих направлениях одновременно (двунаправленный или бинарный поиск)].

Пример. На рисунках 16 и 17 представлены графы демонстрирующие поиск в глубину и поиск в ширину соответственно. Вершины пронумерованы в том порядке, в котором они раскрываются.

Рис. 16. Граф, демонстрирующий поиск в глубину.

Рис. 17. Граф, демонстрирующий поиск в ширину.

При этом оба метода анализируют одинаковое число вершин, однако поиск в ширину требует больше памяти, т.к. он запоминает все пути поиска.

6.1.1.Поиск методом редукции.

Решение задачи этим методом сводится к решению совокупности образующих ее подзадач.

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

Графическое представление процесса разбиения задачи на подзадачи представлено на рисунке 18.(S₀ - исходная точка).

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

Графическое представление соответствующего И-ИЛИ - графа представлено на рисунке 19. При переходе вводится дополнительная вершина, т.к. любая вершина должна быть и-вершиной или или-вершиной.

Рис. 19. Графическое представление И/ИЛИ.

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

Рекурсивное определение разрешаемой вершины:

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

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

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

Для графа И-ИЛИ, также как для поиска в пространстве состояний, можно определить поиск в глубину и поиск в ширину как в прямом так и в обратном направлении.

Пример разбиения задачи на подзадачи при поиске в ширину представлен на рисунке 20.

Рис. 20. Пример разбиения задачи на подзадачи при поиске в ширину.

Пример разбиения задачи на подзадачи при поиске в глубину представлен на рисунке 21.

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

Заметим, что метод редукции является обобщением подхода с использованием пространства состояний. Метод поиска в глубину в И-ИЛИ графе используется в ЭС MYСIN, EMYСIN.

6.1.2.Эвристический поиск.

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

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

6.1.3.Метод “генерация-проверка”.

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

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

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

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

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

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

6.2.1.Поиск в факторизованном пространстве.

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

6.2.2.Поиск в фиксированном множестве пространств.

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

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

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

6.2.3.Поиск в изменяющемся множестве иерархических пространств.

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

Для того, чтобы упростить процесс решения некоторой задачи в сложном пространстве, целесообразно получить обобщенное пространство и получить решение в этом пространстве. Указанный прием можно повторять многократно. При этом процесс решения задачи выглядит как "нисходящее" движение в иерархии пространств от наиболее абстрактного к конкретному, в котором получается окончательное решение. Существенной характеристикой такого процесса является поиск решения задачи в абстрактном пространстве, преобразование этого решения в решение более низкого уровня и т.д.

Формирование более абстрактного пространства осуществляется путем игнорирования части описаний менее абстрактного пространства. Игнорирование описаний осуществляется на основе ранжирования описаний по степени важности. Часто ранжирование осуществляется на основе учета степени неизменности фактов. Наиболее абстрактными считаются те описания, которые не могут изменяться.

Программа ABSTRIPS является наиболее известным примером использования метода "нисходящего уточнения". Она составляет план перемещения роботом объектов между комнатами.

Отметим, что в этом методе абстрактные пространства создаются индивидуально, в соответствии с решаемой задачей.

6.2.4.Метод, основанный на принципе наименьших свершений.

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

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

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

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

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

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

Принцип наименьших свершений использует ЭС MOLGEN, предназначенную для планирования экспериментов по молекулярной генетике. Система чередует использование принципа наименьших свершений и использование эвристических стратегий.

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

6.2.5.Использование метапространства в иерархии пространств.

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

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

Примером ЭС с метапланированием является система MOLGEN.

Таким образом, методы поиска в иерархии пространств используют пространства трех видов: абстрактные, конкретные и метапространства. В одной системе могут использоваться пространства всех трех типов. А поиск решения в пределах одного пространства осуществляется любым способом из 6.1.

6.3.Поиск в альтернативных пространствах.

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

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

Система мнений - множество мнений, свойственных некоторому индивиду (системе). Основываясь на некоторой системе мнений можно образовать пространство поиска, предназначенное для решения каких-либо задач. В ходе рассуждений человек (система) может менять свои мнения, образуя различные системы мнений. Совокупность мнений, которой система придерживается в текущий момент, называется активной системой мнений. Каждой из систем мнений соответствует свое пространство поиска, а все вместе они образуют альтернативные пространства.

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

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

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

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

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

Предположим имеются альтернативные пространства - P,Q,R. Пространство P образовано из исходных посылок C1,B1, предложения A1 и выводов, сделанных на их основе. Пространство Q образовано из посылок C1,B1, предположения A2, предположения D1 и выводов. Пространство R образовано из посылок C1,B1, предположений A2,D2 и выводов, сделанных на их основе.

Пусть, например, при получении утверждения 8 система установила наличие неудачи. При этом возврат необходимо сделать не к предыдущему шагу (утверждение 7), а к шагу 5, на котором было сделано предположение А1, и заменить А1 на некоторое новое предположение, например, А2. Таким образом, осуществляется переход из пространства P в новое пространство (R или Q). Для выполнения описанного способа поиска нужно использовать информацию о зависимости, поэтому соответствующий метод называют поиском, направляемым зависимостью.

Метод поиска с использованием предположений использован в ЭС EL, предназначенной для расчета параметров электрических схем.

6.4. Рассуждения в динамических мирах.

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

Различают случаи:

-динамически изменяемая область, причем изменения полностью описываются операторами;

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

-области, данные которых изменяются во времени и момент их изменения может быть неизвестен системе.

Одна из первых попыток исследования ситуаций, изменяющихся во времени, была предпринята в 1969 году Маккарти и Хэйесом. Для представления последовательности действий и их результатов они предложили использовать исчисление ситуаций. Основная идея их подхода состоит в рассмотрении ситуаций наравне с другими объектами области. Под ситуацией понимается полное состояние мира после очередного действия. Действия в исчислении ситуаций представляются функциями, чьи области определения и области значения являются ситуациями. При решении задач в динамических мирах возникает фрейм-проблема. Суть ее в том, что бы разграничить факты о мире, которые должны изменяться в результате некоторого действия, и факты, которые остаются неизменными в результате этого действия. Маккарти и Хайес предложили следующий подход к решению фрейм-проблемы: все факты разделяются на такие классы, что каждое действие относится только к одному классу, не изменяя остальных. Каждому действию соответствует небольшое множество фактов, на которые это действие оказывает непосредственное влияние. Однако нельзя предполагать, что все остальные факты после свершения действия остаются неизменными, т.к. они могут зависеть от изменившихся фактов по сложным причинно-следственным связям.

Обозначим через ARB, что некоторый факт A изменяется при изменении причинно связанного с ним факта B. Если решатель может доказать, что ~(ARB), то это означает, что изменения B не вызывают изменений A. Теперь при выполнении некоторого действия достаточно проверить для каждого факта A, что он не связан причинной связью ни с одним из фактов, изменяемым этим действием.

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

Примером системы с изменяющимися во времени данными является ЭС VM, которая интерпретирует клинические данные о пациенте, что бы управлять аппаратом "искусственные легкие".

6.5.Поиск с использованием нескольких моделей.

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

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

- ликвидируется неточность данных;

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

Метод использования нескольких моделей для коррекции ошибочных данных и поиска решений в большом пространстве путем расширения и комбинации частных кандидатов рассмотрим на примере системы HEARSAY-II. Система обрабатывает запросы к базе данных, выраженные в устной форме. Важной особенностью системы, облегчающей использование нескольких моделей,является организация HEARSAY-II в виде нескольких источников знаний. Ни один из источников не может гарантировать единственность и правильность получаемых результатов. Источники рассматриваются как независимые, но они решают одну задачу и поэтому взаимодействуют. Это взаимодействие осуществляется через общую память, называемую "классной доской". Поиск решения рассматривается как итеративный процесс, в котором имеют место 2 типа действий источников знаний: выдвижение гипотез; проверка гипотез;

Классная доска разделена на 7 информационных уровней: взаимодействие с базой знаний; фраза (предложение); словосочетание (связная последовательность слов); слово; слог; фонема; дифференциальный признак фонемы (параметр). Они могут рассматриваться как разнородные абстрактные пространства. Источники знаний осуществляют преобразование знаний на одном уровне или преобразуют знания одного уровня в знания другого.

Сложность и многообразие вариантов анализа, возникающих вследствие неопределенностей во входных сигналах и ошибок источников знаний, не позволяют при ограниченности вычислительных ресурсов рассматривать все варианты обработки. Стратегия управления HEARSFY-II состоит в использовании неполного поиска, осуществляющего выбор из всего множества конкурирующих гипотез наиболее перспективных. Поиск решений в HEARSAY-II осуществляется с помощью управляющего процесса, называемого приспосабливающимся планированием. Такое планирование объединяет идеи принципа наименьших свершений со стратегиями управления ограниченными вычислительными ресурсами (варьированием ширины поиска и комбинированием поиска от целей с поиском от данных). В HEARSAY-II одни источники знаний используют поиск от целей, другие - поиск от данных.

Таким образом, HEARSFY-II является примером архитектуры, созданной для преодоления различных конфликтных требований. Разнообразие уровней “классной доски” обеспечивает разбиение большого пространства поиска на абстрактные пространства, а разнородность уровней обеспечивает интерпретацию входных сигналов с различных точек зрения.

Дата добавления: 2014-01-07