Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00271 The Parking Problem for Finite-State Robots Arnold L. Rosenberg Vol. 16, no. 2, pp. 483-506, 2012. Regular paper Abstract This paper is a step toward understanding the algorithmic concomitants of modeling robots as mobile finite-state machines (FSMs, for short) that travel within square two-dimensional meshes (which abstract the floors of laboratories or factories or warehouses). We study the ability of FSMs to scalably perform a simple path-planning task called parking, within fixed square meshes of arbitrary sizes. This task: (1) has each FSM head for its nearest corner of the mesh and (2) has all FSMs within a corner organize into a maximally compact formation (one that minimizes a compactness-measuring potential function). 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 in enabling FSMs to park. Many initial configurations of FSMs can park, including: (a) a single FSM situated initially along an edge of the mesh; (b) any assemblage of FSMs that begins with two designated adjacent FSMs. These configurations can park even without using (digital analogues of) pheromones, an algorithmic aid advocated by some who use FSMs to model ant-inspired robots. In contrast, a single 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
|
Submitted: September 2011. Reviewed: January 2012. Revised: March 2012. Accepted: July 2012. Final: July 2012. Published: August 2012. Communicated by Paolo Ferragina |
| Journal of Graph Algorithms and Applications |