Finite state automata

Finite state automata

Finite state automata (FSA) are FINITE STATE a set of popular mechanisms for specifying
AUTOMATA what a program should be doing at a given time or circumstance. The FSA
STATE DIAGRAM can be written as a table or drawn as a state diagram, giving the designer a
visual representation. Most designers do both. There are many variants of

all possible inputs. As shown in Fig. 5.8, there are only two releasers for the
UGR example, so the table doesn’t have many rows.
TRANSITION FUNCTION The third part of the FSMis the transition function, called , which specifies
what state the robot is in after it encounters an input stimulus, . The set of
stimulus or affordances  that can be recognized by the robot is represented
by  (a capital ). These stimuli are represented by arrows. Each arrow represents
the releaser for a behavior. The new behavior triggered by the releaser
depends on the state the robot is in. This is the same as with Innate Releasing
Mechanisms, where the animal literally ignores releasers that aren’t relevant
to its current state.

Recall also in the serial programimplementations of IRMs in Ch. 3 that the
agent “noticed” releasers every second. At one iteration through the loop,
it might be hungry and “enter” the state of feeding. In the next iteration, it
might still be hungry and re-enter the state of feeding. This can be represented
by having arrows starting at the feeding state and pointing back to
the feeding state.
For the example in Fig. 5.8, the robot starts in the state of following a line.
This means that the robot is not prepared to handle a visual distraction (range
near) until it has started following a line. If it does, the program may fail because
the FSA clearly shows it won’t respond to the distraction for at least
one update cycle. By that time, the robot may be heading in the wrong direction.
Starting in the following-line state fine for the UGR competition, where
it was known in advance that there were no bales of hay near the starting
line. A more general case is shown in Fig. 5.9, where the robot can start either
on a clear path or in the presence of a bale. The FSA doesn’t make it
clear that if the robot starts by a bale, it better be pointed straight down the
path!
The fourth piece of information that a designer needs to know is when the
robot has completed the task. Each state that the robot can reach that terminates
the task is a member of the FINAL STATE set of final state, F. In the UGR example,
the robot is never done and there is no final state—the robot runs until it is
turned off manually or runs out of power. Thus, both states are final states.
If the robot could recognize the finish line, then it could have a finish state.
The finish state could just be stopped or it could be another behavior, such
as a victory wag of the camera. Notice that this adds more rows to the FSA
table, since there must be one row for each unique state.
In many regards, the FSA table is an extension of the behavioral table.
The resulting table is known as a finite state machine and abbreviatedM for
machine. The notation:
M = fK;; ; s; Fg
is used as reminder that in order to use a FSA, the designer must know all
the q states (K), the inputs  the transitions between the states , the special
starting state q0, and the terminating state(s) (F). There must be one arrow
in the state diagram for every row in the table. The table below summarizes
the relationship of FSA to behaviors: