Utility system

Last updated

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.

Contents

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. [1] 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. [2] 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, [3] 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. [4] and "Embracing the Dark Art of Mathematical Modeling in AI" in 2012. [5] 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 [6] 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). [7] 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, [8] entitled "Building Utility Decisions into Your Existing Behavior Tree" [9] 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.

See also

Related Research Articles

Artificial intelligence (AI), in its broadest sense, is intelligence exhibited by machines, particularly computer systems. It is a field of research in computer science that develops and studies methods and software that enable machines to perceive their environment and use learning and intelligence to take actions that maximize their chances of achieving defined goals. Such machines may be called AIs.

<span class="mw-page-title-main">Game theory</span> Mathematical models of strategic interactions

Game theory is the study of mathematical models of strategic interactions. It has applications in many fields of social science, and is used extensively in economics, logic, systems science and computer science. Initially, game theory addressed two-person zero-sum games, in which a participant's gains or losses are exactly balanced by the losses and gains of the other participant. In the 1950s, it was extended to the study of non zero-sum games, and was eventually applied to a wide range of behavioral relations. It is now an umbrella term for the science of rational decision making in humans, animals, and computers.

<span class="mw-page-title-main">Herbert A. Simon</span> American political scientist (1916–2001)

Herbert Alexander Simon was an American scholar whose work influenced the fields of computer science, economics, and cognitive psychology. His primary research interest was decision-making within organizations and he is best known for the theories of "bounded rationality" and "satisficing". He received the Turing Award in 1975 and the Nobel Memorial Prize in Economic Sciences in 1978. His research was noted for its interdisciplinary nature, spanning the fields of cognitive science, computer science, public administration, management, and political science. He was at Carnegie Mellon University for most of his career, from 1949 to 2001, where he helped found the Carnegie Mellon School of Computer Science, one of the first such departments in the world.

<span class="mw-page-title-main">Microeconomics</span> Behavior of individuals and firms

Microeconomics is a branch of economics that studies the behavior of individuals and firms in making decisions regarding the allocation of scarce resources and the interactions among these individuals and firms. Microeconomics focuses on the study of individual markets, sectors, or industries as opposed to the economy as a whole, which is studied in macroeconomics.

Bounded rationality is the idea that rationality is limited when individuals make decisions, and under these limitations, rational individuals will select a decision that is satisfactory rather than optimal.

Satisficing is a decision-making strategy or cognitive heuristic that entails searching through the available alternatives until an acceptability threshold is met, without necessarily maximizing any specific objective. The term satisficing, a portmanteau of satisfy and suffice, was introduced by Herbert A. Simon in 1956, although the concept was first posited in his 1947 book Administrative Behavior. Simon used satisficing to explain the behavior of decision makers under circumstances in which an optimal solution cannot be determined. He maintained that many natural problems are characterized by computational intractability or a lack of information, both of which preclude the use of mathematical optimization procedures. He observed in his Nobel Prize in Economics speech that "decision makers can satisfice either by finding optimum solutions for a simplified world, or by finding satisfactory solutions for a more realistic world. Neither approach, in general, dominates the other, and both have continued to co-exist in the world of management science".

<span class="mw-page-title-main">Behavioral economics</span> Academic discipline

Behavioral economics is the study of the psychological factors involved in the decisions of individuals or institutions, and how these decisions deviate from those implied by traditional economic theory.

<span class="mw-page-title-main">Decision theory</span> Branch of applied probability theory

Decision theory or the theory of rational choice is a branch of probability, economics, and analytic philosophy that uses the tools of expected utility and probability to model how individuals would behave rationally under uncertainty. It differs from the cognitive and behavioral sciences in that it is mainly prescriptive and concerned with identifying optimal decisions for a rational agent, rather than describing how people actually make decisions. Despite this, the field is important to the study of real human behavior by social scientists, as it lays the foundations to mathematically model and analyze individuals in fields such as sociology, economics, criminology, cognitive science, moral philosophy and political science.

Interactive storytelling is a form of digital entertainment in which the storyline is not predetermined. The author creates the setting, characters, and situation which the narrative must address, but the user experiences a unique story based on their interactions with the story world. The architecture of an interactive storytelling program includes a drama manager, user model, and agent model to control, respectively, aspects of narrative production, player uniqueness, and character knowledge and behavior. Together, these systems generate characters that act "human," alter the world in real-time reactions to the player, and ensure that new narrative events unfold comprehensibly.

<span class="mw-page-title-main">State space (computer science)</span> Set of all possible values of a system

In computer science, a state space is a discrete space representing the set of all possible configurations of a "system". It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory.

