|
|
|
Perturbation analysis of stochastic hybrid systems and applications to resource contention games |
Chen YAO, Christos G. CASSANDRAS( ) |
| Division of Systems Engineering and Center for Information and Systems Engineering, Boston University, Brookline, MA 02446, USA |
|
|
|
|
Abstract We provide an overview of the recently developed general infinitesimal perturbation analysis (IPA) framework for stochastic hybrid systems (SHSs), and establish some conditions under which this framework can be used to obtain unbiased performance gradient estimates in a particularly simple and efficient manner. We also propose a general scheme for systematically deriving an abstraction of a discrete event system (DES) in the form of an SHS. Then, as an application of the general IPA framework, we study a class of stochastic non-cooperative games termed “resource contention games” modeled through stochastic flow models (SFMs), where two or more players (users) compete for the use of a sharable resource. Simulation results are provided for a simple version of such games to illustrate and contrast system-centric and user-centric optimization.
|
| Keywords
stochastic flow model (SFM)
perturbation analysis
stochastic hybrid system (SHS)
resource contention games
cyber-physical systems
|
|
Corresponding Author(s):
CASSANDRAS Christos G.,Email:cgc@bu.edu
|
|
Issue Date: 05 September 2011
|
|
| 1 |
Cassandras C G, Lygeros J. Stochastic Hybrid Systems. London: Taylor and Francis Group/CRC Press, 2006
doi: 10.1201/9781420008548
|
| 2 |
Cassandras C G, Lafortune S. Introduction to Discrete Event Systems. 2nd ed. New York, NY: Springer, 2008
doi: 10.1007/978-0-387-68612-7
|
| 3 |
Ho Y C, Cao X R. Perturbation Analysis of Discrete Event Dynamic Systems. Boston , MA: Kluwer Academic Publisher, 1991
doi: 10.1007/978-1-4615-4024-3
|
| 4 |
Glasserman P. Gradient Estimation via Perturbation Analysis. Boston , MA: Kluwer Academic Publisher, 1991
|
| 5 |
Cassandras C G, Wardi Y, Melamed B, Sun G, Panayiotou C G. Perturbation analysis for on-line control and optimization of stochastic fluid models. IEEE Transactions on Automatic Control , 2002, 47(8): 1234-1248
doi: 10.1109/TAC.2002.800739
|
| 6 |
Anick D, Mitra D, Sondhi M M. Stochastic theory of a data-handling system with multiple sources. The Bell System Technical Journal , 1982, 61(8): 1871- 1894
|
| 7 |
Liu B, Guo Y, Kurose J, Towsley D, Gong W B. Fluid simulation of large scale networks: Issues and tradeoffs. In: Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications . 1999, 2136-2142
|
| 8 |
Connor D, Feigin G, Yao D D. Scheduling semiconductor lines using a fluid network model. IEEE Transactions on Robotics and Automation , 1994, 10(2): 88-98
doi: 10.1109/70.282534
|
| 9 |
Yu H, Cassandras C G. Perturbation analysis of feedbackcontrolled stochastic flow systems. IEEE Transactions on Automatic Control , 2004, 49(8): 1317-1332
doi: 10.1109/TAC.2004.832205
|
| 10 |
Wardi Y, Adams R, Melamed B. A unified approach to infinitesimal perturbation analysis in stochastic flow models: The single-stage case. IEEE Transactions on Automatic Control , 2009, 55(1): 89-103
doi: 10.1109/TAC.2009.2034228
|
| 11 |
Sun G, Cassandras C G, Panayiotou C G. Perturbation analysis and optimization of stochastic flow networks. IEEE Transactions on Automatic Control , 2004, 49(12): 2113-2128
doi: 10.1109/TAC.2004.838498
|
| 12 |
Yu H, Cassandras C G. Perturbation analysis and feedback control of communication networks using stochastic hybrid models. Journal of Nonlinear Analysis , 2006, 65(6): 1251-1280
doi: 10.1016/j.na.2005.12.022
|
| 13 |
Cassandras C G, Wardi Y, Panayiotou C G, Yao C. Perturbation analysis and optimization of stochastic hybrid systems. European Journal of Control , 2010, 16(6): 642-664
doi: 10.3166/ejc.16.642-661
|
| 14 |
Yao C, Cassandras C G. Perturbation analysis of stochastic hybrid systems and applications to some non-cooperative games. In: Proceedings of the 10th International Workshop on Discrete Event Systems . 2010, 69-74
|
| 15 |
Kushner H J, Yin G G. Stochastic Approximation Algorithms and Applications. New York , NY: Springer-Verlag, 1997
|
| 16 |
Yao C, Cassandras C G. Perturbation analysis and optimization of multiclass multi-objective stochastic flow models. In: Proceedings of the 48th IEEE Conference of Decision and Control . 2009, 914-919
|
| 17 |
Rubinstein R. Monte Carlo Optimization, Simulation and Sensitivity of Queueing Networks. New York , NY: John Wiley and Sons, 1986
|
| 18 |
Sun G, Cassandras C G, Panayiotou C G. Perturbation analysis of multiclass stochastic fluid models. Journal of Discrete Event Dynamic Systems: Theory and Applications , 2004, 14(3): 267-307
doi: 10.1023/B:DISC.0000028198.41139.20
|
| 19 |
Chen M, Hu J Q, Fu M C. Perturbation analysis of a dynamic priority call center. IEEE Transactions on Automatic Control , 2008, 55(5): 1191-1196
doi: 10.1109/TAC.2010.2041979
|
| 20 |
Yao C, Cassandras C G. Perturbation analysis and resource contention games in multiclass stochastic fluid models. In: Proceedings of the 3rd IFAC Conference on Analysis and Design of Hybrid Systems . 2009, 256-261
|
| 21 |
Yao C, Cassandras C G. Perturbation analysis and resource contention games in multiclass stochastic fluid models. Nonlinear Analysis: Hybrid Systems (in press)
|
| 22 |
Yao C, Cassandras C G. A solution of the lot sizing problem as a stochastic resource contention game. In: Proceedings of the 49th IEEE Conference of Decision and Control . 2010, 6728-6733
doi: 10.1109/CDC.2010.5717766
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
