Dongliang Zheng
(Advisor: Prof. Panagiotis Tsiotras]

will propose a doctoral thesis entitled,

Informed Sampling-based Kinodynamic Motion Planning for Deterministic Systems and Stochastic Systems

On

Tuesday, April 25 at 1:00 p.m.
Montgomery Knight Building 317
https://gatech.zoom.us/j/6852641782

Abstract
Motion planning, as a fundamental component of robot autonomy, has been studied extensively in the last three decades to increase its efficiency and capability. Efficiency means faster convergence to the same solution or finding a better solution given the same amount of time.  Efficient planning algorithms are crucial for robots with limited computation power and for replanning in changing environments. Capability means dealing with more complicated planning problems.  Complicated planning problems, characterized by high dimensional state space, cluttered environments with irregular obstacles, differential dynamics constraints, and motion and measurement uncertainty, still pose challenges for current planning algorithms. This thesis aims to develop efficient algorithms for those complicated problems.

We first consider the planning problem for deterministic systems under differential constraints. An informed dimensionality reduction heuristic is proposed for accelerating existing optimal sampling-based motion planning algorithms. Specifically, we introduce the idea of using a partial-final-state-free (PFF) optimal controller as the steering function in traditional sampling-based kinodynamic planning algorithms. PFF controllers allow us to sample in the reduced state space thus achieve faster convergence. Instead of sampling the full state space, the proposed method only samples part of the state space while the rest of the states are selected by the PFF optimal controller.  By incorporating this heuristic, we developed two new algorithms, Kino-RRT*-PFF and Kino-FMT*-PFF, which are based on the kinodynamic RRT* and FMT*, respectively.  We derived the analytical solution of the PFF optimal controller for linear systems. For nonlinear systems, we show that the PFF optimal controller can be obtained using supervised learning. 

Next, the planning problem for stochastic systems is studied where motion and measurement uncertainties are considered. This problem is also referred to as belief space planning. We consider both multi-query and single-query belief space planning problems. Firstly, a new belief space planning algorithm, called covariance steering Belief RoadMap (CS-BRM), is introduced for multi-query motion planning problems. CS-BRM extends the probabilistic roadmap (PRM) approach to belief spaces based on the recently developed theory of covariance steering (CS) that enables guaranteed satisfaction of terminal belief constraints in finite time. The nodes in the CS-BRM are sampled in belief space and represent distributions of the system states. A covariance steering controller steers the system from one BRM node to another, thus acting as an edge controller of the corresponding belief graph. The CS-BRM algorithm allows the sampling of non-stationary belief nodes and thus can explore the velocity space and find much more efficient trajectories than previous BRM methods. The performance of CS-BRM is evaluated and compared to previous belief space planning approaches using several numerical examples, illustrating the benefits of the proposed approach.

Secondly, the informed batch belief tree (IBBT) algorithm is proposed for single-query belief space planning with Gaussian noise assumption.  The algorithm interleaves between batch sampling, building a graph of nominal trajectories in the state space, and searching over the graph to grow a belief tree. By computing the cost-to-go heuristic using the nominal trajectory graph, an admissible and informed heuristic is obtained to guide the belief tree search. IBBT is an anytime, incremental algorithm. It finds motion plans that converge to the optimal one as more samples are added to the graph.

Lastly, the particle IBBT algorithm is developed to remove the Gaussian noise assumption in IBBT.  By representing the belief using particles and directly forward propagating the nonlinear dynamics to grow a belief tree, particle IBBT is an algorithm for chance-constrained safe motion planning with any initial distribution, process noise, measurement noise, dynamics, and cost function.

Committee

• Prof. Panagiotis Tsiotras – School of Aerospace Engineering (advisor)
• Prof. Kyriakos G. Vamvoudakis– School of Aerospace Engineering
• Prof. Jonathan Rogers – School of Aerospace Engineering
• Prof. Ye Zhao – School of Mechanical Engineering
• Dr. Yebin Wang– Senior Principal Research Scientist, MERL