Geodesic
The Parking Problem for Finite-State Robots
Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 483-506.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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
DOI : 10.7155/jgaa.00271
Keywords: FSM-robots, Finite-state machines, Searching and exploration in a mesh 
@article{JGAA_2012_16_2_a13,
     author = {Arnold Rosenberg},
     title = {The {Parking} {Problem} for {Finite-State} {Robots}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {483--506},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2012},
     doi = {10.7155/jgaa.00271},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00271/}
}
TY  - JOUR
AU  - Arnold Rosenberg
TI  - The Parking Problem for Finite-State Robots
JO  - Journal of Graph Algorithms and Applications
PY  - 2012
SP  - 483
EP  - 506
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00271/
DO  - 10.7155/jgaa.00271
LA  - en
ID  - JGAA_2012_16_2_a13
ER  - 
%0 Journal Article
%A Arnold Rosenberg
%T The Parking Problem for Finite-State Robots
%J Journal of Graph Algorithms and Applications
%D 2012
%P 483-506
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00271/
%R 10.7155/jgaa.00271
%G en
%F JGAA_2012_16_2_a13
Arnold Rosenberg. The Parking Problem for Finite-State Robots. Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 483-506. doi : 10.7155/jgaa.00271. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00271/

Cité par Sources :