Моделирование мультиагентных систем с помощью обобщенных сетей активных ресурсов
Розглянуто проблему моделювання мультиагентних систем з нескінченною множиною станiв. Дослiджено формалiзми, що ґрунтуються на узагальненнi мереж активних ресурсiв. Визначено новi способи моделювання: параметризованi АР-мережi, дворiвневi АР-схеми та дворiвневi АР-мережi. Показано, що цi формалiзми...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2011 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84183 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Моделирование мультиагентных систем с помощью обобщенных сетей активных ресурсов / В.А. Башкин, И.А. Ломазова // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — С. 31-39. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859749870446837760 |
|---|---|
| author | Башкин, В.А. Ломазова, И.А. |
| author_facet | Башкин, В.А. Ломазова, И.А. |
| citation_txt | Моделирование мультиагентных систем с помощью обобщенных сетей активных ресурсов / В.А. Башкин, И.А. Ломазова // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — С. 31-39. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто проблему моделювання мультиагентних систем з нескінченною множиною станiв. Дослiджено формалiзми, що ґрунтуються на узагальненнi мереж активних ресурсiв. Визначено новi способи моделювання: параметризованi АР-мережi, дворiвневi АР-схеми та дворiвневi АР-мережi. Показано, що цi формалiзми мають зручний синтаксис для моделювання мультиагентних систем, а також систем зi складною модульною або iєрархiчною структурою. Доведено, що параметризованi АР-мережi та дворiвневi АР-схеми еквiвалентнi мережам Петрi, дворiвневi АР-системи еквiвалентнi вкладеним мережам Петрi.
The problem of modeling infinite-state multiagent systems is considered. Formalisms based on the generalization of nets of active resources are studied. New modeling techniques are defined: parameterized AR-nets, two-level AR-schemes, and two-level AR-nets. It is shown that the syntax of these formalisms is convenient for modeling multiagent systems such as systems with complex modular or hierarchical structure. It is proved that parameterized AR-nets and two-level AR-schemes are equivalent to Petri nets, while two-level AR-systems are equivalent to nested Petri nets.
|
| first_indexed | 2025-12-01T23:35:19Z |
| format | Article |
| fulltext |
ÓÄÊ 519.711
Â.À. ÁÀØÊÈÍ, È.À. ËÎÌÀÇÎÂÀ
ÌÎÄÅËÈÐÎÂÀÍÈÅ ÌÓËÜÒÈÀÃÅÍÒÍÛÕ ÑÈÑÒÅÌ
Ñ ÏÎÌÎÙÜÞ ÎÁÎÁÙÅÍÍÛÕ ÑÅÒÅÉ ÀÊÒÈÂÍÛÕ ÐÅÑÓÐÑÎÂ1
Êëþ÷åâûå ñëîâà: ìîäåëèðîâàíèå, âåðèôèêàöèÿ, ìóëüòèàãåíòíûå ñèñòåìû,
ñåòè Ïåòðè.
ÂÂÅÄÅÍÈÅ
Îäíèì èç íàèáîëåå ðàñïðîñòðàíåííûõ ñïîñîáîâ ìîäåëèðîâàíèÿ ñëîæíûõ ðàñ-
ïðåäåëåííûõ ñèñòåì ÿâëÿþòñÿ ñåòè Ïåòðè. Ýòî äîñòàòî÷íî âûðàçèòåëüíàÿ ìî-
äåëü ïàðàëëåëèçìà, îáëàäàþùàÿ â òî æå âðåìÿ çíà÷èòåëüíûì íàáîðîì ðàçðå-
øèìûõ ñâîéñòâ.  ÷àñòíîñòè, äëÿ îáûêíîâåííûõ ñåòåé Ïåòðè ðàçðåøèìû ïðî-
áëåìû äîñòèæèìîñòè, îñòàíîâà, æèâîñòè, îãðàíè÷åííîñòè, ïîêðûòèÿ. Åùå
îäíîé ïðè÷èíîé ïîïóëÿðíîñòè ñåòåé Ïåòðè ÿâëÿåòñÿ ïðîñòîòà è íàãëÿäíîñòü
îïèñàíèÿ ïàðàëëåëèçìà, à òàêæå óäîáíîå ãðàôè÷åñêîå ïðåäñòàâëåíèå ìîäåëè.
Îäíàêî ñèíòàêñèñ ñåòåé Ïåòðè äîñòàòî÷íî ñòàòè÷åí è íå âñåãäà ïðèãîäåí
äëÿ ìîäåëèðîâàíèÿ ñëîæíûõ ìóëüòèàãåíòíûõ ñèñòåì, ïîýòîìó ðàçðàáàòûâàþòñÿ
ôîðìàëèçìû, â êîòîðûõ òåì èëè èíûì ñïîñîáîì áîëåå ÿâíî âûäåëÿåòñÿ ïîíÿòèå
àãåíòà [1–3].
 ðàáîòå [4] ïðåäñòàâëåí íîâûé ñïîñîá ìîäåëèðîâàíèÿ ðàñïðåäåëåííûõ ñèñ-
òåì — ñåòè àêòèâíûõ ðåñóðñîâ (ÀÐ-ñåòè). Äàííûé ôîðìàëèçì îáëàäàåò òîé æå
âûðàçèòåëüíîé ìîùíîñòüþ, ÷òî è îáûêíîâåííûå ñåòè Ïåòðè, îäíàêî â íåì èñ-
ïîëüçóåòñÿ èíîé ïðèíöèï ìîäåëèðîâàíèÿ: âìåñòî ðàçäåëåíèÿ êîìïîíåíòîâ ìîäå-
ëè (âåðøèí ãðàôà) íà àãåíòû è ðåñóðñû (ïåðåõîäû è ïîçèöèè) ââîäèòñÿ ðàçäåëå-
íèå ñïîñîáîâ âçàèìîäåéñòâèÿ (äóã ãðàôà) íà ïðîèçâîäñòâî è ïîòðåáëåíèå. Òàêîé
ïîäõîä ïîçâîëÿåò ïîëó÷èòü ìîäåëü, â êîòîðîé áîëåå ÿâíî âûäåëåíû íå òèïû
êîìïîíåíòîâ ñèñòåìû, à ñïîñîáû èõ âçàèìîäåéñòâèÿ ìåæäó ñîáîé.  ðÿäå ñëó÷à-
åâ ýòî ïîçâîëÿåò áîëåå êîìïàêòíî è íàãëÿäíî ôîðìàëèçîâàòü ñåìàíòè÷åñêèå
ñâîéñòâà ìóëüòèàãåíòíûõ ñèñòåì ñî ñëîæíûì ïîâåäåíèåì àãåíòîâ.
 äàííîé ðàáîòå ðàññìàòðèâàþòñÿ âîçìîæíîñòè îáîáùåíèÿ ôîðìàëèçìà ÀÐ-ñå-
òåé. Èñïîëüçóåòñÿ ïîíÿòèå ìåòàñòðóêòóð — ôîðìàëüíîãî ñïîñîáà îïèñàíèÿ íîâûõ
êëàññîâ îáîáùåííûõ ÀÐ-ñåòåé. Ìåòàñòðóêòóðà çàäàåò íàáîð ñïîñîáîâ âçàèìîäåéñò-
âèÿ àêòèâíûõ ðåñóðñîâ (âèäîâ/öâåòîâ äóã) è ïðàâèëî ñðàáàòûâàíèÿ îòäåëüíîãî óçëà
(âåðøèíû ñåòè). Òàêèì îáðàçîì, ìåòàñòðóêòóðû ìîæíî ðàññìàòðèâàòü êàê ñïîñîá
îïèñàíèÿ íîâûõ èíñòðóìåíòîâ ìîäåëèðîâàíèÿ (îáîáùåíèé ÀÐ-ñåòåé).
 òåðìèíàõ ìåòàñòðóêòóð îïðåäåëÿþòñÿ íîâûå ôîðìàëèçìû — ïàðàìåòðèçî-
âàííûå ÀÐ-ñåòè, äâóõóðîâíåâûå ÀÐ-ñõåìû è äâóõóðîâíåâûå ÀÐ-ñåòè. Â ïàðàìåò-
ðèçîâàííûõ ÀÐ-ñåòÿõ ââîäÿòñÿ âûðàæåíèÿ íà äóãàõ (àíàëîã âûñîêîóðîâíåâûõ ñå-
òåé Ïåòðè [5]), ÷òî ïîçâîëÿåò ñóùåñòâåííî óïðîñòèòü ãðàôè÷åñêîå ïðåäñòàâëåíèå
ïëîñêèõ ñèñòåì ñ áîëüøèì êîëè÷åñòâîì îäíîòèïíûõ àãåíòîâ. Âëîæåííûå
ÀÐ-ñåòè ñî÷åòàþò â ñåáå êëþ÷åâûå ñâîéñòâà äâóõ ôîðìàëèçìîâ: ïðîñòîòó ñèí-
òàêñèñà ÀÐ-ñåòåé è êîìïîçèöèîíàëüíîñòü âëîæåííûõ ñåòåé Ïåòðè [3]. Ýòî ïîçâî-
ëÿåò óäîáíî ìîäåëèðîâàòü äîñòàòî÷íî ñëîæíûå ìóëüòèàãåíòíûå ñèñòåìû ñ ìî-
äóëüíîé è èåðàðõè÷åñêîé ñòðóêòóðîé.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2 31
1 Ðàáîòà âûïîëíåíà ïðè ïîääåðæêå ÐÔÔÈ (09-01-00277) è ÔÀÍÈ (02.740.11.0207).
© Â.À. Áàøêèí, È.À. Ëîìàçîâà, 2011
 êà÷åñòâå ìîäåëüíîãî ïðèìåðà ðàññìàòðèâàåòñÿ êëàññè÷åñêàÿ «ïðîáëåìà
îáåäàþùèõ ôèëîñîôîâ» (íàïðèìåð, [5]). Èññëåäóåòñÿ âûðàçèòåëüíàÿ ìîùíîñòü
íîâûõ ôîðìàëèçìîâ.  ÷àñòíîñòè, äîêàçàíî, ÷òî ïàðàìåòðèçîâàííûå ÀÐ-ñåòè
è äâóõóðîâíåâûå ÀÐ-ñõåìû ýêâèâàëåíòíû îáûêíîâåííûì ñåòÿì Ïåòðè, äâóõ-
óðîâíåâûå ÀÐ-ñèñòåìû ýêâèâàëåíòíû âëîæåííûì ñåòÿì Ïåòðè.
ÎÑÍÎÂÍÛÅ ÎÏÐÅÄÅËÅÍÈß
Ïóñòü Nat — ìíîæåñòâî íåîòðèöàòåëüíûõ öåëûõ ÷èñåë, X — íåïóñòîå ìíî-
æåñòâî. Ìóëüòèìíîæåñòâîì M íàä ìíîæåñòâîì X íàçûâàåòñÿ ôóíêöèÿ
M X: � Nat . Ìîùíîñòü ìóëüòèìíîæåñòâà çàïèøåì | | ( )M M x
x X
�
�� . ×èñëà
{ ( ) | }M x x X� íàçûâàþòñÿ êîýôôèöèåíòîì ìóëüòèìíîæåñòâà, êîýôôèöèåíò
M x( ) îïðåäåëÿåò ÷èñëî ýêçåìïëÿðîâ ýëåìåíòà x â M.
Îïåðàöèè è îòíîøåíèÿ òåîðèè ìíîæåñòâ åñòåñòâåííî ðàñøèðÿþòñÿ íà êî-
íå÷íûå ìóëüòèìíîæåñòâà. Îïðåäåëèì òàêæå äîïîëíèòåëüíûå îïåðàöèè —
ñëîæåíèå è âû÷èòàíèå ìóëüòèìíîæåñòâ. Ïóñòü M1, M2 — êîíå÷íûå ìóëüòè-
ìíîæåñòâà íàä X . Ïîëàãàåì � �x X ( )( ) ( ) ( )M M x M x M x1 2 1 2� � �def ;
( )( ) ( ) � ( )M M x M x M x1 2 1 2� � �def (ãäå �� — óñå÷åííîå âû÷èòàíèå).
Ñåòüþ Ïåòðè íàçûâàåòñÿ íàáîð N P T F� ( , , ), ãäå P — êîíå÷íîå ìíîæåñòâî
ïîçèöèé; T — êîíå÷íîå ìíîæåñòâî ïåðåõîäîâ, P T �
; F P T: ( )� �
� � �( )T P Nat— ôóíêöèÿ èíöèäåíòíîñòè (êîíå÷íîå ìíîæåñòâî äóã).
Ðàçìåòêîé (ñîñòîÿíèåì) ñåòè N íàçûâàåòñÿ ôóíêöèÿ M P: � Nat , ñîïîñòàâ-
ëÿþùàÿ êàæäîé ïîçèöèè ñåòè íåêîòîðîå íàòóðàëüíîå ÷èñëî (èëè íîëü). Ðàçìåòêà
ìîæåò ðàññìàòðèâàòüñÿ êàê ìóëüòèìíîæåñòâî íàä ìíîæåñòâîì ïîçèöèé ñåòè.
Ãðàôè÷åñêè ñåòü Ïåòðè èçîáðàæàåòñÿ êàê äâóäîëüíûé îðèåíòèðîâàííûé
ãðàô. Âåðøèíû-ïîçèöèè èçîáðàæàþòñÿ êðóæêàìè è õàðàêòåðèçóþò ëîêàëüíûå
ñîñòîÿíèÿ ñåòè, âåðøèíû-ïåðåõîäû — ïðÿìîóãîëüíèêàìè è ñîîòâåòñòâóþò äåé-
ñòâèÿì. Äóãè ñîîòâåòñòâóþò ýëåìåíòàì F. Ïîçèöèè ìîãóò ñîäåðæàòü ìàðêåðû
(ôèøêè), èçîáðàæàåìûå ÷åðíûìè òî÷êàìè. Ïðè ðàçìåòêå M â êàæäóþ ïîçèöèþ p
ïîìåùàåòñÿ M p( ) ôèøåê.
Ïåðåõîä t T� àêòèâåí ïðè ðàçìåòêå M, åñëè � �p P M p F p t( ) ( , )
(âñå âõîä-
íûå ïîçèöèè ñîäåðæàò äîñòàòî÷íîå êîëè÷åñòâî ôèøåê).
Àêòèâíûé ïðè ðàçìåòêå M ïåðåõîä t ìîæåò ñðàáîòàòü, ïîðîæäàÿ ïðè ýòîì
íîâóþ ðàçìåòêó �M , ãäå � �p P � � � �M p M p F p t F t p( ) ( ) ( , ) ( , )def .
Ðàññìîòðèì â êà÷åñòâå
ïðèìåðà «ïðîáëåìó îáåäàþ-
ùèõ ôèëîñîôîâ» (ðèñ. 1),
êîòîðàÿ ïîëó÷èëà ñòàòóñ
êëàññè÷åñêîé è óïîìèíàåòñÿ
â ðàçíûõ âàðèàíòàõ âî ìíî-
ãèõ ó÷åáíèêàõ. Ýòî îáúÿñíÿ-
åòñÿ òåì, ÷òî â íåé ïðè êà-
æóùåéñÿ ïðîñòîòå èìåþòñÿ
âñå ýëåìåíòû ðàñïðåäåëåí-
íûõ ñèñòåì: âûáîð, êîí-
ôëèêò, ðàñïàðàëëåëèâàíèå
è ñèíõðîíèçàöèÿ. Ôèëîñîôû
(â äàííîì ñëó÷àå èõ ÷åòâåðî)
ñèäÿò çà ñòîëîì, ïîñåðåäèíå
îáùåå áëþäî — ñïàãåòòè
(dish). Ìåæäó êàæäûìè
äâóìÿ ôèëîñîôàìè íà ñàë-
32 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2
put3
thinking3
fork2
fork3
take3
eating3
eat3take2
thinking2
put2
eating2
eat2 dish
eat4
eating4
take4
put4
thinking4
fork4
eat1
eating1
put1
thinking1
take1
fork1
Ðèñ. 1. Ñåòü Ïåòðè (÷åòûðå îáåäàþùèõ ôèëîñîôà)
ôåòêå ëåæèò âèëêà (fork).
Åñòü ñïàãåòòè ìîæíî òîëüêî
îäíîâðåìåííî äâóìÿ âèëêà-
ìè, ïîýòîìó ñîñåäè ïîòåíöè-
àëüíî êîíêóðèðóþò. Êàæäûé
ôèëîñîô ìîæåò íàõîäèòüñÿ â
îäíîì èç äâóõ ñîñòîÿíèé: îí
ëèáî äóìàåò (thinking), ëèáî
åñò (eating). Ïåðåõîäû ìåæäó
ñîñòîÿíèÿìè — take (âçÿë
îáå âèëêè) è put (âåðíóë íà
ìåñòî). Â ñîñòîÿíèè eating îí
òàêæå ìîæåò âûïîëíèòü äå-
éñòâèå eat (âçÿòü ñïàãåòòè).
Ñåòüþ àêòèâíûõ ðåñóð-
ñîâ [4] íàçîâåì íàáîð
AR V I O� ( , , ), ãäå V — êî-
íå÷íîå ìíîæåñòâî âåðøèí;
I V V: ( )� � Nat — ìíîæåñò-
âî ïîòðåáëÿþùèõ äóã; O V V: ( )� � Nat— ìíîæåñòâî ïðîèçâîäÿùèõ äóã.
Ãðàôè÷åñêè âåðøèíû ñåòè èçîáðàæàþòñÿ êðóæêàìè, ïîòðåáëÿþùèå äóãè —
ïóíêòèðíûìè ñòðåëêàìè, ïðîèçâîäÿùèå äóãè — íåïðåðûâíûìè ñòðåëêàìè (ðèñ. 2).
Ðàçìåòêîé ñåòè AR íàçûâàåòñÿ ôóíêöèÿ âèäà M V: � Nat .
Ðåñóðñ (àãåíò) â âåðøèíå ��V àêòèâåí ïðè ðàçìåòêå M, åñëè M( )� � 0 (óçåë �
íåïóñòîé) è � �w V M w I w( ) ( , )
� (â ïîòðåáëÿåìûõ óçëàõ ñîäåðæèòñÿ äîñòàòî÷íîå
êîëè÷åñòâî ôèøåê). Àêòèâíûé ïðè ðàçìåòêå M ðåñóðñ � ìîæåò ñðàáîòàòü, ïîðîæäàÿ
ïðè ýòîì íîâóþ ðàçìåòêó �M , ãäå � �w V � � � �M w M w I w O w( ) ( ) ( , ) ( , )def � � .
Òàêèì îáðàçîì, â ñðàáàòûâàíèè ðåñóðñà ó÷àñòâóþò åãî âõîäíûå è âûõîäíûå
äóãè, â òðàíñôîðìàöèè ðåñóðñà (èçìåíåíèè ðàçìåòêè ñîîòâåòñòâóþùåé âåðøè-
íû) — ïîòðåáëÿþùèå è ïðîèçâîäÿùèå åãî äóãè.
Ïðèìåð òðèâèàëüíîãî âàðèàíòà ìîäåëèðîâàíèÿ ïðèâåäåí íà ðèñ. 2. Â äàí-
íîì ñëó÷àå ïîçèöèè è ïåðåõîäû ñåòè Ïåòðè ïðîñòî çàìåíèëè íà ñîîòâåòñòâóþ-
ùèå óçëû ÀÐ-ñåòè. Îäíàêî ñèíòàêñèñ ÀÐ-ñåòåé ïðåäîñòàâëÿåò è íåêîòîðûå íî-
âûå âîçìîæíîñòè. Íàïðèìåð, ïîâåäåíèå îòäåëüíîãî ôèëîñîôà ìîæåò áûòü ïðî-
ìîäåëèðîâàíî åùå äâóìÿ ñïîñîáàìè (ðèñ. 3).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2 33
thinking1
eating1
eat1
take1
put1
fork1 fork4
fork2 fork3
disheat2
eat3
eat4
eating2
eating3
eating4
take2
take3
take4
put2
put3
put4
thinking2
thinking3
thinking4
Ðèñ. 2. ÀÐ-ñåòü (÷åòûðå îáåäàþùèõ ôèëîñîôà)
Ðèñ. 3. Âàðèàíòû ìîäåëèðîâàíèÿ ïîâåäåíèÿ îòäåëüíîãî ôèëîñîôà: íåñàìîñòîÿòåëüíàÿ ñìåíà ñî-
ñòîÿíèÿ àãåíòà (ôèëîñîôà), ñàìîñòîÿòåëüíîå ïîòðåáëåíèå ðåñóðñà (ñïàãåòòè) (à); ñàìîñòîÿòåëüíàÿ
ñìåíà ñîñòîÿíèÿ, íåñàìîñòîÿòåëüíîå ïîòðåáëåíèå (á)
à á
Ñåòè àêòèâíûõ ðåñóðñîâ ïî âûðàçèòåëüíîé ìîùíîñòè ñîâïàäàþò ñ ñåòÿìè
Ïåòðè [4], íî ïðè ýòîì â íèõ äîáàâëÿåòñÿ âîçìîæíîñòü «äâîéíîãî» èñïîëüçîâà-
íèÿ ðåñóðñà (ôèøêè): íå òîëüêî â êà÷åñòâå ïàññèâíîãî ðåñóðñà, íî è â êà÷åñòâå
àêòèâíîãî àãåíòà. Ýòî ÷èñòî ñèíòàêñè÷åñêîå ðàñøèðåíèå ïîëåçíî íà ïðàêòèêå
ïðè ìîäåëèðîâàíèè ñèñòåì ñ äèíàìè÷åñêîé ñòðóêòóðîé (íàïðèìåð, ñåòåé âåá-
ñåðâèñîâ).  íàñòîÿùåå âðåìÿ èçó÷åí ðÿä ñïîñîáîâ ïîâûøåíèÿ âûðàçèòåëüíîñòè
è óäîáñòâà ìîäåëèðîâàíèÿ ñåòÿìè àêòèâíûõ ðåñóðñîâ.  ÷àñòíîñòè, ïðåäëîæåí
ðÿä åñòåñòâåííûõ ðàñøèðåíèé ÀÐ-ñåòåé äî óíèâåðñàëüíûõ ñèñòåì, à òàêæå óïðî-
ùåíèé èõ ñèíòàêñèñà áåç ïîòåðè âûðàçèòåëüíîñòè [6].
ÎÁÎÁÙÅÍÍÛÅ ÀÐ-ÑÅÒÈ
Îäíî èç îñíîâíûõ îòëè÷èé ÀÐ-ñåòåé îò ñåòåé Ïåòðè — áîëåå íàãëÿäíîå ðàç-
ãðàíè÷åíèå ôóíêöèé äóã (ïîòðåáëåíèå è ïðîèçâîäñòâî). Ôàêòè÷åñêè äóãè â ñå-
òÿõ Ïåòðè òàêæå ðàñïàäàþòñÿ íà äâà êëàññà (â ñèëó äâóäîëüíîñòè ãðàôà),
îäíàêî â ÀÐ-ñåòÿõ òèïû äóã ïîëó÷èëè ñîáñòâåííûå îáîçíà÷åíèÿ. Òàêîé ÷èñòî
ñèíòàêñè÷åñêèé ïðèåì òàêæå ïîçâîëèë èçáàâèòüñÿ îò ðàçäåëåíèÿ âåðøèí íà
ïîçèöèè è ïåðåõîäû, ÷òî ñóùåñòâåííî èçìåíèëî âîçìîæíîñòè ìîäåëèðîâàíèÿ.
Ðàññìîòðèì äàëüíåéøåå åñòåñòâåííîå îáîáùåíèå ñèíòàêñèñà ÀÐ-ñåòåé, ïî-
ëó÷åííîå ââåäåíèåì ïðîèçâîëüíûõ òèïîâ äóã.
Ìåòàñòðóêòóðîé íàçîâåì íàáîð � � �� ( , ), ãäå � � � �{ , , }1 � k — êîíå÷íîå
ìíîæåñòâî òèïîâ äóã, � — îãðàíè÷åíèÿ íà ñòðóêòóðó ãðàôà è ïðàâèëà ñðàáàòû-
âàíèÿ óçëà.
Îáîáùåííîé ÀÐ-ñåòüþ ìåòàñòðóêòóðû � (ñîêðàùåííî �-ñåòüþ) íàçîâåì íà-
áîð G V R� ( , ), ãäå V — êîíå÷íîå ìíîæåñòâî âåðøèí, R V V: ( )� � �� Nat —
ìíîæåñòâî êðàòíûõ äóã, ïîìå÷åííûõ òèïàìè èç �.
 äàííîì îïðåäåëåíèè íå óêàçàí êîíêðåòíûé ñïîñîá çàäàíèÿ ïðàâèëà ñðàáà-
òûâàíèÿ óçëà. Äëÿ èçâåñòíûõ òèïîâ äóã (ïðîèçâîäÿùèõ, ïîòðåáëÿþùèõ, èíãèáè-
òîðíûõ, îáíóëÿþùèõ è ò.ä.) ïðàâèëà ìîãóò îïèñûâàòüñÿ â ñòàíäàðòíîé òåðìèíî-
ëîãèè ñåòåé Ïåòðè, îäíàêî âîçìîæíû è äðóãèå ñïîñîáû.
ÏÀÐÀÌÅÒÐÈÇÎÂÀÍÍÛÅ («ÂÛÑÎÊÎÓÐÎÂÍÅÂÛÅ») ÀÐ-ÑÅÒÈ
Ðàññìîòðèì îáîáùåíèå, ïðè êîòîðîì òèï äóãè îïðåäåëÿåòñÿ ïðèïèñàííûì åé
ïàðàìåòðè÷åñêèì âûðàæåíèåì. Ïîõîæèé ïðèåì èñïîëüçóåòñÿ ïðè îïðåäåëåíèè
òàê íàçûâàåìûõ «âûñîêîóðîâíåâûõ ñåòåé Ïåòðè» (íàïðèìåð, [5]).
Ïóñòü Const — êîíå÷íîå ìíîæåñòâî êîíñòàíò, Var — êîíå÷íîå ìíîæåñòâî
ïåðåìåííûõ, Func — êîíå÷íîå ìíîæåñòâî âñþäó îïðåäåëåííûõ ôóíêöèé èç
Const â Const. Ðàññìîòðèì ïðîñòîé ÿçûê L, îïðåäåëÿåìûé ñëåäóþùèì îáðàçîì:
1) Const � L, Var � L;
2) åñëè �� Var è f � Funñ, òî f L( )� � ;
3) åñëè E L1 � è E L2 � , òî E E L1 2� � .
Òàêèì îáðàçîì, âûðàæåíèÿ ïîñòðîåíû ñ ïîìîùüþ îïåðàöèè ñëîæåíèÿ èç
êîíñòàíò, ïåðåìåííûõ è âûçîâîâ ôóíêöèé îò ïåðåìåííûõ.
Îçíà÷èâàíèå b : Var Const� ñîïîñòàâëÿåò âñåì ïåðåìåííûì êîíêðåòíûå
çíà÷åíèÿ êîíñòàíò. Çàìåòèì, ÷òî ïðè ýòîì ìîãóò áûòü îäíîçíà÷íî âû÷èñëåíû
çíà÷åíèÿ âñåõ ôóíêöèé èç Func. Òàêèì îáðàçîì, âûðàæåíèå E ïðè îçíà÷èâàíèè b
(îáîçíà÷àåòñÿ E b[ ]) îïðåäåëÿåò ìóëüòèìíîæåñòâî êîíñòàíò.
Êîíñòàíòàì â äàííîé ñåòè áóäóò ñîîòâåòñòâîâàòü ðàçëè÷íûå âèäû ôèøåê.
Ïåðåìåííûå è ôóíêöèè áóäóò èãðàòü ðîëü ïàðàìåòðîâ â âûðàæåíèÿõ íà äóãàõ.
Ïóñòü Labels � L — íåêîòîðîå êîíå÷íîå ïîäìíîæåñòâî âûðàæåíèé ÿçûêà L, èñ-
ïîëüçóåìûõ äëÿ îáîçíà÷åíèÿ äóã (äëÿ äóãè � åå ìåòêó îáîçíà÷èì Label( )� ), cons è
prod — îáû÷íûå òèïû äóã ÀÐ-ñåòè — äóãè ïîòðåáëåíèÿ è ïðîèçâîäñòâà ðåñóðñîâ.
34 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2
Ïàðàìåòðèçîâàííîé íàçûâàåòñÿ ìåòàñòðóêòóðà �
par cons prod}� �({ ,
� Labels par, )� , ãäå �
par îïðåäåëÿåò ñëåäóþùåå ïðàâèëî ïîâåäåíèÿ:
1) ôèøêàìè ÿâëÿþòñÿ êîíñòàíòû, ðàçìåòêà îïðåäåëÿåòñÿ êàê M :
( )V � �Const Nat ;
2) ðåñóðñ � àêòèâåí ïðè ðàçìåòêå M è îçíà÷èâàíèè b, åñëè M( )� � 0 (óçåë �
íåïóñòîé) è � �w V , c �Const M w c I w b c( , ) ( ( ( , ))[ ])( )
Label � (â ïîòðåáëÿåìûõ
óçëàõ äîñòàòî÷íî íóæíûõ ôèøåê-êîíñòàíò). Àêòèâíûé ðåñóðñ � ìîæåò ñðàáî-
òàòü, ïîðîæäàÿ ðàçìåòêó �M , ãäå � �w V , c �Const èìååì � � �M w c M w c( , ) ( , )def
� �( ( ( , ))[ ])( ) ( ( ( , ))[ ])( )Label LabelI w b c O w b c� � ;
3) åñëè ïðè äàííîé ðàçìåòêå âîçìîæío íåñêîëüêî îçíà÷èâàíèé ñ àêòèâíûìè
ðåñóðñàìè, òî âûáîð êîíêðåòíîãî îçíà÷èâàíèÿ íåäåòåðìèíèðîâàí.
Ïàðàìåòðèçîâàííûå ñåòè ïðåäîñòàâëÿþò íîâûå âîçìîæíîñòè êîìïàêòíîãî
ìîäåëèðîâàíèÿ ñèñòåì ñ áîëüøèì êîëè÷åñòâîì îäíîòèïíûõ àãåíòîâ. Ïðèìåð
ïðèâåäåí íà ðèñ. 4, ãäå Const ph ph ph ph f f f f� �{ , , , , , , , , }1 2 3 4 1 2 3 4 , Var � { }x ,
Func � { , }l r , l r( ) ( )ph ph f1 2 1� � , l r( ) ( )ph ph f2 3 2� � , l r( ) ( )ph ph f3 4 3� � ,
l( )ph4 �r( )ph f1 4� . Çäåñü ïàðàìåòðèçà-
öèÿ ñóùåñòâåííî óìåíüøèëà ðàçìåð ãðà-
ôè÷åñêîé ìîäåëè.
Òåîðåìà 1. Êëàññ ïàðàìåòðèçîâàí-
íûõ ÀÐ-ñåòåé ïî âûðàçèòåëüíîé ìîùíîñ-
òè ñîâïàäàåò ñ êëàññîì îáûêíîâåííûõ
ñåòåé Ïåòðè.
Äîêàçàòåëüñòâî. Îáûêíîâåííûå
ñåòè Ïåòðè ýêâèâàëåíòíû îáûêíîâåííûì
ÀÐ-ñåòÿì [4], êîòîðûå ÿâëÿþòñÿ ÷àñòíûì
ñëó÷àåì ïàðàìåòðèçîâàííûõ (ïðè
Const � �{ }). Ñëåäîâàòåëüíî, êëàññ ñåòåé
Ïåòðè âêëàäûâàåòñÿ â êëàññ ïàðàìåòðè-
çîâàííûõ ÀÐ-ñåòåé.
Äëÿ äîêàçàòåëüñòâà îáðàòíîãî âëîæå-
íèÿ äîñòàòî÷íî ïîêàçàòü, ÷òî ëþáàÿ ïàðà-
ìåòðèçîâàííàÿ ÀÐ-ñåòü ìîæåò áûòü ïðå-
îáðàçîâàíà â ýêâèâàëåíòíóþ îáûêíîâåí-
íóþ ÀÐ-ñåòü (ñåòü Ïåòðè). Ðàññìîòðèì
ñëåäóþùåå ïðåîáðàçîâàíèå: çàìåíèì â
èñõîäíîé ñåòè êàæäóþ âåðøèíó íà êîíå÷-
íîå ìíîæåñòâî âåðøèí, êàæäàÿ èç êîòîðûõ ñîîòâåòñòâóåò êîíêðåòíîé êîíñòàíòå.
Çàòåì äîïîëíèòåëüíî ðàçìíîæèì êàæäóþ èç ïîëó÷åííûõ âåðøèí ïî ÷èñëó äîïóñ-
òèìûõ îçíà÷èâàíèé ïåðåìåííûõ (ýòî ÷èñëî òàêæå êîíå÷íî â ñèëó êîíå÷íîñòè ìíî-
æåñòâ Const, Var è Func). Çàòåì î÷åâèäíûì îáðàçîì ñîåäèíèì âåðøèíû äóãàìè,
èìèòèðóÿ ïðåîáðàçîâàíèÿ ðàçìåòêè ïðè ñîîòâåòñòâóþùèõ îçíà÷èâàíèÿõ. �
ÄÂÓÕÓÐÎÂÍÅÂÛÅ ÀÐ-ÑÕÅÌÛ
Äëÿ ìîäåëèðîâàíèÿ ñëîæíûõ èåðàðõè÷åñêèõ ñèñòåì èñïîëüçóþòñÿ ðàçëè÷íûå
âèäû âëîæåííûõ ñåòåé Ïåòðè, â êîòîðûõ ôèøêè ñàìè ìîãóò áûòü ñåòÿìè [3].
Ïðè ýòîì äëÿ ñèíõðîíèçàöèè óðîâíåé (ñëîåâ) èñïîëüçóþòñÿ èëè ïåðåõîäû
ñèíõðîíèçàöèè (ñðàáàòûâàþùèå òîëüêî îäíîâðåìåííî íà äâóõ ñîñåäíèõ óðîâ-
íÿõ), èëè îõðàííûå ôóíêöèè íà ïåðåõîäàõ âåðõíåãî ñëîÿ, ïîëó÷àþùèå â êà-
÷åñòâå ïàðàìåòðîâ «çíà÷åíèÿ» èñïîëüçóåìûõ âëîæåííûõ ôèøåê. Çàìåòèì, ÷òî
â îáîèõ ñëó÷àÿõ îäíèì èç èíèöèàòîðîâ ñîáûòèÿ ñèíõðîíèçàöèè ÿâëÿåòñÿ âåðõ-
íèé ñëîé ìîäåëè — èìåííî òàì ñðàáàòûâàåò ïåðåõîä.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2 35
f1
l(x)+r(x)
forks
thinking
dish
eating
take put
x
xx
x
l(x)+r(x)f2f1
f4f3
ph2ph1
ph4ph3
Ðèñ. 4. Ïàðàìåòðèçîâàííàÿ ÀÐ-ñåòü
Ðàññìîòðèì íîâûé ñïîñîá ìîäåëèðîâàíèÿ èåðàðõè÷åñêèõ ñèñòåì, ïðè êîòî-
ðîì ñèíõðîíèçàöèÿ íèæíåãî è âåðõíåãî (âíóòðåííåãî è âíåøíåãî) ñëîåâ ñèñòåìû
îñóùåñòâëÿåòñÿ ñíèçó. Îáúåêòíàÿ ñåòü âçàèìîäåéñòâóåò ñ ñèñòåìíîé ïîñðåä-
ñòâîì ïîòðåáëåíèÿ è ïðîèçâîäñòâà ñèñòåìíûõ ðåñóðñîâ.
 ïðîñòåéøåì ñëó÷àå âíåøíèé óðîâåíü íå îáëàäàåò ñîáñòâåííûì ïîâåäåíè-
åì (ñîáûòèÿìè), à ñëóæèò òîëüêî ñõåìîé âçàèìîäåéñòâèÿ âëîæåííûõ îáúåêòîâ
(õðàíèëèùåì îáùèõ ðåñóðñîâ è «êàðòîé âçàèìîñâÿçåé»).
Ïóñòü Syn — êîíå÷íîå ìíîæåñòâî ïîðòîâ, ãäå cons Syn� , prod Syn� .
Ñõåìíîé íàçûâàåòñÿ ìåòàñòðóêòóðà � �
sch schSyn� ( , ), ãäå �
sch îïðåäåëÿåò
ñëåäóþùåå îãðàíè÷åíèå ñòðóêòóðû ñåòè: ãðàô ÿâëÿåòñÿ äâóäîëüíûì, âñå ìíî-
æåñòâî V ðàñïàäàåòñÿ íà äâà íåïåðåñåêàþùèõñÿ êëàññà — Vres è Vag «ðåñóðñíûõ»
è «àãåíòíûõ» âåðøèí. Â àãåíòíûõ âåðøèíàõ áóäóò íàõîäèòüñÿ îáúåêòû (âëîæåí-
íûå ñåòè), â ðåñóðñíûõ — ñèñòåìíûå ðåñóðñû (îáû÷íûå ôèøêè, íå îáëàäàþùèå
ñîáñòâåííûì ïîâåäåíèåì). Äóãè ìîãóò âåñòè òîëüêî îò àãåíòíûõ óçëîâ ê ðåñóðñ-
íûì (ôàêòè÷åñêè ýòî ðåáðà, ïîêàçûâàþùèå, êàêèå òèïû ðåñóðñîâ ìîãóò
ïîòðåáîâàòüñÿ àãåíòàì äàííîãî òèïà).
Îáúåêòíîé íàçûâàåòñÿ ìåòàñòðóêòóðà � �
o ocons prod Syn� �({ , , }), ãäå �
o
îïðåäåëÿåò ñëåäóþùèå ðàñøèðåííûå ïðàâèëà:
1) äóãè òèïîâ cons è prod ó÷àñòâóþò â ñðàáàòûâàíèè óçëîâ îáû÷íûì îáðà-
çîì ïî ïðàâèëàì ÀÐ-ñåòåé;
2) ïîðò (ýëåìåíò Syn) íå ÿâëÿåòñÿ â ïîëíîì ñìûñëå ñëîâà äóãîé: îí èíöè-
äåíòåí ðîâíî îäíîìó óçëó ñåòè, ò.å. ëèáî â íåãî âõîäèò, ëèáî èç íåãî âûõîäèò;
3) óçåë � îáúåêòíîé ñåòè, íàõîäÿùåéñÿ â àãåíòíîì óçëå W ñèñòåìíîé ñõåìû,
àêòèâåí, åñëè äëÿ ëþáîãî åãî âõîäíîãî ïîðòà êðàòíîñòè k â ñèñòåìíîì ñëîå íàé-
äåòñÿ íàáîð ñîîòâåòñòâóþùèõ (íà÷èíàþùèõñÿ â W) ïîðòîâ òîãî æå òèïà. Ïðè
ýòîì ñóììàðíàÿ ðàçìåòêà ñîîòâåòñòâóþùèõ ñâÿçàííûõ ñ W ðåñóðñíûõ óçëîâ
(ñ ó÷åòîì êðàòíîñòè ñâÿçûâàþùèõ ïîðòîâ) íå ìåíüøå k . Àêòèâíûé óçåë � ìîæåò
ñðàáîòàòü, ïðè ýòîì â ñèñòåìíîé ñõåìå ïîòðåáëÿþòñÿ ðåñóðñû â êîëè÷åñòâå, ñî-
îòâåòñòâóþùåì êðàòíîñòè âõîäÿùèõ â � ïîðòîâ, è ïðîèçâîäÿòñÿ â êîëè÷åñòâå,
ñîîòâåòñòâóþùåì êðàòíîñòè âûõîäÿùèõ èç � ïîðòîâ.
Ðàçìå÷åííîé äâóõóðîâíåâîé ÀÐ-ñõåìîé íàçûâàåòñÿ íàáîð îáîáùåííûõ
ÀÐ-ñåòåé ( , , , )S o on1 � , òàêîé ÷òî:
1) S V R M� (( , ), ) — ðàçìå÷åííàÿ ñèñòåìíàÿ ñõåìà, ãäå ( , )V R — �
sch -ñõåìà,
M V V o on: ( , ({ , , } ))res agNat Nat� � �1 � — íà÷àëüíàÿ ðàçìåòêà;
2) o r mi i i i� (( , ), )� — ðàçìå÷åííàÿ îáúåêòíàÿ ñåòü, ãäå ( , )� i ir — � i
o-ñåòü,
mi i: � � Nat — íà÷àëüíàÿ ðàçìåòêà îáúåêòà.
 îòëè÷èå îò ñåòåé Ïåòðè ñèíòàêñèñ äâóõóðîâíåâûõ ñõåì îáëàäàåò ýëåìåíòàìè
ìîäóëüíîñòè. Ðàññìîòðèì ïðèìåð ìîäåëèðîâàíèÿ (ðèñ. 5). Çäåñü ñèñòåìíàÿ ñõåìà
çàäàåò îáùóþ «êàðòó» îáåäåííîãî ñòîëà. Êàæäûé ôèëîñîô ìîæåò äîòÿíóòüñÿ: ëåâîé
ðóêîé — äî ëåâîé ñàëôåòêè, ïðàâîé ðóêîé — äî ïðàâîé ñàëôåòêè, âèëêàìè — äî
áëþäà. Ñîîòâåòñòâóþùèå òèïû ïîðòîâ îáîçíà÷åíû êàðòèíêàìè «ëåâàÿ ðóêà», «ïðà-
âàÿ ðóêà» è «âèëêà». Íà÷àëüíàÿ ðàçìåòêà ñõåìû ñîñòîèò èç ôèëîñîôîâ íà âñåõ
ñòóëüÿõ, âèëîê íà âñåõ ñàëôåòêàõ è íåêîòîðîãî êîëè÷åñòâà ñïàãåòòè íà áëþäå.
Îáúåêòíàÿ ñåòü çàäàåò ïîâåäåíèå îäíîãî ôèëîñîôà. Âëîæåííîñòü ïîçâîëÿåò
íàì åùå áîëüøå óñëîæíèòü ìîäåëü, ðàçáèâ äåéñòâèÿ «âçÿòü âèëêè» è «ïîëîæèòü
âèëêè» íà íàáîðû èç äâóõ íåçàâèñèìûõ äåéñòâèé («âçÿòü/ïîëîæèòü ëåâóþ/ïðà-
âóþ âèëêó»). Òåïåðü ôèëîñîô — àâòîìàò ñ ÷åòûðüìÿ ñîñòîÿíèÿìè. Óçëû, ñîîòâåò-
ñòâóþùèå ïåðåõîäàì àâòîìàòà (äëÿ íàãëÿäíîñòè ïîìå÷åíû ñåðûì), ñèíõðîíèçè-
ðîâàíû ñ îòíîøåíèÿìè â ñèñòåìíîé ñõåìå. Íàïðèìåð, ïðè ïåðåõîäå èç RFork
â Thinking ïðàâàÿ ðóêà ôèëîñîôà âîçâðàùàåò âèëêó (íà ïðàâóþ ñàëôåòêó), ïðè
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2
ñðàáàòûâàíèè öèêëà Eating-Eating âèëêè â ðóêàõ ôèëîñîôà óíè÷òîæàþò åäèíè÷-
íûé ðåñóðñ òèïà «ñïàãåòòè».
Âëîæåííîñòü ïîçâîëÿåò âåñüìà ïðîñòî è íàãëÿäíî ìîäåëèðîâàòü èåðàðõè-
÷åñêóþ ñòðóêòóðó. Ìû ìîæåì ìåíÿòü âåðõíèé è íèæíèé ñëîè íåçàâèñèìî îäèí
îò äðóãîãî, ïîëó÷àÿ íîâûå èíòåðåñíûå ìîäåëè (ðèñ. 6).  îäíîóðîâíåâûõ ìîäå-
ëÿõ ýòî áûëî áû íåâîçìîæíî. Îäíàêî âûðàçèòåëüíàÿ ìîùíîñòü ñîõðàíÿåòñÿ, ÷òî
ãàðàíòèðóåò ðàçðåøèìîñòü âñåõ îñíîâíûõ ñåìàíòè÷åñêèõ ñâîéñòâ è,
ñëåäîâàòåëüíî, àíàëèçèðóåìîñòü íîâîãî ôîðìàëèçìà.
Òåîðåìà 2. Êëàññ äâóõóðîâíåâûõ ñõåì ïî âûðàçèòåëüíîé ìîùíîñòè ñîâïà-
äàåò ñ êëàññîì îáûêíîâåííûõ ñåòåé Ïåòðè.
Äîêàçàòåëüñòâî. Îáûêíîâåííûå ñåòè Ïåòðè ýêâèâàëåíòíû îáûêíîâåííûì
ÀÐ-ñåòÿì, êîòîðûå ÿâëÿþòñÿ ÷àñòíûì ñëó÷àåì äâóõóðîâíåâûõ ñõåì (îäíà îáúåêò-
íàÿ ñåòü áåç ïîðòîâ). Ñëåäîâàòåëüíî, êëàññ ñåòåé Ïåòðè âêëàäûâàåòñÿ â êëàññ
äâóõóðîâíåâûõ ñõåì.
Äëÿ äîêàçàòåëüñòâà îáðàòíîãî âëîæåíèÿ äîñòàòî÷íî ïîêàçàòü, ÷òî ëþáóþ
äâóõóðîâíåâóþ ñõåìó ìîæíî ïðåîáðàçîâàòü â ýêâèâàëåíòíóþ ÀÐ-ñåòü (ñåòü Ïåò-
ðè). Ðàññìîòðèì ñëåäóþùåå ïðåîáðàçîâàíèå: çàìåíèì â èñõîäíîé ñèñòåìíîé ñõå-
ìå êàæäóþ àãåíòíóþ âåðøèíó íà ïîäñåòü, ñîîòâåòñòâóþùóþ ïî ñòðóêòóðå è ðàç-
ìåòêå âñåì ðàíåå íàõîäèâøèìñÿ â ýòîé âåðøèíå îáúåêòàì (ò.å. ïðîñòî ïåðåíåñåì
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2 37
Ðèñ. 5. Äâóõóðîâíåâàÿ ÀÐ-ñõåìà: ñèñòåìíàÿ ñõåìà (à); îáúåêòíàÿ ñåòü ph i (á)
dish
chair1
chair2
chair3
chair4
f2
f1 f4
f3
ph3
ph4
ph1
ph2
à á
Thinking Eating
RFork
LFork
RFork
LFork
dish
chair1
chair2
chair3
chair4
f1 f4
f3
ph4
f2
ph1
ph2
ph3
Ðèñ. 6. Ñòðóêòóðà äâóõóðîâíåâîé ìîäåëè: ïðÿìîóãîëüíûé ñòîë («äëèííîðóêèå ôèëîñîôû») (à);
ðàññåÿííûé ôèëîñîô (ôðàãìåíò) (á)
à á
âñå îáúåêòû íà ñèñòåìíûé óðîâåíü). Âñå ïîðòû ïðåîáðàçóåì â ïðîèçâîäÿùèå è
ïîòðåáëÿþùèå äóãè, ñâÿçûâàþùèå ïåðåõîäû íîâîé ïîäñåòè ñ ñîîòâåòñòâóþùè-
ìè ðåñóðñíûìè âåðøèíàìè ñõåìû. Î÷åâèäíî, ÷òî ïîëó÷åííàÿ ÀÐ-ñåòü ýêâèâà-
ëåíòíà èñõîäíîé ñõåìå. �
ÄÂÓÕÓÐÎÂÍÅÂÛÅ ÀÐ-ÑÈÑÒÅÌÛ
Ðàññìîòðèì áîëåå ñëîæíûé ñëó÷àé, êîãäà ñèñòåìà îáëàäàåò ñîáñòâåííûì ïî-
âåäåíèåì. Îáúåêòû ìîãóò íå òîëüêî òðàíñôîðìèðîâàòüñÿ (ìåíÿòü ñâîå ñîñòîÿ-
íèå), íî è âîçíèêàòü, èñ÷åçàòü è ïåðåìåùàòüñÿ.
Äëÿ îïèñàíèÿ ñïîñîáîâ óïðàâëåíèÿ îáúåêòàìè â ñèñòåìíîé ñåòè èñïîëüçóåì
ïàðàìåòðèçîâàííûå âûðàæåíèÿ íà ïîòðåáëÿþùèõ è ïðîèçâîäÿùèõ äóãàõ. Ïðè
ýòîì â êà÷åñòâå êîíñòàíò ìîãóò âûñòóïàòü ÀÐ-ñåòè (îáúåêòíûå ôèøêè).
Ñèñòåìíîé íàçûâàåòñÿ ìåòàñòðóêòóðà �
sys cons prod} Labels� � �(({ , )
� Syn sys, )� , ãäå �
sys îïðåäåëÿåò ñëåäóþùèå ðàñøèðåííûå ïðàâèëà:
1) äóãè òèïîâ cons è prod ïîìå÷åíû âûðàæåíèÿìè è ó÷àñòâóþò â ñðàáàòûâà-
íèÿõ ïî ïðàâèëàì ïàðàìåòðèçîâàííûõ ÀÐ-ñåòåé;
2) äóãè-ïîðòû ó÷àñòâóþò â ñðàáàòûâàíèÿõ ïî ïðàâèëàì äâóõóðîâíåâûõ
ÀÐ-ñõåì;
3) â âûðàæåíèÿõ íà ïîòðåáëÿþùèõ äóãàõ íå ìîæåò áûòü êîíñòàíò; â âûðà-
æåíèÿõ íà ðàçëè÷íûõ ïîòðåáëÿþùèõ äóãàõ îäíîãî óçëà íå ìîæåò áûòü
îäèíàêîâûõ ïåðåìåííûõ.
Îãðàíè÷åíèå 3) ìîæåò ïîêàçàòüñÿ íåî÷åâèäíûì, îäíàêî îíî íåîáõîäèìî,
ïîñêîëüêó óáèðàåò âîçìîæíîñòü ïðîâåðêè íà íîëü (êîòîðàÿ ïðèâåëà áû ê óíèâåð-
ñàëüíîé âû÷èñëèòåëüíîé ìîäåëè, ò.å. ìàøèíå Òüþðèíãà) [3].
Ðàçìå÷åííîé äâóõóðîâíåâîé ÀÐ-ñåòüþ íàçûâàåòñÿ íàáîð îáîáùåííûõ
ÀÐ-ñåòåé ( , , , )S o on1 � òàêîé, ÷òî:
1) S V R M� (( , ), ) — ðàçìå÷åííàÿ ñèñòåìíàÿ ñåòü, ãäå ( , )V R — �
sys -ñåòü,
M V o on: ({ , , } )� �1 � Nat — íà÷àëüíàÿ ðàçìåòêà ñèñòåìû;
2) o r mi i i i� (( , ), )� — ðàçìå÷åííàÿ îáúåêòíàÿ ñåòü, ãäå ( , )� i ir — � i-ñåòü,
mi i: � � Nat — íà÷àëüíàÿ ðàçìåòêà îáúåêòà.
Óñëîæíèì ìîäåëü îáåäàþùèõ ôèëîñîôîâ, äîáàâèâ èì âîçìîæíîñòü ïåðåìå-
ùåíèÿ èç ñòîëîâîé â ïàðê (íà ïðîãóëêó) è îáðàòíî (íà ðèñ. 7 èçîáðàæåí ôðàãìåíò
ñåòè, ñîîòâåòñòâóþùèé i-ìó ôèëîñîôó).
Ñ òî÷êè çðåíèÿ ôèëîñîôà ñèòóàöèÿ òà æå, ÷òî è ðàíüøå (âåäü îí ïåðåìåùàåò-
ñÿ ïî ïàðêó â òîì æå ñîñòîÿíèè Thinking), îäíàêî ñ òî÷êè çðåíèÿ ñèñòåìû ïðè
ýòîì îñâîáîæäàåòñÿ ñòóë. Òàêèì îáðàçîì, â ìîäåëè èçìåíèëàñü òîëüêî ñèñòåìíàÿ
ñåòü. Çàìåòèì òàêæå, ÷òî â ïàðêå ìîæåò íàõîäèòüñÿ íåñêîëüêî ôèëîñîôîâ îäíîâðå-
ìåííî, íî íà îäíîì ñòóëå — òîëüêî
îäèí (ýòî ñâîéñòâî îáåñïå÷èâàåòñÿ
èñïîëüçîâàíèåì óçëà-ñåìàôîðà
is_ empty i).
Òåîðåìà 3. Êëàññ äâóõóðîâíå-
âûõ ÀÐ-ñåòåé c îãðàíè÷åííûìè
îáúåêòíûìè ñåòÿìè [7] ñîâïàäàåò
ñ êëàññîì îáûêíîâåííûõ ñåòåé
Ïåòðè; êëàññ äâóõóðîâíåâûõ
ÀÐ-ñåòåé — ñ êëàññîì âëîæåííûõ
ñåòåé Ïåòðè [3].
Äîêàçàòåëüñòâî. Äëÿ äîêàçàò-
åëüñòâà ïåðâîãî óòâåðæäåíèÿ äîñ-
38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2
chairiPark
is_emptyi
x
x
x x
y
�
go_outi
go_ini
f1
f2
phi
Ðèñ. 7. Ôðàãìåíò ñåòè (ïðîãóëêà â ïàðêå)
òàòî÷íî çàìåòèòü, ÷òî ëþáóþ îãðàíè÷åííóþ ñåòü Ïåòðè ìîæíî ïðåäñòàâèòü â
âèäå àâòîìàòíîé ñåòè Ïåòðè, ò.å. ñåòè, ñîäåðæàùåé â êàæäûé ìîìåíò âðåìåíè
ðîâíî îäíó ôèøêó [7]. Òàêèì îáðàçîì, êàæäóþ àãåíòíóþ âåðøèíó ñèñòåìíîé
ñåòè ìîæíî çàìåíèòü íàáîðîì àâòîìàòíûõ ñåòåé, ïî îäíîé äëÿ êàæäîãî âèäà îá-
úåêòà. Êîëè÷åñòâî îáúåêòîâ â äàííîé àãåíòíîé âåðøèíå çàäàäèì êîëè÷åñòâîì
ôèøåê â ñîîòâåòñòâóþùèõ ïîçèöèÿõ ýòèõ àâòîìàòíûõ ñåòåé. Ïîðòû ïðåîáðàçóåì
â äóãè òåì æå ñïîñîáîì, ÷òî è â äîêàçàòåëüñòâå òåîðåìû 2.
Ïðè äîêàçàòåëüñòâå âòîðîãî óòâåðæäåíèÿ ïðèñîåäèíèì ê àãåíòíîé âåðøèíå
ñ ïîìîùüþ ïàðû ðàçíîíàïðàâëåííûõ äóã óçåë-ïåðåõîä äëÿ êàæäîãî ñïîñîáà âçà-
èìîäåéñòâèÿ âëîæåííîãî îáúåêòà ñ êàêèì-ëèáî ïîðòîì. Ñîïîñòàâèì ýòîò ïåðå-
õîä ïàðíîìó óçëó-ïåðåõîäó â îáúåêòå ñ ïîìîùüþ ïàðû ìåòîê âåðòèêàëüíîé ñèí-
õðîíèçàöèè (ñì. [3]). Ñâÿæåì ïåðåõîä ñ ðåñóðñíûìè âåðøèíàìè íåîáõîäèìûìè
ïðîèçâîäÿùèìè èëè ïîòðåáëÿþùèìè äóãàìè. Çàòåì ïðåîáðàçóåì ñèñòåìíóþ è
îáúåêòíûå ÀÐ-ñåòè â ýêâèâàëåíòíûå ñåòè Ïåòðè ñ ïîìîùüþ àëãîðèòìà, îïèñàí-
íîãî â [4], ñîõðàíÿÿ ìåòêè ñèíõðîíèçàöèè. �
Âëîæåííûå ñåòè Ïåòðè — ñóùåñòâåííî áîëåå ìîùíûé êëàññ ñèñòåì, îáëà-
äàþùèé, òåì íå ìåíåå, îáøèðíûì íàáîðîì ðàçðåøèìûõ ñâîéñòâ [3]. Òàêèì îáðà-
çîì, äâóõóðîâíåâûå ÀÐ-ñåòè, òàê æå êàê è îäíîóðîâíåâûå ñåòè è äâóõóðîâíåâûå
ñõåìû, ìîãóò èñïîëüçîâàòüñÿ íå òîëüêî äëÿ ìîäåëèðîâàíèÿ ñèñòåì, íî è äëÿ èõ
âåðèôèêàöèè.
ÇÀÊËÞ×ÅÍÈÅ
Èññëåäîâàíû íîâûå ñïîñîáû ïðåäñòàâëåíèÿ ìóëüòèàãåíòíûõ ñèñòåì ñ ïîìîùüþ
îáîáùåííûõ ñåòåé àêòèâíûõ ðåñóðñîâ. Ðàçðàáîòàí ðÿä ôîðìàëèçìîâ, ïðåäîñòàâ-
ëÿþùèõ óäîáíûå âîçìîæíîñòè ìîäåëèðîâàíèÿ:
1) îáûêíîâåííûå ÀÐ-ñåòè — âçàèìîäåéñòâèå àãåíòîâ è ðåñóðñîâ;
2) ïàðàìåòðèçîâàííûå ÀÐ-ñåòè — ïëîñêèå ñèñòåìû ñ îäíîòèïíûìè àãåíòàìè;
3) äâóõóðîâíåâûå ÀÐ-ñõåìû — ìîäóëüíûå è èåðàðõè÷åñêèå ñèñòåìû;
4) äâóõóðîâíåâûå ÀÐ-ñèñòåìû — ìîäóëüíûå è èåðàðõè÷åñêèå ñèñòåìû ñî
ñëîæíûìè âçàèìîäåéñòâèÿìè ìåæäó ñèñòåìíûì è îáúåêòíûì óðîâíÿìè ìîäåëè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. J e n s e n K . , K r i s t e n s e n L . Coloured Petri nets: modelling and validation of concurrent systems. —
N.Y.: Springer, 2009. — 384 p.
2. K o h l e r M . , R o l k e H . Properties of super-dual nets // Fundamenta Inform. — 2006. — 72. —
P. 245–254.
3. Ë î ì à ç î â à È . À . Âëîæåííûå ñåòè Ïåòðè: ìîäåëèðîâàíèå è àíàëèç ðàñïðåäåëåííûõ ñèñòåì ñ îáú-
åêòíîé ñòðóêòóðîé. — Ì.: Íàó÷íûé ìèð, 2004. — 208 ñ.
4. Á à ø ê è í Â . À . Ñåòè àêòèâíûõ ðåñóðñîâ // Ìîäåëèðîâàíèå è àíàëèç èíôîðìàöèîííûõ ñèñòåì. —
2007. — ¹ 14/4. — Ñ. 13–19.
5. R e i s i g W . Petri net models of distributed algorithms // Lecture Notes in Comput. Sci. — 1995. — 1000.
— 302 p.
6. B a s h k i n V . A . Nets of active resources for distributed systems modeling // Joint Bulletin of NCC&IIS,
C.S. Novosibirsk. — 2008. — 28. — P. 4–54.
7. Ê î ò î â Â . Å . Ñåòè Ïåòðè. — Ì.: Íàóêà, 1984. — 160 ñ.
Ïîñòóïèëà 14.07.2010
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 2 39
|
| id | nasplib_isofts_kiev_ua-123456789-84183 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-01T23:35:19Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Башкин, В.А. Ломазова, И.А. 2015-07-03T15:50:24Z 2015-07-03T15:50:24Z 2011 Моделирование мультиагентных систем с помощью обобщенных сетей активных ресурсов / В.А. Башкин, И.А. Ломазова // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — С. 31-39. — Бібліогр.: 7 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84183 519.711 Розглянуто проблему моделювання мультиагентних систем з нескінченною множиною станiв. Дослiджено формалiзми, що ґрунтуються на узагальненнi мереж активних ресурсiв. Визначено новi способи моделювання: параметризованi АР-мережi, дворiвневi АР-схеми та дворiвневi АР-мережi. Показано, що цi формалiзми мають зручний синтаксис для моделювання мультиагентних систем, а також систем зi складною модульною або iєрархiчною структурою. Доведено, що параметризованi АР-мережi та дворiвневi АР-схеми еквiвалентнi мережам Петрi, дворiвневi АР-системи еквiвалентнi вкладеним мережам Петрi. The problem of modeling infinite-state multiagent systems is considered. Formalisms based on the generalization of nets of active resources are studied. New modeling techniques are defined: parameterized AR-nets, two-level AR-schemes, and two-level AR-nets. It is shown that the syntax of these formalisms is convenient for modeling multiagent systems such as systems with complex modular or hierarchical structure. It is proved that parameterized AR-nets and two-level AR-schemes are equivalent to Petri nets, while two-level AR-systems are equivalent to nested Petri nets. Работа выполнена при поддержке РФФИ (09-01-00277) и ФАНИ (02,740,11,0207). ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Моделирование мультиагентных систем с помощью обобщенных сетей активных ресурсов Моделювання мультиагентних систем за допомогою узагальнених мереж активних ресурсiв Modeling multiagent systems with generalized nets of active resources Article published earlier |
| spellingShingle | Моделирование мультиагентных систем с помощью обобщенных сетей активных ресурсов Башкин, В.А. Ломазова, И.А. Кибернетика |
| title | Моделирование мультиагентных систем с помощью обобщенных сетей активных ресурсов |
| title_alt | Моделювання мультиагентних систем за допомогою узагальнених мереж активних ресурсiв Modeling multiagent systems with generalized nets of active resources |
| title_full | Моделирование мультиагентных систем с помощью обобщенных сетей активных ресурсов |
| title_fullStr | Моделирование мультиагентных систем с помощью обобщенных сетей активных ресурсов |
| title_full_unstemmed | Моделирование мультиагентных систем с помощью обобщенных сетей активных ресурсов |
| title_short | Моделирование мультиагентных систем с помощью обобщенных сетей активных ресурсов |
| title_sort | моделирование мультиагентных систем с помощью обобщенных сетей активных ресурсов |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84183 |
| work_keys_str_mv | AT baškinva modelirovaniemulʹtiagentnyhsistemspomoŝʹûobobŝennyhseteiaktivnyhresursov AT lomazovaia modelirovaniemulʹtiagentnyhsistemspomoŝʹûobobŝennyhseteiaktivnyhresursov AT baškinva modelûvannâmulʹtiagentnihsistemzadopomogoûuzagalʹnenihmerežaktivnihresursiv AT lomazovaia modelûvannâmulʹtiagentnihsistemzadopomogoûuzagalʹnenihmerežaktivnihresursiv AT baškinva modelingmultiagentsystemswithgeneralizednetsofactiveresources AT lomazovaia modelingmultiagentsystemswithgeneralizednetsofactiveresources |