Indian Journal of Science and Technology

Open Access Open Access  Restricted Access Subscription Access

Algorithm for Automaton Specification for Exploring Dynamic Labyrinths


Affiliations
1 School of Computing, Bharath University, Chennai-600073
2 Dept of Computer Applications Bharath University, Chennai-600073
 

A variety of interesting problems arise in the study of finite automata that move about in a two dimensional space. The model proposed by Muller [4] is used here to construct new automaton which can explore any labyrinth and escape through the moving or dynamic obstacles inside over the grid. The earlier results were shown for static obstacles distributed over integer grid and the automaton in this case was constructed to interact on the rectangular grid location endowed with four neighborhood directional states. In this paper we allow obstacles moving in discrete steps and verify that the finite automaton with just five printing symbols can escape or find the exit.

Keywords

Labyrinths, Finite State Automaton, Printing Mouse, Free Way of Escape
User

  • Active-Robots (n.d.) (2008). Cruiser Maze Solver Robot. Available from: http://www.microrobot.co.kr, http://www.activerobots.com/products/robots/cruiser-details-2.shtml.

  • Bruggemann B (2006). Entkommen aus unbekannten labyrinthen mit einbahnstrassen, Master’s thesis, Rheinische Friedrich Wilhelms Universität Bonn.

  • Bruggemann B, Kamphans T et al. (2007). Leaving an unknown maze with one-way roads, in Abstracts 23nd European Workshop Computational Geometry, Graz, Austria, 90–93.

  • Muller H (1977). A one symbol printing automation escaping from every labyrinth, Computing Springer Verlag, vol 19, 95–110.

  • Muller H (1971). Endliche automaten und labyrinthen, Elecktronishe Informations verarbeitung und Kybernetik, vol 7(4), 261–264.

  • Muller H (1971). Stack automaten in labyrinthen, Archiv Für Mathematische Logik Und Grundlagenforschung, vol 14 (3-4), 127–134.

  • Nolfi S, and Floreano D (2000). Evolutionary robotics: the biology, intelligence, and technology of self-organizing machines (Intelligent Robotics and Autonomous Agents), Bradford Books.


Abstract Views: 471

PDF Views: 0




  • Algorithm for Automaton Specification for Exploring Dynamic Labyrinths

Abstract Views: 471  |  PDF Views: 0

Authors

A. Kumaravel
School of Computing, Bharath University, Chennai-600073
K. Rangarajan
Dept of Computer Applications Bharath University, Chennai-600073

Abstract


A variety of interesting problems arise in the study of finite automata that move about in a two dimensional space. The model proposed by Muller [4] is used here to construct new automaton which can explore any labyrinth and escape through the moving or dynamic obstacles inside over the grid. The earlier results were shown for static obstacles distributed over integer grid and the automaton in this case was constructed to interact on the rectangular grid location endowed with four neighborhood directional states. In this paper we allow obstacles moving in discrete steps and verify that the finite automaton with just five printing symbols can escape or find the exit.

Keywords


Labyrinths, Finite State Automaton, Printing Mouse, Free Way of Escape

References





DOI: https://doi.org/10.17485/ijst%2F2013%2Fv6iS5%2F33354