Multi-robot motion planning of k-colored discs is PSPACE-hard

DOI10.4230/LIPICS.FUN.2021.15MaRDI QIDQ6487587zbMATH OpenFDO

Authors Thomas Brocken, G. Wessel van der Heijden, Irina Kostitsyna, Lloyd E. Lo-Wong, Remco J. A. Surtel

Publication date 7 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.FUN.2021.15

zbMATH Keywords

algorithmic complexitydisc-robot motion planningPSPACE-hardness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Artificial intelligence for robotics (68T40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Reducing Multiple Object Motion Planning to Graph Searching
• Motion planning for multiple robots
• Motion planning in the presence of moving obstacles
• Coordinated motion planning: reconfiguring a swarm of labeled robots with bounded stretch
• Lower Bounds for Geometrical and Physical Problems

Cited in

(4)

• Unlabeled multi-robot motion planning with tighter separation bounds
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle and beyond
• Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings
• Optimal motion planning for two square robots in a rectilinear environment

This page was built for publication: Multi-robot motion planning of \(k\)-colored discs is PSPACE-hard

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