# 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] Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019 [2] Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046 [3] Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347 [4] Bernard Bonnard, Jérémy Rouot. Geometric optimal techniques to control the muscular force response to functional electrical stimulation using a non-isometric force-fatigue model. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020032 [5] Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $L^2-$norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077 [6] Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463 [7] Mengni Li. Global regularity for a class of Monge-Ampère type equations with nonzero boundary conditions. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020267 [8] José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020271 [9] Zedong Yang, Guotao Wang, Ravi P. Agarwal, Haiyong Xu. Existence and nonexistence of entire positive radial solutions for a class of Schrödinger elliptic systems involving a nonlinear operator. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020436 [10] Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251 [11] Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253 [12] Hui Lv, Xing'an Wang. Dissipative control for uncertain singular markovian jump systems via hybrid impulsive control. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 127-142. doi: 10.3934/naco.2020020 [13] Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044 [14] Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384 [15] Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444 [16] Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453 [17] Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031 [18] Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075 [19] Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168 [20] M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

Impact Factor: