Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch

DOI10.1137/18M1194341zbMath1452.68240arXiv1801.01689WikidataQ126664291 ScholiaQ126664291MaRDI QIDQ5203793

Christian Scheffer, Sándor P. Fekete, Erik D. Demaine, Phillip Keldenich, Henk G. Meijer

Publication date: 9 December 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

complexityapproximationmakespanrobot swarmsparallel motionbounded stretchcoordinated motion planning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Artificial intelligence for robotics (68T40)

Related Items

Coordinating Swarms of Objects at Extreme Dimensions, Motions of a connected subgraph representing a swarm of robots inside a graph of work stations, Space-aware reconfiguration, Multi-robot motion planning for unit discs with revolving areas, Discrete configuration spaces of squares and hexagons, Shadoks Approach to Low-Makespan Coordinated Motion Planning, Coordinated Path Planning through Local Search and Simulated Annealing, Tilt assembly: algorithms for micro-factories that build objects with uniform external forces, Space-Aware Reconfiguration

Uses Software

• Walksat

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The increasing cost tree search for optimal multi-agent pathfinding
• Strong NP-hardness of moving many discs
• Convex blocking and partial orders on the plane
• On multiple moving objects
• Sorting in constant number of row and column phases on a mesh
• Mesh permutation routing with locality
• Universal continuous routing strategies
• Motion planning for multiple robots
• Graph puzzles, homotopy, and the alternating group
• On reconfiguration of disks in the plane and related problems
• Subdimensional expansion for multirobot path planning
• Conflict-based search for optimal multi-agent pathfinding
• Moving coins
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Approximation Algorithms for Movement Repairmen
• Minimizing movement
• O(1)-Approximations for Maximum Movement Problems
• SLIDING DISKS IN THE PLANE
• Reducing Multiple Object Motion Planning to Graph Searching
• Minimizing Movement: Fixed-Parameter Tractability
• Computing by Mobile Robotic Sensors
• Organic Computing — A Paradigm Shift for Complex Systems
• Enhanced Partial Expansion A*
• Reconfigurations in Graphs and Grids
• Geometry helps in bottleneck matching and related problems
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants