The Parameterized Complexity of Motion Planning for Snake-Like Robots
Authors: Siddharth Gupta, Guy Sa'ar, Meirav Zehavi
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study a motion-planning problem inspired by the game Snake that models scenarios like the transportation of linked wagons towed by a locomotor to the movement of a group of agents that travel in an ant-like fashion. Given a snakelike robot with initial and final positions in an environment modeled by a graph, our goal is to decide whether the robot can reach the final position from the initial position without intersecting itself. ...Nevertheless, we prove that even on general graphs, it is solvable in time k O(k)|I|O(1) where k is the size of the robot, and |I| is the input size. ...We present a comprehensive picture of the parameterized complexity of SNAKE GAME parameterized by the size of the snake, k. ...our contribution is threefold. I. FPT Algorithm. ...we develop an algorithm that solves SNAKE GAME in time k O(k) n O(1). II. Kernelization. ...shows that SNAKE GAME is unlikely to admit a polynomial kernel... III. Treewidth-Reduction. ...we develop a polynomial-time algorithm that given an instance of SNAKE GAME, outputs an equivalent instance of SNAKE GAME where the treewidth of the graph is bounded by a polynomial in k. |
| Researcher Affiliation | Academia | Siddharth Gupta1 , Guy Sa ar1 , Meirav Zehavi1 1Ben-Gurion University of the Negev, Israel {siddhart, saag}@post.bgu.ac.il, meiravze@bgu.ac.il |
| Pseudocode | Yes | Algorithm 1: sparse Configuration Graph(SG, k) |
| Open Source Code | No | The paper does not contain any statements about releasing source code or provide links to a code repository. |
| Open Datasets | No | The paper focuses on theoretical computer science, proving complexity results and designing algorithms. It does not involve empirical evaluation on datasets, thus there is no mention of publicly available datasets for training. |
| Dataset Splits | No | The paper describes theoretical results and algorithms, and does not conduct empirical experiments or use datasets that would require training/validation/test splits. |
| Hardware Specification | No | The paper focuses on theoretical computer science, presenting algorithms and complexity proofs. It does not describe any empirical experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical, describing algorithms and complexity results, and does not mention any software implementations or dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and complexity analysis. It does not include any empirical experiments or mention specific experimental setup details such as hyperparameters or training settings. |