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

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

例子

編輯

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

彈跳球

編輯

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

 ,「流」的統御方程為  , 其中 為因為重力而有的加速度,上述方程指出,若球在地面之上,最終會因為重力而掉到地面。

 ,「跳躍」的統御方程為  , 其中 為耗散係數。方程式是當高度為零(和地面碰撞)時,其速度符號會相反,且會以 的比例減少。這也是非彈性碰撞的特性。

彈跳球系統的特點是有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中也有描述。

相關條目

編輯

參考資料

編輯
  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

延伸閱讀

編輯
  • 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 

外部連結

編輯