The parameterized complexity of motion planning for snake-like robots

DOI10.1613/JAIR.1.11864zbMATH Open1490.68121arXiv1903.02445OpenAlexW3089186721MaRDI QIDQ5130004FDOQ5130004

Authors: Siddharth Gupta, Guy Sa'Ar, Meirav Zehavi 

Publication date: 3 November 2020

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Abstract: We study the parameterized complexity of a variant of the classic video game Snake that models real-world problems of motion planning. Given a snake-like robot with an initial position and a final position in an environment (modeled by a graph), our objective is to determine whether the robot can reach the final position from the initial position without intersecting itself. Naturally, this problem models a wide-variety of scenarios, ranging from the transportation of linked wagons towed by a locomotor at an airport or a supermarket to the movement of a group of agents that travel in an `ant-like' fashion and the construction of trains in amusement parks. Unfortunately, already on grid graphs, this problem is PSPACE-complete [Biasi and Ophelders, 2016]. Nevertheless, we prove that even on general graphs, the problem is solvable in time $k^{mathcalO(k)}|I{|}^{mathcalO(1)}$ where $k$ is the size of the snake, and $|I|$ is the input size. In particular, this shows that the problem is fixed-parameter tractable (FPT). Towards this, we show how to employ color-coding to sparsify the configuration graph of the problem to have size $k^{mathcalO(k)}|I{|}^{mathcalO(1)}$ rather than $|I{|}^{mathcalO(k)}$. We believe that our approach will find other applications in motion planning. Additionally, we show that the problem is unlikely to admit a polynomial kernel even on grid graphs, but it admits a treewidth-reduction procedure. To the best of our knowledge, the study of the parameterized complexity of motion planning problems (where the intermediate configurations of the motion are of importance) has so far been largely overlooked. Thus, our work is pioneering in this regard.

Full work available at URL: https://arxiv.org/abs/1903.02445

Recommendations

• The Complexity of Snake
• Computational complexity of motion planning of a robot through simple gadgets
• The complexity of Snake and undirected NCL variants
• Simple wriggling is hard unless you are a fat hippo
• Minimizing Movement: Fixed-Parameter Tractability

zbMATH Keywords

motion planningrobotics

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Artificial intelligence for robotics (68T40) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Fundamentals of parameterized complexity
• On problems without polynomial kernels
• Graph minors. XIII: The disjoint paths problem
• Title not available (Why is that?)
• Color-coding
• Parameterized algorithms
• Kernelization Lower Bounds by Cross-Composition
• Games, puzzles, and computation
• Survey of robot 3D path planning algorithms
• On two geometric problems related to the travelling salesman problem
• Gaming is a hard job, but someone has to do it!
• A survey of motion planning and related geometric algorithms
• Configuration spaces and robot motion planning algorithms
• Kernelization
• The complexity of Snake and undirected NCL variants
• Towards Tight(er) Bounds for the Excluded Grid Theorem
• Polynomial bounds for the grid-minor theorem
• Parameterized complexity classes beyond para-NP
• Title not available (Why is that?)
• Minimizing movement: fixed-parameter tractability
• Reconfiguring undirected paths
• Push-pull block puzzles are hard
• How to Navigate Through Obstacles

Cited In (3)

• Reconfiguration of time-respecting arborescences
• Reconfiguring (non-spanning) arborescences
• Reconfiguring directed trees in a digraph

This page was built for publication: The parameterized complexity of motion planning for snake-like robots

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5130004)