help me understand utility AI

priyesh · 2017-03-17T19:52:41

I've been designing a survival game while taking inspiration from the NPCs of RimWorld and Prison Architect. (And to some extent more AAA examples like The Sims, as well as rougher examples like Dwarf Fortress). It seems like a utility or needs based AI might be a good way to help the AI manage a variety of goals, and lead to some dynamic behaviors. Pardon my meanderings, but I'm trying to understand how this works, and if utility AI is even the right approach FOOD Let’s just say I have a “hunger” function that helps AIs manage their food supply. On a basic level, hunger gets low enough (high enough?) then the character should eat from their food supply. But what if they have no food? Obviously they should look for some. But you’d be pretty dumb if you waited until you had absolutely no food before you started looking. The answer is that the AI should look for food BEFORE they’re out of food. So now my utility function isn’t hunger. My character is going to eat regularly and this can be an automated (unintelligent) behavior. My utility function should be supply. My utility function for supply: as my food supply goes down, the utility of food goes up. At a certain threshold, it pushes a character to look for food. But is that dumb as well? The real key is if I have enough food to make a safe journey. So I design the supply function as: only look for food if I don’t have enough to make the journey. But this sounds a lot more like a very static behavior tree than a utility function. The agent isn’t really figuring anything out so much as I’m figuring it out for him, and hard coding it. What am I missing? RETREAT Another example I’m having trouble with… I create a utility function for retreating from battle. On a basic level, it compares the defending NPC’s hitpoints to the attacking NPC’s damage per second. If the threat of death is high enough, then flee. But an NPC shouldn’t flee if it can kill the enemy before the enemy kills them. So I factor that into the function. Compare the NPC’s “time to die” against another NPC’s “time to die”. Maybe scale the function so the difference matters more when my time to die is small, but allows more uncertainty and risk taking when my time to die is big. But then I need to factor in the other idiots on the battlefield. Being surrounded by a friendly militia is no reason to flee, whereas I’d feel differently if I saw an enemy army coming over a hill. What happens if alliances and relationships can change? I suppose an NPC could walk into a trap, thinking they are safe around their friends, when actually it’s a mutiny waiting to happen. But some smarter NPCs should be able to estimate the threat by looking at the souring mood of their estranged allies and say “I’m going to get out of here before it gets really ugly”. Does this make my utility function for retreat so convoluted that it no longer represents anything? I’m not sure I understand the best way to do this.

Artificial Intelligence Programming

Started by priyesh February 28, 2017 06:25 AM

34 comments, last by Alturis 7 years, 1 month ago

ApochPiQ

23,138

March 06, 2017 07:33 PM

I guess this is the thing. We're not just talking about utility in a finite combat situation, but in a grand simulation sense. (Yeah, I know this is pretty ambitious -- Dwarf Fortress, The Sims, CK2, Prison Architect, and RimWorld as references.)
If I effectively multiply the number of actions by the number of characters, that's a LOT of actions.
I guess the best way to cull some of the actions is to only consider killing a finite list of "enemies". Or only consider killing the top 5 people I dislike. Similarly, with food I might consider only sources within range, plus whatever I have at home.

Not every action is valid in every game state. Sort your calculations so that the most likely to fail are checked first. This gives you an early-out property that is extremely valuable. For example, I may have a high utility for killing an enemy, but if that enemy is 5km away, the utility is zero. So check his distance first, and bail out of the calculation as soon as you notice that the utility of attacking is very low/zero.

The Building a Better Centaur talk has more details on similar tricks you can do.

Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

IADaveMark

3,839

March 06, 2017 08:00 PM

If you DO want to have a high-level "goal" of sorts, you can determine that at a slower interval and set a flag. Then lower-level behaviors can be switched on or off (or prioritized with a utility function) based on the state of that flag. I'm just confused by what your idea of "satisfying needs" is here. That's not a high-level goal... that's a pretty immediate one in many cases.

In the example of "satisfying hunger", you don't have to make that a separate decision (e.g. "I am now going to satisfy hunger.") Instead, you just add your hunger value as a consideration to anything that would involve moving to or eating food. Therefore, as hunger increases (or food state decreases), those behaviors will gradually rise in score until such point as they become urgent. There is no separate state... just behaviors that respond directly to those changing input values.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

priyesh

125

Author

March 07, 2017 01:55 AM

I ... I think I get it. I think I understand!

You're right, I was overthinking it.

It sounded daunting to program that many "solutions" for each agent to consider for their actions. But even if my initial design doc might try to organize those into groups of actions, that's just because it's easier to plan the game that way. In the code, it's still just a long list of actions.

Culling the agent's mental model seemed so necessary before. But you're right that 100 characters each considering 100 actions is still only 10000 calculations. And even so, there's some obvious culling to do in terms of "too far away, don't bother", or "don't check this every damn second".

Thanks so much everyone. Really appreciate all of this.

wodinoneeye

1,691

March 17, 2017 07:09 PM

A mechanism to adjust priorities of different actions is an escalation graph (can also be modal if-then logic) where the priority increases as the needed resource inventory decrease. Then the available tasks get sorted under one metric - can be a metric for this type of task (vs priorities for Immediate threats - which generally trump 'maintenance' by a magnitude.)

Calculating the priority may have additional factors (like very close proximity making an opportunistic grab viable)

Ive found that trying to develop a general metric to make these decisions is the hardest part of doing this programming (so you will need to be able to make adjustments while tuning the game, and a modal graph is fairly easy to adjust (versus an equation)

--------------------------------------------[size="1"]Ratings are Opinion, not Fact

wodinoneeye

1,691

March 17, 2017 07:16 PM

Most games have fewer than 20 types of action so this is not hard to do.

Caveman has an unusually large number of possible situations it responds to - that's why i use a hierarchical approach to decision making - divide and conquer. Although in the end, they all result in some combo of turning, moving, and attacking.

you can also use a 'less frequent check' type of optimization where the lower priorities usually culled out still get run once in a while (particularly if the opportunity search uses ALOT of processing resources)

One of the problems with AI is that even though you want to follow up on one (the last) decided task, that it is good to process the Current situation fairly frequently to have the behavior reactive to a suddenly changing environment (meaning lots of constant re-detecting/re-classifying/re-evaluating even when it results in no change). And as the game situation gets more complex that processing increases geometrically.

--------------------------------------------[size="1"]Ratings are Opinion, not Fact

Alturis

106

March 17, 2017 07:52 PM

"How do you handle "two birds, one stone" types of problem solving using utility AI?"

One approach would be to use a scoring function for each of the various desire rating types. Then a high level scoring solution (or data set) that is a set of those scoring functions. You pass all the choices to consider through the scoring solution where each functions result is summed to produce a final score per choice. You pick the highest score and can maybe add some randomness to sometimes pick lower scores just to change things up.

Its important that each scoring function always adds positive values rather than ever subtracting. In this way you can mix and match a bunch of desires and the outcomes that are highest will always be the "best" with some tuning.

help me understand utility AI

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

help me understand utility AI

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines