Дисциплина : Экспертные системы

2. Особенности планирования целенаправленных действий 3. Оценка сложности задачи планирования

Кафедра «КРЭМС»

[Электронный ресурс] : учебное пособие / Е. В. Боровская, Н.

А. Да- выдова. — 3-е изд. (эл.). — Электрон. текстовые дан. (1 файл pdf : 130 с.). — М. : Лаборатория знаний, 2016. – Режим доступа: http://files.pilotlz.ru/pdf/cE421-8-ch.pdf – Загл. с экрана.
2. Информационные технологии : учебник / Ю. Ю. Громов, И. В. Дидрих, О. Г. Иванова, М. А. Ивановский, В. Г. Однолько. [Электронный ресурс]: Учебные пособия – Тамбов : Изд-во ФГБОУ ВПО «ТГТУ», 2015. – 260 с. – Режим доступа: http://www.tstu.ru/book/elib/pdf/2015/gromo – Загл. с экрана.
 
2 Дополнительная литература

1. Гаскаров, Д.В. Интеллектуальные информационные системы: учебник для вузов / Д.В. Гаскаров. М.: Высш. шк., 2003. – 431 с. ил.
2. Коробова, Б.Л. Принятие решений в системах, основанных на знаниях: учеб. пособие / Б.Л. Коробова, Г.В. Артёмов. Тамбов: ТГТУ, 2005. – 80 с.
3. Коробова, И.Л. Методы представления знаний: метод. указания / И.Л. Коробова. Тамбов: ТГТУ, 2003. – 24 с.
 
3 Периодическая литература
1. РАДИОТЕХНИКА: науч.-технический журн. / Изд-во «Радиотехника». – Издается с 1937 г. – 12 раз в год.
2. ЭЛЕКТРОНИКА: науч.-технический журн. / Изд-во «Техносфера». – Издается с 1996 г. – 8 раз в год.
3. МИКРОЭЛЕКТРОНИКА: науч.-технический журн. / Изд-во «Наука». – Издается с 1972 г. – 6 раз в год.
4. ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И ПРИНЯТИЕ РЕШЕНИЙ: науч.-технический журн. / Изд-во «Институт системного анализа РАН». – Издается с 2008 г. – 4 раза в год.
 
4 Интернет - ресурсы: выделенные ресурсы представлены ниже.
1. Единое окно доступа к образовательным ресурсам window.edu.ru
2. Научная электронная библиотека www.elibrary.ru
 

актом такого функционирования является решение задачи планирования пути достижения нужной

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

ряда описаний: состояний, множества операторов и их воздействий на переходы

между состояниями, целевых состояний. Описания состояний могут представлять собой строки символов, векторы, двухмерные массивы, деревья, списки и т. п. Операторы переводят одно состояние в другое. Иногда они представляются в виде продукций A=>B, означающих, что состояние А преобразуется в состояние В.

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

Алгоритм кратчайших путей Мура. Исходная вершина X0 помечается числом 0. Пусть в ходе работы алгоритма на текущем шаге получено множество дочерних вершин X(xi) вершины xi. Тогда из него вычеркиваются все ранее полученные вершины, оставшиеся помечаются меткой, увеличенной на единицу по сравнению с меткой вершины xi, и от них проводятся указатели к Xi. Далее на множестве помеченных вершин, еще не фигурирующих в качестве адресов указателей, выбирается вершина с наименьшей меткой и для нее строятся дочерние вершины. Разметка вершин повторяется до тех пор, пока не будет получена целевая вершина.

Мура за счет введения дуг переменной длины.
Алгоритм Дорана и

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

Алгоритм Харта, Нильсона и Рафаэля. В алгоритме объединены оба критерия: стоимость пути до вершины g[x) и стоимость пути от вершины h(x) - в аддитивной оценочной функции f{x) =g(x}-h(x). При условии h(x)

что часто решение задач имеет иерархическую структуру. Однако не обязательно

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

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

Преобразование использует представление произвольного И/ИЛИ-графа как произвольной формулы логики высказываний с дальнейшим преобразованием этой произвольной формулы в дизъюнктивную нормальную форму. Подобное преобразование позволяет далее использовать алгоритм Харта, Нильсона и Рафаэля.

Метод ключевых операторов. Пусть задана задача и известно, что оператор f обязательно должен входить в решение этой задачи. Такой оператор называется ключевым. Пусть для применения f необходимо состояние C, а результат его применения есть I(c). Тогда И-вершина порождает три дочерние вершины: , и , из которых средняя является элементарной задачей. К задачам и также подбираются ключевые операторы, и указанная процедура редуцирования повторяется до тех пор, пока это возможно. В итоге исходная задача разбивается на упорядоченную совокупность подзадач, каждая из которых решается методом планирования в пространстве состояний.

Метод планирования общего решателя задач (ОРЗ). ОРЗ явился первой наиболее известной моделью планировщика. Он использовался для решения задач интегрального исчисления, логического вывода, грамматического разбора и др.

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

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

Метод продукций системы STRIPS. В этом методе оператор представляет продукцию Р, А=>В, где Р, А и В - множества ППФ исчисления предикатов первого порядка, Р выражает условия применения ядра продукции А=>В, где В содержит список добавляемых ППФ и список исключаемых ППФ, т. е. постусловия. Метод повторяет метод ОРЗ с тем отличием, что стандартные задачи определения различий и применения подходящих операторов решаются на основе принципа резолюций.

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

1.3. Планирование с помощью логического вывода

разбиение пространства поиска на уровни иерархии осуществляется с помощью детализации

продукций, используемых в методе STRIPS. Для этого каждой литере ППФ, входящей в множество Р условий применения продукции, присваивается вес j, j=0, k, и на i-м уровне планирования, осуществляемом методом системы STRIPS, учитываются лишь литеры веса j. Таким образом, на k-ом уровне продукции описываются наименее детально, на нулевом-наиболее детально как в методе системы STRIPS. Подобное разбиение позволяет для планирования на j-м уровне использовать решение (j+1)-го уровня как скелет решения j-го уровня, что повышает эффективность поиска в целом.

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

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

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

или требуемый результат) оценивается по наличию в ней знакомых смысловых

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

это дерево из формул используемого исчисления, в корне которого находится

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

правило, допускают эффективное планирование. И хотя доля подобных задач с

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

систем 3. Этапы разработки экспертных систем 4. Интерфейс с конечным

пользователем 5. Представление знаний В ЭС 6. Уровни представления и уровни детальности