Robot motion planning: configuration space exploration and estimation

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Ashur, Stav

Contributors dc:contributor

• Har-Peled, Sariel
• Amato, Nancy M
• Morales, Marco
• Halperin, Dan

• Robotics
• Motion Planning
• Computational Geometry

Statement dc:rights

• Copyright 2025 Stav Ashur

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F129909