2023–24 Projects:
"Motion Planning" is a general problem area that concerns getting a robot from one location or configuration to another in the presence of obstacles and other constraints.
For example, you might give a robot a complete floor plan of the third floor CMC and try to program it to move from Mike Tie's office to Rich Nau's office. Since obstacles not included on a floor plan can appear (people walking to class, Jeff Ondich's furniture being thrown into the hall as he rearranges his room yet again, etc.), you might also program your robot to take sensor input into account as the robot makes its trip. You might also work with two robots whose goal is to switch places without crashing into each other, or a single robot that is required to stay at least a foot from each wall, or a long rectangular robot that needs to rotate itself to go around tight corners.
Another class of motion planning problems involves articulated robots. Suppose you have a robot arm with two joints that permit full circular motion. You might wish to move the arm from its rest position to a new position where the claw on the end of the arm can grasp a part on an assembly line. If there are no barriers, this is easy. But if the arm needs to reach around a post, or avoid contact with other arms, etc., things are more difficult.
Motion planning algorithms have been applied to autonomous robot navigation, automated manufacturing, the simulation of protein folding, the planning of intricate surgeries, and games, among other things.
For this project, you will implement a collection of motion planning algorithms and create a simulation environment that will allow users to experiment with the algorithms, collect data to test complexity analyses, discover when the algorithms fail, etc. Some of the things you will need to do include:
Note that this project does not require your simulation environment to drive physical robots.
In cases where it is appropriate and legal to do so, I have posted PDF versions of these papers in /Accounts/courses/comps/jondich under the last name of the first author (e.g. hwang.pdf).
Yong K. Hwang and Narendra Ahuja, "Gross Motion Planning," in ACM Computing Surveys, Vol. 24, No. 3, September 1992.
Joseph O'Rourke, "Computational Geometry in C," Cambridge University Press, Cambridge, UK, 1993, Chapter 8 (270-316).
Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf, "Computational Geometry, Algorithms and Applications, 2nd edition," Springer-Verlag, New York, 2000, Chapter 13 (267-290).