1932

Abstract

Optimal transport began as the problem of how to efficiently redistribute goods between production and consumers and evolved into a far-reaching geometric variational framework for studying flows of distributions on metric spaces. This theory enables a class of stochastic control problems to regulate dynamical systems so as to limit uncertainty to within specified limits. Representative control examples include the landing of a spacecraft aimed probabilistically toward a target and the suppression of undesirable effects of thermal noise on resonators; in both of these examples, the goal is to regulate the flow of the distribution of the random state. A most unlikely link turned up between transport of probability distributions and a maximum entropy inference problem posed by Erwin Schrödinger, where the latter is seen as an entropy-regularized version of the former. These intertwined topics of optimal transport, stochastic control, and inference are the subject of this review, which aims to highlight connections, insights, and computational tools while touching on quadratic regulator theory and probabilistic flows in discrete spaces and networks.

Loading

Article metrics loading...

/content/journals/10.1146/annurev-control-070220-100858
2021-05-03
2024-10-09
Loading full text...

Full text loading...

/deliver/fulltext/control/4/1/annurev-control-070220-100858.html?itemId=/content/journals/10.1146/annurev-control-070220-100858&mimeType=html&fmt=ahah

Literature Cited

  1. 1. 
    Fleming WH, Rishel RW. 1975. Deterministic and Stochastic Optimal Control New York: Springer
    [Google Scholar]
  2. 2. 
    Fleming WH, Soner HM. 2006. Controlled Markov Processes and Viscosity Solutions New York: Springer
    [Google Scholar]
  3. 3. 
    Blaquière A. 1992. Controllability of a Fokker-Planck equation, the Schrödinger system, and a related stochastic optimal control (revised version). Dyn. Control 2:235–53
    [Google Scholar]
  4. 4. 
    Brockett RW. 2007. Optimal control of the Liouville equation. AMS/IP Stud. Adv. Math. 39:23–35
    [Google Scholar]
  5. 5. 
    Brockett RW 2012. Notes on the control of the Liouville equation. Control of Partial Differential Equations P Cannarsa, J-M Coron101–29 Berlin: Springer
    [Google Scholar]
  6. 6. 
    Grigoriadis KM, Skelton RE. 1997. Minimum-energy covariance controllers. Automatica 33:569–78
    [Google Scholar]
  7. 7. 
    Zhu G, Grigoriadis KM, Skelton RE. 1995. Covariance control design for Hubble Space Telescope. J. Guid. Control Dyn. 18:230–36
    [Google Scholar]
  8. 8. 
    Collins E, Skelton R. 1985. Covariance control discrete systems. 1985 24th IEEE Conference on Decision and Control542–47 Piscataway, NJ: IEEE
    [Google Scholar]
  9. 9. 
    Chen Y, Georgiou TT, Pavon M. 2016. Optimal steering of a linear stochastic system to a final probability distribution, part I. IEEE Trans. Autom. Control 61:1158–69
    [Google Scholar]
  10. 10. 
    Chen Y, Georgiou TT, Pavon M. 2016. Optimal steering of a linear stochastic system to a final probability distribution, part II. IEEE Trans. Autom. Control 61:1170–80
    [Google Scholar]
  11. 11. 
    Halder A, Wendel EDB. 2016. Finite horizon linear quadratic Gaussian density regulator with Wasserstein terminal cost. 2016 American Control Conference7249–54 Piscataway, NJ: IEEE
    [Google Scholar]
  12. 12. 
    Chen Y, Georgiou TT, Pavon M. 2015. Optimal steering of inertial particles diffusing anisotropically with losses. 2015 American Control Conference1252–57 Piscataway, NJ: IEEE
    [Google Scholar]
  13. 13. 
    Chen Y, Georgiou TT, Pavon M. 2017. Optimal transport over a linear dynamical system. IEEE Trans. Autom. Control 62:2137–52
    [Google Scholar]
  14. 14. 
    Chen Y, Georgiou TT, Pavon M. 2018. Optimal steering of a linear stochastic system to a final probability distribution, part III. IEEE Trans. Autom. Control 63:3112–18
    [Google Scholar]
  15. 15. 
    Chen Y, Georgiou TT, Pavon M. 2016. On the relation between optimal transport and Schrödinger bridges: a stochastic control viewpoint. J. Optim. Theory Appl. 169:671–91
    [Google Scholar]
  16. 16. 
    Chen Y, Georgiou TT, Pavon M 2020. Stochastic control liaisons: Richard Sinkhorn meets Gaspard Monge on a Schrödinger bridge. arXiv:2005.10963 [math.OC]
    [Google Scholar]
  17. 17. 
    Chen Y 2016. Modeling and control of collective dynamics: from Schrödinger bridges to optimal mass transport PhD Thesis, Univ. Minn., Minneapolis
    [Google Scholar]
  18. 18. 
    Bakolas E. 2016. Optimal covariance control for discrete-time stochastic linear systems subject to constraints. 2016 IEEE 55th Conference on Decision and Control1153–58 Piscataway, NJ: IEEE
    [Google Scholar]
  19. 19. 
    Bakolas E. 2018. Constrained minimum variance control for discrete-time stochastic linear systems. Syst. Control Lett. 113:109–16
    [Google Scholar]
  20. 20. 
    Ridderhof J, Okamoto K, Tsiotras P. 2019. Nonlinear uncertainty control with iterative covariance steering. 2019 IEEE 58th Conference on Decision and Control3484–90 Piscataway, NJ: IEEE
    [Google Scholar]
  21. 21. 
    Ridderhof J, Tsiotras P 2019. Minimum-fuel powered descent in the presence of random disturbances Paper presented at the AIAA Scitech 2019 Forum, San Diego, CA, Jan. 11–19. https://doi.org/10.2514/6.2019-0646
    [Google Scholar]
  22. 22. 
    Okamoto K, Goldshtein M, Tsiotras P. 2018. Optimal covariance control for stochastic systems under chance constraints. IEEE Control Syst. Lett. 2:266–71
    [Google Scholar]
  23. 23. 
    Chen Y, Georgiou TT, Pavon M, Tannenbaum A. 2016. Robust transport over networks. IEEE Trans. Autom. Control 62:4675–82
    [Google Scholar]
  24. 24. 
    Carrillo JA, Choi YP, Hauray M 2014. The derivation of swarming models: mean-field limit and Wasserstein distances. Collective Dynamics from Bacteria to Crowds A Muntean, F Toschi1–46 Vienna: Springer
    [Google Scholar]
  25. 25. 
    Monge G. 1781. Mémoire sur la théorie des déblais et des remblais Paris: De l'Imprimerie Royale
    [Google Scholar]
  26. 26. 
    Villani C. 2003. Topics in Optimal Transportation Providence, RI: Am. Math. Soc.
    [Google Scholar]
  27. 27. 
    Kantorovich LV. 1942. On the transfer of masses. Dokl. Akad. Nauk. SSSR 37:227–29
    [Google Scholar]
  28. 28. 
    Brenier Y. 1991. Polar factorization and monotone rearrangement of vector-valued functions. Commun. Pure Appl. Math. 44:375–417
    [Google Scholar]
  29. 29. 
    Villani C. 2008. Optimal Transport: Old and New Berlin: Springer
    [Google Scholar]
  30. 30. 
    Jordan R, Kinderlehrer D, Otto F. 1998. The variational formulation of the Fokker–Planck equation. SIAM J. Math. Anal. 29:1–17
    [Google Scholar]
  31. 31. 
    Otto F. 2001. The geometry of dissipative evolution equations: the porous medium equation. Commun. Partial Differ. Equ. 26:101–74
    [Google Scholar]
  32. 32. 
    Ambrosio L, Gigli N, Savaré G. 2006. Gradient Flows: In Metric Spaces and in the Space of Probability Measures Basel, Switz.: Birkhäuser
    [Google Scholar]
  33. 33. 
    Schrödinger E. 1931. Über die Umkehrung der Naturgesetze. Sitzungsber. Preuss Akad. Wissen. Phys. Math. Klasse Sonderausg. 9:144–53
    [Google Scholar]
  34. 34. 
    Schrödinger E. 1932. Sur la théorie relativiste de l'électron et l'interprétation de la mécanique quantique. Ann. Inst. Henri Poincaré 2:269–310
    [Google Scholar]
  35. 35. 
    Föllmer H 1988. Random fields and diffusion processes. École d'Été de Probabilités de Saint-Flour XV–XVII, 1985–87 PL Hennequin101–203 Berlin: Springer
    [Google Scholar]
  36. 36. 
    Léonard C. 2014. A survey of the Schrödinger problem and some of its connections with optimal transport. Discrete Contin. Dyn. Syst. A 34:1533–74
    [Google Scholar]
  37. 37. 
    Fortet R. 1940. Résolution d'un système d'équations de M. Schrödinger. J. Math. Pures Appl. 9:83–105
    [Google Scholar]
  38. 38. 
    Beurling A. 1960. An automorphism of product measures. Ann. Math. 72:189–200
    [Google Scholar]
  39. 39. 
    Jamison B. 1974. Reciprocal processes. Z. Wahrscheinlichkeitstheor. Verw. Geb. 30:65–86
    [Google Scholar]
  40. 40. 
    Essid M, Pavon M. 2019. Traversing the Schrödinger bridge strait: Robert Fortet's marvelous proof redux. J. Optim. Theory Appl. 181:23–60
    [Google Scholar]
  41. 41. 
    Chen Y, Georgiou TT, Pavon M. 2016. Entropic and displacement interpolation: a computational approach using the Hilbert metric. SIAM J. Appl. Math. 76:2375–96
    [Google Scholar]
  42. 42. 
    Benamou JD, Brenier Y. 2000. A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numer. Math. 84:375–93
    [Google Scholar]
  43. 43. 
    Rockafellar RT. 1970. Convex Analysis Princeton, NJ: Princeton Univ. Press
    [Google Scholar]
  44. 44. 
    Karatzas I, Shreve S. 1988. Brownian Motion and Stochastic Calculus New York: Springer
    [Google Scholar]
  45. 45. 
    Dai Pra P. 1991. A stochastic control approach to reciprocal diffusion processes. Appl. Math. Optim. 23:313–29
    [Google Scholar]
  46. 46. 
    Gentil I, Léonard C, Ripani L 2015. About the analogy between optimal transport and minimal entropy. arXiv:1510.08230 [math.PR]
    [Google Scholar]
  47. 47. 
    Carlen E 2006. Stochastic mechanics: a look back and a look ahead. Diffusion, Quantum Theory and Radically Elementary Mathematics WG Faris117–39 Princeton, NJ: Princeton Univ. Press
    [Google Scholar]
  48. 48. 
    Mikami T. 2004. Monge's problem with a quadratic cost by the zero-noise limit of h-path processes. Probab. Theory Relat. Fields 129:245–60
    [Google Scholar]
  49. 49. 
    Mikami T, Thieullen M. 2008. Optimal transportation problem by stochastic optimal control. SIAM J. Control Optim. 47:1127–39
    [Google Scholar]
  50. 50. 
    Léonard C. 2012. From the Schrödinger problem to the Monge–Kantorovich problem. J. Funct. Anal. 262:1879–920
    [Google Scholar]
  51. 51. 
    Chen Y, Georgiou TT, Pavon M. 2015. Fast cooling for a system of stochastic oscillators. J. Math. Phys. 56:113302
    [Google Scholar]
  52. 52. 
    Chen Y, Georgiou TT, Pavon M. 2015. Steering state statistics with output feedback. 2015 54th IEEE Conference on Decision and Control6502–507 Piscataway, NJ: IEEE
    [Google Scholar]
  53. 53. 
    Chen Y, Georgiou TT, Pavon M. 2019. Covariance steering in zero-sum linear-quadratic two-player differential games. 2019 58th IEEE Conference on Decision and Control8204–9 Piscataway, NJ: IEEE
    [Google Scholar]
  54. 54. 
    Ciccone V, Chen Y, Georgiou TT, Pavon M 2020. Regularized transport between singular covariance matrices. arXiv:2006.10000 [math.OC]
    [Google Scholar]
  55. 55. 
    Georgiou TT. 2002. The structure of state covariances and its relation to the power spectrum of the input. IEEE Trans. Autom. Control 47:1056–66
    [Google Scholar]
  56. 56. 
    Chen Y, Georgiou TT, Pavon M. 2018. Steering the distribution of agents in mean-field games system. J. Optim. Theory Appl. 179:332–57
    [Google Scholar]
  57. 57. 
    Yi Z, Cao Z, Theodorou E, Chen Y 2020. Nonlinear covariance control via differential dynamic programming. In 2020 American Control Conferencepp. 357176 Piscataway, NJ: IEEE
    [Google Scholar]
  58. 58. 
    Bakshi K, Fan DD, Theodorou EA 2018. Schrödinger approach to optimal control of large-size populations. arXiv:1810.06064 [math.OC]
    [Google Scholar]
  59. 59. 
    Hörmander L. 1967. Hypoelliptic second order differential equations. Acta Math. 119:147–71
    [Google Scholar]
  60. 60. 
    Kappen HJ. 2005. Path integrals and symmetry breaking for optimal control theory. J. Stat. Mech. Theory Exp. 2005:P11011
    [Google Scholar]
  61. 61. 
    Kappen HJ. 2005. Linear theory for control of nonlinear stochastic systems. Phys. Rev. Lett. 95:200201
    [Google Scholar]
  62. 62. 
    Theodorou E, Buchli J, Schaal S. 2010. A generalized path integral control approach to reinforcement learning. J. Mach. Learn. Res. 11:3137–81
    [Google Scholar]
  63. 63. 
    Theodorou EA, Todorov E. 2012. Relative entropy and free energy dualities: connections to path integral and KL control. 2012 51st IEEE Conference on Decision and Control1466–73 Piscataway, NJ: IEEE
    [Google Scholar]
  64. 64. 
    Caluya KF, Halder A 2019. Wasserstein proximal algorithms for the Schrödinger bridge problem: density control with nonlinear drift. arXiv:1912.01244 [math.OC]
    [Google Scholar]
  65. 65. 
    Elamvazhuthi K, Liu S, Li W, Osher S 2020. Optimal transport of nonlinear control-affine systems. Work. Pap. https://www.researchgate.net/publication/340271497_Dynamical_Optimal_Transport_of_Nonlinear_Control-Affine_Systems
  66. 66. 
    Chen Y, Georgiou TT, Pavon M, Tannenbaum A. 2017. Efficient robust routing for single commodity network flows. IEEE Trans. Autom. Control 63:2287–94
    [Google Scholar]
  67. 67. 
    Chen Y, Georgiou TT, Pavon M, Tannenbaum A. 2019. Relaxed Schrödinger bridges and robust network routing. IEEE Trans. Control Netw. Syst. 7:923–31
    [Google Scholar]
  68. 68. 
    Todorov E 2007. Linearly-solvable Markov decision problems. Advances in Neural Information Processing Systems 19 B Schölkopf, JC Platt, T Hoffman1369–76 Cambridge, MA: MIT Press
    [Google Scholar]
  69. 69. 
    Todorov E. 2009. Efficient computation of optimal actions. PNAS 106:11478–83
    [Google Scholar]
  70. 70. 
    Todorov E 2009. Compositionality of optimal control laws. Advances in Neural Information Processing Systems 22 Y Bengio, D Schuurmans, JD Lafferty, CKI Williams, A Culotta1856–64 Red Hook, NY: Curran
    [Google Scholar]
  71. 71. 
    Ruelle D. 2004. Thermodynamic Formalism: The Mathematical Structure of Equilibrium Statistical Mechanics Cambridge, UK: Cambridge Univ. Press
    [Google Scholar]
  72. 72. 
    Delvenne JC, Libert AS. 2011. Centrality measures and thermodynamic formalism for complex networks. Phys. Rev. E 83:046117
    [Google Scholar]
  73. 73. 
    Georgiou TT, Karlsson J, Takyar MS. 2008. Metrics for power spectra: an axiomatic approach. IEEE Trans. Signal Process. 57:859–67
    [Google Scholar]
  74. 74. 
    Karlsson J, Ringh A. 2017. Generalized sinkhorn iterations for regularizing inverse problems using optimal mass transport. SIAM J. Imaging Sci. 10:1935–62
    [Google Scholar]
  75. 75. 
    Chen Y, Karlsson J. 2018. State tracking of linear ensembles via optimal mass transport. IEEE Control Syst. Lett. 2:260–65
    [Google Scholar]
  76. 76. 
    Reich S 2018. Data assimilation: the Schrödinger perspective. arXiv:1807.08351 [math.NA]
    [Google Scholar]
  77. 77. 
    Taghvaei A, Mehta PG 2019. An optimal transport formulation of the ensemble Kalman filter. arXiv:1910.02338 [eess.SY]
    [Google Scholar]
  78. 78. 
    Elvander F, Haasler I, Jakobsson A, Karlsson J. 2020. Multi-marginal optimal transport using partial information with applications in robust localization and sensor fusion. Signal Process. 171:107474
    [Google Scholar]
  79. 79. 
    Haasler I, Ringh A, Chen Y, Karlsson J 2020. Multi-marginal optimal transport and Schrödinger bridges on trees. arXiv:2004.06909 [math.OC]
    [Google Scholar]
  80. 80. 
    Singh R, Haasler I, Zhang Q, Karlsson J, Chen Y 2020. Inference with aggregate data: an optimal transport approach. arXiv:2003.13933 [cs.LG]
    [Google Scholar]
  81. 81. 
    Zhai H, Egerstedt M, Zhou H 2019. Path planning in unknown environments using optimal transport theory. arXiv:1909.11235 [math.OC]
    [Google Scholar]
  82. 82. 
    Krishnan V, Martínez S. 2018. Distributed optimal transport for the deployment of swarms. 2018 IEEE Conference on Decision and Control4583–88 Piscataway, NJ: IEEE
    [Google Scholar]
  83. 83. 
    Wakolbinger A 1992. Schrödinger bridges from 1931 to 1991. Proceedings of the 4th Latin American Congress in Probability and Mathematical Statistics, Mexico City 199061–79 Contrib. Probab. Estad. Mat. 3
    [Google Scholar]
  84. 84. 
    Cuturi M 2013. Sinkhorn distances: lightspeed computation of optimal transport. Advances in Neural Information Processing Systems 26 CJC Burges, L Bottou, M Welling, Z Ghahramani, KQ Weinberger2292–300 Red Hook, NY: Curran
    [Google Scholar]
  85. 85. 
    Okamoto K, Tsiotras P. 2019. Input hard constrained optimal covariance steering. 2019 IEEE 58th Annual Conference on Decision and Control3497–502 Piscataway, NJ: IEEE
    [Google Scholar]
  86. 86. 
    Pavon M, Triglia G, Tabak EG 2021. The data-driven Schrödinger bridge. Commun. Pure Appl. Math https://doi.org/10.1002/cpa.21975
    [Google Scholar]
  87. 87. 
    Cullen M, Gangbo W. 2001. A variational approach for the 2-dimensional semi-geostrophic shallow water equations. Arch. Ration. Mech. Anal. 156:241–73
    [Google Scholar]
  88. 88. 
    Cheng J, Cullen M, Feldman M. 2018. Classical solutions to semi-geostrophic system with variable Coriolis parameter. Arch. Ration. Mech. Anal. 227:215–72
    [Google Scholar]
  89. 89. 
    Ning L, Carli FP, Ebtehaj AM, Foufoula-Georgiou E, Georgiou TT. 2014. Coping with model error in variational data assimilation using optimal mass transport. Water Resour. Res. 50:5817–30
    [Google Scholar]
  90. 90. 
    Angenent S, Pichon E, Tannenbaum A. 2006. Mathematical methods in medical image processing. Bull. Am. Math. Soc. 43:365–96
    [Google Scholar]
  91. 91. 
    Peyré G, Cuturi M. 2019. Computational optimal transport: with applications to data science. Found. Trends Mach. Learn. 11:355–607
    [Google Scholar]
  92. 92. 
    Santambrogio F. 2015. Optimal Transport for Applied Mathematicians Basel, Switz.: Birkhäuser
    [Google Scholar]
  93. 93. 
    Kolouri S, Park SR, Thorpe M, Slepcev D, Rohde GK. 2017. Optimal mass transport: signal processing and machine-learning applications. IEEE Signal Process. Mag. 34:443–59
    [Google Scholar]
/content/journals/10.1146/annurev-control-070220-100858
Loading
/content/journals/10.1146/annurev-control-070220-100858
Loading

Data & Media loading...

  • Article Type: Review Article
This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error