The applications of discrete optimal transport in path planning and data clustering

Optimal transport;Path planning;Fokker-Planck equation

Zhai, Haoyan ; Zhou, Haomin Mathematics Dieci, Luca Kang, Sung Ha Short, Martin Zhang, Fumin ; Zhou, Haomin

University:Georgia Institute of Technology

Department:Mathematics

关键词: Optimal transport;    Path planning;    Fokker-Planck equation;   

Others  :  https://smartech.gatech.edu/bitstream/1853/61712/1/ZHAI-DISSERTATION-2019.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Optimal transport introduces the concept of Wasserstein distance, which has been widely used in various applications in computational mathematics, machine learning as well as many areas in engineering. Meanwhile, control theory and path planning is an active branch in mathematics and robotics, focusing on algorithms that calculate feasible or optimal paths for robotic systems. In this thesis, we use the properties of the gradient flows induced by Wasserstein-2 metric to design algorithms to handle different types of path planning and control problems. Also, we define the Wasserstein K-means problems on graphs and propose an efficient algorithm to solve it. First of all, we provide an algorithm to handle the path planning problem in unknown environments. We develop a deterministic approach with finite-step convergence guarantee. Also, there is a theoretical relation between this algorithm and the Fokker-Planck equations, which bounds the searching region of the algorithm. We use numerical examples to show the efficiency of the algorithm as well as to support the theoretical results. Then, we generalize the algorithm to solve the general control problem in the unknown environments and similar convergence results can be proven. Besides, there is an evidence that the algorithm is guided by the evolution of Fokker-Planck equation, and we use experiments to demonstrate our theorems. We move on to study the optimal path planning in flow field. In this case, the objective function, the traveling time or kinetic energy, is to be minimized with a given flow field. Following the idea of method of evolving junctions, we first transform the original infinite dimensional optimal control into a finite dimensional global optimization problem by introducing junctions located only on the discontinuity positions of the dynamics. To handle the global optimization, intermittent diffusion is used here to guarantee the completeness of the method. At last, we define the discrete Wasserstein-(1,p) distance that depends on the graph structure. With this distance function, we further propose the Wasserstein K-means problem on a general graph and provide an algorithm in the framework of Lloyd method. The key part of the algorithm is the calculation of discrete Wasserstein-(1,p) distance and the gradient flow induced by Wasserstein-2 metric to solve an optimization with objective function being a linear combination of Wasserstein-(1.p) distance. Examples and simulation results are provided in the thesis.