Моделирование баз знаний с использованием сетей Петри

Modeling knowledge bases using Petri nets

Maria Rodionova

student, Don State Technical University, Russia, Rostov-on-Don

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

Abstract. This paper proposes an approach to modeling knowledge bases using Petri Nets is discussed and inference engine operations are compared for both diagnostic and planning expert system.

Ключевые слова: экспертные системы, инженерия знаний, база знаний, сети Петри

Keywords: expert systems, knowledge engineering, knowledge base, Petri nets

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

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

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

Рисунок 1. Общая структура экспертной системы, основанной на правилах

Общая структура экспертной системы, основанной на правилах приведена на рисунке 1. Современные экспертные системы не полагаются на чисто простые логические правила. Они справляются с неопределенностью, с которыми не справляются простые производственные правила. Общее правило производства ЕСЛИ ТОГДА c, где a является антецедентом правила и c является следствием правила, может быть смоделировано с сетью Петри Пример отображения простого правила в сети Петри приведен на рисунке 2.

Рисунок 2. Простое правило вида условие-действие в сетях Петри

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

Рисунок 3. Сеть Петри с ингибитором

Каждая позиция в сети Петри моделирует гипотезу, которая может быть доказана или отвергнута. А состояние перехода означает проверку правильности. Для выражения управляющих потоков и построения баз знаний рассматривается только те правила, которые непосредственно влияют на процесс вывода в данный момент. Это достигается путем структурирования базы знаний, чтобы информация контроля вывода была неотъемлемой частью антецедентов правил [2]. Механизм вывода (его действие приведено на рисунке 4), затем исследует только антецеденты (или антецедентные поддеревья) тех правил, которые ранее были активированы наличием маркера управления выводами в одном из входных позиций. Используя взвешенную сеть Петри, возможно моделировать следующие типы правил. И, ИЛИ.

Рисунок 4. Процесс вывода во время диагностики

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

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

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