Utility Based AI

Utility Based AI is a method of assigning scores to Behaviors (or any other object for that matter, but we will focus on Behaviors) based on some heuristic, usually involving Curves. Then algorithm analyzes those scores and chooses the most suitable Behavior.

Basic concepts of Utility

Evaluators

Evaluators are responsible for calculating score of assigned Behaviors.

Consideration

Consideration is a number representing a subset of gamestate which, from the perspective of the algorithm, is worth being considered during score calculation.

Considerations you may come up with given the necessity of evaluating AttackOpponent behavior

  • agent’s health

  • opponent’s health

  • distance between agents

  • agent’s weapon damage

  • etc.

Curve

Curve is a function which converts one value into another. It usually takes form of an analytical curve.

Aggregator

Aggregators are responsible for merging multiple scores into one.

Selector

Selectors are responsible for selecting most suitable behavior based on scores received from evaluators.

Flow of Utility

  1. Evaluators assigned to behaviors recursively gather scores of connected Evaluators.

  2. Results of the whole Evaluator tree evaluation are passed to the Selector along with Behavior instances which are described by those scores.

  3. Selector chooses most suitable behavior

Example

Let’s say that our example situation involves two archers shooting at each other and trying to defeat his opponent.

Agent can execute one of the following behaviors

  • Attack

  • Flee

Available considerations

  • agent’s health

  • opponent’s health

  • distance between agents

All considerations' values will be in range [0, 100]. Additionally we’ll assume simple structure of Evaluators - one Aggregator to which we connect few Curves with one Consideration connected to each of them.

Let’s assume that Attack behavior will look into health considerations while Flee behavior should consider agent’s health and distance.

We want to implement berserk-like behavior, so our character should prefer attacking when he is at full health or at very low health. Additionally the less health his opponent has, the more likely agent is to attack.

Flee should be executed whenever opponent comes too close to us. Also it should be more likely with each health loss.

Curves corresponding to available behaviors may look like this:

Attack Utility
Figure 1. Attack utility curves
Flee Utility
Figure 2. Flee utility curves.

After curves are prepared we decide that attack evaluations should be aggregated by multiplication, so we connect them to Product Aggregator. On the other hand flee should make use of Min Aggregator.

We decide that selector should choose behavior with highest score.

Let’s check how it will behave in some test scenarios.

Scenario 1

  • agent’s health = 100

  • opponent’s health = 100

  • distance = 100

Attack evaluation = ah(100) * oh(100) = 1 * 0.5 = 0.5
Flee evaluation = min(ah(100), d(100)) = min(0, 0) = 0

Chosen behavior - Attack

Scenario 2

  • agent’s health = 12.5

  • opponen’s health = 100

  • distance = 100

Attack evaluation = ah(12.5) * oh(100) = 0.5 * 0.5 = 0.25
Flee evaluation = min(ah(12.5), d(100)) = min(0.625, 0) = 0

Chosen behavior - Attack

Scenario 3

  • agent’s health = 12.5

  • opponent’s health = 100

  • distance = 30

Attack evaluation = ah(12.5) * oh(100) = 0.5 * 0.5 = 0.25
Flee evaluation = min(ah(12.5), d(30)) = min(0.625, 1) = 0.625

Chosen behavior - Flee

Scenario 4

  • agent’s health = 6.25

  • opponent’s health = 10

  • distance = 30

Attack evaluation = ah(6.25) * oh(10) = 0.75 * 0.95 = 0.7125
Flee evaluation = min(ah(6.25), d(30)) = min(0.6875, 1) = 0.6875

Chosen behavior - Attack