Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00271
The Parking Problem for Finite-State Robots
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 Supporters
|