Open Review
HCSM_Teaser.medium_01

HCSM: A Framework for Behavior and Scenario Control in Virtual Environments

Luke Dicken on December 7, 2009

Finite-state machines have been getting a lot of bad press over the past couple years, and justifiably so! When applied to AI for building purposeful goal-directed behaviors, traditional FSMs just don't scale very well. This is the main reason developers in the games industry have been primarily moving towards systems like behavior trees instead...

However, hierarchical concurrent state machines (aka. HCSM) were bumped up to the top of our list of topics since the bots in Left 4 Dead are apparently based on HCSM. Indeed, as Mike Booth (Project Lead at Valve on the game) confirmed for this article, the implementation of the bots is based on ideas in the paper discussed here. Read on to find out more!

The rest of this white paper review is written by Luke Dicken, researcher at the University of Strathclyde and our resident academic here at AiGameDev.com. He's also known as @LukeD on Twitter.

Airliner crashing at the start of the Dead Air campaign.

Screenshot 1: The bots in Left 4 Dead 1 are controlled using HCSM.

Motivation

Designing and organizing sophisticated AI systems is very hard, particularly when building them as one large monolithic control system. Working out the processes by which you can make a system do what you want it to in a complex and changing environment can be a lengthy process, and invariably some set of circumstances that the system needs to cope with end up being overlooked.

In this article, you'll learn about the Hierarchical Concurrent State Machine (HCSM) which gives a framework in which AI systems can be described in a modular manner, whilst still capturing the interactions between aspects of the world and the system, or between different components of the system itself.

Contribution

HCSMs were introduced in 1995 in a paper entitled HCSM: A Framework for Behavior and Scenario Control in Virtual Environments, written by Cremer, Kearney and Papelis. The concept of the HCSM has been influenced heavily by the Statechart extension to State Automata. Designed primarily for embedded and real-time systems, statecharts allow for a group of states to be gathered into a single superstate. Superstates can then be linked with transitions and treated more or less as states themselves. (This is a very very brief synopsis of statecharts, see the paper linked from this page for details).

HCSM takes this notion a stage further, by abolishing the concept of state altogether; the basic building block in an HCSM is an HCSM. However, unlike in statecharts, HCSMs are not made transparent to their parent HCSM. Another difference is that each HCSM has an "activity function" associated with it which is used to generate an output based on, but independent of, the active state within the HCSM. The HCSM specification defines input wires used to supply a continuous stream of data to the machine, as well as controls and dials which are used to set parameters within the machine. It is important to note that time within the machine is discretely modeled, and although changes to the input are visible immediately inside the machine, changes made to the controls are not reflected until the next tick.

An HCSM is "Sequential" if the HCSMs it contains are linked by transitions, and "Concurrent" if the HCSMs are not linked by transitions. In sequential HCSMs, a single HCSM child can be active at a given tick, whilst concurrent HCSMs allow for all the children to be active at each tick.

Diagram from the paper showing the structure of an HCSM.


Figure 2: Diagram from the paper showing the structure of an HCSM. (Click to enlarge.)

HCSMs provide a very robust modular formalism in which you can define the behaviors of an AI system, and easily capture intricate interactions between these behavior. This avoids a lot of the confusion that designing these complex systems might otherwise lead to, and makes for a much more understandable representation of what you are trying to achieve.

Abstract & Download

Here's the official abstract of the white paper, published in 1995:

“This paper presents a framework for behavior modeling and scenario control based on hierarchical, concurrent state machines (HCSM). We present the structure and informal operational semantics of hierarchical, concurrent state machines. We describe the use of HCSM for scenario control in the Iowa Driving Simulator (IDS), a virtual environment for real-time driving simulation. The paper concludes with an outline of a forthcoming HCSM-based scenario authoring system that will permit non-specialists to graphically program behaviors and design experiments for IDS.”

Here's the reference for the paper and the link for downloading the PDF:

HCSM: A Framework for Behavior and Scenario Control in Virtual Environments
J. Cremer, J. Kearney & Y. Papelis
Download PDF

Discussion

It isn't a massive leap to see how this approach can be used to design control systems for agents, for example the bots in Left 4 Dead. After all, at their core they are still State Automata. HCSMs can be arranged such that behaviors that need to execute simultaneously are contained within a concurrent HCSM, while more traditional mode-switching can be captured using a sequential HCSM, and these can be nested within each other, and feed into each other in order to generate a complex system using a set of very basic building blocks.

However, one of the main proposed uses for the HCSM technique is not for agent control, but for scenario control. HCSMs being used in this manner are termed "Directors" and can be used to orchestrate specific conditions within a noisy environment. In the paper introducing the technique, the authors talk specifically about creating specific circumstances within the "Iowa Driving Simulator" (a precursor to the more modern "National Advanced Driving Simulator"), a virtual environment with a physical simulator component based around an actual vehicle shell, making for a very advanced simulation experience — comparable for example to airline training simulators.

The problem with this simulated environment at the time was that there was not a good technique to allow situations to be created that a user of the simulator would need to react to. For example, consider another driver in traffic who cuts the user off. It is difficult to orchestrate this as a general case whilst making the simulation seem fluid, since it depends to a large extent on the behavior of the user — not just from a timing point of view but also from an aggression point of view. A naive technique might have the other vehicle execute its maneuver when the user's vehicle hits a specific trigger point in the road, but in a fully dynamic world, a vehicle sat waiting to be triggered would be very noticeable and jar the user out of the suspension of disbelief that the simulation encourages.

Fire in the warehouse of Death Toll.

Screenshot 3: Bots moving through a warehouse in Left 4 Dead 1.

An initial solution used a complex one-layer state machine to model speed matching and slowing behavior to put the "enemy" vehicle in the right position at the right time to perform the required action that the user would need to react to, but as you can imagine, a typical state diagram that could capture this level of complexity was of unmanageable complexity, leading to significant issues in terms of code reuse and debugging.

HCSMs model these interactions in a much more elegant way, making the whole process easier by virtue of their modular hierarchical nature — the states for speed control to make sure an incident occurs at the correct location relevant to the user's vehicle for example are much more portable under this architecture and can be lifted with much less trauma and put into another structure to replicate the functionality in a different scenario, essentially providing a behavior-centric view of a state machine.

Implementation

Conceptually this seems a robust approach, but how does this work in practice? After all, what really matters is how you can implement this in our own applications. The original paper on HCSM kindly provides some pseudo-code algorithms that define exactly how an HCSM is put together. The original pseudo-code is as follows:

ExecuteHCSM(hcsm)
{
  ExecutePreActivity(hcsm.pre_activity_function);
  transition_to_fire := SelectTransitionToFire(hcsm);
  if (transition_to_fire) then
    hcsm.active := transition_to_fire.to_state;
    ActivateState(hcsm.active);

  for each active child m of hcsm do
    ExecuteHCSM(m);

  return(ExecuteActivity(hcsm.activity_function));
}

So you can see from this that each HCSM is made up of essentially four functions — at the top level you see the overall ExecuteHCSM function. There is a pre-activity function which allows controlling the flow of information into the child HCSMs to be executed this iteration. You then select which transition to fire using the SelectTransitionToFire function, and then activate the relevant state for that transition within the HCSM. Remember that transitions are only relevant for sequential HCSMs, concurrent ones will have all the children active at all times. Then, you iterate across the list of active child HCSMs and execute each one. Note importantly that this is a recursive process, and the algorithm descends the hierarchy of the HCSM structure executing the pre-activity functions of each one in a descending manner, but the activity functions themselves are activated as you bubble back up the execution stack. This is a very important aspect of the temporal order of each iteration as it allows the children of an HCSM to directly affect the activity function of their parent HCSM.

A hierarchical graph-like structure representing a HCSM.


Figure 4: A hierarchical graph-like structure representing a HCSM. (Click to enlarge.)

Evaluation

Applicability to Games: 9/10
Not all games are going to benefit from this technology, but any developer that wants to retain a degree of directorial control over the play whilst at the same not constricting the choices offered to the players will find it beneficial.
Usefulness for Character AI: 6/10
HCSMs don't really bring much new to the table in terms of controlling NPCs. They would be appropriate for use, but they aren't necessarily the best approach.
Simplicity to Implement: 6/10
HCSMs are more of a paradigm than something precisely implementable. As such they can be as simple or complicated as you need them to be. At their most basic, an HCSM object is 4 functions, making implementation relatively straightforward, but this overlooks the interplay of multiple HCSMs and parents with children.

HCSMs provide a useful way for reworking traditional state automata into an architecture better suited to the kind of work AI developers do. Their power lies in the simplistic way they represent complex interactions, with an almost emergent component in the way that they can be put together to create interesting behaviors. Their use as a stage manager is particularly significant for game developers since it provides a lightweight reusable technique to create game worlds that are both interesting and believable, and support altering the world and NPCs within it so that things you want to happen in the world happen in a way that is appropriate given the player's activity. This brief introduction to HCSMs has been based off the original paper by Cremer, Kearney and Papelis, and for a much more detailed overview of the technique I recommend reading this.

Discussion 1 Comments

alexjc on December 7th, 2009

Luke, thanks for your analysis. Great article! I'd personally rate the paper an 8, 8, 8. For applicability to games, I think it assumes a certain complexity of the behavior, which narrows down its use for simple games. For character AI, I think this is the main selling point; displaying concurrent behaviors is something increasingly important, and HCSM are very well placed to handle this. In terms of implementation, I'd also say this was quite high, maybe even 9/10. Frankly, it's a simple algorithm compared to other navigation or animation systems; the challenge is building good behaviors! Of course, it makes me think about how behavior trees would handle this, in particular: [LIST] [*][B]Parameters[/B]: The HCSM model has an interesting approach for wiring up inputs and outputs that behavior trees sidestep. I'm wondering to what extent you could combine the two. [*][B]Concurrency[/B]: I like to implement Behavior Trees with support for parallel branches in the tree, which basically emulates HCSM. The question of synchronization and coordination though, seems to be the biggest open question. [*][B]Events[/B]: HCSM don't seem too well suited by default for dealing with events, so most behavior tree implementations have a head start here. [/LIST] Anyway, lots to think about. I hope we can dig in to the Left 4 Dead bot implementation in a future review also. Alex

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!