User:Sssky Nan/sandbox/Utility AI

“Utility AI” is an intelligent agent(an entity controlled by an AI program to receive information from it and perform behaviors) equipped with the utility system. This system is a software program designed based on the utility theory(people choose the optimal behavior by comparing their own preferences over all available behaviors) to help intelligent agents make rational decision and perform the optimal behavior. The utility system evaluates the usefulness of each available behavior based on current situations and then assigns one value(can be integers and decimals) to each behavior. These values describe how useful an option is given a specific condition, so they will increase or decrease when corresponding actions become urgent or useless. The names of them are various, such as utility, priority, weight, rank, urgency, importance, etc. Thus, by comparing values among all options, the utility system helps utility AI find out the optimal option and execute it.

The utility AI has several advantages. It can make a rational decision given a specific condition, which makes its agents behave like a real person. In addition, the utility AI program is easily extendable, which gives programmers room to design more independent agents. Therefore, the utility AI has been used in many video games to help their AIs make dynamic decisions(the ability to make rational decisions as the current situation changes), such as the Sim 3(a life simulation game) and the killzone 2(a first-person shooter game).

Utility System

How does it work?

The utility system can help an agent evaluate all the actions and execute the optimal one. This approach has three general steps:

1. Build the option list for an agent. All the options are its available behaviors based on the current condition.
2. Evaluate each option. The agent assigns each option with a value called utility. Utility is used to describe the usefulness of an action given a specific condition.
3. Select the optimal action. By calculating and comparing all the utilities of actions, the agent executes the action with the top utility.

In the second step, the utility system needs to continuously evaluate the condition around the agent, so all the utilities are required to be calculated at a run time. In other words, the utility of an action is not fixed, but is adjusted based on the changes in the current situation. For example, when the agent is hungry, the utility of eating will increase rapidly to make sure it will go to find foods, instead of talking with others. Besides, all the utilities must be consistent across the entire system because they are used to compare with each other. Therefore, all the values used to be utilities must be on the same scale, such as the scale from 0 to 1.0 or from 1.0 to 10.0.

The adjustment in the agent's utilities is related to the changes of the environmental factors in the current situation. Environmental factors can be the distance to enemies(in a first-person shooter game) or the agent's own feeling like hungry and sleepy in the Sim 3. So several functions are designed to describe the relationship between environmental factors and utilities, and they are called utility functions. Utility functions can be linear functions, quadratic functions, exponential functions, etc. For example, the relationship between the utility of firing at enemies and the distance to enemies can be written as a function: f = 100 - d. The variable f is the utility of firing, and d stands for the distance to enemies. As the enemies get closer to the agent, the utility of firing increases.

Calculating and comparing all the utilities in the third step is a significant process in the utility system. The calculation process shows how useful an action is based on the current situation, and the comparing process shows which action is optimal in the option list.

Basic method to select utility

A common and simple technique to select the top utility is to multiply the utility of an action by the possibility of that action. This weighted value is called expected utility. For example, if an agent is attacking a group of enemies, the possibility of hitting the first soldier is 80% (so the possibility of missing is 20%), and the utility of this action is 0.5. So the expected utility is: 0.5*0.8 = 0.4. This can be applied to all possible actions based on the current situation, and the agent then executes the action with the top expected utility. This is called the principle of maximum expected utility.

In most situations, the utility calculation of an action relies on several decision factors. To evaluate this kind of actions, the utility system averages the expected utilities of all the factors related to an action together. Then it gets a new expected utility of the action, which describes how useful this action is based on all related factors. For example, the agent attacking a group of enemies finds that the captain is in the middle of the enemies, which is hard to shoot. The expected utility of hitting the first soldier is 0.4, and the expected utility of hitting the captain is 0.2. However, another factor is that hitting the captain cause disorder to the enemies. The expected utility of this is 0.8. Therefore, the new expected utility of hitting the captain becomes (0.2+0.8)/2 = 0.5, which is higher than that of hitting the first soldier. So in this situation, the AI agent will choose to fire at the captain.

