混合系統

混合系統（hybrid system）是同時包括連續及離散動態特性的動力系統，這類系統中同時有「流」（flow，以微分方程描述）以及跳躍（以有限狀態機或自動機理論描述）的特性。有時也會用混合動態系統（hybrid dynamical system）這個詞語，比較不會和結合人工神經網絡及模糊邏輯的系統，或是同時應用電子及機械的系統混唏。混合系統的好處是其結構可以包括更多種類的系統，在針對系統特性建模時也有更大的彈性。

一般而言，混合系統的狀態可以用連續變數的值以及其他離散的模式來表示。狀態可能依照其「流條件」（flow condition）有連續性的變化，或依照控制圖（control graph）有離散的變化。只要所謂的不變量維持不變，就會有連續性的變化，不過若滿足了特定的跳躍條件，就會有離散轉態。離散轉態也可能和事件有關。

例子

混合系統可以用來為許多系統進行建模，包括有碰撞的物理系統、邏輯動態控制器，甚至是互聯網擁堵問題等。

彈跳球

彈跳球（英語：bouncing ball）屬於有碰撞的物理系統，混合系統中的經典範例。在此例中，球（以點狀質量表示）由啟始高度掉到地面彈跳，每一次的彈跳都會耗散能量。球在每一次彈跳之間都是連續的動態特性，當球碰到地面時，因為非彈性碰撞，球的速度會有離散的變化。彈跳球的數學模型如下：令 $x_{1}$ 是球的高度， $x_{2}$ 是球的速度，其混合系統如下：

當 $x\in C=\{x_{1}>0\}$ ，「流」的統御方程為 ${\dot {x_{1}}}=x_{2},{\dot {x_{2}}}=-g$ , 其中 $g$ 為因為重力而有的加速度，上述方程指出，若球在地面之上，最終會因為重力而掉到地面。

若 $x\in D=\{x_{1}=0\}$ ，「跳躍」的統御方程為 $x_{1}^{+}=x_{1},x_{2}^{+}=-\gamma x_{2}$ , 其中 $0<\gamma <1$ 為耗散系數。方程式是當高度為零（和地面碰撞）時，其速度符號會相反，且會以 $\gamma$ 的比例減少。這也是非彈性碰撞的特性。

彈跳球系統的特點是有Zeno行為。Zeno行為有嚴格的數學定義，可以大致描述為系統在有限時間內進行了無限次的「跳躍」。在此例中，彈跳球每次碰到地面，就會損失能量，因此之後碰到地面的時間間隔也就會越來越接近。

混合系統的驗證

有關混合系統的形式驗證，有些方法可以自動證明一些混合系統的特性，驗證混合系統安全性的常用工具包括可到達集的計算、抽象模型檢查（英語：Abstraction model checking）以及barrier certificate（英語：barrier certificate）。

大部份的驗證工作都是不可判定問題^[1]，因此沒有辦法找出通用的驗證演算法。不過，這些工具會在指標性問題上展現其分析能力。這些可以驗證所有強健案例的混合系統驗證法^[2]帶來一個可能的理論性結論：混合系統中的許多問題雖然是不可判定的，但至少是準可判定的^[3]。

其他建模方式

基本的混合系統建模方式可以分為兩種：隱式以及顯式。顯式的方式會用混合自動機（英語：hybrid automaton）、混合程式或是混合Petri網表示。隱式的作法會用統御方程式來表示，因此會得到微分代數方程（英語：differential algebraic equation）（DAE）的系統，也有可以透過混合鍵結圖來表示。

若是考慮混合系統分析的統一仿真方法，有一種以DEVS（英語：DEVS）形式化為基礎的方法，其中微分方程的積分子會量化為原子性的DEVS模型。該方法以離散事件系統的行為產生系統的軌跡，和離散時間系統不同。在參考資料[Kofman2004]、[CF2006]及[Nutaro2010]中有描述該作法的細節，而軟件工具PowerDEVS（英語：PowerDEVS）中也有描述。

參考資料

^ Thomas A. Henzinger, Peter W. Kopke, Anuj Puri, and Pravin Varaiya: What's Decidable about Hybrid Automata, Journal of Computer and System Sciences, 1998
^ Martin Fränzle: Analysis of Hybrid Systems: An ounce of realism can save an infinity of states, Springer LNCS 1683
^ Stefan Ratschan: Safety verification of non-linear hybrid systems is quasi-decidable, Formal Methods in System Design, volume 44, pp. 71-90, 2014, doi:10.1007/s10703-013-0196-2

延伸閱讀

Henzinger, Thomas A., The Theory of Hybrid Automata, 11th Annual Symposium on Logic in Computer Science (LICS), IEEE Computer Society Press: 278–292, 1996, （原始內容存檔於2010-01-27）
Alur, Rajeev; Courcoubetis, Costas; Halbwachs, Nicolas; Henzinger, Thomas A.; Ho, Pei-Hsin; Nicollin, Xavier; Olivero, Alfredo; Sifakis, Joseph; Yovine, Sergio, The algorithmic analysis of hybrid systems, Theoretical Computer Science, 1995, 138 (1): 3–34, doi:10.1016/0304-3975(94)00202-T, （原始內容存檔於2010-01-27）
Goebel, Rafal; Sanfelice, Ricardo G.; Teel, Andrew R., Hybrid dynamical systems, IEEE Control Systems Magazine, 2009, 29 (2): 28–93, doi:10.1109/MCS.2008.931718
Acary, Vincent; Brogliato, Bernard, Numerical Methods for Nonsmooth Dynamical Systems, Lecture Notes in Applied and Computational Mechanics, 2008, 35
[Kofman2004] Kofman, E, Discrete Event Simulation of Hybrid Systems, SIAM Journal on Scientific Computing, 2004, 25 (5): 1771–1797, doi:10.1137/S1064827502418379
[CF2006] Francois E. Cellier and Ernesto Kofman, Continuous System Simulation first, Springer, 2006, ISBN 978-0-387-26102-7
[Nutaro2010] James Nutaro, Building Software for Simulation: Theory, Algorithms, and Applications in C++ first, Wiley, 2010

外部連結

IEEE CSS Committee on Hybrid Systems

[1] Thomas A. Henzinger, Peter W. Kopke, Anuj Puri, and Pravin Varaiya: What's Decidable about Hybrid Automata, Journal of Computer and System Sciences, 1998

[2] Martin Fränzle: Analysis of Hybrid Systems: An ounce of realism can save an infinity of states, Springer LNCS 1683

[3] Stefan Ratschan: Safety verification of non-linear hybrid systems is quasi-decidable, Formal Methods in System Design, volume 44, pp. 71-90, 2014, doi:10.1007/s10703-013-0196-2

[1]

[2]

[3]

例子

彈跳球

混合系統的驗證

其他建模方式

相關條目

參考資料

延伸閱讀

外部連結