3.4. Засоби верифікації та аналізу властивостей сіткових моделей

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

Ця послідовність подій має характеристики паралельних процесів, аналіз яких потребує визначення наступних умов:

1) повторна ініціалізація операцій в процесі допустима тільки після завершення попереднього її виконання у системі;

2) використання в дискретній системі ресурсів має кількісне обмеження по застосуванню;

3) у взаємодії частин паралельних процесів не повинно з’являтися блокувань розвитку подій, тупикових станів або зациклювань у виконанні послідовних дій.

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

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

Так структурні елементи сітки повинні інтерпретуватися наступним чином: позиції – це умови виконання або ознаки здійснення дій (операцій) на об’єкті; переходи – це події, що здійснюються на об’єкті у випадку виконання необхідних умов; маркування – це поточний стан об’єкта.

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

При описі процесів сітками Петрі будь-яке маркування сітки асоціюється з визначеним станом моделюємого об’єкта. Спрацьовування будь-якого переходу t_j сітки N пов’язане зі зміною його стану (виконанням елементарної дії у процесі).

Перевірка властивостей сіток може виконуватись шляхом:

1) дослідження структури дерева досяжності;

2) дослідження матричного подання сітки Петрі;

3) редукційного аналізу структури і динаміки роботи сітки Петрі.

3.4.1. Дослідження дерева досяжності

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

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

– внутрішнє маркування, яке є досяжним з початкового маркування та не є тупиковим (рис. 3.15, а);

– тупикове маркування (рис. 3.15, б), з якого не може спрацьовувати ні один перехід;

– дублююче маркування _д (рис. 3.15, в), яке відповідає вже введеному раніше у дерево маркуванню  = _д. Якщо на шляху з початкового маркування до _д зустрічається маркування  = _д, то _д стає маркуванням-циклом або циклічним маркуванням _ц (рис. 3.15, г);

– накопичуюче маркування _н, відповідно якому на шляху від початкового маркування існує інше маркування  таке, що   _н (рис. 3.15, д).

Рис. 3.15 Типи маркувань: а – внутрішнє; б – тупикове; в – дублююче; г – циклічне; д – накопичуюче

Нескінченність дерева можлива тільки у випадку існування накопичуючих маркувань, які породжують циклічне повторення однакових послідовностей спрацьовуючих переходів.

Для того щоб побудувати скінченне дерево досяжності і подати процес нескінченного накопичування маркерів у позиціях сітки, вводиться позначення у вигляді символу w, який має наступні властивості:

w + a = w; w – a = w; a < w.

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

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

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

Нові кінцеві маркування   визначаються за результатами спрацьовування збуджених у  переходів за наступними правилами:

– якщо (p_i) = w, то  (p_i) = w;

– якщо на шляху з початкового маркування до   існує таке маркування  , що   <    і  (p_i) <  (p_i), то  (p_i) = w;

– у протилежному випадку  (p_і) зберігає своє значення, отримане внаслідок спрацьовування переходу.

3. Коли всі вершини будуть оброблені, алгоритм завершується.

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

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

– в позначеннях дуг дерева використані усі переходи сітки;

– немає вершин дерева, що позначають як тупикові або накопичуючі маркування;

– шляхи, що ведуть до вершин – циклічних маркувань, мають хоча б одне розгалуження, яке спрямоване до початкового маркування;

– існує хоча б один шлях повернення у вершину початкового маркування.

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

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

Теоретико-множинне визначення сітки:

P = {p₁, p₂, p₃, p₄);

T = {t₁, t₂, t₃);

F(p_i, t₁) = 1 для і = 1, 2, 3;

F(p₄, t₁) = 0, F(p₄, t₂) = 1, F(p_i, t₂) = 0 для і = 1, 2, 3;

F(p₃, t₃) = 1, F(p_i, t₃) = 0 для і = 1, 2, 4;

H(t₁, p₁) = 1, H(t₁, p_i) = 0 для і = 2, 3, 4;

H(t₂, p_i) = 1 для і = 2, 3; H(t₂, p_i) = 0 для і = 1, 4;

H(t₃, p₄) = 1, H(t₃, p_i) = 0 для і = 1, 2, 3;

₀(p₁) = ₀(p₃) = 1; ₀(p₂) = ₀(p₄) = 0.

Множини вхідних позицій переходів:

^t₁ = {p₁, p₂, p₃}; ^t₂ = {p₄}; ^t₃ = {p₃}.

Множини вихідних позицій переходів:

t₁^ = {p₁}; t₂^ = {p₂, p₃}; t₃^ = {p₄}.

Рис. 3.16. Сітка Петрі з накопиченням маркерів

Матричне подання:

Позиції p₁, p₃, p₄ – безпечні, а позиція p₂ – необмежена. Тому сітка в цілому необмежена і незберігаюча.

Переходи спрацьовують усі, але є тупикове маркування ₃, циклічне повторення маркувань ₂  ₄  ₅ та початкове маркування недосяжне з будь-якого іншого у дереві. Тому сітка нежива.

Рис. 3.17. Кінцеве дерево досяжності