Hierarchies

Understanding HFSMs involves defining a hierarchy. A hierarchy is a set of objects assembled together on multiple levels, generally contained within each other. As objects are nested inside others, hierarchies can be represented as trees, with the root node of the tree being the top object of the hierarchy (see Figure 41.1).

Figure 41.1. Example of nested nodes and the corresponding tree representing the hierarchy.

In the case of finite-state machines, hierarchies can be defined just as nested states or entire machines. This proves to be a good way of understanding the different benefits of hierarchical state machines (HSMs).

Nested States

The definition of an HSM primarily allows states to be defined within each other. States that englobe other states are known as superstates. This has no effect on the computational capabilities of finite-state machines, because all hierarchical models can be flattened out with each transition made explicit. In many cases, the hierarchy leads to simpler models.

The number of states in the HSM will generally not diminish compared to the flat finite-state machine. In fact, if the higher-level states are counted too (that is, superstates), the total number of states increases. This kind of hierarchy allows the abstraction of transitions (see Figure 41.2).

Figure 41.2. A superstate defined as the parent of three nested states, each having the same outbound transition.

Transitions that are outbound from a group of states should be interpreted as connected to each of the nested states (known as generalized transitions). Conversely, inbound transitions are only redirected to specific states.

By grouping states together with the same outgoing transitions, it's possible to cut down on the number of transitions. This is the initial interpretation of a hierarchy, on the state level. Nested states will accept only a subset of the input/output alphabet.

In practice, the benefits of such nested states are not restricted to strict hierarchies; the states at the top of the hierarchy are not necessarily mutually exclusive. Instead, superstates are defined to englobe standard states. These are known as AND states, because the outbound transitions apply to all the nested states. It's possible to define superstates around arbitrary areas of the finite-state machines to reduce the number of transitions.

Hierarchy of State Machines

Instead of just simplifying the representation with superstates, the hierarchy can be considered as a functional decomposition. Specifically, each nested state is a component providing exclusive functionality. The outer finite-state machine can assemble these components in the most suitable fashion to provide functionality.

Abstraction

A hierarchy provides different levels of detail for each of the finite-state machines. By not displaying the lower levels of the tree, it's possible to mask out the details of the underlying implementation. Essentially, this abstracts out the complexity of the implementation. This operation is known as zooming out (see Figure 41.3).

Figure 41.3. Zooming in and out. A nested finite-state machine is abstracted by hiding the lower levels of the hierarchy, which are then reinserted when required.

In many cases, it is beneficial to consider a state as a black box, disregarding the layout of the nested finite-state machine. During the design phase, this can increase productivity. When a higher-level finite-state machine is created, certain functionality is assumed from a state and it is used transparently. In a similar fashion to programming, this requires a clear definition of the state's behavior and the facilities it provides.

Refinement

After the higher-level finite-state machines have been created, it's necessary to zoom in to each of the states. The underlying implementation is thereby revealed, as the state itself is refined into a nested finite-state machine.

When the requirements of any state are too large to handle with simple procedures, refinement provides the methodology to expand the state transparently. A set of nested states can be created trivially, while still maintaining the same output behavior.

Modularity

Given the two previous properties of HSMs, it's trivial to extend the definition to deal with modular finite-state machines. Reminiscent of object-oriented programming, each finite-state machine can be treated as a modular component (see Figure 41.4). This implies it can be reused in any place and any in level of the hierarchy.

Figure 41.4. Two states reuse the same modular finite-state machine as a nested component.

During the design phase, modularity allows working finite-state machines to be stored in a common library, and imported into models when necessary. It's also convenient to spread the workload among multiple AI designers.

Heterogeneous Computational Models

Flexibility is one of the major advantages of these hierarchical models. Thanks to the high levels of abstraction and modularity, it's possible to use various different models of computation within each state. This is a tremendous advantage because finite-state machines are ill suited to certain tasks (for instance, counting).

Some models of computation related to finite-state machines have been integrated within finite-state machines (including synchronous data flow, discrete events, and reactive systems) [Girault99]. In games, however, other AI techniques such as rule-based systems or scripts are usually used within states to provide specific behaviors.