Integrating Methods of Conceptual and Behavioral Modeling of Discrete Event Systems: I. Synthesis and Analysis of a Conceptual Model

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 Other publications by this author     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 Other publications by this author     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 Other publications by this author

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 Other publications by this author

Концептуальные и поведенческие модели нашли широкое применения в экспертно-имитационном моделировании дискретно-событийных систем различной природы. Согласно одному из распространенных определений ^[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 и др.