Utilitay - utility based AI

For the past several days I've been working on a fairly flexible utility AI based system quite similar to Dave Mark's IAUS. (technically it's a port of a previous C++ based implementation of IAUS I wrote)

For those needing a refreshing (spoiler used to avoid wall of text):

Spoiler: Utility based AI ranks actions by how useful they are. This is done by scoring each action with a number of considerations/criteria that return an evaluated normalized weight. The weights of all considerations are multiplied together to arrive at a final utility (a modifier is available to prioritize some things over others, such as "I'm hurt, I really don't want to fight, bias against offensive actions"). The action with the greatest utility is chosen. Utility systems have huge advantages in being extremely tunable and very organic due to everything being on curves. Since the selection test is ultimately just about whose best, thoughtful organization of criteria can result in culling Actions or entire sets of Actions once it's been determined that it is no longer possible for the action (or any actions in the set) to win.

For those needing a refreshing, Utility based AI ranks actions by how useful they are. This is done by scoring each action with a number of considerations/criteria that return an evaluated normalized weight. The weights of all considerations are multiplied together to arrive at a final utility (a modifier is available to prioritize some things over others, such as "I'm hurt, I really don't want to fight, bias against offensive actions"). The action with the greatest utility is chosen.

Utility systems have huge advantages in being extremely tunable and very organic due to everything being on curves. Since the selection test is ultimately just about whose best, thoughtful organization of criteria can result in culling Actions or entire sets of Actions once it's been determined that it is no longer possible for the action (or any actions in the set) to win.

Most notable things

• Purely functional curves (the slowest curve, the parabola, is ~260 ns [that's nano] to evaluate)
  • Constant
  • Linear
  • Quadratic
  • Logistic
  • Logit
  • Threshold
  • Sine
  • Parabolic
  • All can be inverted along X or Y axes
• Criteria evaluations can optionally be cached to prevent reevaluating "How's my health in a linear sense?" constantly
• Properly biased to minimize the progressive penalty of many criteria vs just a few
  • the 0.9 * 0.9 * 0.9 decay problem
• Flexible / reusable
  • As few hard dependencies as possible (ie. ResponseCurve can be used for anything)
• Adding a new Action or Criteria type is as simple as implementing an abstract class, everything gets hooked up on its own
  • Fields of bool, int, float, enum, UnityObject subclasses, Vector2, Vector3, Vector4, Quaternion, Color, and a few delegate signatures are properly exposed in the inspector to configure Actions/Criteria
• ActionSets / Packages can come from files (ScriptableObject assets) for sharing the same identical set of actions among entities
• Weight entire sets of Actions with tags to emphasize/de-emphasize certain things
  • Tag weights can also use Criteria to calculate their weights instead of explicit values
• Early opt-out
  • As soon as an action (or entire ActionSet) realizes that it can't possibly be chosen (score too low) it'll just halt further evaluation
• Fail-safe load
  • Everything can be bypassed in an emergency (such as renaming a class resulting in being unable to find it)
• Minimal allocations
  • All throw-aways are pooled
• Understandable
  • Reordering list elements includes non-instrusive animation so it's clear "what moved where"
    • It's a utility system, you'll be doing a lot of sorting
  • Mini-curves and overridable "Quick info" display on collapsed criteria to digest the important bits without scrutinizing everything
  • Hovering the mouse over the curve graph will by default print the X and Y values for that point so you can examine the values
  • Behavior is overridable in Criteria implementations so that it's possible to include additional information
    • For instance, the value that "Hit Points" would have to be to result in that score could be included (ie. "X: 0.440 Y: 0.777 HP: 23" instead of the default of "X: 0.440 Y: 0.777" - line separators there of course)
• Helpers
  • DelegateCriteria
    • Use arbitrary functions in DelegateCriteria, lookup/seek is preloaded
    • Select delegates in the inspector from a list of identified compatible methods
  • ActionAreaHook
    
    • Add temporary zone specific ActionSets (reference counted)
    • Example: Entity walks into a bar, now it gets "Bar Actions"
    • Keeps evaluation options down to what really matters

What's left to do:

• Polish and glamour, lots and lots of inspector polish
• Probably include a light-weight behavior tree library
  • As proof of flexibility for the use of the system in "composites" and leaves
• Wrap up porting my implementation of infinite res. influence maps to include
  • Really handy to have with utility systems
• Copy/Paste and Drag/Drop everything
• Documentation
  • 20% of all file content is comments (mostly because of large function signature docs)
  • Proper guide/tutorial style documentation is missing though
• Prototype Action Library
  • Set of actions suitable for prototypes
• Default Criteria library
  • Covering the major basics of what Criteria make sense for Unity GameObject's in general
• Solid example project demonstrating everything
  • Likely just a port of my original C++ "proof", though my volunteer victim (err... tester) might whip something nicer up
• Profiled action sort
  • Utility systems involve a lot of manual sorting, hopefully reduce much of it down to a button click to automate
  • Running some quick execution tests in the editor to sort Criteria by their performance and evaluation characteristics
    • If it's slow (like a raycast), it goes at the end of the list
    • If it's fast and likely to fail, it goes at the front of the list
• Runtime display / diagnostics
• Sliced evaluation
  • Tracking just how many "decision makers" exist and slicing up who runs on which frame

Example of a custom Criteria:

Spoiler

Code (CSharp):

1.     public class StatCriteria : Criteria
2.     {
3.         public Stats Stat;
4.         public bool BasedOnModifier = false;
5.  
6.         /// <summary>
7.         /// Normalize our value to feed to the curve
8.         /// </summary>
9.         public override float GetNormalizedValue(IDecisionMaker context)
10.         {
11.             if (BasedOnModifier)
12.                 return Criteria.Normalize(((RPGDecisionContext)context).GetStatModifier(Stat), Constants.GetStatModifierMin(Stat), Constants.GetStatModifierMax(Stat));
13.             return Criteria.Normalize(((RPGDecisionContext)context).GetStat(Stat), Constants.GetStatMin(Stat), Constants.GetStatMax(Stat));
14.         }
15.  
16.         /// <summary>
17.         /// Generate text used in the editor for some more meaningful display when collapsed
18.         /// </summary>
19.         public override string GetQuickInfo()
20.         {
21.             return base.GetQuickInfo() + " " + UnityEditor.ObjectNames.NicifyVariableName(Stat.ToString());
22.         }
23.     }

Where most things happen in the inspector (purple indicates that it's a shared action set, thus changes are global, not unique to the GameObject):


Naturally everything looks better dark:


File tree shot for an overview of scale (tiny - sort of small):


------------------------------

Probably a solid 2 weeks of work left, but everything has checked out so far and is fully functional.

Unsure at the present of it's ultimate fate - whether it'll be an asset store submission, a free github dump, etc.

Stuff that'd be great feedback to on:

• Many files vs few big files opinions? (ie. ActionSet databases instead of assets for each shared action set)
• What sort of use cases would you like to see in an example?
• Woes you've encountered with Utility systems you've used in the past (or present)?
  • Especially work-flow related ones (ie. "Putting together the same health check 50 million times")
• When you customize a code asset what do you normally end up attacking?
  • For example, would splitting classes into "partials" and keeping serialization/deserialization isolated be convenient because you're probably going to rip out my serialization for your own - and this will make updating easier on you?
• Integer tag IDs or bit masks to tag things?
• Wizards useful or not? (such as a wizard to whip up basic criteria/action class code quickly)

 

The most recent focus has been data management. Specifically being able to find and view everything relevant to the utility AI system.

Search ActionSet assets, explore what Action/Criteria types exist (and search them of course). They can also be drag-and-dropped onto the inspector to aid creation/editing of ActionSets/Actions. Though the normal process of adding an Action/Criteria presents a list the browser allows searching for field names and such, so if you can't remember that "TargetSizeCriteria" is what you want you can search for the field you remember "VsGiant" to find it and drag it onto the action.

ActionSets can now be migrated into shared assets or cloned into locally unique instances (for customization), they can also be duplicated to serve as bases for new action sets. This should cover profiling and tweaking quite well. The natural assumption is that cloning is mostly for prefab GameObjects, or "uniques."





The "card" style representation most likely needs to go away in favor of a DataTable/DataSheet style view. Because, "WOW! Is that ugly!"

---

Implementation of infinite resolution influence maps is mostly finished, final usage is all that remains. For those that don't quite get the "infinite" part it's a point based approach to influence maps instead of a fixed/raster style grid. Instead of using tons of memory for what is essentially a bitmap you classify points in space and their influence. Influence is effectively a curve function (or rather falloff function). Finding the min/max can be done with just about any function fitting algorithm (gradient descent in this case) - and the point based representation removes the needs of packing data (See Lewis' article in Game AI Pro 2 for nitty gritty).

Which introduces the problem of "views" of the data. They're as much of a problem as they are an advantage. Because the influence is represented as finite points with an influence function, how that data is combined is entirely irrelevant. One "view" may include "allies units - enemy units" while another includes just "ally buildings - enemy buildings" and yet another is "ally buildings + enemy units" (finding if a building in our area of interest is in danger). Each of those "operands" is a different influence map, but the view is the aggregation of them - because the representation of the influence is in a point based form these combinations don't create an explosion in the representation of the influence map - just a couple of kdTrees - all the view does is set up how those maps are queried and their results aggregated.

---

Project is progressing well, some tests to confirm that the overall architecture is flexible enough to integrate with anything (ie. NodeCanvas, PlayMaker, etc) will start soon.

Edit: Automated sorting is almost there, humorously using the ResponseCurves of the system to bias the balance between performance and failure rate.

 

Recent changes are mostly "hidden" in the form of a heavy refactoring triggered by tests of how cleanly everything will integrate with "basically anything."

Placing the utility AI types into third party code was a complete no-brainer but placing other things into it was a different story - for "shake your fist at other programmers" reasons ("MonoBehaviour bleeding" is what I'll call it - the use of MonoBehaviour where it is not necessary or genuinely stupid).

A bit of a fence issue but ultimately I opted to just say to hell with it and do the wrong thing for the sake of making everything a no-brainer to merge with anything else in basically anyway. Some functionality was lost - or reduced to "only practical to do at edit-time" in regards to unique versus shared sets of Actions/Decisions - but that loss should reduce the opportunity to become confused as to what's going on.

There were alternatives, but they weren't particularly great and required more effort than is probably reasonable to expect for someone to hook things together. Now at least it doesn't matter how atrocious that state-machine tool you use really is - just slap it in there.

A property drawer now exists for ResponseCurve so that it can be reused anywhere:


Other minor enhancements are the addition of "Normal distribution" as a curve shape to the ResponseCurve:


Response curves are now faster with the previous slow(ish) Parabolic now down to ~140 ns and normal distribution taking the throne of "slowest" at 172 ns average.

Onward to heavy testing and making everything look snazzy.

 

This looks pretty solid. Still working on it?

 

It'll be open-sourced as soon as I finish documentation (had to bail on Unity for the current project, so it was untouched for a bit) and confirm the state of a few things (on whether to strip them or they're complete enough).

From the last time I mentioned anything about it:

• All "magic values" and tunable constants have been appropriately moved to "Tuning" source files in their respective locations
  • Example 1) Object pool sizes
  • Example 2) Number of gradient descent steps to take
• Editor GUI cleaned up
  • Iconography support in the "database" (reflected collection of available things), helps a ton
• Same iconography used in all of the "picker" windows for selecting Criteria/Actions/Delegates
  
• Influence maps implemented (not directly tied to Utility based AI / LOPA, but still useful)
  • Function based, not raster based
  • Room for expansion
    • Such as a direction and an angle to create cones of influence
    • Primitive obstacles and decomposing/clipping an influence emitter
  • Virtual debug view available by rasterizing the emitters in relation to a camera
  • Comprised of InfluenceMaps and InfluenceMapViews
    • InfluenceMap is equivalent to a "single channel" in graphics terms
    • InfluenceMapView is an arbitrary virtual combination of InfluenceMaps
      • You could have a map view that's just "Ally Buildings" + "Enemy Units" that represents the relative risk to your "buildings"
      • You could have a map view that's "Enemy Turrets" + "Enemy Units", a minima search would yield the safest staging or entry point
      • Or the usual "Allies" + "Enemies" map view that is the front line
      • Subtraction and Multiplication available for InfluenceMap aggregation into the final view
• Reversed decision to go with Monobehaviour/ScriptableObject-centric serialization, scene and object entities you care about should be made accessible to your own specializations of the DecisionContext class (which is given to Actions/Criteria to perform evaluations)

 

This sounds perfect for my project! Is this still going to be open sourced soon?

 

Yeap, it's been checked against 5.4 and I'm pushing it out sometime tomorrow.

I got sidetracked by CryEngine 5's release. The only substantial change is that major (as in the really important bits) serialization has been moved into separate files via partials so that if someone doesn't like how serialization is handled they can easily handle it themselves in very narrow place that will have minimal conflicts with any bug-fixing that occurs in the future. Serialization is a sort of personal bias problem.

In general it should be rather well documented code and the documentation written is more for overview and intent. The most important part of the documentation will probably be the PDF file that demonstrates how changes in X, Y, Slope, Exponent values effects the different curves (but you can just use the float edit field's sliding mode to see for yourself as well).

 

Recently, I have reading a lot about utlity based systems. This is a dumb question but are there any disadvantages compared to behavior trees and fsm's?

 

I also have been recently reading about utility based AI and quite fascinated by how simple the approach is relative to how behavior trees and FSMs are designed and set up.

Regarding disadvantages of utility systems, I came across this 2-year old IGDA webinar about it, of which the presenter mentioned that one key disadvantage is that it is not deterministic compared to behavior trees and FSMs. In other words, if you want something to happen based on exact conditions, you would have to use rule-based systems like behavior trees and FSMs; if you want emergent behavior, use utility based systems. A cool suggestion was to mix both approaches, ie. use behavior trees as the framework and engage utility systems from within certain actions.

 

Abandoned project?

 

You could check out this project of mine (https://github.com/ThelDoctor/CrystalAI), its not production ready yet and is short on documentation (for the moment), but could prove useful.

 

Not so much abandoned as no longer interested in dealing with the release issues involved in supporting an AI related project and no longer using Unity and thus ported to C++ and the C# version has languished extensively.

I will touch up and release when there is an advantageous situation to do so that would benefit other works.

 

Fingers crossed this actually happens. I was pondering writing my own comprehensive data-driven utility AI, almost exactly like you've done here, and I just stumbled across this thread while looking for infinite influence map discussions.

I can't blame you though, I've written a few things that we think have some Asset Store resale potential, but the hassles of support more than offset the utility (ha!) of an occasional sale...

 

Hi, any progress on this? Would you mind putting the source out there (if you were planning to) so we could learn from it? Thanks!

 

Looks really solid, and much like what I implemented on some projects but with more detailed UI. Would love to be able to look at the code to compare.

Just a few language nitpicks :
Criteria is the plural of criterion. Use criterion if you mean to use the singular.
Weight is the noun, the verb is to weigh.

 

It's been about 2 years since the dev said anything. I would venture a guess that there won't be much happening.

 

Anyone know if a version of this tool was ever released?