Jayson
Lynch,
PhD
candidate
Massachusetts
Institute
of
Technology
This talk describes a general theory for characterizing the computational complexity of motion planning of robot(s) through a graph of “gadgets,” where each gadget has its own state defining a set of allowed traversals which in turn modify the gadget’s state.
We study two general families of such gadgets within this theory, one which naturally leads to motion planning problems with polynomially bounded solutions, and another which leads to polynomially unbounded (potentially exponential) solutions. We also study a range of competitive game-theoretic scenarios, from one player controlling one robot to teams of players each controlling their own robot and racing to achieve their team’s goal.
Under certain restrictions on these gadgets, we fully characterize the complexity of bounded 1-player motion planning (NL vs. NP-complete), unbounded 1-player motion planning (NL vs. PSPACE-complete), and bounded 2-player motion planning (P vs. PSPACE-complete), and we partially characterize the complexity of unbounded 2-player motion planning (P vs. EXPTIME-complete), bounded 2-team motion planning (P vs. NEXPTIME-complete), and unbounded 2-team motion planning (P vs. undecidable). This framework then used to simplify existing proofs and show new results about video games and models of micro-assembly.
Bio: Jayson Lynch is a PhD student at MIT under Erik Demaine. Jayson’s work includes the computational complexity of geometric and motion planning problems; designing reversible algorithms for more energy efficient computing; and exploring the capability and limitations of cache based and parallel algorithms.