Gadgets and Gizmos: A Formal Model of Simulation in the Gadget Framework for Motion Planning
Recent work has developed a theory of motion-planning gadgets, which are a useful tool for proving hardness for a variety of problems that can be thought of in terms of an agent navigating a dynamic environment. We introduce formal objects representing motion-planning gadgets, which we call gizmos,...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/139275 |
| _version_ | 1811077406509760512 |
|---|---|
| author | Hendrickson, Dylan |
| author2 | Demaine, Erik D. |
| author_facet | Demaine, Erik D. Hendrickson, Dylan |
| author_sort | Hendrickson, Dylan |
| collection | MIT |
| description | Recent work has developed a theory of motion-planning gadgets, which are a useful tool for proving hardness for a variety of problems that can be thought of in terms of an agent navigating a dynamic environment. We introduce formal objects representing motion-planning gadgets, which we call gizmos, and ask which gizmos simulate each other—simulations between gizmos yield reductions between natural decision problems, so this has consequences for complexity.
We define several classes of gizmos, and prove that they are closed under simulation: gizmos with some property cannot simulate gizmos without it. For several of these classes, we also find a gizmo which can simulate every gizmo in the class; this is analogous to completeness for a complexity class. We consider gizmo simulation and prove unsimulability and universality in two restricted settings: planar simulation, where the simulation must embed in the plane without crossings, and input/output simulation, which is a model for fully deterministic settings. We mostly focus on simulations with finitely many gizmos and gizmos with finitely many states (called regular), but many of our results carry over to more exotic infinite gizmos. |
| first_indexed | 2024-09-23T10:42:31Z |
| format | Thesis |
| id | mit-1721.1/139275 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:42:31Z |
| publishDate | 2022 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1392752022-01-15T03:49:37Z Gadgets and Gizmos: A Formal Model of Simulation in the Gadget Framework for Motion Planning Hendrickson, Dylan Demaine, Erik D. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Recent work has developed a theory of motion-planning gadgets, which are a useful tool for proving hardness for a variety of problems that can be thought of in terms of an agent navigating a dynamic environment. We introduce formal objects representing motion-planning gadgets, which we call gizmos, and ask which gizmos simulate each other—simulations between gizmos yield reductions between natural decision problems, so this has consequences for complexity. We define several classes of gizmos, and prove that they are closed under simulation: gizmos with some property cannot simulate gizmos without it. For several of these classes, we also find a gizmo which can simulate every gizmo in the class; this is analogous to completeness for a complexity class. We consider gizmo simulation and prove unsimulability and universality in two restricted settings: planar simulation, where the simulation must embed in the plane without crossings, and input/output simulation, which is a model for fully deterministic settings. We mostly focus on simulations with finitely many gizmos and gizmos with finitely many states (called regular), but many of our results carry over to more exotic infinite gizmos. S.M. 2022-01-14T15:00:56Z 2022-01-14T15:00:56Z 2021-06 2021-06-24T19:22:17.427Z Thesis https://hdl.handle.net/1721.1/139275 In Copyright - Educational Use Permitted Copyright retained by author(s) https://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Hendrickson, Dylan Gadgets and Gizmos: A Formal Model of Simulation in the Gadget Framework for Motion Planning |
| title | Gadgets and Gizmos: A Formal Model of Simulation in the Gadget Framework for Motion Planning |
| title_full | Gadgets and Gizmos: A Formal Model of Simulation in the Gadget Framework for Motion Planning |
| title_fullStr | Gadgets and Gizmos: A Formal Model of Simulation in the Gadget Framework for Motion Planning |
| title_full_unstemmed | Gadgets and Gizmos: A Formal Model of Simulation in the Gadget Framework for Motion Planning |
| title_short | Gadgets and Gizmos: A Formal Model of Simulation in the Gadget Framework for Motion Planning |
| title_sort | gadgets and gizmos a formal model of simulation in the gadget framework for motion planning |
| url | https://hdl.handle.net/1721.1/139275 |
| work_keys_str_mv | AT hendricksondylan gadgetsandgizmosaformalmodelofsimulationinthegadgetframeworkformotionplanning |