Harvey Mudd College
Computer Science 154 - Robotics
Independent Assignment Ideas

Open Lab Assignment Ideas

The Complexity of Motion Planning

There has been a great deal of work by algorithm developers and computational geometers in finding lower bounds on the complexity of path planning problems. For example, it is known that finding the shortest path among polyhedral obstacles in any three-dimensional configuration space (e.g., ordinary 3-space) is PSPACE-complete. In fact, only relatively recently did the best known algorithm for solving this problem drop from being doubly exponential to singly exponential!

One possibility for an independent robotics project would be to investigate and report on these results, how they are obtained, and what interesting open problems remain in the field of path planning. As a start, here are links to a number of papers in the area:

• A Single-Exponential Upper Bound for Finding Shortest Paths in Three Dimensions in PDF form. This paper presents the singly-exponential upper bound mentioned above.



• Kinodynamic Motion Planning in PDF form. This paper considers the case of robot motion under kinematic or dynamic constraints (e.g., for nonholonomic robots) and provides the first provably "good" approximation algorithm for this NP-hard problem.



• Motion Planning in the Presence of Moving Obstacles in PDF form. This paper shows that finding any path from start to goal in the presence of known, moving obstacles in PSPACE-hard in the general case, but provides polynomial algorithms in the case that the obstacles only translate and do not rotate at all (the asteroid avoidance problem).



• Shortest Paths in the Plane with Polygonal Obstacles in PDF form. This paper shows an O(N^2) algorithm for finding the shortest obstacle-avoiding path between two planar points and a linear algorithm in the case that there are a bounded number of "island" obstacles in the environment.



• Lower Bounds for Shortest Path and Related Problems in postscript form. This is the paper that shows that finding the optimal path in 3d is NP-hard.

Other ideas are welcome...