混合系統
混合系統(hybrid system)是同時包括連續及離散動態特性的動力系統,這類系統中同時有「流」(flow,以微分方程描述)以及跳躍(以有限狀態機或自動機理論描述)的特性。有時也會用混合動態系統(hybrid dynamical system)這個詞語,比較不會和結合人工神經網絡及模糊邏輯的系統,或是同時應用電子及機械的系統混唏。混合系統的好處是其結構可以包括更多種類的系統,在針對系統特性建模時也有更大的彈性。
一般而言,混合系統的狀態可以用連續變數的值以及其他離散的模式來表示。狀態可能依照其「流條件」(flow condition)有連續性的變化,或依照控制圖(control graph)有離散的變化。只要所謂的不變量維持不變,就會有連續性的變化,不過若滿足了特定的跳躍條件,就會有離散轉態。離散轉態也可能和事件有關。
例子
混合系統可以用來為許多系統進行建模,包括有碰撞的物理系統、邏輯動態控制器,甚至是互聯網擁堵問題等。
彈跳球
彈跳球屬於有碰撞的物理系統,混合系統中的經典範例。在此例中,球(以點狀質量表示)由啟始高度掉到地面彈跳,每一次的彈跳都會耗散能量。球在每一次彈跳之間都是連續的動態特性,當球碰到地面時,因為非彈性碰撞,球的速度會有離散的變化。彈跳球的數學模型如下:令 是球的高度, 是球的速度,其混合系統如下:
當 ,「流」的統御方程為 , 其中 為因為重力而有的加速度,上述方程指出,若球在地面之上,最終會因為重力而掉到地面。
若 ,「跳躍」的統御方程為 , 其中 為耗散系數。方程式是當高度為零(和地面碰撞)時,其速度符號會相反,且會以 的比例減少。這也是非彈性碰撞的特性。
彈跳球系統的特點是有Zeno行為。Zeno行為有嚴格的數學定義,可以大致描述為系統在有限時間內進行了無限次的「跳躍」。在此例中,彈跳球每次碰到地面,就會損失能量,因此之後碰到地面的時間間隔也就會越來越接近。
混合系統的驗證
有關混合系統的形式驗證,有些方法可以自動證明一些混合系統的特性,驗證混合系統安全性的常用工具包括可到達集的計算、抽象模型檢查以及barrier certificate。
大部份的驗證工作都是不可判定問題[1],因此沒有辦法找出通用的驗證演算法。不過,這些工具會在指標性問題上展現其分析能力。這些可以驗證所有強健案例的混合系統驗證法[2]帶來一個可能的理論性結論:混合系統中的許多問題雖然是不可判定的,但至少是準可判定的[3]。
其他建模方式
基本的混合系統建模方式可以分為兩種:隱式以及顯式。顯式的方式會用混合自動機、混合程式或是混合Petri網表示。隱式的作法會用統御方程式來表示,因此會得到微分代數方程(DAE)的系統,也有可以透過混合鍵結圖來表示。
若是考慮混合系統分析的統一仿真方法,有一種以DEVS形式化為基礎的方法,其中微分方程的積分子會量化為原子性的DEVS模型。該方法以離散事件系統的行為產生系統的軌跡,和離散時間系統不同。在參考資料[Kofman2004]、[CF2006]及[Nutaro2010]中有描述該作法的細節,而軟件工具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