# American Institute of Mathematical Sciences

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

* Corresponding author

Fund Project: This work was funded by Mitsubishi Electric Research Labs.

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.

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:

show all references

##### References:
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$.
(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.
(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$.
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.
nvariant manifolds and lobe-dynamics in the double-gyre system (reproduced from Ref. [39]).
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}$.
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
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.
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}).$
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$.
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.
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] Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437 [2] Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183 [3] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [4] Xiaohong Li, Mingxin Sun, Zhaohua Gong, Enmin Feng. Multistage optimal control for microbial fed-batch fermentation process. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021040 [5] John T. Betts, Stephen Campbell, Claire Digirolamo. Examination of solving optimal control problems with delays using GPOPS-Ⅱ. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 283-305. doi: 10.3934/naco.2020026 [6] Shanjian Tang, Fu Zhang. Path-dependent optimal stochastic control and viscosity solution of associated Bellman equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5521-5553. doi: 10.3934/dcds.2015.35.5521 [7] Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037 [8] Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311 [9] Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247 [10] Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008 [11] Yves Dumont, Frederic Chiroleu. Vector control for the Chikungunya disease. Mathematical Biosciences & Engineering, 2010, 7 (2) : 313-345. doi: 10.3934/mbe.2010.7.313 [12] Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022 [13] Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021 [14] Y. Latushkin, B. Layton. The optimal gap condition for invariant manifolds. Discrete & Continuous Dynamical Systems - A, 1999, 5 (2) : 233-268. doi: 10.3934/dcds.1999.5.233 [15] Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271 [16] J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 [17] Martin Bohner, Sabrina Streipert. Optimal harvesting policy for the Beverton--Holt model. Mathematical Biosciences & Engineering, 2016, 13 (4) : 673-695. doi: 10.3934/mbe.2016014 [18] Xingchun Wang, Yongjin Wang. Variance-optimal hedging for target volatility options. Journal of Industrial & Management Optimization, 2014, 10 (1) : 207-218. doi: 10.3934/jimo.2014.10.207 [19] Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463 [20] Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329

Impact Factor: