Алгебри предикатних операцій та їх застосування у системах штучного інтелекту

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

27

ХАРКІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ

АВТОРЕФЕРАТ

АЛГЕБРИ ПРЕДИКАТНИХ ОПЕРАЦІЙ ТА ЇХ ЗАСТОСУВАННЯ У СИСТЕМАХ ШТУЧНОГО ІНТЕЛЕКТУ

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

На теперішній час інформація стала важливішою складовою ресурсів матеріального виробництва. Тому, щоб безпосередньо сприяти успіху організації на ринку інформаційні системи, що забезпечують взаємодію з навколишнім світом, повинні швидко розроблюватися, функціонувати у різнорідних мережних середовищах, поєднувати використання таких видів інформації як аудіо, відео, графіку і текст, мати доступ до ізольованих джерел інформації. Всім необхідним вимогам задовольняють системи інформаційного обслуговування з розподіленою архітектурою. Однак при розробці багатомодульних систем різко зростає трудомісткість етапу верифікації програмного забезпечення. Це зробило особливо актуальною проблему розробки інтелектуальних інструментальних засобів, які дозволяють перевіряти функціонально-логічну коректність таких систем.

Актуальність теми. Одним з найбільш популярних інструментів моделювання інформаційних процесів та систем, в яких розподіл ресурсів, комунікацій та синхронізація відіграють важливу роль, є сітки Петрі. Для ефективного використання сіток Петрі необхідна розробка інструментальних засобів формалізації моделювання систем і аналізу сіток Петрі. В цей час залишається актуальною проблема розробки методів аналізу простору становищ сітки Петрі з урахуванням того, що множина досяжності розміток сітки може бути незкінченною. Теорія множин, теорія комплектів, а також матричний підхід не дають достатніх можливостей для аналізу простору становищ сітки та розв'язання задачі досяжності розмітки.

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

У своїх дослідженнях автор базувався на роботах Котова В.Є., Мальцева А. І., Попова Е. В. , Поспєлова Д. О., Шабанова-Кушнаренко Ю. П.. У рамках вказаного кола проблем формулюється постановка задачі дослідження, що викладено в дисертації. Дисертаційна робота присвячена удосконаленню методів моделювання багатомодульних систем інформаційного обслуговування з розподіленим управлінням.

Зв'язок роботи з науковими програмами, планами, темами. Тема даної дисертаційної роботи відповідає проблематиці держбюджетної науково-дослідницької роботи за темою № 413 "Розробка теорії штучного та природного інтелекту і її застосування для автоматизації процесів навчання і виховання в навчальних закладах України" (№ДР 0195U023071). У рамках даної теми здобувачем доведена повнота і рівносильність фундаментальної і прикладної алгебр предикатних операцій, а також розроблена підсистема формульного представлення предикатних операцій у програмній системі логічної підтримки проектування систем штучного інтелекту.

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

Для досягнення зазначеної мети в роботі ставляться і вирішуються такі задачі:

Доведення повноти диз'юнктивно-кон'юнктивної і фундаментальної алгебр предикатних операцій.

Доведення рівносильності фундаментальної і прикладної алгебр предикатних операцій.

Розробка опису логічної структури і функціонування ординарної і розфарбованої сітки Петрі на мові фундаментальної алгебри предикатних операцій.

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

Розробка алгоритму визначення властивостей збереження та обмеженості розфарбованої сітки Петрі.

Розробка системи, що реалізує імітаційну модель розфарбованої сітки Петрі з використанням мови фундаментальної алгебри предикатних операцій та технологій штучного інтелекту.

Об'єктом дослідження є моделі багатомодульних систем інформаційного обслуговування з розподіленим управлінням.

Предметом дослідження є алгебро-логічні моделі сіток Петрі з використанням інтелектуальних компонент.

Методи дослідження. При побудові алгебро-логічних моделей сіток Петрі і дослідженні їх властивостей використовувались методи алгебр предикатних операцій, метод інваріантів місць і метод дерева досяжності.

Наукова новизна одержаних результатів.

У роботі доведена повнота диз'юнктивно-кон'юнктивної і фундаментальної алгебр предикатних операцій.

У роботі доведена рівносильність фундаментальної і прикладної алгебр предикатних операцій.

Вперше запропоновано використовувати апарат фундаментальної алгебри предикатних операцій для опису структури і функціонування ординарної сітки Петрі та розфарбованої сітки Петрі, що дозволяє доповнювати модель інтелектуальною компонентою.

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

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

Практичне значення одержаних результатів. Розроблена програмна система може бути використана як інструментальний засіб моделювання при розробці програмного забезпечення і інформаційних систем. Крім цього, дана система може бути використана як навчальна. Результати дисертації у вигляді інструментального засобу для верифікації при розробці функціонального програмного забезпечення на цифрові автоматичні телефонні станції впроваджені на Харківському державному приладобудівному заводі ім.Т.Г.Шевченка, де у 1999 році розроблено і впроваджено до експлуатації програмне забезпечення вузла доступу для цифрової автоматичної телефонної станції "Донець-5". Модель, що розроблена в дисертації, була у явному вигляді застосована в цьому інструментальному засобі.

Особистий внесок здобувача. Усі основні результати, які представлені в роботі, одержані особисто здобувачем. У роботах [1, 2, 4, 5] автором проведений подальший розвиток методів формалізації функцій інтелекту людини і аналіз можливого використання для цієї мети алгебр предикатних операцій. У роботах [4, 5] здобувачу належать приклади змістової інтерпретації предикату еквівалентності, а також аналіз перспектив і приклади формального опису математичних понять на мові алгебри скінченних предикатів. У роботі [1] автором доведені теореми щодо повноти диз'юнктивно-кон'юнктивної і фундаментальної алгебр предикатних операцій, а у роботі [2] - теорема щодо рівносильності фундаментальної і прикладної алгебр.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідались та обговорювались на таких конференціях:

Research and Innovation in Open and Distance Learning, The First Research Workshop of EDEN (European Distance Education Network ) (Prague, 16-17 march 2000);

2^th International Virtual Reality Meeting "Laval Virtual 2000" (Laval - France, 18-21 may 2000);

4-й Міжнародній науково-методичній Конференції "ОСВІТА ТА ВІРТУАЛЬНІСТЬ (ВІРТ 2000)" (Севастополь, 12-17 вересня 2000 р.);

5-й Всеукраїнській міжнародній конференції по обробці сигналів і зображень та розпізнаванню образів "УкрОБРАЗ - 2000" (27 листопада - 1 грудня 2000 р.).

Публікації. Результати досліджень опубліковані в 7 виданих роботах, з них 3 статті в наукових спеціалізованих виданнях і в збірках наукових праць, список яких затверджено ВАК України, 2 депонованих рукописи, 2 - в матеріалах і тезах конференцій.

Структура і обсяг роботи. Дисертаційна робота складається із вступу, чотирьох розділів, висновків і додатків та має загальний обсяг 137 сторінок, містить 16 рисунків, 1 таблицю, 6 додатків на 35 сторінках, список літературних джерел зі 101 найменування на 9 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обгрунтовано актуальність дисертаційної роботи, сформульовано основну мету і задачі дослідження, наведено відомості про зв'язки обраного напрямку досліджень із планами організації, де виконана робота, відзначено наукову новизну та практичну цінність одержаних результатів і наведено дані про їх використання у народному господарстві.

У першому розділі наведено огляд областей застосування багатомодульних систем інформаційного обслуговування з розподіленим управлінням та проблем їх розробки. Досліджено можливі застосування інтелектуальних технологій у моделюванні. В роботі як один із засобів моделювання використовуються сітки Петрі, тому що вони дозволяють моделювати широкий спектр інформаційних процесів і систем від функціонування операційної системи, однозв'язних N-арних семантичних сіток до гіпертекстових систем. Проведено порівняльний аналіз існуючих методів представлення та сформульовані основні проблеми аналізу сіток Петрі. предикат алгебра isicpn

У результаті обгрунтовано необхідність дослідження алгебро-логічних моделей сіток Петрі, доповнення їх інтелектуальними компонентами та розробки на їх базі інструментальних засобів для формалізації процесів моделювання. На підставі проведених досліджень сформульовані наведені вище мета і задачі дисертаційної роботи.

У другому розділі наведено визначення алгебри предикатів, вивчено можливості її застосування для формального опису відносин, а також методи перетворення і аналізу її формул. Специфіка досліджень даної роботи передбачає розгляд відносин, визначених у термінах алгебри предикатів та алгебр предикатних операцій, як засобу для побудови моделей сіток Петрі, що дозволяють підвищити ефективність розробки багатомодульних систем з розподіленим управлінням.

Будь-яка функція P(x₁, x₂,…, x_m), яка відображує множину U^m у множину = {0, 1}, називається предикатом, заданим на U^m. Предикат P називається скінченним, якщо множина U кінцева, та нескінченним - у протилежному випадку. Змінні x₁, x₂,…, x_m називаються аргументами предиката P(x₁, x₂,…, x_m ). Алгеброю предикатів над M називається будь-яка алгебра, носієм якої служить множина M усіх предикатів на U^m

(1)

Предикат (1) називається предикатом упізнання букви а. Упізнання букв є елементарними предикатами алгебри предикатів. Сукупність елементарних операцій і елементарних предикатів складає базис алгебри предикатів.Формул алгебри скінченних предикатів більше, ніж предикатів які вони позначають. Щоб із множини усіх формул виділити клас формул, що називаються нормальними формами, у якому кожному предикату відповідала б тільки одна формула алгебри скінченних предикатів, вводиться поняття довершеної диз'юнктивної нормальної форми. Розглянуто теорему щодо диз'юнктивного розкладення та її висновки.

Предикатні операції використовуються у тих випадках, коли виникає необхідність проводити дії над предикатами або описувати зв'язки між ними. Алгебра предикатних операцій є поширенням алгебри предикатів. Предикатні операції визначено таким чином: нехай U - універсум предметів; X₁, X₂, ..., X_m - предметні змінні. M - множина усіх предикатів P (X₁, X₂, ..., X_m) на предметному просторі U^m. Множина M називається універсумом предикатів. Змінні, які визначені на множині M, називаються предикатними змінними. Їх значеннями служать предикати, які задані на U^m. Множина Mⁿ називається предикатним простором розмірності n над предметним простором U^m. Елементи множини Mⁿ (набори предикатів) називаються предикатними векторами. Будь-яка функція F(X₁, X₂, ..., X_n) = , що відображує множину Mⁿ у множину M називається предикатною операцією.

Запереченням F = предикатної операції F називається така предикатна операція, значення якої визначаються рівнянням:

(F)(X₁, X₂, ..., X_n) = F(X₁, X₂, ..., X_n), (2)

де X₁, X₂,..., X_n M - довільні предикатні змінні.

Диз'юнкцією F G предикатних операцій F и G називається предикатна операція, значення якої визначаються рівнянням:

(F G)(X₁, X₂, ..., X_n) = F(X₁, X₂, ..., X_n) G(X₁, X₂, ..., X_n), (3)

де X₁, X₂,..., X_n M - довільні предикатні змінні.

Кон'юнкцією F G предикатних операцій F и G називається предикатна операція, значення якої визначаються рівнянням:

(F G)(X₁, X₂, ..., X_n) = F(X₁, X₂, ..., X_n) G(X₁, X₂, ..., X_n), (4)

де X₁, X₂,..., X_n M - довільні предикатні змінні.

Константною предикатною операцією називається будь-яка операція із значенням

F(X₁, X₂, ..., X_n) = P, (5)

де X₁, X₂,..., X_n M - довільні предикатні змінні;

P - фіксований предикат із M.

Визначено предикатну операцію упізнання предиката:

 (6)

Предикатною операцією упізнання предиката P по змінній X_i називається операція (6).

Розглянуто різні види алгебр предикатних операцій, наведена оцінка їх повноти і виразних можливостей, а також розглядається можливість їх редукції та рівносильність.

Алгеброю предикатних операцій називається будь-яка алгебра, що задана на множині усіх предикатних операцій. Як основні критерії при визначенні практичної цінності апарату тієї або іншої алгебри предикатних операцій у роботі використані властивості повноти алгебри і системи основних тотожностей алгебри. Повною є така алгебра предикатних операцій, в якій для кожної предикатної операції буде знайдена формула, що її позначає. Система тотожностей алгебри є повною, якщо за допомогою цих тотожностей можна довести тотожність двох будь-яких формул алгебри предикатних операцій, що позначають одну і ту ж предикатну операцію.

Проведено аналіз цих властивостей для таких алгебр предикатних операцій:

- булевої алгебри предикатних операцій;

- алгебри предикатних операцій з константами і змінними;

- диз'юнктивно-кон'юктивної алгебри предикатних операцій, якою називається алгебра предикатних операцій, у якій базисними операціями служать диз'юнкція і кон'юнкція, а базисними елементами - будь-які константи P M і предикати упізнання предиката X_i^P (, P M) (6);

- фундаментальної алгебри предикатних операцій , якою називається алгебра предикатних операцій, у якої базисними операціями є диз'юнкція, кон'юнкція і заперечення (2 - 4), а базисними елементами - предикати 0 і 1 та будь-які предикати упізнання предметів x_i^a (, a U) (1) і предикати упізнання предикатів X_j^P (, P M) (6);

- прикладною алгеброю називається алгебра предикатних операцій з базисом операцій, що утворені із підстановок виду x_i/a(X) (, a U), а також операцій заперечення і диз'юнкції, і базисом елементів, що утворені із предикатів рівняння виду D(x₁, x_i) () (тут вони виступають у ролі константних предикатних операцій), предикатних змінних Х_i ().

Під час аналізу доведені такі теореми :

Теорема щодо повноти диз'юнктивно-кон'юктивної алгебр предикатних операцій. При будь-яких U, m і n диз'юнктивно-кон'юктивна алгебра предикатних операцій повна.

Теорема щодо повноти фундаментальної алгебри. Фундаментальна алгебра при будь-яких U, m та n повна.

Доведення цих теорем базується на властивостях довершеної диз'юнктивної нормальної форми.

На підставі проведеного аналізу визначено, що фундаментальна алгебра повна. Наведені закони, що пов'язують предметні і предикатні змінні. Представлено вираження на мові фундаментальної алгебри заміни аргументу предиката, перестановки аргументів предиката, операцію підстановки. Заміну, перестановку і підстановку можна розуміти не тільки як предикатні операції, але і як операції над предикатними операціями. Виражено на мові фундаментальної алгебри квантори спільності та існування.

Проведено порівняльний аналіз властивостей прикладної і фундаментальної алгебр предикатних операцій, у ході якого доведена теорема щодо їх рівносильності. Алгебри вважаються рівносильними, якщо на мові їх формул описується одна і та ж множина об'єктів.

Теорема щодо рівносильності фундаментальної і прикладної алгебр. Фундаментальна і прикладна алгебри предикатних операцій, що мають один і той же носій, рівносильні.

Проте, тільки для фундаментальної алгебри відома повна система законів, що дозволяє вирішити питання чи, виражають дві довільно взяті її формули одну і ту ж предикатну операцію. Наведені вище якості фундаментальної алгебри є підставою для вибору цієї алгебри як інструменту для побудови алгебро-логічної моделі сіток Петрі.

У третьому розділі розроблено модель логічної структури та функціонування ординарної сітки Петрі і ординарної розфарбованої сітки Петрі без контролю часу на мові фундаментальної алгебри предикатних операцій. Розглянуто формальне визначення обмеженої ординарної сітки Петрі у термінах алгебри предикатних операцій. Визначено ординарну сітку, так як існує алгоритм перетворення будь-якої сітки Петрі з кратними дугами в ординарну.

Сітка Петрі визначається такою множиною:

N = < P, V, F, H, Cond, M₀>, (7)

де Р - кінцева непуста множина місць;

V - кінцева непуста множина переходів;

F - функція інцидентності, що вказує на наявність дуг, які з'єднують місця з переходами;

Н - функція інцидентності, що вказує на наявність дуг, які з'єднують переходи з місцями;

Cond - функція, що визначає умови спрацьовування переходів;

М₀ - початкова розмітка сітки.

Елементи множини (7) представлено таким чином:

Р - кінцева непуста множина символів { P₁, P₂, ... P_n}, що називаються місцями. Подамо їх як кінцеву непусту множину предикатів: P₁ = x^a1, P₂ = x^a2, ... P_n = x^an, де а₁, а₂,… а_n {0, 1, 2,…} означають кількість фішок в даному місці, n - кількість місць сітки.

V - кінцева непуста множина предикатних операцій {V₁, V₂,... V_k}, де k - кількість переходів сітки, що називаються переходами. Спрацьовування переходу - є множиною операцій над предикатами Р_i і предикатом розмітки M. Це дозволяє представляти і помічені (або розфарбовані) сітки Петрі.

Функцію інцидентності F подамо як предикат F (p₁ , p₂ , ... p_n), де р_i {1, 2,... k}.

(8)

де n - кількість місць сітки;

k - кількість переходів сітки.

Функцію інцидентності Н подано аналогічно функції F, як предикат H(v₁,v₂,…v_k), де v_i {1, 2,… n}.

(9)

де n - кількість місць сітки;

k - кількість переходів сітки.

В окремих випадках функція Cond може бути однакова для всіх переходів:

(10)

де .

В загальних випадках Cond складається із множини умов: Cond = {C₁, C₂, … C_k}, де C₁ = C₀ U₁; C₂ = C₀ U₂; …; C_k = C₀ U_k; U_i може дорівнювати 1 або визначатися логічним виразом.

М₀ - початкова розмітка сітки Петрі, тобто відображення з множини місць у множину цілих невід'ємних чисел. Розмітка визначається предикатом

(11)

де предикатом упізнавання l_i^ai {0, 1} визначається число фішок в i-му місці. Спрацьовування переходу V_i сітки Петрі записано так:

(12)

де ;,

(13)

де ; .

Таким чином, застосування фундаментальної алгебри предикатних операцій для представлення і опису функціонування сіток Петрі дає суттєву економію пам'яті під час програмування, особливо для моделювання складних систем.

Фундаментальна алгебра предикатних операцій дозволяє формалізувати більш складні перетворення сіток Петрі. Так використання фундаментальної алгебри предикатних операцій при визначенні приєднання, виключення, накладення і т. ін. сіток Петрі в алгебрі регулярних сіток Петрі дозволяє раціоналізувати формалізацію перетворень сіток Петрі.

Але при представленні звичайної сітки Петрі потужність апарату фундаментальної алгебри предикатних операцій використовується не в повній мірі, кількість фішок в місцях сітки дублюється предикатами P_i і M.

Розроблено модель логічної структури і функціонування ординарної розфарбованої сітки Петрі. Розфарбована сітка Петрі визначається такою семіркою:

N = < P, V, m, F, H, Cond, M₀ >, (14)

де Р - кінцева непуста множина місць;

V - кінцева непуста множина переходів;

m - кількість типів фішок;

F - функція інцидентності, яка вказує на наявність дуг, що з'єднують місця з переходами;

Н - функція інцидентності, яка вказує на наявність дуг, що з'єднують переходи з місцями;

Cond - функція, яка визначає умови спрацювання переходів;

М₀ - початкова розмітка сітки.

Елементи множини (14) представлено таким чином:

Р - кінцева непуста множина символів {P₁, P₂, ... P_n}, що називаються місцями (n - кількість місць). Їх наведено як кінцеву непусту множину предикатів виду де m - кількість типів фішок (кольрів); a_j - кількість фішок j - го типу в місці P_i , a_j {0, 1, 2, ...}; j { 1,. ...m}.

Функції H і F подано аналогічно відповідним функціям для ординарної сітки Петрі (8), (9). Для розфарбованої сітки Петрі Cond матиме вигляд кон'юнкції логічних виражень.

(15)

де i - номер переходу;

; k {1,…,m};

n - кількість місць сітки;

h - кількість наборів фішок різних кольорів у вхідних місцях переходу m - кількість кольорів фішок; g - кількість вхідних місць переходу.

Щоб визначити загальний вигляд умов спрацьовування переходу для розфарбованої сітки Петрі введено предикатну операцію G:

G_i (P, X) = x_i X P (x₁,…, x_m) , (16)

де X може приймати значення .

Тоді умови зміни розмітки вихідних місць переходу та умови спрацьовування переходів записуються у вигляді диз`юнкції операцій (16).

V - кінцева непуста множина предикатних операцій {V₁, V₂,... V_k}, що називаються переходами.

(17)

де i - номер переходу;

l - номер набору фішок різних кольорів у вхідних місцях переходу m - кількість кольорів фішок; g - кількість вхідних місць переходу;

- номер вхідного місця сітки;

- номер вихідного місця сітки;

n - кількість місць у сітці;

k {1, m} ;

- умови спрацьовування та зміни розмітки і-го переходу.

M₀ - початкова розмітка. Розмітка є предикатом виду M = P₁ P₂ … P_n . Спрацьовуванням переходу є множина операцій (17) над предикатами Р_i і предикатом розмітки M.

Далі наведено визначення основних властивостей сіток Петрі та проаналізовано метод їх визначення за допомогою дерева досяжності. Розроблено метод визначення множини тупікових розміток сітки.

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

(18)

де C_i - умова спрацьовування i-го переходу (15);

к - кількість переходів у сітці.

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

Вивчено проблеми розробки багатомодульних систем з розподіленим управлінням. Описані основні функції і архітектура системи ISICPN. Програмна система ISICPN дозволяє імітувати функціонування розфарбованої сітки Петрі без контролю часу і аналізувати деякі її властивості, спираючись на апарат алгебри предикатних операцій. А саме, розроблений алгоритм визначення властивостей збереження і обмеженості. Програмна система ISICPN виконує такі функції:

· побудова та корекція графічного зображення розфарбованої сітки Петрі за допомогою зручного інтерфейсу і графічного редактора;

· задання користувачем початкової розмітки і умов спрацьовування сітки;

· перевірка логічної коректності введеної інформації;

· імітація виконання сітки в інтерактивному режимі;

· редактування структури, початкової розмітки та умов спрацьовування переходів сітки;

· перевірка властивостей збереження і обмеженості;

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

Інтелектуальну компоненту системи розроблено у вигляді інтелектуального агента. Агент є автономною компонентою, яка функціонує у фоновому режимі та керується запитами користувача. Ціль функціонування агента полягає у формуванні та повідомленні користувачу рекомендацій щодо модифікації моделі, для забезпечення найбільшої надійності системи. Вхідними даними для агента є запит користувача і структура, параметри та властивості моделі. Вихідні дані: рекомендації щодо обробки тупікових ситуацій, повідомлення користувачу про властивості для всіх модифікацій моделі, що аналізується, виділення контрастним кольором місць та переходів сітки, у які бажано внести зміни для виконання певних властивостей сітки. Задачі, що виконує агент, належать до класу задач діагностики і виконуються на основі структури, властивостей моделі і експертних оцінок. Агент містить у собі базу знань, що модифікується у процесі моделювання. Продукції бази знань описані формулами фундаментальної алгебри предикатних операцій.

Умови спрацьовування переходів зберігаються у вигляді формул фундаментальної алгебри предикатних операцій, що дозволяє використовувати для аналізу властивостей сітки метод визначення множини тупікових розміток. Таким чином, система ISICPN підтримує всі три основних методи аналізу сіток Петрі (імітація, аналіз простору становищ, інваріанти місць). Під час інтерактивної імітації можна побачити ефект окремих кроків безпосередньо на графічному представленні розфарбованої сітки Петрі. Це дає можливість при наскрізному контролі моделі сітки, досліджувати різні сценарії та перевіряти чи відповідає робота моделі очікуванням.

Система ISICPN використана як інструментальний засіб моделювання при розробці функціонального програмного забезпечення на цифрові автоматичні телефонні станції на Харьківскому державному приладобудівному заводі ім. Т.Г.Шевченко. Система ISICPN використовувалася розробниками прикладного програмного забезпечення системи на етапі верифікації. Визначення властивостей збереження, обмеженості та метод визначення множини тупікових розміток сітки використовувались для з'ясування ступеня функціонально-логічної коректності системи. В процесі інтерактивного виконання сітки розробники підбирали оптимальну конфігурацію структури програмної системи, використовуючи як критерії ефективності властивості збереження і обмеженості, кількість досяжних тупікових розміток. Таким чином, система ISICPN дозволяє розробляти і послідовно удосконалювати когнитивно-наглядну та "прозору" структуру системи.

У додатках наведено екранні форми, що демонструють основні функції програмної системи ISICPN та тестові приклади, акти впровадження результатів дисертаційного дослідження, а також лістинги деяких модулей системи.

ВИСНОВКИ

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

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

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

Доведено повноту диз'юнктивно-кон'юнктивної і фундаментальної алгебр предикатних операцій; а також рівносильність фундаментальної та прикладної алгебр предикатних операцій (доведено вперше). На базі доведених теорем фундаментальна алгебра предикатних операцій обрана у ролі математичного апарата для розробки опису логічної структури і функціонування ординарної і розфарбованої сітки Петрі.

Розроблено модель логічної структури та функціонування ординарної сітки Петрі і ординарної розфарбованої сітки Петрі без контролю часу на мові фундаментальної алгебри предикатних операцій, що дозволяє доповнювати модель інтелектуальною компонентою (отримано вперше).

Розроблено метод визначення множини тупікових розміток для розфарбованої сітки Петрі, що дозволив зменшити трудомісткість процесу перевірки функціонально-логічної коректності системи, що моделюється (отримано вперше).

Розроблено структуру і функції інтелектуальної компоненти системи моделювання, яка дозволяє проводити діагностику функціонально-логічної коректності системи, що моделюється з рекомендаціями щодо внесення змін у структуру моделі.

Розроблений алгоритм визначення властивостей збереження і обмеженості розфарбованої сітки Петрі, що дозволяє визначати властивості, які є основними крітеріями аналізу моделі у розробленій програмній системі.

Розроблено систему ISICPN інтерактивної імітації розфарбованої сітки Петрі, яку доповнено інтелектуальною компонентою. Система ISICPN застосована у вигляді інструментального засобу для верифікації при розробці функціонального програмного забезпечення на цифрові автоматичні телефонні станції на Харківському державному приладобудівному заводі ім.Т.Г.Шевченка, що дозволило значно зменшити трудомісткість процесу розробки.

СПИСОК ОПУБЛІКОВАНИХ АВТОРОМ ПРАЦЬ ДО ТЕМИ ДИСЕРТАЦІЇ

1. Дударь З. В., Кравец Н. С., Шабанов-Кушнаренко Ю. П. О фундаменталь-ной алгебре предикатных операций // Проблемы бионики.- 1998.- Вып.49.-С. 3-13.

2. Дударь З. В., Кравец Н. С., Шабанов-Кушнаренко Ю. П. О прикладной алгебре предикатных операций // Проблемы бионики.- 1999.- Вып. 51.- С. 70-78.

3. Кравец Н.С. Моделирование структуры сетей Петри с помощью алгебры предикатных операций // Новые решения в современных технологиях. Вестник Харьк. гос. политехн. ун-та. - 1999. - Вып. 44. - С. 13-14.

4. Кравец Н.С., Шабанов-Кушнаренко С.Ю. Общий вид эквивалентности// Харьк. гос. техн. ун-т. радиоэлектроники. - Харьков, 1996. - 5с. - Библиогр.: 3 назв. - Рус. - Деп.в УкрИНТЭИ 2.12.96, №201- Ук96 - (і).

5. Кравец Н.С., Шабанов-Кушнаренко Ю.П. Методы записи отношений и отображений в виде формул алгебры предикатов// Харьк. гос. техн. ун-т. радиоэлектроники. - Харьков, 1996. - 8с. - Библиогр.: 2 назв. - Рус. - Деп.в УкрИНТЭИ 2.12.96, №198 - Ук96 - (і).

6. Кравец Н. С. Обучающая система моделирования логической структуры систем с помощью алгебры предикатных операций // Образование и виртуальность - 2000.Сборник научных трудов 4-й Международной конференции Украинской ассоциации дистанционного образования. - Харьков-Севастополь: УАДО, 2000. - С196-201.

7. Кравець Н. С. Інтерактивна імітація та аналіз розкрашеної сітки Петрі з використанням алгебри предикатних операцій // Праці п'ятої всеукраїнської міжнародної конференції "Оброблення сигналів і зображень та розпізнавання образів" (УкрОБРАЗ-2000). - Київ. - С. 313-316.

АНОТАЦІЯ

Кравець Н. С. Алгебри предикатних операцій та їх застосування у системах штучного інтелекту. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - математичне моделювання та обчислювальні методи. - Харківський державний технічний університет радіоелектроніки, Харків, 2001.

Дисертація присвячена питанням розробки математичних моделей, методів та інструментальних засобів для формалізації опису і моделювання багатомодульних систем інформаційного обслуговування з розподіленим управлінням за допомогою алгебр предикатних операцій, сіток Петрі та технологій штучного інтелекту. У роботі запропоновано використовувати апарат фундаментальної алгебри предикатних операцій для опису структури і функціонування ординарної сітки Петрі та розфарбованої сітки Петрі. Розроблено метод визначення множини тупікових розміток для розфарбованої сітки Петрі за допомогою апарата фундаментальної алгебри предикатних операцій. Розроблено систему інтерактивної імітації розфарбованої сітки Петрі та аналізу її властивостей з використанням інтелектуальної компоненти.

Результати дисертації впроваджено на Харківському державному приладобудівному заводі ім. Т.Г.Шевченка, у вигляді інструментального засобу моделювання при розробці функціонального програмного забезпечення на цифрові автоматичні телефонні станції.

Ключові слова: багатомодульні системи, системи штучного інтелекту, алгебри предикатних операцій, розфарбовані сітки Петрі, тупікові розмітки, імітаційне моделювання.

АННОТАЦИЯ

Кравец Н. С. Алгебры предикатных операций и их применение в системах искусственного интеллекта. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. - Харьковский государственный технический университет радиоэлектроники, Харьков, 2001.

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

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

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

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

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

Результаты диссертации внедрены на Харьковском государственном приборостроительном заводе им. Т.Г.Шевченко в виде инструментального средства для моделирования при разработке функционального программного обеспечения для цифровых автоматических телефонных станций.

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

ABSTRACT

Kravets N. S. Algebras of predicate operations and their application in the systems of artificial intelligence. - Manuscript.

Dissertation on the competition for the academic degree of candidate of technical sciences on the specialty 01.05.02 - mathematical modeling and computational methods. - Kharkiv State Technical University of radioelectronics, Kharkiv, 2001.

The dissertation deals with the development of mathematical models, methods and software tools to formalize the description and modeling of multi-module systems of information service with distributed control using the algebras of predicate operations, Petri nets, and technologies of artificial intelligence. There was proposed to use the tool of fundamental algebra of predicate operations to describe the structure and functioning of an ordinary Petri net and colored Petri net. There was developed the method to define a deadlock marking set for a colored Petri net by means of the tool of fundamental algebra of predicate operations. There was developed the system to interactively imitate a colored Petri net and to analyze its features using intelligent component.

The dissertation results are implemented in the Kharkiv State T.G. Shevchenko Instrument-making Plant. They are implemented as a modeling software tool for the development of functional software for digital automatic telephone exchange.

Key words: multi-module systems, artificial intelligence systems, algebra of predicate operations, colored Petri nets, deadlock marking, imitative modeling.

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