The expected utility hypothesis is a foundational assumption in mathematical economics concerning decision making under uncertainty. It postulates that rational agents maximize utility, meaning the subjective desirability of their actions. Rational choice theory, a cornerstone of microeconomics, builds this postulate to model aggregate social behaviour.

In video games, artificial intelligence (AI) is used to generate responsive, adaptive or intelligent behaviors primarily in non-playable characters (NPCs) similar to human-like intelligence. Artificial intelligence has been an integral part of video games since their inception in 1948, first seen in the game Nim. AI in video games is a distinct subfield and differs from academic AI. It serves to improve the game-player experience rather than machine learning or decision making. During the golden age of arcade video games the idea of AI opponents was largely popularized in the form of graduated difficulty levels, distinct movement patterns, and in-game events dependent on the player's input. Modern games often implement existing techniques such as pathfinding and decision trees to guide the actions of NPCs. AI is often used in mechanisms which are not immediately visible to the user, such as data mining and procedural-content generation. One of the most infamous examples of this NPC technology and gradual difficulty levels can be found in the game Mike Tyson's Punch-Out!! (1987).

<span class="mw-page-title-main">Intelligent agent</span> Software agent which acts autonomously

In intelligence and artificial intelligence, an intelligent agent (IA) is an agent that perceives its environment, takes actions autonomously in order to achieve goals, and may improve its performance with learning or acquiring knowledge.

Game Description Language (GDL) is a specialized logic programming language designed by Michael Genesereth. The goal of GDL is to allow the development of AI agents capable of general game playing. It is part of the General Game Playing Project at Stanford University.

In artificial intelligence research, the situated approach builds agents that are designed to behave effectively successfully in their environment. This requires designing AI "from the bottom-up" by focussing on the basic perceptual and motor skills required to survive. The situated approach gives a much lower priority to abstract reasoning or problem-solving skills.

In economics, and in other social sciences, preference refers to an order by which an agent, while in search of an "optimal choice", ranks alternatives based on their respective utility. Preferences are evaluations that concern matters of value, in relation to practical reasoning. Individual preferences are determined by taste, need, ..., as opposed to price, availability or personal income. Classical economics assumes that people act in their best (rational) interest. In this context, rationality would dictate that, when given a choice, an individual will select an option that maximizes their self-interest. But preferences are not always transitive, both because real humans are far from always being rational and because in some situations preferences can form cycles, in which case there exists no well-defined optimal choice. An example of this is Efron dice.

<span class="mw-page-title-main">Behavior tree (artificial intelligence, robotics and control)</span> Mathematical model of plan execution

A behavior tree is a mathematical model of plan execution used in computer science, robotics, control systems and video games. They describe switchings between a finite set of tasks in a modular fashion. Their strength comes from their ability to create very complex tasks composed of simple tasks, without worrying how the simple tasks are implemented. Behavior trees present some similarities to hierarchical state machines with the key difference that the main building block of a behavior is a task rather than a state. Its ease of human understanding make behavior trees less error prone and very popular in the game developer community. Behavior trees have been shown to generalize several other control architectures.

In artificial intelligence, a behavior selection algorithm, or action selection algorithm, is an algorithm that selects appropriate behaviors or actions for one or more intelligent agents. In game artificial intelligence, it selects behaviors or actions for one or more non-player characters. Common behavior selection algorithms include:

This glossary of artificial intelligence is a list of definitions of terms and concepts relevant to the study of artificial intelligence (AI), its subdisciplines, and related fields. Related glossaries include Glossary of computer science, Glossary of robotics, and Glossary of machine vision.

The following outline is provided as an overview of, and topical guide to, machine learning:

References

  1. ↑ Mark, Dave (August 2012). "AI Architectures: A Culinary Guide".
  2. ↑ Evans, Richard. "Modeling Individual Personalities in The Sims 3". GDC Vault. pp. 36–38. Retrieved 21 September 2015.
  3. ↑ Mark, Dave (March 2009). Behavioral Mathematics for Game AI. Course Technology Cengage Learning. ISBN   978-1584506843.
  4. ↑ Mark, Dave; Dill, Kevin (2010). "Improving AI Decision Modeling Through Utility Theory". GDC Vault.
  5. ↑ Mark, Dave; Dill, Kevin (2012). "Embracing the Dark Art of Mathematical Modeling in AI". GDC Vault.
  6. ↑ Graham, David "Rez" (September 2013). "An Introduction to Utility Theory" (PDF). GameAIPro.
  7. ↑ Mark, Dave; Lewis, Mike (2015). "Building a Better Centaur: AI at Massive Scale". GDC Vault.
  8. ↑ Rabin, Steve (September 2013). "Game AI Pro". Amazon.
  9. ↑ Merrill, Bill (September 2013). "Building Utility Decisions into Your Existing Behavior Tree" (PDF). GameAIPro.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.