The parameterized complexity of motion planning for snake-like robots

DOI10.1613/JAIR.1.11864MaRDI QIDQ5130004zbMATHOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• A survey of motion planning and related geometric algorithms
• Color-coding
• Configuration spaces and robot motion planning algorithms
• Coordinated motion planning: reconfiguring a swarm of labeled robots with bounded stretch
• Fundamentals of parameterized complexity
• Games, puzzles, and computation
• Gaming is a hard job, but someone has to do it!
• Graph minors. XIII: The disjoint paths problem
• How to navigate through obstacles?
• Kernelization Lower Bounds by Cross-Composition
• Kernelization. Theory of parameterized preprocessing
• Minimizing movement: fixed-parameter tractability
• On problems without polynomial kernels
• On two geometric problems related to the travelling salesman problem
• Parameterized algorithms
• Parameterized complexity classes beyond para-NP
• Polynomial bounds for the grid-minor theorem
• Push-pull block puzzles are hard
• Reconfiguring undirected paths
• Survey of robot 3D path planning algorithms
• The complexity of Snake and undirected NCL variants
• Towards tight(er) bounds for the excluded grid theorem

Cited in

(6)

• The parameterized complexity of coordinated motion planning
• Computational complexity of motion planning of a robot through simple gadgets
• The complexity of Snake and undirected NCL variants
• 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)