Perturbation analysis of stochastic hybrid systems and applications to resource contention games

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

References

[1] Cassandras C G, Lygeros J. Stochastic Hybrid Systems. London: Taylor and Francis Group/CRC Press, 2006

[2] Cassandras C G, Lafortune S. Introduction to Discrete Event Systems. 2nd ed. New York, NY: Springer, 2008

[3] Ho Y C, Cao X R. Perturbation Analysis of Discrete Event Dynamic Systems. Boston, MA: Kluwer Academic Publisher, 1991

[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

[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

[9] Yu H, Cassandras C G. Perturbation analysis of feedbackcontrolled stochastic flow systems. IEEE Transactions on Automatic Control, 2004, 49(8): 1317-1332

[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

[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

[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

[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

[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

[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

[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

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg