Software

Introduction to Finite State Machines

Posted 13 Jul 2002 at 22:03 UTC by steve Share This

AI Depot has posted a very good article by Jason Brownlee that introduces and explains Finite State Machines. The article is written from the perspective of a video game AI designer but could be applied equally well to robotics. If you find FSM's an intriguing idea for robotics use, check out NMI's IsoPod controller that we covered recently. It uses a programming language called IsoMax which is based on FSMs.


Finite State Machines, posted 15 Jul 2002 at 17:08 UTC by RMDumse » (Master)

The realization of the use of Finite State Machines dates back to the beginning days of computing. The two men first writing about them were Mealy and Moore in the mid fifties. Each had a slightly different view of where the outputs were connected to the state machine, but otherwise had similar views. (Moore thought the state itself made the outputs, and Mealy thought the transition made the outputs, which were then static while in the state.)

The classic text describing Finite State Machines is "Switching and Finite Automata Theory" by Kohavi first published in 1970. While long a regular tool of the hardware designer, it has not been widely known in software circles.

As mentioned Finite State Machines have widely been used to design hardware. You will commonly see them when tough sequencing problems are described. They stand in where flow charts simply become to wild to follow, for instance in describing the bus arbitration in early 68000 documents.

It is very interesting to see the game software had to resort to state machine technology. In retrospect, it almost seems obvious they'd have to given the difficulty in creating Isostructure with in a structured programming environment. Similarly Brooks finds them the preferred way to design behaviors, as described in Mobile Robots.

Some problems just scream for a solution of one kind or another, and Finite State Machines answer many common programming problems better than any other particularly where real time control or process control are involved. So to see the concept discovered and rediscovered over and over again testifies (at least hopefully) to its forecoming popularity.

My experience in working on IsoMax(TM) development over past eight years is: every programmer who makes the paradigm shift, is forever changed, and can never look at one of those intractable IF THEN nests of structured confusion without seeing the essence of the problem, the need for a state machine to simplify and streamline the code. I would strongly recommend robotics users to look into State Machines if you don't know them, or how to program them. There is a huge reward in programming efficiency, and tools to make that even easier (IsoMax(TM)) are now available.

The best description of FSM's , posted 22 Jul 2002 at 00:44 UTC by Chuck McM. » (Master)

If you can find a copy of the "Feignman Lectures on Computation" you will find an excellent description of FSM's of all types and their relationship with Turing engines. I must say I never really understood how they worked until I read that book.

Feynman Lectures on Computation, posted 23 Jul 2002 at 15:49 UTC by steve » (Master)

Here's a link to the book on Amazon:

Feynman Lectures on Computation

See more of the latest robot news!

Recent blogs

17 Oct 2014 mwaibel (Master)
14 Oct 2014 shimniok (Journeyer)
5 Aug 2014 svo (Master)
20 Jul 2014 Flanneltron (Journeyer)
3 Jul 2014 jmhenry (Journeyer)
3 Jul 2014 steve (Master)
2 Jul 2014 Petar.Kormushev (Master)
10 Jun 2014 robotvibes (Master)
10 May 2014 evilrobots (Observer)
2 Mar 2014 wedesoft (Master)
X
Share this page