Relocating Units in Robot Swarms with Uniform Control Signals is PSPACE-Complete

Title: Relocating Units in Robot Swarms with Uniform Control Signals is PSPACE-Complete

Authors: David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, Tim Wylie

Conference: The 32nd Canadian Conference on Computational Geometry (CCCG 2020)

Abstract: This paper investigates a restricted version of robot motion planning, in which particles on a board uniformly respond to global signals that cause them to move one unit distance in a particular direction on a 2D grid board with geometric obstacles. We show that the problem of deciding if a particular particle can be relocated to a specified location on the board is PSPACE-complete when only allowing 1×1 particles. This shows a separation between this problem, called the relocation problem, and the occupancy problem in which we ask whether a particular location can be occupied by any particle on the board, which is known to be in P with only 1×1 particles. We then consider both the occupancy and relocation problems for the case of extremely simple rectangular geometry, but slightly more complicated pieces consisting of 1×2 and 2×1 domino particles, and show that in both cases the problems are PSPACE-complete.

Virtual Talk:

Accompanying Videos: