Back to search

Georgia Institute of Technology

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

Abstract

dc:description.abstract

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.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhai, Haoyan
Advisor dc:contributor.advisor
  • Zhou, Haomin
Committee members dc:contributor.committeemember
  • Dieci, Luca
  • Kang, Sung Ha
  • Short, Martin
  • Zhang, Fumin

Subjects

dc:subject × 3

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/61712

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Zhai, Haoyan. The applications of discrete optimal transport in path planning and data clustering. Doctoral thesis, Georgia Institute of Technology, 2019. http://hdl.handle.net/1853/61712