[+] Motion-Planning Gadgets. Gadgets, states, locations, transitions, traversals, tunnels, buttons; system, connection graph, reachability, simulation. Door, self-closing door, symmetric self-closing door, universality, planarity. Deterministic reversible gadgets, hardness characterization, 2-state 2-tunnel gadgets. Checkable gadgets, Sokoban, Push-1F. I/O gadgets, 0-player, ARRIVAL. DAG vs. LDAG gadgets. | |||||
Gadgets gadgets gadgets! This lecture describes a growing general theory of "gadgets" in the context of "motion planning": an agent (e.g., Mario) traversing an environment with local state. We'll define a very general model of such gadgets, where each gadget consists of states, locations, and transitions between pairs of states and locations, and systems/networks of these gadgets connected in a graph structure. Then we'll describe some of the key results in this ongoing theory:
| |||||
|
Handwritten notes, page 1/11 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/11 • [previous page] • [next page] • [PDF] |
|
Slides, page 1/67 •
[previous page] •
[next page] •
[PDF]
https://erikdemaine.org/papers/Mario_FUN2016/ Slides, page 1/67 • [previous page] • [next page] • [PDF] |