The Parking Problem for Finite-State Robots - Rosenberg, Arnold (Journal of Graph Algorithms and Applications, 2012)
This paper is a step toward understanding the algorithmic concomitantsof modeling robots as mobile finite-state machines (FSMs, for short)that travel within square two-dimensional meshes (which abstract thefloors of laboratories or factories or warehouses). We study theability of FSMs to scalably perform a simple path-planning taskcalled parking, within fixed square meshes of arbitrary sizes.This task: (1) has each FSM head for its nearest corner of the meshand (2) has all FSMs within a corner organize into a maximally compactformation (one that minimizes a compactness-measuring potentialfunction). The problem thus requires FSMs to know "where they are"within a mesh, specifically which quadrant they reside in. Indeed,quadrant determination is the central technical issue inenabling FSMs to park. Many initial configurations of FSMs canpark, including: (a) a single FSM situated initially along an edgeof the mesh; (b) any assemblage of FSMs that begins with twodesignated adjacent FSMs. These configurations can park even withoutusing (digital analogues of) pheromones, an algorithmic aid advocatedby some who use FSMs to model ant-inspired robots. In contrast, asingle FSM in the interior of (even a one-dimensional) mesh cannot park, even with the help of (volatile digital) pheromones. <!----> Key words:FSM-robots; Finite-state machines; Searching and exploration in a mesh