第 5 章 計算例 24
5.4 遺伝子トグルスイッチの探索
の離散抽象化にはk-有界双模倣が適していると考えられる．
図 5.10: 分割階数と領域の分割数の変化
x(k+ 1) =
Aix(k) +u(k) +ai
with the prob. 0.9, x(k)
with the prob. 0.1, if x(k)∈ Si
(5.8)
A1 = [
0.99 0 0 0.98
] , a1 =
[ 0.92 1.53 ]
, A2 = [
0.99 0
−0.03 0.98 ]
, a2 = [
0.92 2.9
]
A3 = [
0.99 0 0 0.98
] , a3 =
[ 0.92 0.15 ]
, A4 = [
0.99 −0.02 0 0.98
] , a4 =
[ 1.39 0.153
]
A5 = [
0.99 −0.02
−0.03 0.98 ]
, a5 = [
1.38 2.9
]
, A6 = [
0.99 −0.02 0 0.98
] , a6 =
[ 1.41 0.15 ]
A7 = [
0.99 0 0 0.98
] , a7 =
[ 1.7 1.53
]
, A8 = [
0.99 0
−0.03 0.98 ]
, a8 = [
0.17 2.92 ]
A9 = [
0.99 0 0 0.98
] , a9 =
[ 0.17 0.15 ]
を考える．ここで，x(k) ∈ X ⊆ [0 100]×[0 100]，u(k) ∈ U ⊆ [−15 15]×[−18 18]，
I(k)∈ M:={1,2, ...,9}，である．
それぞれのモードで対応した数字のダイナミクスが採用される．1,2, ...9までのダイナ ミクスが採用される確率を0.9とし，どのモードであっても0.1の確率で状態が変化しな いダイナミクスが採用される．モードの領域は図に示されているため省略する．
交互に遷移する領域を探すのが目的であるため，2ステップ分の遷移関係を求めた．各 ステップの領域数を以下の表に示す．
表 5.2: 遺伝子の例題の分割数 ステップ数 領域の分割数
0 9
1 69
2 1394
図5.12に1ステップの離散抽象化で得られた領域と，領域間の遷移関係を示す．なお，
図5.12の描画はGraphviz(Graph Visualization Software)[19]を用いた．2重の円に配置さ れているノードのうち，内周部にある9個のノードが初期分割π0 = {S1,S2, ...,S9}であ り，外周部の62個のノードがπ1 ={S1′, S2′, ...S62′ }である．ノードのラベルを拡張状態の
図 5.11: 状態空間の初期分割
図 5.12: 1ステップ分の離散抽象化
領域をX へ射影した際の分割を元に割り振ることで，同じ状態であっても入力の与え方 によって別の遷移確率を持つ拡張状態の領域をグラフに表現してる．また，ラベルの括弧 内の数字はステップ数を示しており，初期分割π0 として与えた領域を(0),1回離散抽象化 して得たπ1内の領域を(1)としている．
π1のノードが初期分割のどの領域に含まれているかを色で示している．今回はモード の領域と初期分割の領域が同じため，同色のノードならば同じモードとなる．遷移確率は エッジにラベルが割り振っているが，エッジの太さでも区別している．太く描画されてい るエッジは遷移確率が大きく，細く描画されているエッジの遷移確率は小さい．
k= 2までの遷移関係を見ると，領域5と領域6ではほかの領域に比べて特に相互の領 域へ遷移可能な領域が多かった．そこで，得られた結果のうち領域5，領域6，領域5と 一定確率以上で遷移可能な領域を求めた．領域S5に遷移可能な領域6内の領域S1 ⊂ S6
とS1に遷移可能な領域S2 ⊂ S5のX への射影を図5.13 に示す．
計算結果から拡張状態の領域S2からS1へ，S1からS5へ遷移可能なことは保障されて いる．しかし，S5にはS2以外の領域も存在しているため，S1から遷移したS5上の状態 から領域6内の状態へ再び遷移可能か計算結果からは判別できない．
S2に対して再びP re(X)の計算を行うことで，S2へ遷移可能な領域が導出できる．
P re(P roX(S2))の領域を図5.14に示す．
図 5.13: 領域S5への遷移確率が高い領域 図 5.14: S2へ遷移可能な領域
得られた領域のXへの射影は，S1のXへの射影を包含する領域であることがわかった．
P re(P roX(S2))内の状態であればS2へ遷移可能であり，S2内の状態であればP re(P roX(S2)) 内の領域であるS1へ遷移可能であるため，この二つの拡張状態の領域S1, S2間では，入 力を適切に与えることである確率で交互に遷移できることが分かった．
このように，2状態2入力9モードの複雑なシステムであっても，離散抽象化を行うと 目的としている機能が実現可能な状態集合を離散ダイナミクスから探索できる．
第 6 章 おわりに
本論文では，確率ハイブリッドシステムに対する離散抽象化について考察した．双模倣 性に基づく場合，離散抽象化システムの計算手続きの停止性は一般に保証されていない．
そこで，文献[17]で提案された有界双模倣性を確率ハイブリッドシステムに拡張すること で，停止性が保証された離散抽象化システムの計算方法を提案した．
確率ハイブリッドシステムは，確定的なハイブリッドシステムではモードごとに一つず つであった連続ダイナミクスを複数存在することを認め，異なる確率分布を与えることで システムの確率的な振る舞いを表現した．
提案手法の説明としてまず，確率ハイブリッドシステムに制約を加え，確定的なハイブ リッドシステムとしてk-有界双模倣の解説と計算手順の確認を行った．次に，確率ハイブ リッドシステムに対して提案手法である拡張したk-有界双模倣の計算を行い，得られた 離散ダイナミクスについて説明した．
確率ハイブリッドシステムの離散抽象化に有界双模倣を用いることの有効性について は，異なるダイナミクスで構成された確率ハイブリッドシステムを離散抽象化し，領域の 分割数を比較することで説明した．また，遺伝子トグルスイッチの例では，システムが特 定の機能を満たす条件を離散抽象化によって得られた結果から求めた．
離散抽象化システムを用いることで，確率ハイブリッドシステムの解析や制御は容易と なることからさまざまな応用が期待できる．
しかしながら，拡張状態空間の分割数は時間に関して指数関数的に増加するため，分割 の計算が困難になる場合が考えられる．近似双模倣による離散抽象化[15, 16]や，遷移確 率の低い領域の枝狩りなど，近似手法の検討は今後の課題の一つである．
また，具体的な例題を用いた有効性の評価も今後の課題である．
謝辞
最後に，本研究を進めるにあたり貴重な御指導をいただいた，指導教官であり北陸先端 科学技術大学院大学情報科学研究科の平石邦彦教授に衷心より感謝いたします．
また，同研究室の小林孝一助教，並びに大学院教育イニシアティブセンターの崔舜星特 任助教には終始適切な助言をいただきました．心よりお礼申し上げます．
参考文献
[1] A. Abate, A. D’Innocenzo, and M. D. Di Benedetto, Approximate abstractions of stochastic hybrid systems,IEEE Trans. on Automatic Control, vol. 56, no. 11, pp. 2688–2694, 2011.
[2] R. Alur, T. A. Henzinger, G. Lafferriere, and G. J. Pappas, Discrete abstractions of hybrid systems, Proceedings of the IEEE, vol. 88, no. 7, pp. 971–984, 2000.
[3] R. Alur, T. Dang, and F. Ivanˇci´c, Predicate abstraction for reachability analysis of hybrid systems, ACM Trans. on Embedded Computing Systems, vol. 5, no, 1, pp. 152–199, 2006.
[4] A. Bemporad and S. Di Cairano, Model-predictive control of discrete hybrid stochastic automata,IEEE Trans. on Automatic Control, vol. 56, no. 6, pp. 1307–1321, 2011.
[5] P. Bolzern, P. Colaneri, and G. D. Nicolao, Markov Jump Linear Systems with switching transition rates: Mean square stability with dwell-time, Automatica, pp. 1081–1088, 2010.
[6] M. L. Bujorianu and J. Lygeros, General stochastic hybrid systems: Modelling and optimal control, Proc. 43rd IEEE Conf. on Decision and Control, pp. 1872–1877, 2004.
[7] M. L. Bujorianu and J. Lygeros, Bisimulation for general stochastic hybrid systems, Proc.
Int’l Workshop on Hybrid Systems: Computation and Control, LNCS 3414, pp. 198–214, 2005.
[8] J. P. Hespanha, A model for stochastic hybrid systems with application to communication networks, Nonlinear Analysis, vol. 62, pp. 1353–1383, 2005.
[9] J. P. Hespanha, Why Should I Care About Stochastic Hybrid Systems?, 49th IEEE Conf.
on Decision and Control, Semi-plenary talk, 2010.
[10] A. A. Julius, A. Girard and G, J. Pappas, Approximate bisimulation for a class of stochastic hybrid systems Proc. 2006 American Control Conf., pp. 4724–4729, 2004.
[11] L. Shi, A. Abate, and S. Sastry, Optimal Control for a class of Stochastic Hybrid Systems, Proc. 43rd IEEE Conf. on Decision and Control, pp. 1842–1847, 2004.
[12] P. Tabuada,Verification and Control of Hybrid Systems, Springer, 2009.
[13] Y. Tazaki and J. Imura, Discrete abstractions of nonlinear systems based on error propa-gation analysis,IEEE Trans. on Automatic Control, vol. 57, no. 3, pp. 550–564, 2011.
[14] J. Tumova，I. Cerna，J. Barnat，C. Belta，B. Yordanov，Temporal Logic Control of Discrete-Time Piecewise Affine SystemsIEEE Trans. on Automatic Control, vol. 57, no. 6, pp. 1491–1504, 2012.
[15] 潮，足立，ハイブリッドオートマトンの双模倣関係とその近似計算，システム/制御/情報，
vol. 53，no. 10，pp. 434-442，2009．
[16] 崔，平石，小林，遷移関係に基づくハイブリッドシステムの近似双模倣，計測自動制御学会 論文集，vol. 47，no. 12，pp. 614-620，2011．
[17] 平石，小林，崔，有限時間区間に対するハイブリッドシステムの離散抽象化，計測自動制御 学会論文集，vol. 44，no. 9，pp. 751-759，2008．
[18] Multi-Parametric Toolbox: http://control.ee.ethz.ch/˜mpt/
[19] Graphviz: http://www.graphviz.org/