Hardness of Reconfiguring Robot Swarms with Uniform External Control in\n Limited Directions

Motivated by advances is nanoscale applications and simplistic robot agents,\nwe look at problems based on using a global signal to move all agents when\ngiven a limited number of directional signals and immovable geometry. We study\na model where unit square particles move within a 2D grid based on uniform\nexternal forces. Movement is based on a sequence of uniform commands which\ncause all particles to move 1 step in a specific direction. The 2D grid board\nadditionally contains "blocked" spaces which prevent particles from entry.\nWithin this model, we investigate the complexity of deciding 1) whether a\ntarget location on the board can be occupied (by any) particle (\\emph{occupancy\nproblem}), 2) whether a specific particle can be relocated to another specific\nposition in the board (\\emph{relocation problem}), and 3) whether a board\nconfiguration can be transformed into another configuration\n(\\emph{reconfiguration problem}). We prove that while occupancy is solvable in\npolynomial time, the relocation and reconfiguration problems are both\nNP-Complete even when restricted to only 2 or 3 movement directions. We further\ndefine a hierarchy of board geometries and show that this hardness holds for\neven very restricted classes of board geometry.\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC