{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/46659"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/46659","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Fast numerical algorithms for optimal robot motion planning","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Yershov, Dmytro"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["LaValle, Steven M.","Heath, Michael T.","Olson, Luke N.","Frazzoli, Emilio"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-01-16T17:57:58Z","date_published":"2014-01-16T17:57:58Z","updated_at":"2026-07-22T22:25:36Z","subjects":["Optimal Motion Planning","Hamilton-Jacobi-Bellman","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","Robotics","Control","Optimal Control","Feedback Control","Obstacles","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"],"languages":["en"],"rights":["Copyright 2013 Dmytro S. Yershov"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/46659","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["LaValle, Steven M.","Heath, Michael T.","Olson, Luke N.","Frazzoli, Emilio"]},{"key":"dc:creator","label":"Author","values":["Yershov, Dmytro"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-01-16T17:57:58Z","2013-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Optimal Motion Planning","Hamilton-Jacobi-Bellman","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","Robotics","Control","Optimal Control","Feedback Control","Obstacles","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"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Dmytro S. Yershov"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/46659"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2013-11-26T17:01:23Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Yershov_Dmytro.pdf: 3433238 bytes, checksum: 8266d5f6fa72e51efb4524436bff9825 (MD5)","Made available in DSpace on 2014-01-16T17:57:58Z (GMT). No. of bitstreams: 2 Dmytro_Yershov.pdf: 3432672 bytes, checksum: a3ebcee3f27fd022cfed3542812d0f08 (MD5) license.txt: 4058 bytes, checksum: dae5136623401b4179c7e27362eadd1a (MD5)"]},{"key":"dc:title","label":"Title","values":["Fast numerical algorithms for optimal robot motion planning"]}]}],"canonical_facts":{"dc:contributor":["LaValle, Steven M.","Heath, Michael T.","Olson, Luke N.","Frazzoli, Emilio"],"dc:creator":["Yershov, Dmytro"],"dc:date":["2014-01-16T17:57:58Z","2013-12"],"dc:description":["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.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2013-11-26T17:01:23Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Yershov_Dmytro.pdf: 3433238 bytes, checksum: 8266d5f6fa72e51efb4524436bff9825 (MD5)","Made available in DSpace on 2014-01-16T17:57:58Z (GMT). No. of bitstreams: 2 Dmytro_Yershov.pdf: 3432672 bytes, checksum: a3ebcee3f27fd022cfed3542812d0f08 (MD5) license.txt: 4058 bytes, checksum: dae5136623401b4179c7e27362eadd1a (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/46659"],"dc:language":["en"],"dc:rights":["Copyright 2013 Dmytro S. Yershov"],"dc:subject":["Optimal Motion Planning","Hamilton-Jacobi-Bellman","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","Robotics","Control","Optimal Control","Feedback Control","Obstacles","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"],"dc:title":["Fast numerical algorithms for optimal robot motion planning"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:36Z"}