# 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] 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] 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 [7] 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 [8] 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 [9] 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 [10] 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 [11] 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 [12] 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 [13] 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 [14] 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 [15] 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 [16] 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 [17] 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 [18] 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 [19] 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 [20] Yujing Wang, Changjun Yu, Kok Lay Teo. A new computational strategy for optimal control problem with a cost on changing control. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 339-364. doi: 10.3934/naco.2016016

Impact Factor:

## Tools

Article outline

Figures and Tables