Toward a general complexity theory of motion planning: Characterizing which gadgets make games hard
We begin 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 withi...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
2020
|
| Online Access: | https://hdl.handle.net/1721.1/128783 |