Интеграция методов концептуального и поведенческого моделирования дискретно-событийных систем: I. Синтез и анализ концептуальной модели

Зинкин Сергей Александрович доктор технических наук профессор, кафедра вычислительной техники, ФГБОУ ВО "Пензенский государственный университет" 440026, Россия, Пензенская область, г. Пенза, ул. Красная, 40 Zinkin Sergei Aleksandrovich Doctor of Technical Science professor of the Department of Computing Technics at Penza State University 440026, Russia, Penza Region, Penza, str. Krasnaya, 40 zsa49@yandex.ru Другие публикации этого автора     Пащенко Дмитрий Владимирович доктор технических наук профессор, кафедра вычислительной техники, ФГБОУ ВО "Пензенский государственный университет" 440026, Россия, Пензенская область, г. Пенза, ул. Красная, 40 Pashchenko Dmitrii Vladimirovich Doctor of Technical Science professor of the Department of Computer-Based Technology at Penza State University 440026, Russia, Penza Region, Penza, str. Krasnaya, 40 dmitry.pashchenko@gmail.com Другие публикации этого автора     Пучкова Ульяна Николаевна аспирант, кафедра вычислительной техники, ФГБОУ ВО "Пензенский государственный университет" 440026, Россия, Пензенская область, г. Пенза, ул. Красная, 40 Puchkova Ul'yana Nikolaevna post-graduate student of the Department of Computer-Based Technology at Penza State University 440026, Russia, Penza Region, Penza, str. Krasnaya, 40 u.puchkova@mail.ru Другие публикации этого автора

Мустафа Садек Джафар аспирант, кафедра вычислительной техники, ФГБОУ ВО "Пензенский государственный университет" 440026, Россия, Пензенская область, г. Пенза, ул. Красная, 40 Mustafa Sadek Dzhafar post-graduate student of the Department of Computer-Based Technology at Penza State University 440026, Russia, Penza Region, Penza, str. Krasnaya, 40 mustafajaafar221087@gmail.com Другие публикации этого автора

Работа выполнена в рамках Федеральной целевой программы “Исследования и разработки по приоритетным направлениям развития научно-технического комплекса России на 2014-2020 годы” (Соглашение № 14.574.21.0045 от 19.06.14, UIN: RFMEFI57414X0045).

Концептуальные и поведенческие модели нашли широкое применения в экспертно-имитационном моделировании дискретно-событийных систем различной природы. Согласно одному из распространенных определений ^[1], концептуальная модель – это “абстрактная модель предметной области, состоящая из множества понятий и связей между ними, классифицированных по типам и ситуациям свойств и характеристик, являющихся смысловой структурой (описанием) рассматриваемой предметной области, содержит необходимые для достижения цели моделирования причинно-следственные связи, присущие системе”. Данное определение предполагает использование как неформализованного, так и формализованного описания предметной области. Формализация концептуальных знаний о проблемной области является сложной проблемой и может быть основана на представлении знаний в системах искусственного интеллекта ^[2].

Для представления основных парадигм искусственного интеллекта, таких как логической, структурной и процедурной используются логические, сетевые и продукционные модели. К сетевым моделям относятся семантические сети и сети фреймов. Сценарии можно отнести к некоторым разновидностям семантических сетей и сетей фреймов с ролевыми отношениями, дополненных событиями и причинно-следственными отношениями между событиями и объектами ^[3].

Сценарием обычно называют формализованное представление совокупности взаимосвязанных фактов, определяющих смену ситуаций какой-либо предметной области. Знания о ситуациях реального мира, представленные в экспертных системах и системах ситуационного управления, помогают восстанавливать информацию, неточно представленную или утраченную при описании ситуаций, устанавливать закономерности в смысле ситуаций и зависимости одних ситуаций от других, предсказывать появление новых ситуаций. При помощи сценарных моделей возможно представлять проблемно-зависимые каузальные знания о событиях, действиях и процедурах, происходящих в предметной области ^{[4, 5, 6]}.

Целью настоящей работы является формализация процесса построения и анализа сценарных моделей при учете логической, сетевой и продукционной компонент модели представления знаний о предметной области. Для достижения этой цели необходимо осуществить переход от концептуальной модели сценария к его представлению в реляционной базе данных и возможному дальнейшему использованию в составе экспертно-имитационной модели системы ситуационного управления. При представлении сценариев будут использоваться как традиционные модели представления знаний – семантические сети с событиями и причинно-следственными, или каузальными, связями между ними, концептуальные графы и новые модели, основанные на формализме сетей абстрактных машин ^{[7, 8]}. В отличие от моделей в ^{[9, 10, 11]}, рассматриваемые в части I настоящей работы концептуальные модели близки к инфологическим моделям.

1. Описание предметной области и постановка задачи

на содержательном уровне

В качестве примера подходящей предметной области рассматривается участок гибкого автоматизированного производства, сокращенно ГАП (FMS – Flexible Manufacturing Systems). Применяемые на различных участках ГАП промышленные роботы (роботы-манипуляторы, робокары, погрузчики-робокары, роботы-погрузчики, складские роботы-штабелеры и др.) различаются по специализации, грузоподъемности, возможностям передвижения, способам установки на рабочем месте, адаптивности к окружающей среде, видам управления, способам программирования. Управляющие программы для роботов с программным управлением реализуют различные алгоритмы для исполнительных устройств, связанные с выполнением функций робота и позволяющие ему преодолевать различные препятствия в работе ^{[9, 10, 11]}.

Промышленная мобильная связь, сокращенно ПМС (IMC – Industrial Mobile Communication), обеспечивающая возможность обмена данными через беспроводные каналы связи сетей, позволяет использовать для управления промышленными роботами различные радиосети, например, WLAN, GSM, GPRS, UMTS; она охватывает программные и аппаратные компоненты ^[12].

Рассмотрим представление знаний на содержательном уровне в виде следующего предложения, несколько модифицируя и комбинируя соответствующие фразы из работ ^{[9, 10]}: «Автомат подает партию заготовок на станок (точнее, в подающий накопитель – часть станка), затем партия деталей обрабатывается по одной детали и оказывается в выходном накопителе станка, откуда их забирает первый робот-манипулятор, который упаковывает партию деталей в кассету. Затем второй робот-погрузчик грузит кассеты с деталями на робокар (число кассет, размещаемых на робокаре, ограничено), который перевозит их на склад. На складе, в зависимости от некоторого условия α робот-штабелер помещает кассеты в ячейки (при α = true) или же, при наличии транспорта (при α = false), третий робот упаковывает имеющиеся кассеты в контейнер (объем контейнера ограничен), который по заполнении грузится роботом-автопогрузчиком на грузовой автомобиль по его прибытии».

Построение похожих моделей для данной предметной области рассматривались, например, в работах ^{[13, 14]}. Однако в работе ^[13] построена только семантическая сеть, без учета каузальных связей. Для выполнения запросов здесь рекомендовано осуществлять поиск изоморфных графам запросов подграфов семантической сети, что приводит к большому объему переборов. В работе ^[14] рассмотрена программная реализация процесса управления участком ГАП как системой массового обслуживания с очередями, а не с позиций систем искусственного интеллекта.

2. Концептуальный граф для модели роботизированного

производства и его контекстное представление

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

– множество концептов-событий (фактов):

F = {F₀, F₁, F_2, F₃, F₄, F₅, F₆, F₇, F₈, F₉},

имеющих, соответственно, следующие названия (имена):

X_N = {Подача, Обработка, Упаковка_1, Погрузка_1, Перевозка, Размещение, Упаковка_2, Погрузка_2, Местонахождение_1, Местонахождение_2};

– множество R всех отношений:

R = {Имя, Агент, Объект, Место, След, Возм_след};

– множество ролевых отношений, то есть отношений без отношений следования (След) и возможного следования (Возм_след):

R₁ = {Имя, Агент, Объект, Место};

– множество X всех концептов, включая все концепты-события из множества F и имена (названия) этих событий из множества X_N;

– множество концептов модели без концептов-событий;

– множество концептов, обозначающих физические объекты.

Концептуальное представление (основная часть концептуального графа C) сценария работы участка ГАП приведено на рис. 1.

Здесь прямоугольниками представлены концепты – концепты-объекты и концепты-события, а овалами – отношения между некоторыми концептами. Причинно-следственные (каузальные) связи между событиями представлены бинарным отношением След. Так, истинность высказывания След(F_i, F_j), где След – одноименный отношению бинарный предикатный символ, означает, что вслед за событием F_i выполняется событие F_j. В овале, связывающем в концептуальном графе концепты-события F₄ и F₅, может быть записана формула α&След(F₄, F₅), а в овале, связывающем концепты-события F₄ и F₆, может быть записана формула `not` α&След(F₄, F₆), то есть первая связь реализуется при α = true, а вторая – при α = false. Однако в целях упрощения последующего анализа концептуального графа и представления его в реляционной базе данных в обоих случаях введем отношение “возможного следования” Возм_след, имя которого проставлено в обоих овалах.

На рис. 2 представлен подграф концептуального графа C с отношением одновременности Одновр между событиями F₈, F₉ и остальными событиями.

При построении концептуального графа C использовался распространенный в мировой практике редактор CharGer ^[15], позволяющий представить граф в виде XML-файла. Такое представление позволяет осуществить в дальнейшем автоматический переход от концептуального графа к отношениям реляционной базы данных. Полученные отношения, представленные таблицами 1 – 7, используются далее при анализе сценария, представленного концептуальным графом C на рис. 1 и 2.

3. Логика запросов и сети абстрактных машин

Далее будут использоваться логико-алгебраические выражения для абстрактных модулей, выполняющих запросы к базе знаний, сформированной на основании концептуального представления модели роботизированного производства. При построении логико-алгебраических выражений для модулей сети абстрактных машин, детально рассмотренных в работах ^{[7, 8]}, использованы некоторые элементы нотации из алгебры алгоритмов В. М. Глушкова ^[14]. Например, выражение [α](m₁`vv` m₂), где α – некоторое условие, а m₁ и m₂ – выражения для модулей абстрактных машин, соответствует тернарной операции α-дизъюнкции, когда при α = true выполняется модуль m₁, а при α = false выполняется модуль m₂. Одним из модулей в приведенном выражении может быть пустой (“тождественный”) оператор E, не выполняющий никаких действий. Выражения m₁ и m₂ могут, в свою очередь, содержать другие α-дизъюнкции. Запятыми в выражениях для абстрактных модулей разделяются последовательно выполняемые действия.

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

Рис. 1. Концептуальный граф C сценария роботизированного производства

(основная часть)

Рис. 2. Подграф концептуального графа C сценария роботизированного

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

Таблица 1 – Имя

Таблица 2 - Агент

Таблица 3 - Объект

Таблица 4 - Место

Таблица 5 - След

Таблица 6 – Возм­_след

Таблица 7 - Одновр

В логике второго порядка, применение которой при построении сетей абстрактных машин предложено в работах ^{[7, 8]}, дополнительно используются предикатные и функциональные переменные. Необходимые сведения о логиках второго и высших порядков даны в работах ^[17-20]. Несмотря на неполноту, характерную также и для теории множеств, выразительные возможности логики второго порядка богаче выразительных возможностей логики первого порядка. В настоящей работе рассмотрены такие логические модели, которые допускают простую переинтерпретацию логики второго порядка в многосортную первопорядковую логику, обладающую полнотой.

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

,

где – термы различных сортов, а s – функциональный или предикатный символ. В случае, если s – функциональный символ, – суть терм любого сорта, а если s – предикатный символ, то – булево выражение. Отметим, что подобные правила активно используются в теории машин абстрактных состояний Ю. Гуревича ^[21]. В модулях абстрактных машин второго порядка s может быть предикатной или функциональной переменной ^{[7, 8]}. Дополнительно отметим, что символ двойной стрелки “`lArr`”, используемый вместо символа обычной стрелки “←”, означает множественное обновление предиката или функции.

При построении выражений для абстрактных модулей возможно использование определенных в работах ^{[7, 8]} “квантифицированных” операторов выборки `EE` _{Sel_any}, `EE` _{Sel_one}, `AA` _Sel и `AA` _{Sel _all} кортежей из отношений при условии истинности выражений справа от данных операторов. При выполнении оператора `EE` _{Sel_any} в области истинности предиката, описываемого выражением справа, отмечается произвольный кортеж. При выполнении оператора `EE` _{Sel_one} отмечается единственный кортеж, находящийся в области истинности записанного справа предиката. При выполнении оператора `AA` _Sel отмечаются все кортежи, составляющие область истинности соответствующего предиката. Оператор `AA` _{Sel_all} позволяет отметить все кортежи из области истинности предиката в случае, если его область определения совпадает с его же областью истинности. Во всех случаях подразумевается, что предикат описывается выражением, стоящим справа от символа квантифицированного оператора. Описанные операторы не модифицируют области истинности предикатов, а только выделяют некоторые кортежи в этих областях. Дальнейшие действия, связанные с модификацией предикатов и функций реализуются при помощи описанных выше помощи правил обновления, заключенных в круглые скобки и, возможно, сгруппированных в блоки, ограниченные фигурными скобками.

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

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

4. Примеры запросов к базе знаний в виде выражений для модулей

сети абстрактных машин

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

1. Какие ролевые отношения связывают событие F₇ с концептами Погрузка_2, Автопогрузчик, Контейнер и Автомобиль?

При построении запроса на языке сетей абстрактных машин, основанного на логике предикатов первого и второго порядков, определены предикатная переменная r `in` R и унарный предикат Роль_ответ(r) для отображения результата поиска по отношениям и концептам графа. Ответ на указанный запрос может быть получен при реализации модулями запросов следующих выражений:

[(`AA` _Selr `in` R) r(F₇, Погрузка_2)]( Роль_ответ(r) `lArr` true `vv` E);

[( `AA` _Sel r `in` R) r(F₇, Автопогрузчик)]( Роль_ответ(r) ` lArr ` true `vv` E);

[( `AA` _Sel r `in` R) r(F₇, Контейнер)]( Роль_ответ(r) `lArr` true `vv` E);

[(`AA` _Sel r `in` R) r(F₇, Автомобиль)]( Роль_ответ(r) `lArr` true `vv` E).

В результате выполнения данных запросов переменная r будет принимать значения в множестве отношений {Имя, Агент, Объект, Место}. Использование предикатной переменной r означает применения логики предикатов второго порядка.

В приведенных выражениях использован квантифицированный оператор выбора `AA` _Sel (а не оператор `EE` _{Sel_one} или оператор `EE` _{Sel_any}), поскольку некоторые концепты-события в концептуальной модели могли быть связаны с концептами-объектами несколькими отношениями; например, концепт-событие F₁ Обработка связано с концептом-объектом Станок отношениями Место и Агент, то есть станок является и агентом, поскольку производит обработку деталей, и местом, на котором размещаются детали при обработке. Так как в общем случае для всего графа при этом оператор `AA` _Sel находит, возможно, не единственное значение предикатной переменной r, то используемый символ “`lArr`” означает возможное множественное обновление, или модификацию, предиката Роль_ответ(r). Например, в результате выполнения запроса

[(`AA` _Sel r `in` R) r(F₁, Станок)]( Роль_ответ(r) `lArr` true `vv` E)

будут истинны высказывания Роль_ответ(Агент) и Роль_ответ(Место).

2. Какие несобытийные концепты связаны с реализацией события F₀?

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

[(`EE` _{Sel_one} x `in` X₁) Имя(F₀, x)](Концепт_ответ(x) ← true `vv` E);

[(`EE` _{Sel_one} x `in` X₁) Агент(F₀, x)](Концепт_ответ(x) ← true `vv` E);

[(`EE` _{Sel_one} x `in` X₁) Объект(F₀, x)](Концепт_ответ(x) ← true `vv` E);

[(`EE` _{Sel_one} x `in` X₁) Место(F₀, x)](Концепт_ответ(x) ← true `vv` E).

В результате выполнения этих запросов будет определен унарный предикат Концепт_ответ(x), область истинности которого составят искомые концепты {Подача, Автомат, Заготовка, Станок}.

Другой вариант решения возможен на основе использования характеристической функции (унарного предиката) Q_R1(r), определенной для множества отношений R₁. Более компактное представление запроса, заменяющее приведенные выше четыре выражения для запросов к базе знаний тогда можно представить в следующем виде:

[(`AA` _All r `in` R₁) Q_R1(r)]([(`EE` _{Sel_one} x `in` X₁₎ r(F₀, x)]

(Концепт_ответ(x) `lArr` true `vv` E) `vv` E).

Построение данного выражения основано на логике предикатов второго порядка. Здесь при выполнении квантифицированного оператора (`AA` _All r `in` R₁) Q_R1(r) выбираются все значения предикатной переменной r, поскольку область определения предиката Q_R1(r) совпадает с областью его истинности. Эти значения затем учитываются при дальнейшем выполнении квантифицированного оператора (`EE` _{Sel_one} x `in` X₁) r(F₀, x). Таким образом, выполнение множественного обновления предиката

Концепт_ответ(x) `lArr` true

будет эквивалентно выполнению множества одиночных обновлений того же самого предиката:

{Концепт_ответ(Подача) ← true, Концепт_ответ(Автомат) ← true,

Концепт_ответ(Заготовка) ← true, Концепт_ответ(Станок) ← true}.

Рис. 3. Основная часть концептуального графа C с некоторыми неизвестными

концептами и отношениями

В случае, когда пользователь экспертной системы не уверен в функциональности ролевых отношений, в выражениях для запросов оператор `EE` _{Sel_one} следует заменить на `AA` _Sel и использовать далее операцию “`lArr`” множественного обновления предиката Концепт_ответ(x):

[(`AA` _All r `in` R₁) Q_R1(r)]([(`AA`_Selx `in` X₁) r(F₀, x)]

(Концепт_ответ(x) `lArr` true `vv` E) `vv` E).

3. Определить концепты-события, необходимо следующие за событием F₂.

Выполнение следующего выражения для запроса позволит получить ответ на заданный вопрос:

[(`AA`_Selx `in` F) След(F₂, x)](След_ответ(x) `lArr` true `vv` E).

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

[(`EE`_{Sel_one} x `in` F) След(F₂, x)](След_ответ(x) ← true `vv` E).

4. Определить концепты-события, возможно следующие за событием F₄.

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

[(`AA`_Selx `in` F) Возм_след(F₄, x)](Возм_след_ответ(x) `lArr` true `vv` E).

Для рассматриваемого сценария после выполнения данного запроса область истинности предиката Возм_след_ответ(x) будет содержать два события – F₅ и F₆.

5. Какое отношение связывает концепты-события F₄ и F₅? Другой вариант вопроса: «Возможно ли следование события F₅ непосредственно после события F₄?».

[(`EE`_{Sel_one} r `in` {След, Возм_след}) r(F₄, F₅)]

(Отношение_ответ(r) ← true `vv` E).

В результате применения подобного запроса к базе знаний рассматриваемого примера будет истинно высказывание Отношение_ответ(Возм_след), означающее, что события F₄ и F₅ связывает отношение непосредственного следования, или что возможно следование события F₅ непосредственно после события F₄.

6. В каких событиях и в каких ролях участвовал робокар?

[(`AA`_All r `in` R₁) Q_R1(r)]([(`AA`_Sel x `in` F) r(x, Робокар)]

(Результат_1(x, r) `lArr` true `vv` E) `vv` E).

В результате выполнения данного запроса область истинности бинарного предиката Результат должны содержать кортежи <F₃, Место>и <F₄, Агент>, то есть должны оказаться истинными высказывания Результат(F₃, Место) и Результат(F₄, Агент). Это означает, что робокар при выполнении события F₃ был местом для размещения кассет, а при выполнении события F₄ стал агентом для этих же кассет.

Для того, чтобы узнать названия событий F₃ и F₄, необходимо выполнить два следующих запроса:

[(`EE`_{Sel_one} y `in` X_N) Имя(F₃, y)](Имя_события(F3, y) ← true `vv` E);

[(`EE`_{Sel_one} y `in` X_N) Имя(F₄, y)](Имя_события(F4, y) ← true `vv` E),

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

7. Связаны ли события F₆ и F₇ отношением непосредственного следования?

При поиске ответа на данный вопрос просто проверяется истинность или ложность высказывания След(F_6, F₇). Для рассматриваемого примера это высказывание истинно.

Приведенные выражения для запросов к базе знаний представляют точные формализованные спецификации для сценариев получения новых знаний о предметной области или уточнения прежних забытых или утраченных знаний. При проектировании человеко-машинного интерфейса интеллектуальной системы возможно использовать известные языки, например, C++, C#, SQL, Visual Prolog. Последние два языка не используют логику второго порядка, поэтому при реализации запросов необходимо просто перечислять отношения, из которых выбираются кортежи.

Заключение

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

2. Формализован процесс построения сценарных моделей на основе концептуальных графов, что позволило использовать указанные модели в составе экспертно-имитационных моделей систем ситуационного управления.

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

4. Запросы к базе знаний, построенной на основе концептуального графа, могут быть формализованы на языке сетей абстрактных машин с использованием логики первого и второго порядков, что упрощает дальнейшее проектирование человеко-машинного интерфейса интеллектуальной системы на базе известных языков типа C++, C#, SQL, Visual Prolog и др.