The dual utility

As an agent behaving like a real person, it should not keep doing the action with the top utility in all conditions. Otherwise, it will only perform the same behavior when facing the same condition, which makes it robotic. The dual utility is used to improve this problem. It divides all possible actions into different categories by their own usefulness and then randomly executes one of actions in the best category.

There are two approaches to select utility. The first, absolute utility, is to evaluate every option and take the one with the highest utility. The second, relative utility, is to select an option at random, using the utility of each option to define the probability that it will be selected. The probability (P) for selecting an option (O) is determined by dividing the utility (U) of that option by the total utility of all options:

$P_{0}=U_{0}/(\sum _{k=1}^{N}U_{k})$

The dual utility uses both of two approaches. An agent with dual utility assigns a utility (absolute utility) to each action and figure out a weight (relative utility) for each of them. The weight is used to divide the options into different categories. By controlling the weight interval among all categories, actions with similar weight will get into the same category. The agent only selects actions from the category with the top weight interval. In this category, choosing every action is rational. Then the agent assigns continuous numbers to the remaining actions. So if 3 actions are remained, the agent gives 1,2,3 to each of them. After doing this, it generates a random number from the scale of the assigned numbers and execute the action that this random number corresponds to. For example, there are many kinds of food: hamburgers (the food with the top utility to reduce the hungry feeling), noodles, biscuits, etc. For the agent with the dual utility, it will not keep choosing hamburgers, but choose different food when feeling hungry, which makes it behave like a real person.  

Application

Video games

The utility AI has been already used in the video games. As a video game, one of the ways to make it stand apart from others is making its characters behave realistically as much as possible, which can be realized by using the utility AI.

For example, the Sim 3, a game about real life simulation, used utility system to design all kinds of characters in the game. As utility AI agents, these characters can choose their actions independently and rationally.

Besides, Killzone 2, a first-person shooter video game designed by Guerilla Games, has used a utility system to help their characters make dynamic decisions.

Other areas

The utility AI is versatile. It can be used in all kinds of areas that requires intelligent agents to make decisions independently, such as:

• Complex Behavior
• Prioritizing actions
• Tactical reasoning
• Goal-based behaviors
• Strategic planning
• Group-behavior
• Dynamic, context-sensitive dialogues
• Target prioritization
• Desires
• Emotions
• Simulation of human behavior

Advantages

The utility AI has several advantages:

• Behaving like a real person: The agents of utility AI can constantly evaluate all available options with accurate values and make a rational decision based on the current situation. So when facing an urgent problem, they can find the optimal way to handle it. The abilities of decision making and dealing with emergencies make agents behave like a real person.

• Easily Extendable: Programmers can add additional options into an existing intelligent agent at any time without worrying about breaking the relationship among different options because all the options are independent. By resetting the utilities of both previous and new options, the agent can perform more complex behaviors.

• Reducing programmers' debugging time: The utility system saves the programmers' time on dealing with bugs (errors in the program making it not work). In the utility system, bugs caused by adjusting the utilities will not cause the whole program break down because each option is independent, and no relationship exists between each two decision making steps. So a bug can only cause one decision incorrect, instead of causing all the steps behind this bug wrong. As a result, this bug only requires programmers to re-test part of the program, not spending a large amount of time in debugging the whole program.

Limitations

• Programmers of the utility AI have to express the usefulness of each option with specific values(not just true or false), which is unnatural (especially at first). They also have to tweak the scorers to ensure utility AI agents' correct behaviors. This process requires a large amount of developer-time and game testing.

• The utility AI agents cannot be smarter than their programmers. As an agent, all its behaviors are based on the option list built by programmers. So even though the agent is designed to make rational decision under current conditions, it will still behave unnaturally at several specific situations. Therefore, the programmers' option list is the factor deciding how smart the utility AI agents can behave.