Finite-State Module Development

In the preceding chapter, three finite-state techniques were presented: transducers (finite-state machines), recognizers, and acceptors (finite-state automata). Both modules have different interfaces, but there are common concepts in the passing of information within the architecture.

Data Exchange

Like other AI modules, finite-state machines take inputs and produce outputs. The data can be passed as parameters to functions (used synchronously to pass control), or messages between the components of the architecture (used asynchronously to interrupt control). In the case of finite-state machines, it's often convenient to support both of these paradigms. The functions provide efficient support for batch processing, whereas the events allow incremental updates driven by events.

Depending on the approach taken, a different representation may be the most efficient. For example, the functional approach needs to identify transitions based on the current state, whereas the event-driven approach needs to identify the state based on the transition symbol.

A Finite-State Automaton

finite-state automata can recognize and classify sequences. The input of finite-state automata is therefore an array of characters, or any other type of symbol that can trigger transitions between states. The output can be any form of data, although usually a categorical variable (for classification) or a Boolean (for recognition):

bool Accept( const vector<Symbol>& sequence );
Symbol Recognize( const vector<Symbol>& sequence );

Using these functions, the automaton will be reset before the simulation starts. Using message passing, the inputs will be processed incrementally. An output message will be sent when a terminal state is reached. The automaton is reset automatically in this case, but this is also possible using the Reset() function in the interface if necessary.

A Finite-State Machine

Finite-state machines, on the other hand, provide an output for every input symbol. The interface to the finite-state machine could alternatively provide a step-by-step approach, or take a sequence of symbols and return another:

Symbol Tick( const Symbol in );
void Simulate( const vector<Symbol>& in, vector<Symbol>& out );

These functions provide synchronous behavior. On the other hand, the asynchronous approach works incrementally, generating messages immediately as others are received. Again, an explicit Reset() call may be used to initialize the machine.

Specification

The file format used to store the layout of the finite-state machines is XML, as shown in Listing 39.1. The file is an arbitrary number of states, each with outgoing transitions. The transitions have a target state and matching inputs. Both states and transitions can optionally have outputs.

Listing 39.1 An Example of a Single State of a Finite-State Machine Described Using XML

<state name="surprise">
     <transition input="door_open" target="anticipation" />
     <transition input="explosion" target="fear" />
     <output
          precision="0.4"
          delay="0.1"
     />
</state>

The definition for a finite-state machine that processes symbols is relatively straightforward. When the finite-state machine relies on procedural code and the declarative approach, the specification needs additional syntax. This will be introduced in Chapter 42.

Further Information The Library Reference on the web site at http://fear.sf.net/ contains more information about the specification and implementation of finite-state machines in FEAR.

Implementation

The finite-state automata and machines need to store their internal graph, as well as the active state. The current state itself can be represented as an index into the array of states, or even a reference to a C++ instance. The transition table is stored as an array of states, each mapping the input symbol onto the destination state. Each state also stores the data that has been defined by the user.

The generic containers from the Standard Template Library provide a convenient way to load the layout from a file and allocate arbitrary arrays at runtime—without having to worry about memory issues.

After the interfaces have been defined, the data structures have been declared, and the layout of the finite-state machine has been loaded, the simulation is surprisingly easy to implement, as shown in Listing 39.2. The declarative approach used in this chapter simplifies the module significantly.

Listing 39.2 A Single Update of a Moore Finite-State Machine

function Tick( Symbol in )
      # look up the next state in the array of lists
      state = transition[state][in]
      # locate the data stored for this state
      return data[state]
end function