Robot motion planning: configuration space exploration and estimation

Ashur, Stav

Permalink

https://hdl.handle.net/2142/129909 Copy

Description

Title

Robot motion planning: configuration space exploration and estimation

Author(s)

Ashur, Stav

Issue Date

2025-06-25

Director of Research (if dissertation) or Advisor (if thesis)

Har-Peled, Sariel

Doctoral Committee Chair(s)

• Har-Peled, Sariel
• Amato, Nancy M

Committee Member(s)

• Morales, Marco
• Halperin, Dan

Department of Study

Siebel School Comp & Data Sci

Discipline

Computer Science

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Robotics
• Motion planning
• Computational geometry

Abstract

Fully or semi-autonomous machines, such as robots, are increasingly present in every domain of human society. Cleaning robots, self-driving cars, assembly machines in factories, and exploration vessels for deep sea and space. One of the core challenges when designing and deploying these robots is motion planning, which encompasses almost every action of the robot that requires the operation of a motor -- traveling by land, water, or air, grasping, pushing, or pulling objects, and positioning and utilizing tools, all require motion planning capabilities. Motion planning is frustratingly easy for people -- consider tasks such as assembling a LEGO set or cutting a vegetable into equal parts. Meanwhile, these tasks are quite difficult to automate. The conceived easiness of the task is misleading - young children cannot perform these actions, and years of ``training'' are required to develop the prerequisite set of skills. These tasks require precise motions using a large number of muscles operating in coordination, happening in some space significantly more complicated than the 3D physical workspace, all done by technology that took hundreds of millions of years to emerge via evolution. In this dissertation, we present research on robot motion planning performed in the robot configuration space, a space that captures the complexity of motions problems, striving to improve and utilize methods that efficiently search the space for solutions. We use novel techniques to improve the speed of motion planning algorithms, by modifying the exploration strategies, and the representations of the search space they use. Two of our methods can be easily incorporated in many motion planning algorithms, improving their performance, as measured by runtime, sampling efficiency, or length of the solution. Significantly, these improvements are also present in highly constrained scenarios where motion planning is difficult. We show that these techniques are beneficial when used with various types of robots, suggesting they are widely applicable. We also present a method to update quickly motion planning roadmaps, enabling planning in the presence of changing environments. This method out-performs the state of the art dynamic roadmap, and thus leads to faster planning. We also show the applicability of the new dynamic data-structure to another task planning problem, in which the robot is required to rearrange objects.

Graduation Semester

2025-08

Type of Resource

Thesis

Handle URL

https://hdl.handle.net/2142/129909

Copyright and License Information

Copyright 2025 Stav Ashur

Owning Collections