Article
Full entry |
PDF
(3.5 MB)
Feedback
PDF
(3.5 MB)
Feedback
Keywords:
idempotent; max-plus; tropical; network; dynamic programming; game theory; command and control
idempotent; max-plus; tropical; network; dynamic programming; game theory; command and control
Summary:
A game is considered where the communication network of the first player is explicitly modelled. The second player may induce delays in this network, while the first player may counteract such actions. Costs are modelled through expectations over idempotent probability measures. The idempotent probabilities are conditioned by observational data, the arrival of which may have been delayed along the communication network. This induces a game where the state space consists of the network delays. Even for small networks, the state-space dimension is high. Idempotent algebra-based methods are used to generate an algorithm not subject to the curse-of-dimensionality. An example is included.
References:
[1] Akian, M.: Densities of idempotent measures and large deviations. Trans. Amer. Math. Soc. 351 (1999), 4515-4543. DOI 10.1090/s0002-9947-99-02153-4 | MR 1466943 | Zbl 0934.28005
[2] Akian, M., Gaubert, S., Lakhoua, A.: The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis. SIAM J. Control Optim. 47 (2008), 817-848. DOI 10.1137/060655286 | MR 2385864 | Zbl 1157.49034
[3] Baccelli, F. L., Cohen, G., Olsder, G. J., Quadrat, J.-P.: Synchronization and Linearity. Wiley, New York 1992. MR 1204266 | Zbl 0824.93003
[4] Cohen, G., Gaubert, S., Quadrat, J.-P.: Duality and separation theorems in idempotent semimodules. Linear Algebra Appl. 379 (2004), 395-422. DOI 10.1016/j.laa.2003.08.010 | MR 2039751 | Zbl 1042.46004
[5] Elliot, N. J., Kalton, N. J.: The existence of value in differential games. Mem. Amer. Math. Soc. 126 (1972). DOI 10.1090/memo/0126 | MR 0359845
[6] Fleming, W. H.: Max-plus stochastic processes. Appl. Math. Optim. 49 (2004), 159-181. DOI 10.1007/s00245-003-0785-3 | MR 2033833 | Zbl 1138.93379
[7] Fleming, W. H., Kaise, H., Sheu, S.-J.: Max-plus stochastic control and risk-sensitivity. Applied Math. Optim. 62 (2010), 81-144. DOI 10.1007/s00245-010-9097-6 | MR 2653896 | Zbl 1197.49029
[8] Gaubert, S., McEneaney, W. M.: Min-max spaces and complexity reduction in min-max expansions. Applied Math. Optim. 65 (2012), 315-348. DOI 10.1007/s00245-011-9158-5 | MR 2902695 | Zbl 1244.93051
[9] Gaubert, S., Qu, Z., Sridharan, S.: Bundle-based pruning in the max-plus curse of dimensionality free method. In: Proc. 21st Int. Symp. Math. Theory of Networks and Systems 2014.
[10] Heidergott, B., Olsder, G. J., Woude, J. van der: Max-Plus at Work: Modeling and Analysis of Synchronized Systems. Princeton Univ. Press 2006. DOI 10.1515/9781400865239 | MR 2188299
[11] Kolokoltsov, V. N., Maslov, V. P.: Idempotent Analysis and Its Applications. Kluwer 1997. DOI 10.1007/978-94-015-8901-7 | MR 1447629 | Zbl 0941.93001
[12] Litvinov, G. L., Maslov, V. P., Shpiz, G. B.: Idempotent functional analysis: an algebraic approach. Math. Notes 69 (2001), 696-729. DOI 10.1023/a:1010266012029 | MR 1846814 | Zbl 1017.46034
[13] McEneaney, W. M.: Distributed dynamic programming for discrete-time stochastic control, and idempotent algorithms. Automatica 47 (2011), 443-451. DOI 10.1016/j.automatica.2010.10.006 | MR 2878297 | Zbl 1219.93146
[14] McEneaney, W. M.: Max-Plus Methods for Nonlinear Control and Estimation. Birk\-hau\-ser, Boston 2006. DOI 10.1007/0-8176-4453-9 | MR 2189436 | Zbl 1103.93005
[15] McEneaney, W. M.: A curse-of-dimensionality-free numerical method for solution of certain HJB PDEs. SIAM J. Control Optim. 46 (2007), 1239-1276. DOI 10.1137/040610830 | MR 2346381 | Zbl 1251.65168
[16] McEneaney, W. M.: Idempotent method for deception games. In: Proc. 2011 Amer. Control Conf., pp. 4051-4056. DOI 10.1109/acc.2011.5990870
[17] McEneaney, W. M., Desir, A.: Games of network disruption and idempotent algorithms. In: Proc. European Control Conf. 2013, pp. 702-709.
[18] McEneaney, W. M.: Idempotent algorithms for discrete-time stochastic control through distributed dynamic programming. In: Proc. IEEE CDC 2009, pp. 1569-1574. DOI 10.1109/cdc.2009.5400306
[19] McEneaney, W. M., Charalambous, C. D.: Large deviations theory, induced log-plus and max-plus measures and their applications. In: Proc. Math. Theory Networks and Sys. 2000.
[20] Nitica, V., Singer, I.: Max-plus convex sets and max-plus semispaces I. Optimization 56 (2007) 171-205. DOI 10.1080/02331930600819852 | MR 2288512 | Zbl 1121.52002
[21] Puhalskii, A.: Large Deviations and Idempotent Probability. Chapman and Hall/CRC Press 2001. DOI 10.1201/9781420035803 | MR 1851048 | Zbl 0983.60003
[22] Qu, Z.: A max-plus based randomized algorithm for solving a class of HJB PDEs. In: Proc. 53rd IEEE Conf. on Dec. and Control 2014. DOI 10.1109/cdc.2014.7039624
[23] Rubinov, A. M., Singer, I.: Topical and sub-topical functions, downward sets and abstract convexity. Optimization 50 (2001), 307-351. DOI 10.1080/02331930108844567 | MR 1892908 | Zbl 1007.26010
[24] Singer, I.: Abstract Convex Analysis. Wiley-Interscience, New York 1997. MR 1461544 | Zbl 0941.49020
Search
Partner of
