Toward a General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard

Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch

We build 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…