Utility system

In video game AI, a utility system, or utility AI, is a simple but effective way to model behaviors for non-player characters. Using numbers, formulas, and scores to rate the relative benefit of possible actions, one can assign utilities to each action. A behavior can then be selected based on which one scores the highest "utility" or by using those scores to seed the probability distribution for a weighted random selection. The result is that the character is selecting the "best" behavior for the given situation at the moment based on how those behaviors are defined mathematically.

Key concepts

The concept of utility has been around for centuries – primarily in mathematically dependent areas such as economics. However, it has also been used in psychology, sociology, and even biology. Because of this background and the inherent nature of needing to convert things to math for computer programming, it was something that came naturally as a way of designing and expressing behaviors for game characters.

Naturally, different AI architectures have their various pros and cons. One of the benefits of utility AI is that it is less "hand-authored" than many other types of game AI architectures. While behaviors in a utility system are often created individually (and by hand), the interactions and priorities between them are not inherently specified. For example, behavior trees (BTs) require the designer to specify priorities in sequence to check if something should be done. Only if that behavior (or tree branch) is NOT executed will the behavior tree system fall through to check the next one.

By comparison, behaviors in many utility systems sort themselves out by priority based on the scores generated by any mathematical modeling that defines every given behavior. Because of this, the developer isn't required to determine exactly where the new behavior "fits" in the overall scheme of what could be thousands of behavior "nodes" in a BT. Instead, the focus is on simply defining the specific reasons why the single behavior in question would be beneficial (i.e. its "utility"). The decision system then scores each behavior according to what is happening in the world at that moment and selects the best one. While some care must be taken to ensure that standards are being followed so that all behavior scoring is using the same or similar premises, the "heavy lifting" of determining how to process tens – or even hundreds – of different behaviors is offloaded from the designer and put into the execution of the system itself.

Background

Early use

Numbers and formulas and scores have been used for decades in games to define behavior. Even something as simple as a defining a set percentage chance for something to happen (e.g. 12% chance to perform Action X) was an early step into utility AI. Only in the early 21st century, however, has that method started to take on more of a formalized approach now referred to commonly as "utility AI".

Mathematical modeling of behavior

In The Sims (2000) an NPCs current "need" for something (e.g. rest, food, social activity) was combined with a score from an object or activity that could satisfy that same need. The combinations of these values gave a score to the action that told the Sim what it should do. This was one of the first visible uses of utility AI in a game. While the player didn't see the calculations themselves, they were made aware of the relative needs of the Sim and the varying degrees of satisfaction that objects in the game would provide. It was, in fact, the core gameplay mechanism.

In The Sims 3 (2009), Richard Evans used a modified version of the Boltzmann distribution to choose an action for a Sim, using a temperature that is low when the Sim is happy, and high when the Sim is doing badly to make it more likely that an action with a low utility is chosen. He also incorporated "personalities" into the Sims. This created a sort of 3-axis model — extending the numeric "needs" and "satisfaction values" to include preferences so that different NPCs might react differently from others in the same circumstances based on their internal wants and drives.

In his book, Behavioral Mathematics for Game AI, Dave Mark detailed how to mentally think of behavior in terms of math including such things as response curves (converting changing input variables to output variables). He and Kevin Dill went on to give many of the early lectures on utility theory at the AI Summit of the annual Game Developers Conference (GDC) in San Francisco including "Improving AI Decision Modeling Through Utility Theory" in 2010. and "Embracing the Dark Art of Mathematical Modeling in AI" in 2012. These lectures served to inject utility AI as a commonly-referred-to architecture alongside finite state machines (FSMs), behavior trees, and planners.

A "Utility System"

While the work of Richard Evans, and subsequent AI programmers on the Sims franchise such as David "Rez" Graham were heavily based on utility AI, Dave Mark and his co-worker from ArenaNet, Mike Lewis, went on to lecture at the AI Summit during the 2015 GDC about a full stand-alone architecture he had developed, the Infinite Axis Utility System (IAUS). The IAUS was designed to be a data-driven, self-contained architecture that, once hooked up to the inputs and outputs of the game system, did not require much programming support. In a way, this made it similar to behavior trees and planners where the reasoner (what makes the decisions) was fully established and it was left to the development team to add behaviors into the mix as they saw fit.

Utility with other architectures

Additionally, rather than a stand-alone architecture, other people have discussed and presented methods of incorporating utility calculations into existing architectures. Bill Merrill wrote a segment in the book, Game AI Pro, entitled "Building Utility Decisions into Your Existing Behavior Tree" with examples of how to re-purpose selectors in BTs to use utility-based math. This made for a powerful hybrid that kept much of the popular formal structure of behavior trees but allowed for some of the non-brittle advantages that utility offered.

Utility decision-making is relatively fast, in terms of real-time performance, compared to more computationally expensive planning approaches such as Monte Carlo tree search. This mainly stems from the fact that Utility System is reactive, i.e., chooses decision based on the present state. The planning approaches involve some kind of search that enables to consider various future scenarios at the expense of heavy computations. However, both architectures can be combined. In a conference paper about AI in Tactical Troops: Anthracite Shift game, Utility System is responsible for high-level strategical decision making, whereas Monte Carlo Tree Search is responsible for deep tactical situations which require more exact planning.

See also

• Behavior Trees
• Video game AI