Finite-State Robots in a Warehouse: Achieving Linear Parallel Speedup While Rearranging Objects

We have teams of r identical mobile finite-state machines (FSMs, for short) act as robots that rearrange objects within a "warehouse" whose floor is the side-n square mesh M_n. We study a variety of rearrangement problems that (teams of) FSMs can solve via algorithms that are scalable-i.e., that work in arbitrarily large meshes-and fully pipeline able-i.e., that achieve (asymptotic) linear speedup when larger teams of FSMs are deployed. Regarding pipelining, in detail: If r FSMs can solve a problem on M_n in time T_r(n), then as r grows, even as large as n, T_r(n) = O((1/r) T_1(n)), uniformly in n and r. The rearrangement problems we have chosen are reminiscent of tasks that one might have robots perform in a warehouse. Sample problems have FSMs move objects from the top edge of M_n to the bottom edge: (1) in the reverse of the objects\´ original top-edge order, (2) in piles organized by object type (from a fixed set of types).