Figure 1.
Approximation of infinitesimal generator $A$ . The entry $A_{ij}$ is proportional to flux across $B_i\cap B_j$ from $B_i$ to $B_j$ , due to vector field $f$ .
- Previous Article
- JCD Home
- This Issue
-
Next Article
Balanced model order reduction for linear random dynamical systems driven by Lévy noise
June & December 2018, 5(1&2): 1-32.
doi: 10.3934/jcd.2018001
Optimal transport over nonlinear systems via infinitesimal generators on graphs
| 1. | School for Engineering of Matter, Transport and Energy, Arizona State University, Tempe, AZ 85281, USA |
| 2. | Mitsubishi Electric Research Labs, 201 Broadway, Cambridge, MA 02139, USA |
We present a set-oriented graph-based computational framework for continuous-time optimal transport over nonlinear dynamical systems. We recover provably optimal control laws for steering a given initial distribution in phase space to a final distribution in prescribed finite time for the case of non-autonomous nonlinear control-affine systems, while minimizing a quadratic control cost. The resulting control law can be used to obtain approximate feedback laws for individual agents in a swarm control application. Using infinitesimal generators, the optimal control problem is reduced to a modified Monge-Kantorovich optimal transport problem, resulting in a convex Benamou-Brenier type fluid dynamics formulation on a graph. The well-posedness of this problem is shown to be a consequence of the graph being strongly-connected, which in turn is shown to result from controllability of the underlying dynamical system. Using our computational framework, we study optimal transport of distributions where the underlying dynamical systems are chaotic, and non-holonomic. The solutions to the optimal transport problem elucidate the role played by invariant manifolds, lobe-dynamics and almost-invariant sets in efficient transport of distributions in finite time. Our work connects set-oriented operator-theoretic methods in dynamical systems with optimal mass transportation theory, and opens up new directions in design of efficient feedback control strategies for nonlinear multi-agent and swarm systems operating in nonlinear ambient flow fields.
Mathematics Subject Classification:
Primary: 93C10, 47D03, 37M99; Secondary: 93C20.
Citation:
Karthik Elamvazhuthi, Piyush Grover. Optimal transport over nonlinear systems via infinitesimal generators on graphs. Journal of Computational Dynamics,
2018, 5
(1&2)
: 1-32.
doi: 10.3934/jcd.2018001
![]()
References:
| [1] |
Intel Inc, Intel Xeon Processor X5690 https://ark.intel.com/products/52576/Intel-Xeon-Processor-X5690-12M-Cache-3_46-GHz-6_40-GTs-Intel-QPI, [Online; accessed 19-March-2018]. |
| [2] |
A. Agrachev and P. Lee,
Optimal transportation under nonholonomic constraints, Transactions of the American Mathematical Society, 361 (2009), 6019-6047.
doi: 10.1090/S0002-9947-09-04813-2. |
| [3] |
A. A. Agrachev and Y. Sachkov, Control Theory from the Geometric Viewpoint, Springer-Verlag, Berlin, 2004.
doi: 10.1007/978-3-662-06404-7. |
| [4] |
M. Aicardi, G. Casalino, A. Bicchi and A. Balestrino,
Closed loop steering of unicycle like vehicles via Lyapunov techniques, IEEE Robotics & Automation Magazine, 2 (1995), 27-35.
doi: 10.1109/100.388294. |
| [5] |
L. Ambrosio, N. Gigli and G. Savaré, Gradient Flows: In Metric Spaces and in the Space of Probability Measures, Springer Science & Business Media, 2008. |
| [6] |
J.-D. Benamou and Y. Brenier,
A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numerische Mathematik, 84 (2000), 375-393.
doi: 10.1007/s002110050002. |
| [7] |
S. Berman, Á. Halász, M. Ani Hsieh and V. Kumar,
Optimized stochastic policies for task allocation in swarms of robots, IEEE Transactions on Robotics, 25 (2009), 927-937.
doi: 10.1109/TRO.2009.2024997. |
| [8] |
P. Bernard and B. Buffoni,
Optimal mass transportation and mather theory, J. Eur. Math. Soc. (JEMS), 9 (2007), 85-121, math/0412299.
doi: 10.4171/JEMS/74. |
| [9] |
A. Bloch, J. Baillieul, P. Crouch, J. E. Marsden, P. S. Krishnaprasad, R. M. Murray and D. Zenkov, Nonholonomic Mechanics and Control, vol. 24, Springer, 2003.
doi: 10.1007/b97376. |
| [10] |
E. M. Bollt and N. Santitissadeekorn, Applied and Computational Measurable Dynamics, vol. 18, SIAM, 2013.
doi: 10.1137/1.9781611972641. |
| [11] |
P. Boyland, H. Aref and M. Stremler,
Topological fluid mechanics of stirring, Journal of Fluid Mechanics, 403 (2000), 277-304.
doi: 10.1017/S0022112099007107. |
| [12] |
M. Budišić, R. Mohr and I. Mezić, Applied koopmanism, Chaos: An Interdisciplinary Journal of Nonlinear Science, 22 (2012), 047510, 33pp.
doi: 10.1063/1.4772195. |
| [13] |
A. Chapman and M. Mesbahi,
Advection on graphs, 2011 50th IEEE Conference on Decision and Control and European Control Conference, IEEE, (2011), 1461-1466.
doi: 10.1109/CDC.2011.6161471. |
| [14] |
U. K. Cheang, K. Lee, A. A. Julius and M. J. Kim, Multiple-robot drug delivery strategy through coordinated teams of microswimmers, Applied Physics Letters, 105 (2014), 083705.
doi: 10.1063/1.4893695. |
| [15] |
Y. Chen, T. T. Georgiou and M. Pavon,
On the relation between optimal transport and Schrödinger bridges: A stochastic control viewpoint, Journal of Optimization Theory and Applications, 169 (2016), 671-691.
doi: 10.1007/s10957-015-0803-z. |
| [16] |
____,
Optimal transport over a linear dynamical system, IEEE Transactions on Automatic Control, 62 (2017), 2137-2152.
doi: 10.1109/TAC.2016.2602103. |
| [17] |
M. Dellnitz, G. Froyland and O. Junge, The algorithms behind GAIO - set oriented numerical methods for dynamical systems, Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems (B. Fiedler, ed. ), Springer, Berlin-Heidelberg-New York, 2001,145-174. |
| [18] |
M. Dellnitz, O. Junge, W. S. Koon, F. Lekien, M. W. Lo, J. E. Marsden, K. Padberg, R. Preis, S. D. Ross and B. Thiere,
Transport in dynamical astronomy and multibody problems, Int. J. Bifurc. Chaos, 15 (2005), 699-727.
doi: 10.1142/S0218127405012545. |
| [19] |
M. Dellnitz and O. Junge,
On the approximation of complicated dynamical behavior, SIAM Journal on Numerical Analysis, 36 (1998), 491-515.
doi: 10.1137/S0036142996313002. |
| [20] |
J. Eckstein and W. Yao, Augmented Lagrangian and alternating direction methods for convex optimization: A tutorial and some illustrative computational results, RUTCOR Research Reports, 32 (2012). |
| [21] |
K. Elamvazhuthi and S. Berman,
Optimal control of stochastic coverage strategies for robotic swarms, 2015 IEEE International Conference on Robotics and Automation (ICRA), IEEE, (2015), 1822-1829.
doi: 10.1109/ICRA.2015.7139435. |
| [22] |
K. Elamvazhuthi, V. Deshmukh, M. Kawski and S. Berman, Mean-field controllability and decentralized stabilization of Markov chains, part ⅰ: Global controllability and rational feedbacks, arXiv preprint, arXiv: 1703.08243, (2017). |
| [23] |
D. L. Elliott, Bilinear Control Systems: Matrices in Action, vol. 169, Springer Science & Business Media, 2009.
doi: 10.1023/b101451. |
| [24] |
K.-J. Engel and R. Nagel, One-parameter Semigroups for Linear Evolution Equations vol. 194, Springer-Verlag, New York, 2000. |
| [25] |
H. O. Fattorini, The Cauchy Problem, vol. 13517, Encyclopedia of Mathematics and its Applications, 18. Addison-Wesley Publishing Co., Reading, Mass., 1983. |
| [26] |
A. Figalli and L. Rifford,
Mass transportation on sub-riemannian manifolds, Geometric And Functional Analysis, 20 (2010), 124-159.
doi: 10.1007/s00039-010-0053-z. |
| [27] |
M. D. Finn and J.-L. Thiffeault,
Topological optimization of rod-stirring devices, SIAM Review, 53 (2011), 723-743.
doi: 10.1137/100791828. |
| [28] |
G. Froyland and M. Dellnitz,
Detecting and locating near-optimal almost-invariant sets and cycles, SIAM Journal on Scientific Computing, 24 (2003), 1839-1863.
doi: 10.1137/S106482750238911X. |
| [29] |
G. Froyland and K. Padberg,
Almost-invariant sets and invariant manifolds - connecting probabilistic and geometric descriptions of coherent structures in flows, Physica D, 238 (2009), 1507-1523.
doi: 10.1016/j.physd.2009.03.002. |
| [30] |
G. Froyland, N. Santitissadeekorn and A. Monahan, Transport in time-dependent dynamical systems: Finite-time coherent sets, Chaos, 20 (2010), 043116, 10pp.
doi: 10.1063/1.3502450. |
| [31] |
G. Froyland,
Dynamic isoperimetry and the geometry of Lagrangian coherent structures, Nonlinearity, 28 (2015), 3587-3622.
doi: 10.1088/0951-7715/28/10/3587. |
| [32] |
G. Froyland, C. González-Tokman and T. M. Watson,
Optimal mixing enhancement by local perturbation, SIAM Review, 58 (2016), 494-513.
doi: 10.1137/15M1023221. |
| [33] |
G. Froyland, O. Junge and P. Koltai,
Estimating long-term behavior of flows without trajectory integration: The infinitesimal generator approach, SIAM Journal on Numerical Analysis, 51 (2013), 223-247.
doi: 10.1137/110819986. |
| [34] |
G. Froyland and N. Santitissadeekorn, Optimal mixing enhancement, SIAM J. Appl. Math., 77 (2017), 1444-1470, arXiv: 1610.01651.
doi: 10.1137/16M1091496. |
| [35] |
A. Ghosh and P. Fischer,
Controlled propulsion of artificial magnetic nanostructured propellers, Nano letters, 9 (2009), 2243-2245.
doi: 10.1021/nl900186w. |
| [36] |
N. Gigli and J. Maas,
Gromov-hausdorff convergence of discrete transportation metrics, SIAM Journal on Mathematical Analysis, 45 (2013), 879-899.
doi: 10.1137/120886315. |
| [37] |
R. Gilmore,
Topological analysis of chaotic dynamical systems, Reviews of Modern Physics, 70 (1998), 1455-1529.
doi: 10.1103/RevModPhys.70.1455. |
| [38] |
M. Grant, S. Boyd and Y. Ye, CVX: Matlab software for disciplined convex programming, Global Optimization, Nonconvex Optim. Appl., Springer, New York, 84 (2006), 155-210.
doi: 10.1007/0-387-30528-9_7. |
| [39] |
P. Grover and K. Elamvazhuthi,
Optimal perturbations for nonlinear systems using graph-based optimal transport, Communications in Nonlinear Science and Numerical Simulation, 59 (2018), 197-215.
doi: 10.1016/j.cnsns.2017.09.020. |
| [40] |
P. Grover, S. D. Ross, M. A. Stremler and P. Kumar, Topological chaos, braiding and bifurcation of almost-cyclic sets, Chaos: An Interdisciplinary Journal of Nonlinear Science, 22 (2012), 043135, 16pp.
doi: 10.1063/1.4768666. |
| [41] |
G. Haller,
Lagrangian coherent structures, Annual Review of Fluid Mechanics, 47 (2015), 137-162.
|
| [42] |
D. Damir Harabor, A. Grastien, et al., Online graph pruning for pathfinding on grid maps, AAAI, 2011. |
| [43] |
A. Hindawi, J.-B. Pomet and L. Rifford,
Mass transportation with LQ cost functions, Acta Applicandae Mathematicae, 113 (2011), 215-229.
doi: 10.1007/s10440-010-9595-1. |
| [44] |
S. Jerg, O. Junge and M. Post,
Global optimal feedbacks for stochastic quantized nonlinear event systems, AIMS, 1 (2014), 163-176.
doi: 10.3934/jcd.2014.1.163. |
| [45] |
O. Junge and H. M. Osinga,
A set oriented approach to global optimal control, ESAIM: Control, Optimisation and Calculus of Variations, 10 (2004), 259-270.
doi: 10.1051/cocv:2004006. |
| [46] |
E. W. Justh and P. S. Krishnaprasad, Optimality, reduction and collective motion, Proc. R. Soc. A, The Royal Society, 471 (2015), 20140606, 22pp.
doi: 10.1098/rspa.2014.0606. |
| [47] |
E. Kirillova and K. Spindler,
Optimal control of a vehicle during parking, 2004 IFAC Symposium on Nonlinear Control Systems (NOLCOS), 37 (2004), 925-930.
doi: 10.1016/S1474-6670(17)31344-7. |
| [48] |
W. S. Koon, M. Lo, J. E. Marsden and S. D. Ross, Dynamical Systems, The Three-Body Problem and Space Mission Design, Marsden Books, 2008. |
| [49] |
P. S. Krishnaprasad, Optimal Control and Poisson Reduction, Tech. report, DTIC Document, 1993. |
| [50] |
A. Lasota and M. Mackey, Chaos, Fractals and Noise, Springer-Verlag, New York, 1994.
doi: 10.1007/978-1-4612-4286-4. |
| [51] |
J. B. Lasserre, D. Henrion, C. Prieur and E. Trélat,
Nonlinear optimal control via occupation measures and LMI-relaxations, SIAM Journal on Control and Optimization, 47 (2008), 1643-1666.
doi: 10.1137/070685051. |
| [52] |
F. Lekien and C. Coulliette,
Chaotic stirring in quasi-turbulent flows, Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 365 (2007), 3061-3084.
doi: 10.1098/rsta.2007.0020. |
| [53] |
P. F. J. Lermusiaux, T. Lolla, P. J. Haley Jr, K. Yigit, M. P. Ueckermann, T. Sondergaard and W. G. Leslie,
Science of Autonomy: Time-optimal Path Planning and Adaptive Sampling for Swarms of Ocean Vehicles, Springer Handbook of Ocean Engineering: Autonomous Ocean Vehicles, Subsystems and Control, (2015), 481-498.
doi: 10.1007/978-3-319-16649-0_21. |
| [54] |
J. Maas,
Gradient flows of the entropy for finite markov chains, Journal of Functional Analysis, 261 (2011), 2250-2292.
doi: 10.1016/j.jfa.2011.06.009. |
| [55] |
J. D. Meiss,
Symplectic maps, variational principles, and transport, Rev. Mod. Phys., 64 (1992), 795-848.
doi: 10.1103/RevModPhys.64.795. |
| [56] |
I. Mezic,
Analysis of fluid flows via spectral properties of the Koopman operator, Annual Review of Fluid Mechanics, 45 (2013), 357-378.
doi: 10.1146/annurev-fluid-011212-140652. |
| [57] |
A. Mielke,
Geodesic convexity of the relative entropy in reversible markov chains, Calculus of Variations and Partial Differential Equations, 48 (2013), 1-31.
doi: 10.1007/s00526-012-0538-8. |
| [58] |
R. M. Murray and S. S. Sastry,
Nonholonomic motion planning: Steering using sinusoids, IEEE Transactions on Automatic Control, 38 (1993), 700-716.
doi: 10.1109/9.277235. |
| [59] |
B. O'Donoghue, E. Chu, N. Parikh and S. Boyd, Operator splitting for conic optimization via homogeneous self-dual embedding, Journal of Optimization Theory and Applications, 159 (2016), 1042-1068, arXiv: 1312.3039.
doi: 10.1007/s10957-016-0892-3. |
| [60] |
J. M. Ottino and S. Wiggins,
Introduction: Mixing in microfluidics, Philosophical Transactions: Mathematical, Physical and Engineering Sciences, 362 (2004), 923-935.
doi: 10.1098/rsta.2003.1355. |
| [61] |
N. Papadakis, G. Peyré and E. Oudet,
Optimal transport with proximal splitting, SIAM Journal on Imaging Sciences, 7 (2014), 212-238.
doi: 10.1137/130920058. |
| [62] |
K. E. Peyer, L. Zhang and B. J. Nelson,
Bio-inspired magnetic swimming microrobots for biomedical applications, Nanoscale, 5 (2013), 1259-1272.
doi: 10.1039/C2NR32554C. |
| [63] |
H. Poincaré, Les Méthodes Nouvelles de la Mécanique Céleste: Méthodes de mm. Newcomb, Glydén, Lindstedt et Bohlin, (French) Dover Publications, Inc., New York, N. Y., 1957. |
| [64] |
A. C. Poje and G. Haller,
Geometry of cross-stream mixing in a double-gyre ocean model, Journal of Physical Oceanography, 29 (1999), 1649-1665.
doi: 10.1175/1520-0485(1999)029<1649:GOCSMI>2.0.CO;2. |
| [65] |
A. Raghunathan and U. Vaidya,
Optimal stabilization using Lyapunov measures, IEEE Transactions on Automatic Control, 59 (2014), 1316-1321.
doi: 10.1109/TAC.2013.2289707. |
| [66] |
L. Rifford, Sub-riemannian Geometry and Optimal Transport, Springer, 2014.
doi: 10.1007/978-3-319-04804-8. |
| [67] |
S. D Ross, S. Jerg and O. Junge,
Optimal capture trajectories using multiple gravity assists, Communications in Nonlinear Science and Numerical Simulations, 14 (2009), 4168-4175.
doi: 10.1016/j.cnsns.2008.12.009. |
| [68] |
J. Sabuco, M. A. F. Sanjuán and J. A. Yorke, Dynamics of partial control, Chaos, 22 (2012), 047507, 9pp.
doi: 10.1063/1.4754874. |
| [69] |
C. Senatore and S. D. Ross,
Fuel-efficient navigation in complex flows, 2008 American Control Conference, IEEE, (2008), 1244-1248.
doi: 10.1109/ACC.2008.4586663. |
| [70] |
J. Solomon, R. Rustamov, L. Guibas and A. Butscher, Continuous-flow graph transportation distances, arXiv preprint, arXiv: 1603.06927, (2016). |
| [71] |
M. A. Stremler, S. D. Ross, P. Grover and P. Kumar, Topological chaos and periodic braiding of almost-cyclic sets, Physical Review Letters, 106 (2011), 114101. |
| [72] |
H. J Sussmann,
A general theorem on local controllability, SIAM Journal on Control and Optimization, 25 (1987), 158-194.
doi: 10.1137/0325011. |
| [73] |
P. Tallapragada and S. D. Ross,
A set oriented definition of finite-time Lyapunov exponents and coherent sets, Communications in Nonlinear Science and Numerical Simulation, 18 (2013), 1106-1126.
doi: 10.1016/j.cnsns.2012.09.017. |
| [74] |
J.-L. Thiffeault and M. D. Finn,
Topology, braids and mixing in fluids, Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 364 (2006), 3251-3266.
doi: 10.1098/rsta.2006.1899. |
| [75] |
S. M. Ulam, Problems in Modern Mathematics, Science Editions John Wiley & Sons, Inc., New York, 1964. |
| [76] |
U. Vaidya and P. G. Mehta,
Lyapunov measure for almost everywhere stability, IEEE Transactions on Automatic Control, 53 (2008), 307-323.
doi: 10.1109/TAC.2007.914955. |
| [77] |
U. Vaidya, P. G. Mehta and U. V. Shanbhag,
Nonlinear stabilization via control Lyapunov measure, IEEE Transactions on Automatic Control, 55 (2010), 1314-1328.
doi: 10.1109/TAC.2010.2042226. |
| [78] |
U. Vaidya and I. Mezić,
Controllability for a class of area-preserving twist maps, Physica D: Nonlinear Phenomena, 189 (2004), 234-246.
doi: 10.1016/j.physd.2003.10.008. |
| [79] |
D. L. Vainchtein, A. I. Neishtadt and I. Mezic, On passage through resonances in volume-preserving systems, Chaos: An Interdisciplinary Journal of Nonlinear Science, 16 (2006), 043123, 11pp.
doi: 10.1063/1.2404585. |
| [80] |
C. Villani, Topics in Optimal Transportation no. 58, American Mathematical Society, 2003.
doi: 10.1007/b12016. |
| [81] |
S. Wiggins,
The dynamical systems approach to Lagrangian transport in oceanic flows, Annu. Rev. Fluid Mech., 37 (2005), 295-328.
doi: 10.1146/annurev.fluid.37.061903.175815. |
| [82] |
____, Chaotic Transport in Dynamical Systems, vol. 2, Springer Science & Business Media, 2013. |
| [83] |
S. Wiggins and J. M. Ottino,
Foundations of chaotic mixing, Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 362 (2004), 937-970.
doi: 10.1098/rsta.2003.1356. |
| [84] |
R. Wood, R. Nagpal and G.-Y. Wei,
Flight of the robobees, Scientific American, 308 (2013), 60-65.
doi: 10.1038/scientificamerican0313-60. |
show all references
References:
| [1] |
Intel Inc, Intel Xeon Processor X5690 https://ark.intel.com/products/52576/Intel-Xeon-Processor-X5690-12M-Cache-3_46-GHz-6_40-GTs-Intel-QPI, [Online; accessed 19-March-2018]. |
| [2] |
A. Agrachev and P. Lee,
Optimal transportation under nonholonomic constraints, Transactions of the American Mathematical Society, 361 (2009), 6019-6047.
doi: 10.1090/S0002-9947-09-04813-2. |
| [3] |
A. A. Agrachev and Y. Sachkov, Control Theory from the Geometric Viewpoint, Springer-Verlag, Berlin, 2004.
doi: 10.1007/978-3-662-06404-7. |
| [4] |
M. Aicardi, G. Casalino, A. Bicchi and A. Balestrino,
Closed loop steering of unicycle like vehicles via Lyapunov techniques, IEEE Robotics & Automation Magazine, 2 (1995), 27-35.
doi: 10.1109/100.388294. |
| [5] |
L. Ambrosio, N. Gigli and G. Savaré, Gradient Flows: In Metric Spaces and in the Space of Probability Measures, Springer Science & Business Media, 2008. |
| [6] |
J.-D. Benamou and Y. Brenier,
A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numerische Mathematik, 84 (2000), 375-393.
doi: 10.1007/s002110050002. |
| [7] |
S. Berman, Á. Halász, M. Ani Hsieh and V. Kumar,
Optimized stochastic policies for task allocation in swarms of robots, IEEE Transactions on Robotics, 25 (2009), 927-937.
doi: 10.1109/TRO.2009.2024997. |
| [8] |
P. Bernard and B. Buffoni,
Optimal mass transportation and mather theory, J. Eur. Math. Soc. (JEMS), 9 (2007), 85-121, math/0412299.
doi: 10.4171/JEMS/74. |
| [9] |
A. Bloch, J. Baillieul, P. Crouch, J. E. Marsden, P. S. Krishnaprasad, R. M. Murray and D. Zenkov, Nonholonomic Mechanics and Control, vol. 24, Springer, 2003.
doi: 10.1007/b97376. |
| [10] |
E. M. Bollt and N. Santitissadeekorn, Applied and Computational Measurable Dynamics, vol. 18, SIAM, 2013.
doi: 10.1137/1.9781611972641. |
| [11] |
P. Boyland, H. Aref and M. Stremler,
Topological fluid mechanics of stirring, Journal of Fluid Mechanics, 403 (2000), 277-304.
doi: 10.1017/S0022112099007107. |
| [12] |
M. Budišić, R. Mohr and I. Mezić, Applied koopmanism, Chaos: An Interdisciplinary Journal of Nonlinear Science, 22 (2012), 047510, 33pp.
doi: 10.1063/1.4772195. |
| [13] |
A. Chapman and M. Mesbahi,
Advection on graphs, 2011 50th IEEE Conference on Decision and Control and European Control Conference, IEEE, (2011), 1461-1466.
doi: 10.1109/CDC.2011.6161471. |
| [14] |
U. K. Cheang, K. Lee, A. A. Julius and M. J. Kim, Multiple-robot drug delivery strategy through coordinated teams of microswimmers, Applied Physics Letters, 105 (2014), 083705.
doi: 10.1063/1.4893695. |
| [15] |
Y. Chen, T. T. Georgiou and M. Pavon,
On the relation between optimal transport and Schrödinger bridges: A stochastic control viewpoint, Journal of Optimization Theory and Applications, 169 (2016), 671-691.
doi: 10.1007/s10957-015-0803-z. |
| [16] |
____,
Optimal transport over a linear dynamical system, IEEE Transactions on Automatic Control, 62 (2017), 2137-2152.
doi: 10.1109/TAC.2016.2602103. |
| [17] |
M. Dellnitz, G. Froyland and O. Junge, The algorithms behind GAIO - set oriented numerical methods for dynamical systems, Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems (B. Fiedler, ed. ), Springer, Berlin-Heidelberg-New York, 2001,145-174. |
| [18] |
M. Dellnitz, O. Junge, W. S. Koon, F. Lekien, M. W. Lo, J. E. Marsden, K. Padberg, R. Preis, S. D. Ross and B. Thiere,
Transport in dynamical astronomy and multibody problems, Int. J. Bifurc. Chaos, 15 (2005), 699-727.
doi: 10.1142/S0218127405012545. |
| [19] |
M. Dellnitz and O. Junge,
On the approximation of complicated dynamical behavior, SIAM Journal on Numerical Analysis, 36 (1998), 491-515.
doi: 10.1137/S0036142996313002. |
| [20] |
J. Eckstein and W. Yao, Augmented Lagrangian and alternating direction methods for convex optimization: A tutorial and some illustrative computational results, RUTCOR Research Reports, 32 (2012). |
| [21] |
K. Elamvazhuthi and S. Berman,
Optimal control of stochastic coverage strategies for robotic swarms, 2015 IEEE International Conference on Robotics and Automation (ICRA), IEEE, (2015), 1822-1829.
doi: 10.1109/ICRA.2015.7139435. |
| [22] |
K. Elamvazhuthi, V. Deshmukh, M. Kawski and S. Berman, Mean-field controllability and decentralized stabilization of Markov chains, part ⅰ: Global controllability and rational feedbacks, arXiv preprint, arXiv: 1703.08243, (2017). |
| [23] |
D. L. Elliott, Bilinear Control Systems: Matrices in Action, vol. 169, Springer Science & Business Media, 2009.
doi: 10.1023/b101451. |
| [24] |
K.-J. Engel and R. Nagel, One-parameter Semigroups for Linear Evolution Equations vol. 194, Springer-Verlag, New York, 2000. |
| [25] |
H. O. Fattorini, The Cauchy Problem, vol. 13517, Encyclopedia of Mathematics and its Applications, 18. Addison-Wesley Publishing Co., Reading, Mass., 1983. |
| [26] |
A. Figalli and L. Rifford,
Mass transportation on sub-riemannian manifolds, Geometric And Functional Analysis, 20 (2010), 124-159.
doi: 10.1007/s00039-010-0053-z. |
| [27] |
M. D. Finn and J.-L. Thiffeault,
Topological optimization of rod-stirring devices, SIAM Review, 53 (2011), 723-743.
doi: 10.1137/100791828. |
| [28] |
G. Froyland and M. Dellnitz,
Detecting and locating near-optimal almost-invariant sets and cycles, SIAM Journal on Scientific Computing, 24 (2003), 1839-1863.
doi: 10.1137/S106482750238911X. |
| [29] |
G. Froyland and K. Padberg,
Almost-invariant sets and invariant manifolds - connecting probabilistic and geometric descriptions of coherent structures in flows, Physica D, 238 (2009), 1507-1523.
doi: 10.1016/j.physd.2009.03.002. |
| [30] |
G. Froyland, N. Santitissadeekorn and A. Monahan, Transport in time-dependent dynamical systems: Finite-time coherent sets, Chaos, 20 (2010), 043116, 10pp.
doi: 10.1063/1.3502450. |
| [31] |
G. Froyland,
Dynamic isoperimetry and the geometry of Lagrangian coherent structures, Nonlinearity, 28 (2015), 3587-3622.
doi: 10.1088/0951-7715/28/10/3587. |
| [32] |
G. Froyland, C. González-Tokman and T. M. Watson,
Optimal mixing enhancement by local perturbation, SIAM Review, 58 (2016), 494-513.
doi: 10.1137/15M1023221. |
| [33] |
G. Froyland, O. Junge and P. Koltai,
Estimating long-term behavior of flows without trajectory integration: The infinitesimal generator approach, SIAM Journal on Numerical Analysis, 51 (2013), 223-247.
doi: 10.1137/110819986. |
| [34] |
G. Froyland and N. Santitissadeekorn, Optimal mixing enhancement, SIAM J. Appl. Math., 77 (2017), 1444-1470, arXiv: 1610.01651.
doi: 10.1137/16M1091496. |
| [35] |
A. Ghosh and P. Fischer,
Controlled propulsion of artificial magnetic nanostructured propellers, Nano letters, 9 (2009), 2243-2245.
doi: 10.1021/nl900186w. |
| [36] |
N. Gigli and J. Maas,
Gromov-hausdorff convergence of discrete transportation metrics, SIAM Journal on Mathematical Analysis, 45 (2013), 879-899.
doi: 10.1137/120886315. |
| [37] |
R. Gilmore,
Topological analysis of chaotic dynamical systems, Reviews of Modern Physics, 70 (1998), 1455-1529.
doi: 10.1103/RevModPhys.70.1455. |
| [38] |
M. Grant, S. Boyd and Y. Ye, CVX: Matlab software for disciplined convex programming, Global Optimization, Nonconvex Optim. Appl., Springer, New York, 84 (2006), 155-210.
doi: 10.1007/0-387-30528-9_7. |
| [39] |
P. Grover and K. Elamvazhuthi,
Optimal perturbations for nonlinear systems using graph-based optimal transport, Communications in Nonlinear Science and Numerical Simulation, 59 (2018), 197-215.
doi: 10.1016/j.cnsns.2017.09.020. |
| [40] |
P. Grover, S. D. Ross, M. A. Stremler and P. Kumar, Topological chaos, braiding and bifurcation of almost-cyclic sets, Chaos: An Interdisciplinary Journal of Nonlinear Science, 22 (2012), 043135, 16pp.
doi: 10.1063/1.4768666. |
| [41] |
G. Haller,
Lagrangian coherent structures, Annual Review of Fluid Mechanics, 47 (2015), 137-162.
|
| [42] |
D. Damir Harabor, A. Grastien, et al., Online graph pruning for pathfinding on grid maps, AAAI, 2011. |
| [43] |
A. Hindawi, J.-B. Pomet and L. Rifford,
Mass transportation with LQ cost functions, Acta Applicandae Mathematicae, 113 (2011), 215-229.
doi: 10.1007/s10440-010-9595-1. |
| [44] |
S. Jerg, O. Junge and M. Post,
Global optimal feedbacks for stochastic quantized nonlinear event systems, AIMS, 1 (2014), 163-176.
doi: 10.3934/jcd.2014.1.163. |
| [45] |
O. Junge and H. M. Osinga,
A set oriented approach to global optimal control, ESAIM: Control, Optimisation and Calculus of Variations, 10 (2004), 259-270.
doi: 10.1051/cocv:2004006. |
| [46] |
E. W. Justh and P. S. Krishnaprasad, Optimality, reduction and collective motion, Proc. R. Soc. A, The Royal Society, 471 (2015), 20140606, 22pp.
doi: 10.1098/rspa.2014.0606. |
| [47] |
E. Kirillova and K. Spindler,
Optimal control of a vehicle during parking, 2004 IFAC Symposium on Nonlinear Control Systems (NOLCOS), 37 (2004), 925-930.
doi: 10.1016/S1474-6670(17)31344-7. |
| [48] |
W. S. Koon, M. Lo, J. E. Marsden and S. D. Ross, Dynamical Systems, The Three-Body Problem and Space Mission Design, Marsden Books, 2008. |
| [49] |
P. S. Krishnaprasad, Optimal Control and Poisson Reduction, Tech. report, DTIC Document, 1993. |
| [50] |
A. Lasota and M. Mackey, Chaos, Fractals and Noise, Springer-Verlag, New York, 1994.
doi: 10.1007/978-1-4612-4286-4. |
| [51] |
J. B. Lasserre, D. Henrion, C. Prieur and E. Trélat,
Nonlinear optimal control via occupation measures and LMI-relaxations, SIAM Journal on Control and Optimization, 47 (2008), 1643-1666.
doi: 10.1137/070685051. |
| [52] |
F. Lekien and C. Coulliette,
Chaotic stirring in quasi-turbulent flows, Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 365 (2007), 3061-3084.
doi: 10.1098/rsta.2007.0020. |
| [53] |
P. F. J. Lermusiaux, T. Lolla, P. J. Haley Jr, K. Yigit, M. P. Ueckermann, T. Sondergaard and W. G. Leslie,
Science of Autonomy: Time-optimal Path Planning and Adaptive Sampling for Swarms of Ocean Vehicles, Springer Handbook of Ocean Engineering: Autonomous Ocean Vehicles, Subsystems and Control, (2015), 481-498.
doi: 10.1007/978-3-319-16649-0_21. |
| [54] |
J. Maas,
Gradient flows of the entropy for finite markov chains, Journal of Functional Analysis, 261 (2011), 2250-2292.
doi: 10.1016/j.jfa.2011.06.009. |
| [55] |
J. D. Meiss,
Symplectic maps, variational principles, and transport, Rev. Mod. Phys., 64 (1992), 795-848.
doi: 10.1103/RevModPhys.64.795. |
| [56] |
I. Mezic,
Analysis of fluid flows via spectral properties of the Koopman operator, Annual Review of Fluid Mechanics, 45 (2013), 357-378.
doi: 10.1146/annurev-fluid-011212-140652. |
| [57] |
A. Mielke,
Geodesic convexity of the relative entropy in reversible markov chains, Calculus of Variations and Partial Differential Equations, 48 (2013), 1-31.
doi: 10.1007/s00526-012-0538-8. |
| [58] |
R. M. Murray and S. S. Sastry,
Nonholonomic motion planning: Steering using sinusoids, IEEE Transactions on Automatic Control, 38 (1993), 700-716.
doi: 10.1109/9.277235. |
| [59] |
B. O'Donoghue, E. Chu, N. Parikh and S. Boyd, Operator splitting for conic optimization via homogeneous self-dual embedding, Journal of Optimization Theory and Applications, 159 (2016), 1042-1068, arXiv: 1312.3039.
doi: 10.1007/s10957-016-0892-3. |
| [60] |
J. M. Ottino and S. Wiggins,
Introduction: Mixing in microfluidics, Philosophical Transactions: Mathematical, Physical and Engineering Sciences, 362 (2004), 923-935.
doi: 10.1098/rsta.2003.1355. |
| [61] |
N. Papadakis, G. Peyré and E. Oudet,
Optimal transport with proximal splitting, SIAM Journal on Imaging Sciences, 7 (2014), 212-238.
doi: 10.1137/130920058. |
| [62] |
K. E. Peyer, L. Zhang and B. J. Nelson,
Bio-inspired magnetic swimming microrobots for biomedical applications, Nanoscale, 5 (2013), 1259-1272.
doi: 10.1039/C2NR32554C. |
| [63] |
H. Poincaré, Les Méthodes Nouvelles de la Mécanique Céleste: Méthodes de mm. Newcomb, Glydén, Lindstedt et Bohlin, (French) Dover Publications, Inc., New York, N. Y., 1957. |
| [64] |
A. C. Poje and G. Haller,
Geometry of cross-stream mixing in a double-gyre ocean model, Journal of Physical Oceanography, 29 (1999), 1649-1665.
doi: 10.1175/1520-0485(1999)029<1649:GOCSMI>2.0.CO;2. |
| [65] |
A. Raghunathan and U. Vaidya,
Optimal stabilization using Lyapunov measures, IEEE Transactions on Automatic Control, 59 (2014), 1316-1321.
doi: 10.1109/TAC.2013.2289707. |
| [66] |
L. Rifford, Sub-riemannian Geometry and Optimal Transport, Springer, 2014.
doi: 10.1007/978-3-319-04804-8. |
| [67] |
S. D Ross, S. Jerg and O. Junge,
Optimal capture trajectories using multiple gravity assists, Communications in Nonlinear Science and Numerical Simulations, 14 (2009), 4168-4175.
doi: 10.1016/j.cnsns.2008.12.009. |
| [68] |
J. Sabuco, M. A. F. Sanjuán and J. A. Yorke, Dynamics of partial control, Chaos, 22 (2012), 047507, 9pp.
doi: 10.1063/1.4754874. |
| [69] |
C. Senatore and S. D. Ross,
Fuel-efficient navigation in complex flows, 2008 American Control Conference, IEEE, (2008), 1244-1248.
doi: 10.1109/ACC.2008.4586663. |
| [70] |
J. Solomon, R. Rustamov, L. Guibas and A. Butscher, Continuous-flow graph transportation distances, arXiv preprint, arXiv: 1603.06927, (2016). |
| [71] |
M. A. Stremler, S. D. Ross, P. Grover and P. Kumar, Topological chaos and periodic braiding of almost-cyclic sets, Physical Review Letters, 106 (2011), 114101. |
| [72] |
H. J Sussmann,
A general theorem on local controllability, SIAM Journal on Control and Optimization, 25 (1987), 158-194.
doi: 10.1137/0325011. |
| [73] |
P. Tallapragada and S. D. Ross,
A set oriented definition of finite-time Lyapunov exponents and coherent sets, Communications in Nonlinear Science and Numerical Simulation, 18 (2013), 1106-1126.
doi: 10.1016/j.cnsns.2012.09.017. |
| [74] |
J.-L. Thiffeault and M. D. Finn,
Topology, braids and mixing in fluids, Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 364 (2006), 3251-3266.
doi: 10.1098/rsta.2006.1899. |
| [75] |
S. M. Ulam, Problems in Modern Mathematics, Science Editions John Wiley & Sons, Inc., New York, 1964. |
| [76] |
U. Vaidya and P. G. Mehta,
Lyapunov measure for almost everywhere stability, IEEE Transactions on Automatic Control, 53 (2008), 307-323.
doi: 10.1109/TAC.2007.914955. |
| [77] |
U. Vaidya, P. G. Mehta and U. V. Shanbhag,
Nonlinear stabilization via control Lyapunov measure, IEEE Transactions on Automatic Control, 55 (2010), 1314-1328.
doi: 10.1109/TAC.2010.2042226. |
| [78] |
U. Vaidya and I. Mezić,
Controllability for a class of area-preserving twist maps, Physica D: Nonlinear Phenomena, 189 (2004), 234-246.
doi: 10.1016/j.physd.2003.10.008. |
| [79] |
D. L. Vainchtein, A. I. Neishtadt and I. Mezic, On passage through resonances in volume-preserving systems, Chaos: An Interdisciplinary Journal of Nonlinear Science, 16 (2006), 043123, 11pp.
doi: 10.1063/1.2404585. |
| [80] |
C. Villani, Topics in Optimal Transportation no. 58, American Mathematical Society, 2003.
doi: 10.1007/b12016. |
| [81] |
S. Wiggins,
The dynamical systems approach to Lagrangian transport in oceanic flows, Annu. Rev. Fluid Mech., 37 (2005), 295-328.
doi: 10.1146/annurev.fluid.37.061903.175815. |
| [82] |
____, Chaotic Transport in Dynamical Systems, vol. 2, Springer Science & Business Media, 2013. |
| [83] |
S. Wiggins and J. M. Ottino,
Foundations of chaotic mixing, Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 362 (2004), 937-970.
doi: 10.1098/rsta.2003.1356. |
| [84] |
R. Wood, R. Nagpal and G.-Y. Wei,
Flight of the robobees, Scientific American, 308 (2013), 60-65.
doi: 10.1038/scientificamerican0313-60. |
Figure 2.
(A) Some minimizing geodesics to the origin in the Grushin plane. (B) Analytically computed optimal transport solution between a uniform measure whose support is the disk $\Omega = \{(x, y)|x^2+(y-.8)^2<.15^2\}$ , and a measure concentrated at the origin.
Figure 3.
(A)-(E) The optimal transport solution in the Grushin plane using graph based algorithm between a measure whose support is the disk $\Omega = \{(x, y)|x^2+(y-.8)^2<.15^2\}$ , and delta measure at the origin. The parameters are $m = 10^4, k = 75$ . (F) Convergence of optimal transport cost with number of time discretization steps $k$ and grid size $m$ .
Figure 4.
Particle trajectories with feedback control computed using Eq. (47) from the optimal transport solution in the Grushin plane. Each box contained in the support of uniform initial measure $\mu_0$ is initially populated with 4 particles.
Figure 6.
Optimal transport in the periodic double gyre system (Eqs.(57a-57b)) between measures at $t = 0$ and $t_f = 1$ . The parameters are $m = 1800, \Delta t = \dfrac{1}{40}$ .
Figure 7.
Optimal transport in the periodic double gyre system between measures at $t = 0$ and $t_f = 10, \Delta t = \dfrac{1}{40}$ . The optimal transport solution shows a quantization phenomenon. Ten 'packets' are transported via lobe-dynamics from the left side to the right side of the domain. During $2<t<5$ , the third packet is transported to the right side via the sequence $F^{-1}(A)\rightarrow A\rightarrow F(A) \rightarrow F^2(A)$ , where set $A$ is defined in Fig. 5. The last packet gets transported to the right side over $9<t<10$ . Animation available at: https://www.youtube.com/watch?v=Pu7sCkpm4RY
Figure 8.
The cost of optimal transport between two measures supported on two AIS for the double-gyre system, as a function of time-horizon of the problem.
Figure 9.
Initial and final measures shown on $(x, y)$ plane for two cases of optimal transport in the unicycle model. The green arrows indicate the third coordinate $\theta$ . (A) $\mu_0$ is supported on $(0, 0.5, 0)$ , $\mu_1$ is supported on $(1, 0, 0)$ and $(1, 1, 0)$ . (B) $\mu_0$ is supported on $(0, 0.5, 0)$ , $\mu_1$ is supported on $(1, 0, \frac{3\pi}{2})$ and $(1, 1, \frac{\pi}{2}).$
Figure 10.
The optimal transport solution of unicycle model shown in the $x-y$ plane for case 1. The grid size is $m = 25^3$ , and $k = 20$ .
Figure 11.
The optimal transport solution of unicycle model shown in the $x-y$ plane for case 2. The grid size is $m = 25^3$ , and $k$ = 20.
Figure 12.
Illustration of the proof of Theorem 3.7. The existence of an trajectory $f$ approximating a curve $\gamma$ connecting $B_v$ to $B_w$ , obtained by piecewise constant control, is guaranteed by the small time local controllability. By continuity, this leads to non-zero transition rates, and hence strong connectivity of the control graph $\mathcal{G}_c$ .
| [1] |
Abbas Moameni. Invariance properties of the Monge-Kantorovich mass transport problem. Discrete & Continuous Dynamical Systems - A, 2016, 36 (5) : 2653-2671. doi: 10.3934/dcds.2016.36.2653 |
| [2] |
Stefan Klus, Péter Koltai, Christof Schütte. On the numerical approximation of the Perron-Frobenius and Koopman operator. Journal of Computational Dynamics, 2016, 3 (1) : 51-79. doi: 10.3934/jcd.2016003 |
| [3] |
Jesus Garcia Azorero, Juan J. Manfredi, I. Peral, Julio D. Rossi. Limits for Monge-Kantorovich mass transport problems. Communications on Pure & Applied Analysis, 2008, 7 (4) : 853-865. doi: 10.3934/cpaa.2008.7.853 |
| [4] |
Zuo Quan Xu, Jia-An Yan. A note on the Monge-Kantorovich problem in the plane. Communications on Pure & Applied Analysis, 2015, 14 (2) : 517-525. doi: 10.3934/cpaa.2015.14.517 |
| [5] |
Giuseppe Buttazzo, Eugene Stepanov. Transport density in Monge-Kantorovich problems with Dirichlet conditions. Discrete & Continuous Dynamical Systems - A, 2005, 12 (4) : 607-628. doi: 10.3934/dcds.2005.12.607 |
| [6] |
Yupeng Li, Wuchen Li, Guo Cao. Image segmentation via $ L_1 $ Monge-Kantorovich problem. Inverse Problems & Imaging, 2019, 13 (4) : 805-826. doi: 10.3934/ipi.2019037 |
| [7] |
Martin Lustig, Caglar Uyanik. Perron-Frobenius theory and frequency convergence for reducible substitutions. Discrete & Continuous Dynamical Systems - A, 2017, 37 (1) : 355-385. doi: 10.3934/dcds.2017015 |
| [8] |
Gary Froyland, Ognjen Stancevic. Escape rates and Perron-Frobenius operators: Open and closed dynamical systems. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 457-472. doi: 10.3934/dcdsb.2010.14.457 |
| [9] |
Nassif Ghoussoub, Bernard Maurey. Remarks on multi-marginal symmetric Monge-Kantorovich problems. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1465-1480. doi: 10.3934/dcds.2014.34.1465 |
| [10] |
Stefan Klus, Christof Schütte. Towards tensor-based methods for the numerical approximation of the Perron--Frobenius and Koopman operator. Journal of Computational Dynamics, 2016, 3 (2) : 139-161. doi: 10.3934/jcd.2016007 |
| [11] |
Jean-Pierre de la Croix, Magnus Egerstedt. Analyzing human-swarm interactions using control Lyapunov functions and optimal control. Networks & Heterogeneous Media, 2015, 10 (3) : 609-630. doi: 10.3934/nhm.2015.10.609 |
| [12] |
Hang-Chin Lai, Jin-Chirng Lee, Shuh-Jye Chern. A variational problem and optimal control. Journal of Industrial & Management Optimization, 2011, 7 (4) : 967-975. doi: 10.3934/jimo.2011.7.967 |
| [13] |
Peter I. Kogut, Olha P. Kupenko. On optimal control problem for an ill-posed strongly nonlinear elliptic equation with $p$-Laplace operator and $L^1$-type of nonlinearity. Discrete & Continuous Dynamical Systems - B, 2019, 24 (3) : 1273-1295. doi: 10.3934/dcdsb.2019016 |
| [14] |
Jiu Ding, Noah H. Rhee. A unified maximum entropy method via spline functions for Frobenius-Perron operators. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 235-245. doi: 10.3934/naco.2013.3.235 |
| [15] |
Marc Kesseböhmer, Sabrina Kombrink. A complex Ruelle-Perron-Frobenius theorem for infinite Markov shifts with applications to renewal theory. Discrete & Continuous Dynamical Systems - S, 2017, 10 (2) : 335-352. doi: 10.3934/dcdss.2017016 |
| [16] |
Ellina Grigorieva, Evgenii Khailov, Andrei Korobeinikov. An optimal control problem in HIV treatment. Conference Publications, 2013, 2013 (special) : 311-322. doi: 10.3934/proc.2013.2013.311 |
| [17] |
Christian Léonard. A survey of the Schrödinger problem and some of its connections with optimal transport. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1533-1574. doi: 10.3934/dcds.2014.34.1533 |
| [18] |
V.N. Malozemov, A.V. Omelchenko. On a discrete optimal control problem with an explicit solution. Journal of Industrial & Management Optimization, 2006, 2 (1) : 55-62. doi: 10.3934/jimo.2006.2.55 |
| [19] |
Urszula Ledzewicz, Heinz Schättler. Drug resistance in cancer chemotherapy as an optimal control problem. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 129-150. doi: 10.3934/dcdsb.2006.6.129 |
| [20] |
Akram Kheirabadi, Asadollah Mahmoudzadeh Vaziri, Sohrab Effati. Solving optimal control problem using Hermite wavelet. Numerical Algebra, Control & Optimization, 2019, 9 (1) : 101-112. doi: 10.3934/naco.2019008 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]