Files in this item



application/pdfDmytro_Yershov.pdf (3MB)
(no description provided)PDF


Title:Fast numerical algorithms for optimal robot motion planning
Author(s):Yershov, Dmytro
Director of Research:LaValle, Steven M.
Doctoral Committee Chair(s):Heath, Michael T.
Doctoral Committee Member(s):LaValle, Steven M.; Olson, Luke N.; Frazzoli, Emilio
Department / Program:Department of Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Optimal Motion Planning
Numerical methods
Fast Marching Method
Simplicial Discretization
Simplicial Dijkstra Algorithm
Simplicial A* Algorithm
Simplicial Label Correcting Algorithm
Simplicial Value Iteration Algorithm
Simplicial Policy Iteration Algorithm
Mobile Robots
Optimal Control
Feedback Control
Shortest Path Problem
Weighted Region Problem
Differential Constraints
Nonholonomic Constraints
Stochastic Control
Stochastic Shortest Path Problem
Nearby Deterministic System
Turing Decidability
Turing Semidecidability
Sampling Metric Spaces
Resolution Completeness
Abstract:Optimization of high-level autonomous tasks requires solving the optimal motion planning problem for a mobile robot. For example, to reach the desired destination on time, a self-driving car must quickly navigate streets and avoid hazardous obstacles such as buildings or other cars, as well as provide safety for pedestrians. Our approach to solve the optimal planning problem is to use the optimal control formalism borrowed from the control theory. In this setting, safety constraints for either a robot or its surroundings are defined as obstacles, which are penalized using infinite cost to guarantee that tasks are performed safely. Unlike in control theory, the complexity of real-world tasks in addition with safety constraints prohibit finding an analytic solution to the optimal motion planning problem. Hence, the application of numerical algorithms is necessary. In this thesis, we demonstrate that solutions to a general motion planning problem are computable, which permits the use of numerical algorithms to solve this problem. Moreover, we propose a numerical discretization of a general optimal motion planning problem and prove that this discretization is accurate. Numerical algorithms that use the proposed discretization are applied to several realistic motion planning problems. Using these algorithms, we demonstrate the practicality of the proposed numerical approach. In addition, we extend our consideration beyond the classical deterministic models of motion and apply the proposed numerical algorithms to solve a stochastic optimal motion planning problem.
Issue Date:2014-01-16
Rights Information:Copyright 2013 Dmytro S. Yershov
Date Available in IDEALS:2014-01-16
Date Deposited:2013-12

This item appears in the following Collection(s)

Item Statistics