# 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] Simone Fiori. Error-based control systems on Riemannian state manifolds: Properties of the principal pushforward map associated to parallel transport. Mathematical Control & Related Fields, 2021, 11 (1) : 143-167. doi: 10.3934/mcrf.2020031 [3] Claudia Lederman, Noemi Wolanski. An optimization problem with volume constraint for an inhomogeneous operator with nonstandard growth. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020391 [4] 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 [5] Hai Huang, Xianlong Fu. Optimal control problems for a neutral integro-differential system with infinite delay. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020107 [6] Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Fractional optimal control problems on a star graph: Optimality system and numerical solution. Mathematical Control & Related Fields, 2021, 11 (1) : 189-209. doi: 10.3934/mcrf.2020033 [7] Christian Clason, Vu Huu Nhu, Arnd Rösch. Optimal control of a non-smooth quasilinear elliptic equation. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020052 [8] Hongbo Guan, Yong Yang, Huiqing Zhu. A nonuniform anisotropic FEM for elliptic boundary layer optimal control problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1711-1722. doi: 10.3934/dcdsb.2020179 [9] Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122 [10] Yuan Tan, Qingyuan Cao, Lan Li, Tianshi Hu, Min Su. A chance-constrained stochastic model predictive control problem with disturbance feedback. Journal of Industrial & Management Optimization, 2021, 17 (1) : 67-79. doi: 10.3934/jimo.2019099 [11] Xin Zhang, Jie Xiong, Shuaiqi Zhang. Optimal reinsurance-investment and dividends problem with fixed transaction costs. Journal of Industrial & Management Optimization, 2021, 17 (2) : 981-999. doi: 10.3934/jimo.2020008 [12] 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 [13] Pierluigi Colli, Gianni Gilardi, Jürgen Sprekels. Deep quench approximation and optimal control of general Cahn–Hilliard systems with fractional operators and double obstacle potentials. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 243-271. doi: 10.3934/dcdss.2020213 [14] Stefan Doboszczak, Manil T. Mohan, Sivaguru S. Sritharan. Pontryagin maximum principle for the optimal control of linearized compressible navier-stokes equations with state constraints. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020110 [15] Elimhan N. Mahmudov. Infimal convolution and duality in convex optimal control problems with second order evolution differential inclusions. Evolution Equations & Control Theory, 2021, 10 (1) : 37-59. doi: 10.3934/eect.2020051 [16] Lars Grüne, Roberto Guglielmi. On the relation between turnpike properties and dissipativity for continuous time linear quadratic optimal control problems. Mathematical Control & Related Fields, 2021, 11 (1) : 169-188. doi: 10.3934/mcrf.2020032 [17] Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control & Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026 [18] Arthur Fleig, Lars Grüne. Strict dissipativity analysis for classes of optimal control problems involving probability density functions. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020053 [19] Wen Li, Wei-Hui Liu, Seak Weng Vong. Perron vector analysis for irreducible nonnegative tensors and its applications. Journal of Industrial & Management Optimization, 2021, 17 (1) : 29-50. doi: 10.3934/jimo.2019097 [20] 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

Impact Factor: