COMP 648

This course focuses on algorithmic approaches to
motion planning problems. Motion planning problems
are often hard in the sense of computational
complexity (e.g., NPhard, PSPACEcomplete, 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.