McConnell Engineering, room 320
This course focuses on algorithmic approaches to motion planning problems. Motion planning problems are often hard in the sense of computational complexity (e.g., NP-hard, PSPACE-complete, etc.) This is often the case when the object to be moved has an arbitrary number n of joints. On the other hand, there are tractable algorithmic approaches for many problems. This course studies both algorithmic techniques and techniques for proving lower bounds.
Students should come away from the course with some knowledge of specific algorithms for motion planning, plus some knowledge of methods for proving intractability, plus a knowledge of current research themes in the area.
An undergraduate background in algorithms design such as COMP 360 is expected. A course in computational geometry, such as COMP 507, and an introductory course in complexity theory, such as COMP 506, are also desireable background, but not required.