Utility system
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.