Представление сложных связей в описаниях предметной области для решения задач целенаправленного поведения

Размещено на http://www.allbest.ru/

ПРЕДСТАВЛЕНИЕ СЛОЖНЫХ СВЯЗЕЙ В ОПИСАНИЯХ ПРЕДМЕТНОЙ ОБЛАСТИ ДЛЯ РЕШЕНИЯ ЗАДАЧ ЦЕЛЕНАПРАВЛЕННОГО ПОВЕДЕНИЯ

В.М. Трембач (trembach@yandex.ru)

Московский авиационный институт, Москва

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

интегрированный сеть петри знание

Введение

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

Одним из подходов к устранению таких трудностей при использовании ИИС, является использование таких базовых связей, которые позволяли бы, в дальнейшем, описывать вновь возникающие связи между сущностями с приемлемой точностью и достоверностью. В статье рассматривается подход к представлению сложных связей с помощью элементарных на основе использования эволюционирующих знаний [Трембач, 2008] для описания предметных областей.

1. Представление и формирование сложных связей

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

Содержание описания составной связи аналогично описанию вершины [Трембач, 2008] и может включать:

NR - имя рассматриваемой связи,

PRUS - множество признаков, определяющих возможность передачи сигнала активизации),

PSUS - признак активизации мнимой вершины рассматриваемой связей,

LN_LS - список имен вершин, от которых поступает сигнал активизации,

LN_HS - имена вершин, к которым идет сигнал активизации,

LN_Ex - список примеров, активизирующих вершину связи,

W - весовые коэффициенты.

Интегрированная модель представления знаний позволяет на основе элементарных связей создать составные связи между сущностями действительности. В процессе формирования составных связей можно выделить следующие основные этапы:

выделение вершин-сущностей из проблемной области;

выделение подмножества связей рассматриваемой вершины-сущности с другими вершинами-сущностями;

анализ каждой связи:

если рассматриваемая связь не является элементарной, то определение и описание ситуации при которой эта связь активизирована. Представление этой ситуации в виде предусловия для мнимой вершины-сущности;

добавление в предусловие самой связи;

выход мнимой вершины-сущности соединить с требуемой вершиной-сущностью.

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

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

2. Анализ сложных связей

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

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

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

Действительность состоит из множества сущностей, среди которых можно выделить два типа: сущности-действия Сд и сущности-признаки Сп. Эти два типа сущностей присутствуют в составной связи. С использованием выделенных типов сущностей можно определить элементарную связь.

Определение. Элементарная связь представляет собой сущность-действие, у которой постусловие повторяет предусловие, т.е. ПсУ=ПрУ.

Сущность, для моделирования сетью Петри, в формате интегрированного метода представления знаний, минимально может определяться тремя элементами в следующем виде:

Сщ = (И, ПрУ, ПсУ), где

И = (и1, и2, …, иv) - конечное множество имен сущностей, v ? 0;

ПрУ = (ПрУ1, ПрУ2, …, ПрУv) - конечное множество предусловий сущностей, v ? 0;

ПсУ = (ПсУ1, ПсУ2, …, ПсУv) - конечное множество постусловий сущностей, v ? 0.

Составная связь СтС является пятеркой:

СтС = (ИСтС, СП, СД, ПрУ, ПсУ), где

ИСтС = (и1, и2, …, иv1) - конечное множество имен сущностей составных связей, v1 ? 0;

СП = (сп1, сп2, …, спn) - конечное множество сущностей-признаков, n ? 0;

СД = (сд1, сд2, …, сдm) - конечное множество сущностей-действий, m ? 0;

ПрУ = (ПрУ1, ПрУ2, …, ПрУv1) - конечное множество предусловий сущностей составных связей, v1 ? 0;

ПсУ = (ПсУ1, ПсУ2, …, ПсУv1) - конечное множество постусловий сущностей составных связей, v1 ? 0;

ПрУ: СД СПвх входная функция, сопоставляющая сущности-действию СД множество ее входных признаков;

ПсУ: СД СПвых выходная функция, сопоставляющая сущности-действию СД множество ее выходных признаков.

Сущность-признак спСП является входом для сущности-действия сдСД, если спПрУ(сд).

Сущность-признак спСП является выходом для сущности-действия сдСД, если спПсУ(сд).

Структура сети Петри для сложной связи определяется ее сущностями-признаками, сущностями-действиями, предусловиями и постусловиями.

Сеть Петри, моделирующая сложную связь «находит» между вершинами «робот» и «объект», в виде алгоритма поиска роботом объекта, представлена на рис. 1.

Рис. 1. Сеть Петри, моделирующая сложную связь «находит».

Построенная сеть Петри теперь может использоваться для анализа моделируемой сложной связи. Основными подходами к анализу сетей Петри являются [Котов, 1984] методы, основанные на использовании дерева достижимости, подход, основанный на матричном представлении сетей Петри, решении матричных уравнений и методах преобразования сетей.

3. Формирование сложных связей с помощью сетей Петри

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

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

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

Полученная сеть Петри представлена на Рис.2. Созданная модель синтезирована из предположения, что условия возникновения событий всегда выполняются. В силу этого предположения не требуется вводить новые позиции, которые соответствуют набору условий выполнения событий t1-1, t1-2, t2, … , t6-1, t6-2 , t7.

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

Рис.2. Синтезированная сеть Петри.

Основными методами анализа свойств достижимости являются:

построение дерева достижимости;

метод матричных уравнений.

Для синтезированной сети Петри (Рис.2.) дерево достижимости представлено на рис.3. Из основных свойств сетей Петри для сложных связей могут использоваться следующие: живость - отсутствие тупиковых состояний, исключая выходное (целевое) состояние сложной связи; безопасность - метки вершин включают только «0» и «1», что означает отсутствие зацикливаний; правильность - сеть безопасна и живая; пассивность переходов - переходу не соответствует ни одной дуги графа.

Методы матричных уравнений. Альтернативным по отношению к определению сети Петри PN в виде (S, T, I, O) является определение сети Петри PN в виде двух матриц D- и D+, представляющих входную и выходную функции I и O. Каждая из матриц D- и D+ имеет m = ¦T¦ строк (по одной на переход и n = ¦S¦ столбцов (по одному на позицию). Матричный вид сети Петри PN = (S,T,I,O) задаётся парой (D, D+), где

D[k,i] = ^#(si,tk) - кратность дуги, ведущей из позиции pi в переход tk;

D+[k,i] = #^(si,tk) - кратность дуги, ведущей из перехода tk в позицию si, для произвольных 1 ? k ?m, 1 ? i ?n.

Рис.3. Дерево достижимости для синтезированной сети Петри

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

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

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

1. Формируется/запрашивается имя рассматриваемой сущности.

2. По входным в позицию или переход дугам формируется предусловие сущности: условие включает имя сущности (перехода или позиции, если их имена идентичны) откуда берет начало дуга и признак его активности - «1». Таким образом формируется каждое условие из предусловий сущности.

3. По выходным дугам формируется постусловие рассматриваемой сущности. Для обеспечения безопасности сети Петри признаки активности могут соответствовать признаку активности только для одной ситуации. В качестве постусловия берется признак срабатывания перехода.

4. Cписок имен нижнего уровня формируется из имен сущностей- признаков, используемых в предусловиях.

5. Список имен верхнего уровня формируется из имен элементов сети Петри в условиях которых присутствует признак срабатывания рассматриваемой сущности (перехода,

Сформированная составная связь «Найти объект» не является конкретной, а позволяет создавать связь для всех допустимых ситуаций.

Заключение

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

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

Благодарности. Работа выполнена при финансовой поддержке РФФИ (проект № 10-07-00672).

Список литературы

1. [Котов, 1984] Котов В.Е. Сети Петри. - М.: Наука. Главная редакция физико-математической литературы. 1984.

2. [Питерсон, 1984] Питерсон Дж. Теория сетей Петри и моделирования систем: Пер. с англ. - М.: Мир, 1984.

3. [Трембач, 2008] Трембач В.М. Методы представления эволюционирующих знаний, обеспечения и оценки их соответствия действительности //КИИ-2008. XI-я Национальная конференция по искусственному интеллекту с международным участием. Сборник научных трудов в 3-х томах. Т.3. - М.: Физматлит, 2008.

Размещено на Allbest.ru