Control Logic

Until now, we've discussed finite-state machines as computational models capable of creating an output string in terms of an input string. These outputs can also indicate whether the input was recognized or accepted. When embedded within a real system, these outputs can also be used as a control mechanism. Although the theory behind finite-state machines is very robust, the extent of the practical applications reveals the finite-state machine to be an undeniably useful tool.

All the finite-state machines discussed can be directly applied to control already. This section discusses specific tricks that are often used, and points out potential problems that can arise. Solutions to these problems are explained.

Procedural Approach

Although the symbol processing model captures the essence of control logic, this is a very formal way of proceeding. A more practical approach is often taken instead: the procedural approach. In this case, each transition is a hard-coded function, which can be queried to determine whether the transition should be taken.

The states themselves are also native procedures performing tasks when the respective state is active. This approach proves often easier in the short term; building one state machine will involve minimal overhead and allow all the code to be explicit. There is also no need for a mechanism to pass symbols around; everything can be programmed as sensors (transitions) and actuators (states).

Potential Problems with Procedural Finite-State Machines

Aside from the practical problems (that is, code complexity), there are also theoretical issues to deal with. The finite-state machine that is implemented may not behave as expected diverging from the design.

Sequential Chaos and Ambiguity

In theory, finite-state machines are passed a sequence of input characters that are used for the transitions. These inputs are implicitly ordered because they belong to a sequence; that's the way the problem is defined. In procedural code, there is no dedicated queue where all the symbols are placed; the transition functions are checked by the simulation. The order in which the transition functions are processed has a great impact on the result of the simulation; the transitions checked first have an implicit priority over all the other transitions.

Consider, for instance, an animat is in a wander state. If the presence of an enemy is checked first, the hunt mode will be engaged. On the other hand, if nearby armor is identified first, the gather state may become active. These variations potentially result in unintuitive bugs.

Theoretically speaking, the finite-state machine basically interprets the order of the symbols based on the implementation, which results in an unforeseen bias in the design. (Some transitions are preferred.) This poses problems because there's no formal way to model such ambiguity. So the procedural implementation may behave differently than the design itself. This can be understood as a type of nondeterminism (discussed further in Chapter 40, "Nondeterministic State Machines").

Loss of Data

If the code is purely procedural, each transition is checked on-the-fly. There's no intrinsic way to remember sequences of events that happen. Given two transition conditions that are true at the same time, only the first transition is processed; the second is ignored. In general, this approach intrinsically discards all the information about transitions conditions that occur after the first has been taken.

For example, the animat is in combat mode. Simultaneously, the health drops very low and an armor object appears nearby. The armor is checked first, so the gather state becomes active. The low health transition to the flee state is ignored and forgotten, and the animat gets shot as a result.

This problem is a consequence of dealing with ambiguity using plain procedural code. In many such cases, ignoring transitions can lead to incomplete or inconsistent behaviors. Once again, this results in buggy behaviors that are not obvious from the finite-state machine design.

Flow Control

In the code, transitions may be processed within the states' procedures. Indeed, it's often easier to check for transitions during the update which can also prevent redundant processing. The problem is deciding where the control goes next. Is the transition followed immediately? Does the simulation continue processing the procedural state code instead? In this second case, how do we deal with multiple transitions that happen at different times during the state update?

Remedies for Procedural Control

The first step for solving these problems is to identify them. Precautions can then be taken when they are encountered. However, a better approach defines methodologies preventing the problems from arising at all.

When to Redesign?

Most of the problem can be understood as having to deal with large state procedures (for instance, wander behavior) that can be interrupted by multiple transitions (for instance, to flee or gather).

A programmer's solution would find a programming language trick that can be used to simplify the issue. For example, the state procedure could check the transitions itself, and return a code indicating the necessary transition. If multiple nested procedures are required to simulate this state, the return codes need to be cascaded.

However, the AI engineer would realize that a lot of redundant work is being done, and that each of the code paths can in fact be handled by the finite-state machine. Enforcing this requires respecting a single constraint; state procedures are atomic and cannot be interrupted. The entire finite-state machine can be designed around this principle, instead of using programmatic hacks as temporary solutions.

Code Structure

Given these principles of atomicity, the code can be reorganized. It's good practice to keep transitions and state procedures separate. Then, a convention can be established to decide when to process the transitions. Usually, they are all checked after the state update has been done.

The great advantage of grouping all the transitions at once is that they can be easily identified in the code. Problems of ambiguity can be resolved very simply; the transitions can be given a priority. The transition with the highest priority can be checked first, and the rest discarded. These priorities can be built in to the design and translated directly into code.

There are still two problems remaining that code organization doesn't solve. First, there is a small efficiency price to pay for this, because the transitions may do some redundant processing (which could be made common in the state procedures). Second, there is no way to deal with multiple transitions and storing events for later.

Message Passing

A small data structure solves both these problems by temporarily storing requests for transitions. This can be as a simple message-passing mechanism, but used to simulate the sequence of input characters. This is not as efficient as the purely procedural finite-state machine, but still beats all the other AI techniques in the book in terms of raw performance.

The state update procedure can queue transition messages so the transitions do not need to process redundant information. These messages can also persist, such that important events are not forgotten, and will eventually be taken into account. (For instance, the need to flee is important and should affect the state.)

Naturally, not all the messages generated by the state update procedure need to be stored until processed. These can be called temporary messages. These need to be collected separately from the message queue, and discarded if they are not needed.

Merging this queuing system with the transition priorities, we get a priority queue that is capable of dealing with all the problems discussed. In this case, only the temporary message with the highest priority needs to be kept, and is discarded if its priority is lower than the priority of the message at the front of the queue.

Note

The priority queue is not adding extra power to the finite-state machine. The simulation uses a data structure to transform procedural information into a more formal input sequence, mainly to maintain coherence ensuring that the behaviors in the game correspond intuitively to the design.