Представление простых фактов

Представление - это действие, делающее некоторое понятие воспринимаемым посредством фигуры, записи, языка или формализма. Теория знаний изучает связи между субъектом (изучающим) и объектом. Знание (в объективном смысле) - то, что известно (то, что знаем после изучения).

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

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

- описание ситуации в игре (например, расположение фигур в шахматах)

- описание размещения персонала предприятия

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

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

Язык логики предикатов задается синтаксисом. Для представления знаний базисные синтаксические категории языка изображаются такими символами, которые несут достаточно четкую информацию и дают довольно ясную картину об области рассуждений (экспертизы).

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

o Константы. Они служат именами индивидуумов (в отличие от имен совокупностей): объектов, людей или событий. Константы представляются символами вроде Жак_2 (добавление 2 к слову Жак указывает на вполне определенного человека среди людей с таким именем), Книга_22, Посылка_8.

o Переменные. Обозначают имена совокупностей, таких как человек, книга, посылка, событие. Символ Книга_22 представляет вполне определенный экземпляр, а символ книга указывает либо множество "всех книг", либо "понятие книги". Символами x, y, z представлены имена совокупностей (определенных множеств или понятий).

o Предикатные имена. Они задают правила соединения констант и переменных, например, правила грамматики, процедуры, математические операции. Для предикативных имен используются символы наподобие следующих: Фраза, Посылать, Писать, Плюс, Разделить. Предикатное имя иначе называется предикатной константой.

o Функциональные имена представляют такие же правила, как и предикаты. Чтобы не спутать с предикатными именами, функциональные имена пишут одними строчными буквами: фраза, посылать, писать, плюс, разделить. Их называют так же функциональными константами.

Символы, которые применяются для представления констант, переменных, предикатов и функций, не являются "словами русского языка". Они суть символы некоторого представления - слова "объектного языка" (в нашем случае языка предикатов).

Представление должно исключать всякую двусмысленность языка. Поэтому имена индивидуумов содержат цифры, приписываемые к именам совокупностей. Жак_1 и Жак_2 представляют двух людей с одинаковыми именами. Эти представления суть конкретизации имени совокупности "Жак". Предикат - это предикатное имя вместе с подходящим числом термов. Предикат называют так же предикатной формой.

Примеры применения логики для представления знаний.

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

(Сравнивая два последних примера, видим, что замена прилагательного "каждый" на "некоторые" влечет при переводе не только замену квантора " на $, но и замену связки É на Ù. Это иллюстрирует тот факт, что перевод фразы естественного языка на логический, вообще говоря, не является трафаретной операцией.)

- По-русски: Ни один человек не прогуливается,

Логически: Ø ($ x (Человек(x) Ù Прогуливается(x))).

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

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

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

При планировании в пространстве задач ситуация несколько иная. Пространство образуется в результате введения на множестве задач отношения типа: "часть - целое", "задача - подзадача", "общий случай - частный случай" и т. п. Другими словами, пространство задач отражает декомпозицию задач на подзадачи (цели на подцели). PR-проблема состоит в поиске декомпозиции исходной задачи на подзадачи, приводящей к задачам, решение которых системе известно. Например, ИС известно, как вычисляются значения sin x и cos x для любого значения аргумента, и как производится операция деления. Если ИС необходимо вычислить tg x, то решением PR-проблемы будет представление этой задачи в виде декомпозиции tg x = a = sin x/cos x (кроме л = л/2 + k л).

Дадим классификацию методов, используемых при решении SS- и PR-проблем.

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

Пространство состояний можно представить как граф, вершины которого помечены состояниями, а дуги – операторами. Если некоторая дуга направлена от вершины n_i, к вершине n,, то п, называется дочерней, а n_j – родительской вершинами

Последовательность вершин n_i1, n_i2,...,n_ik, в которой каждая n_i-дочерняя вершина для вершины n_ij-1, /=2,..., k, называется путем длиной k от вершины n_i1, к вершине n_ik.

Таким образом, проблема поиска решения задачи <А,В> при планировании по состояниям представляется как проблема поиска на графе пути из A в B. Обычно графы не задаются, а генерируются по мере надобности.

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

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

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

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

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

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

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

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

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

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

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

Возможны альтернативы по выбору ключевых операторов, так что в общем случае будет иметь место И/ИЛИ-граф. В большинстве задач удается не выделить ключевой оператор, а только указать множество, его содержащее. В этом случае для задачи <А, В> вычисляется различие между A и В, которому ставится в соответствие оператор, устраняющий это различие. Последний и является ключевым.

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

анализ целей и средств и рекурсивное решение задач. В каждом цикле поиска ОРЗ решает в жесткой последовательности три типа стандартных задач: преобразовать объект A в объект В, уменьшить различие D между A и В, применить оператор f к объекту A. Решение первой задачи определяет различие D второй - подходящий оператор f, третьей - требуемое условие применения С. Если С не отличается от A, то оператор f применяется, иначе С представляется как очередная цель и цикл повторяется, начиная с задачи "преобразовать A в С". В целом стратегия ОРЗ осуществляет обратный поиск - от заданной цели В к требуемому средству ее достижения С, используя редукцию исходной задачи <A, В> к задачам <A, С> и <С, В>.

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

3. Планирование с помощью логического вывода. Такое планирование предполагает: описание состояний в виде правильно построенных формул (ППФ) некоторого логического исчисления, описание операторов в виде либо ППФ, либо правил перевода одних ППФ в другие. Представление операторов в виде ППФ позволяет создавать дедуктивные методы планирования, представление операторов в виде правил перевода - методы планирования с элементами дедуктивного вывода.

Дедуктивный метод планирования системы QA3, ОРЗ не оправдал возлагавшихся на него надежд в основном из-за неудовлетворительного представления задач. Попытка исправить положение привела к созданию вопросно-ответной системы QA3. Система рассчитана на произвольную предметную область и способна путем логического вывода ответить на вопрос: возможно ли достижение состояния В из A? В качестве метода автоматического вывода используется принцип резолюций. Для направления логического вывода QA3 применяет различные стратегии, в основном синтаксического характера, учитывающие особенности формализма принципа резолюций. Эксплуатация QA3 показала, что вывод в такой системе получается медленным, детальным, что несвойственно рассуждениям человека.

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

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

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

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

Комплексная схема нечеткого планирования

Недостатком большинства известных в настоящее время систем планирования является их жесткая привязка к схеме планирования. Любая из них всегда ищет решение либо SS-проблемы, либо PR-проблемы. Связано это с фиксацией формы представления информации для планирования. Для классических моделей SS- и PR-проблем эти формы различны. Ясно, однако, что человек в своей деятельности успешно комбинирует шаги планирования из решения SS- и PR-проблем. Вторым недостатком является детерминированность систем планирования. В реальных ИС детерминированность планирования, как правило, не имеет места. Обобщение нечетких SS- и PR-проблем заключается в допущении нечетких состояний и нечетких операторов перехода из состояния в состояние. Разбиение задачи на подзадачи имеет весовые коэффициенты на дугах со значениями из [0, 1], которые интерпретируются как достоверности решения соответствующих подпроблем. Достоверность решения PR-проблемы определяется как минимум достоверностей решения ее подпроблем.

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

Схемой SS-проблемы называется пара M=(S,G), где S-множество состояний, G-множество отображений g: S->S, называемых операторами. Путем из состояния s₀эS в состояние s_rэS называется конечная последовательность p = ((s₀,, g₀ ), ( s₁, g₁ ),...,( s_k-1, g_k-1 ) s_k ), такая, что g_iO s_i= s_i+1 для i=0,..., k- 1. SS-проблема-это четверка Р=(S, G, i,f), где (S, G)-схема SS-проблемы, i, fэS – соответственно начальное и заключительное состояние. Путь х, ведущий из i в f, есть решение Р, а множество всех подобных путей составляет множество решений.

Схемой PR-проблемы называется пара.N=(S, Г), где S -множество проблем, Г-множество отображений g: S ->S ⁺, называемых операторами. Если РэS, p эS ⁺, то g _р(p) -отображение, представляющее проблему Р в виде цепочки подпроблем p =P1...Pn. Для схемы N= (S, Г) накрывающий путь q из проблемы s ₀ в конечное множество проблем S _k= {s ₁,..., s _n}э _S ^| является конечной последовательностью, где q = (( x₀, y₀ ), ( x₁, y₁ ),..., ( x_k-1, y_k-1 ), x_k ), x_iэS ⁺ для i=0,...,k, yэГ⁺ для i=0,..., k-1, так что x₀=s ₀, x_kэS ⁺_k. PR-проблема представляет собой четверку Z=(S, Г, Ро, Ф), где (S, Г)-схема PR-проблемы, Р_оэS -начальная проблема, ФÌ S -множество конечных проблем. Решение Z представляет собой накрывающий путь (S, Г) из Р_о в Ф^/_x_Ì Ф, множество решений x_z, есть множество всех решений Z.

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

Импликата проблемы Р есть пара (p, y), где p =P_iP₂... P_k - цепочка проблем, y -отображение из Х_р1 C Х_р2... C Х_рk в Х_р(Х_рi обозначает множество решений Р_i<). Импликативная схема есть тройка L =(Р, p, y), такая, что Р -проблема, (p, y) - импликата Р. Множество Т импликативных схем называется импликативной сетью. Множество проблем импликативной сети

Объединим синтаксис и семантику подхода, основанного на разбиении проблемы на подпроблемы. PR-проблема Z=(S, Г, Ро, Ф) представляет импликативную сеть Т тогда и только тогда, когда S =W _t и для каждого L =(Р, p,y)эT существует в точности одно g эГ, такое, что Рg =p, и для каждого g эГ, и для каждого Р из области определения g существует в точности одно L =(Р, p, Y) ' T, такое, что p =Pg Проблема Р решена тогда и только тогда, когда Х_p- непустое множество.

Если PR-проблема представляет импликативную сеть, то проблема Р₀ разрешима. Для существования решения достаточно, чтобы импликативные схемы в импликативной сети Т существовали только для всех пар (xi, у,), i=0,..., k- 1, входящих в накрывающий путь схемы PR-проблемы. В этом случае синтаксис и семантика PR-проблемы не совпадают. В данном случае PR-проблема частично представляет импликативную сеть Т.

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

Рассмотрим головоломку "Ханойская башня". Имеются три стержня 1, 2 и 3 и три диска различных размеров А, В, С с отверстием в центре, которые могут одеваться на стержни. В исходной позиции диски находятся на стержне 1; самый большой диск С – внизу, самый маленький диск А- наверху. Требуется перенести все диски на стержень 3, перемещая за один раз только один диск. Брать можно только самый верхний диск на стержне, причем его нельзя класть на диск, меньший по размерам. Используем для записи состояний и операторов классическую формализацию. Выражение ijk обозначает конфигурацию, при которой диск С находится на стержне i, диск В – на стержне j и диск А – на стержне k. Выражение xij обозначает действие, при котором диск х перемещается со стержня i на стержень j. С помощью этого формализма можно просто записать все состояния и переходы головоломки в виде треугольного графа, где вершины соответствуют расположению дисков на стержнях, а дуги – возможным перекладываниям дисков (рис.1). На этой головоломке легко проиллюстрировать все основные понятия обобщенной стратегии проблем.

Представим головоломку в виде модели I-проблемы. Рассмотрим I-проблему R=(B, Г, P₀T), где B={Р₀, P₁,...,P₉}; Г={g}; T=={L ₁,L ₂,L ₃}. SS-проблемы Р₀,P_1...,P₉ определяются следующим образом. На рис. 1 показана схема SS-проблемы M==(S, G), где

Схема PR-проблемы N = (В, Г) приведена на рис. 2; импликативная сеть Т - на рис. 3, причем L₁= (P₀, P₁Р₂Р₃, Y), L₂= (P₁, P₄P₅P₆, Y), Lз = (Р₃, P₇P₈P₉,Y), где Y (x₁,x₂,x₃) = x₁x₂x₃.

Проблемы Р₂ и P₄ -P₉ решаются перекладыванием одного диска и являются элементарными. Проблемы P₁ и Р₃ решаются с помощью манипуляций только с дисками В и А и являются более простыми, чем Р₀. Проблемы P₁ и Р₃ решаются, а проблема Р₀ сводится к P₁, P₂ и Р₃ аналогичной манипуляцией с дисками, синтаксис которой выражен оператором g, а семантика - отображением Y.

Представление этой головоломки в виде PR-проблемы (рис.2) является более компактным и наглядным, чем представление в виде SS-проблемы (рис.1), а представление в виде I-проблемы (рис..3) сочетает достоинство обоих и показывает взаимосвязь подпроблем и тех действий, которые нужно выполнить, чтобы решить головоломку.

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

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

Нечеткой SS-проблемой назовем SS-проблему, у которой i, f- нечеткие множества, операторы g э G - нечеткие матрицы, a -решением нечеткой SS-проблемы называется путь g=g₁...g_n,g_iэG,i=1,...,n, такой, что iOg₁O...... Og_nOf? a, где О - максимальное произведение нечетких матриц.

Нечеткой PR-проблемой называется PR-проблема, у которой элементам g э Г приписывается степень принадлежности m g (p)э[0,1], a -решением нечеткой PR-проблемы называется решение PR-проблемы, для которой min g _ij_?a,g _ijэy_i.

Накрывающий путь в этом случае называется накрывающим a -путем. Степень принадлежности m g (p) интерпретируется как степень возможности разбиения проблемы на подпроблемы.

Нечеткой импликативной схемой называется импликативная схема, все отображения Y которой имеют степень принадлежности m Y (p)э[0,1]. Степень принадлежности интерпретируется как возможность получения решения проблемы из решений соответствующих подпроблем. Нечеткой импликативной сетью называется импликативная сеть с нечеткими импликативными схемами. Нечеткая PR-проблема представляет нечеткую импликативную сеть, если кроме обычных условий для импликативной сети выполняется неравенство m Y (p)? m g (p)? a,

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

Аналогично определяется нечеткая I-проблема. Но построить a -решение нечеткой PR-проблемы по a -решениям ее нечетких подпроблем можно лишь в частных случаях и при наложении дополнительных условий. Пусть задана нечеткая PR-проблема, где S -нечеткие SS-проблемы, и существует простейшее a -решение Z,

т.е. такое p э S ⁺,что m g _p_? _a,и если p =P₁..P_n,то все проблемы P_i_a -разрешимы,

где P_i= (S_i,G_i,J_i,F_i).a - решение проблемы P₀существует при m Y (p)? m g (p)? a для импликативной сети. Запишем более конструктивное условие для этого. Пусть для всех i оператор g_i есть a -путь решения проблемы P_iи F_i=J_i+1.Тогда,если выполняется max m [F_n_Ç (F_n-1_Ç (...F₁_Ç (J o g₁)o g₂)...)o g_n)]? a и g=g₁...g_n, то g- a -решение SS-проблемы P₀.

Особенности планирования целенаправленных действий

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

Пусть задан некоторый предметный мир, в котором действие ИС состоит в достижении целевых ситуаций s_k из некоторых исходных ситуаций s_nc помощью планов действий;V=bi1...b_in, где bi-исполнительный модуль из данного набора В₀. Задать ситуацию s в таком мире – это значит указать свойства с_i_Î С предметов а_k_Î A₀ и отношения между ними r_p_Î R₀, которые имели, имеют или будут иметь место в момент t. Модель предметного мира для такого действия ИС можно представить в виде Mо = <Aо, Во, Со, Ro>, а задачу планирования действий в мире Мо следующим образом: заданы исходная s_n и целевая s_k" ситуации, необходимо построить из исполнительных модулей b_i_Î Во план действий V, который, будучи примененным к Sn, позволяет достичь Sk.

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

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

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

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

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: