Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Hardness of Reconfiguring Robot Swarms with Uniform External Control in
  Limited Directions   Motivated by advances is nanoscale applications and simplistic robot agents,
we look at problems based on using a global signal to move all agents when
given a limited number of directional signals and immovable geometry. We study
a model where unit square particles move within a 2D grid based on uniform
external forces. Movement is based on a sequence of uniform commands which
cause all particles to move 1 step in a specific direction. The 2D grid board
additionally contains "blocked" spaces which prevent particles from entry.
Within this model, we investigate the complexity of deciding 1) whether a
target location on the board can be occupied (by any) particle (\emph{occupancy
problem}), 2) whether a specific particle can be relocated to another specific
position in the board (\emph{relocation problem}), and 3) whether a board
configuration can be transformed into another configuration
(\emph{reconfiguration problem}). We prove that while occupancy is solvable in
polynomial time, the relocation and reconfiguration problems are both
NP-Complete even when restricted to only 2 or 3 movement directions. We further
define a hierarchy of board geometries and show that this hardness holds for
even very restricted classes of board geometry.

13
The categories of this paper are: quant-ph
2
The categories of this paper are: math
8
The categories of this paper are: hep-ex
17
The categories of this paper are: q-fin
31
The categories of this paper are: ao-sci
29
The categories of this paper are: funct-an
21
The categories of this paper are: adap-org
24
The categories of this paper are: dg-ga
37
The categories of this paper are: supr-con
14
The categories of this paper are: math-ph
19
The categories of this paper are: eess
35
The categories of this paper are: mtrl-th
0
The categories of this paper are: hep-ph
3
The categories of this paper are: physics
9
The categories of this paper are: nlin
28
The categories of this paper are: alg-geom