| 講演名 | 2018-11-12 閉路フロー行列変換によるペトリネットの安定部分ネットの検知 張江 洋次朗(信州大), 和﨑 克己(信州大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ペトリネットは，離散事象システムを表現・解析が可能な数学的手法の一つである.ペトリネットの動的解析には初期状態からの振る舞いを状態空間として生成する必要があり，状態空間が大規模になると計算時間や記憶領域のコストが大きくなる状態爆発の問題が存在する．大規模ネットに対する現実的な解析法として，ネット分割やネット縮約がある．ペトリネットのプレース内の重み付きトークン総和が一定であることを示す性質に$S$-インバリアントがある．状態方程式からインバリアントを求めるが，その総数は一般的に未確定であり，安定的な振る舞いの部分ネットを容易に取り出すことは性質検証や状態生成において有益であるといえる．本研究はペトリネットの部分ネット分割を行うにあたり，プレース間のトークンの増減の比率を接続とする，重み付き有向グラフ「フローネット」への変換を行う．フローネット上でトークン数が一定であることを示す基準としてStabilityを定義し，与えられた分割に対しStabilityに基づき評価する最大化問題へ帰着させる．分割はノード集合の集合族で得られるが，連結成分のみを抽出することで効率化を図る．本稿では，対象ネットを閉路ネットに限定し，活性なFCネットを例に安定部分ネットの検知が可能であることを示した． |
| 抄録(英) | Petri net is a graphical and mathematical modeling tool describes distributed systems. For dynamic analysis of Petri net, it is necessary to generate behaviors from the initial state as state space. However, there is a problem that exploring an large state space incurs significant memory and time costs. In the analysis method for large scale net, graph partitioning and contraction are proposed. The S-invariant is a property which means the total sum of weighted tokens in Petri net places is constant. Although invariants are obtained from state equations, the total number is generally unknown. Therefore, for the easy retrieval of partial net of stable behavior is useful for property verification and state generation. In this research, in order to perform partial net partitioning of Petri nets, we convert to the weighted directed graph "Flow-net" with the ratio of increase / decrease of tokens between places as a connection. We define "Stability" as a criterion for the constant number of tokens on the flow net. It reduces to a maximizing problem that evaluates based on Stability for a given partition. Graph partitioning can be obtained by a set of family of node sets, but for the efficiency we extract only connected components. In this paper, we show that the detection of Stability subnet of the liveness Free Choice net is enabled restricting target net to cycle net. |
| キーワード(和) | ペトリネット / フロー行列変換 / グラフ分割 / 安定部分ネット / Stability |
| キーワード(英) | Petri Net / Flow-Matrix Transformation / Graph Partitioning / Stability Subnet / Stability |
| 資料番号 | CAS2018-64,MSS2018-40 |
| 発行日 | 2018-11-05 (CAS, MSS) |
| 研究会情報 | |
| 研究会 | MSS / CAS / IPSJ-AL |
|---|---|
| 開催期間 | 2018/11/12(から2日開催) |
| 開催地（和） | 熱海伊豆山温泉 ハートピア熱海 |
| 開催地（英） | |
| テーマ（和） | システムのモデリングと制御・検証・最適化の手法，機械学習的アプローチ及び一般 |
| テーマ（英） | |
| 委員長氏名（和） | 名嘉村 盛和(琉球大) / 岡崎 秀晃(湘南工科大) |
| 委員長氏名（英） | Morikazu Nakamura(Univ. of Ryukyus) / Hideaki Okazaki(Shonan Inst. of Tech.) |
| 副委員長氏名（和） | 髙井 重昌(阪大) / 山脇 大造(日立) |
| 副委員長氏名（英） | Shigemasa Takai(Osaka Univ.) / Taizo Yamawaki(Hitachi) |
| 幹事氏名（和） | 豊嶋 伊知郎(東芝エネルギーシステムズ) / 金澤 尚史(阪大) / 橘 俊宏(湘南工科大) / 中村 洋平(日立) |
| 幹事氏名（英） | Ichiro Toyoshima(Toshiba) / Takahumi Kanazawa(Osaka Univ.) / Toshihiro Tachibana(Shonan Inst. of Tech.) / Yohei Nakamura(Hitachi) |
| 幹事補佐氏名（和） | 金城 秀樹(沖縄大) / 山口 基(ルネサスエレクトロニクス) |
| 幹事補佐氏名（英） | Hideki Kinjo(Okinawa Univ.) / Motoi Yamaguchi(Renesas Electronics) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Mathematical Systems Science and its applications / Technical Committee on Circuits and Systems / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 閉路フロー行列変換によるペトリネットの安定部分ネットの検知 |
| サブタイトル（和） | |
| タイトル（英） | Stability Subnet Detection of Petri Net by Circuit Flow-Matrix Transformation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri Net |
| キーワード(2)（和/英） | フロー行列変換 / Flow-Matrix Transformation |
| キーワード(3)（和/英） | グラフ分割 / Graph Partitioning |
| キーワード(4)（和/英） | 安定部分ネット / Stability Subnet |
| キーワード(5)（和/英） | Stability / Stability |
| 第 1 著者 氏名（和/英） | 張江 洋次朗 / Yojiro Harie |
| 第 1 著者 所属（和/英） | 信州大学(略称：信州大) Shinshu University(略称：Shinshu Univ.) |
| 第 2 著者 氏名（和/英） | 和﨑 克己 / Katsumi Wasaki |
| 第 2 著者 所属（和/英） | 信州大学(略称：信州大) Shinshu University(略称：Shinshu Univ.) |
| 発表年月日 | 2018-11-12 |
| 資料番号 | CAS2018-64,MSS2018-40 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | CAS-295,MSS-296 |
| ページ範囲 | pp.37-42(CAS), pp.37-42(MSS), |
| ページ数 | 6 |
| 発行日 | 2018-11-05 (CAS, MSS) |