Jump to content

  • Log In with Google      Sign In   
  • Create Account


Why Behavior Architectures?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
12 replies to this topic

#1 mklingen   Members   -  Reputation: 162

Like
2Likes
Like

Posted 01 September 2013 - 07:55 PM

In AI, it seems very common to want to make some kind of "Behavior Architecture" for ordering and building different ways that agents can interface with the world. I see a lot of state machines, Behavior Trees, HSFMs,  etc. I've implemented these for many different projects (and for my research in robotics as well), but recently I'm starting to doubt their usefulness. 

 

What benefit do I get out of using such an architecture over just coding the entirety of the behavior using modular, native functions and built in control structures (or, if we're concerned about compilation or runtime modification, with simple scripts in a scripting language?) Am I missing something conceptually here?

 

EDIT:

And by the way, what I mean by this is literally interpreting the concept of a behavior architecture as a series of explicit "State" or "Behavior" nodes that interact with each other dynamically as opposed to just straight code calling and evaluating functions in any way the programmer desires. I've been on so, so many projects where development starts with "class Behavior ..." or "class State ..." and then proceeds to link them up in data files dynamically or (much worse) using C macros.


Edited by mklingen, 01 September 2013 - 07:59 PM.


Sponsor:

#2 Norman Barrows   Crossbones+   -  Reputation: 1835

Like
0Likes
Like

Posted 01 September 2013 - 11:16 PM

i've only ever found one type of AI superior to all others.   and its by and large what you describe.    i don't know if it has an official name.    its sort of a combo of decision tree, hierarchical state machines, and expert systems.   well,  sort of...     it layered in a hierarchy, overall its an expert system  - or at least it damn good at what it does, if not expert.  but it does use states, and a a tree type structure as far as the decision process goes.  really, its hierarchy of expert systems.  each one has it own implementation, usually a rule based expert system or state machine / decision tree type stuff.


Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#3 AllEightUp   Moderators   -  Reputation: 4067

Like
2Likes
Like

Posted 01 September 2013 - 11:29 PM

The simple answer is that the "uniform" solutions are more controllable in the overall balancing act required to *complete* a game. AI not only counts for general behavior but also highly influences difficulty levels. I.e. one of your AI objects which is "too smart" because of a really good script can be perfect in a one on one encounter, but that same script used in a group encounter can be too devastating to the player. So, in the group encounter you say, make it more dumb, what does that do to the one on one encounters? Systematically, the balance is wrong and improper if you make an enemy dumber in "one" case than it is in another. Or better stated, I learn how smart some enemy is individually by playing and all of a sudden, mix them with others and it behaves "stupid", it breaks the player knowledge flow.

Overall, the idea is that one solution, the canned "architecture", is more easily balanced in the long run than the other solutions. It's not better by any means, but for larger games it is better in the long run for game balance adjustments.

Many folks may have different opinions on this, I'm just pointing out a specific reason I've found these systems as a good solution in the long run. They don't reduce the problems in the long run but they do localize things such that "x" is now too easy, "y" is too tough and usually you can get away with simple opposition count modifications to maintain a linear'ish difficulty curve. Data driven (scripts count as data for games in many ways), just lets you fiddle a lot faster to get the best balance.

#4 LorenzoGatti   Crossbones+   -  Reputation: 2458

Like
0Likes
Like

Posted 02 September 2013 - 02:15 AM

Contrasting traditional AI architectures with getting things done with "modular, native functions and built in control structures" etc. is illogical, because they represent different levels: well-written code realizes a certain architecture.

Reading between the lines, you are actually comparing AI architectures: the proven and principled ones vs doing things completely ad-hoc. 

AllEightUp gives a good summary of the practical software engineering benefit of contrasting complicated and open-ended modifications by having a regular architecture with a place for everything, and there's also the more formal benefit of being able to reason about one's AI thanks to its systematic organization. For example, the structure of a behaviour tree makes it very easy to prove that some behaviours can never happen together, and will continue to be mutually exclusive as long as they are behind appropriate selection and conditional nodes.  


Produci, consuma, crepa

#5 mklingen   Members   -  Reputation: 162

Like
0Likes
Like

Posted 02 September 2013 - 09:21 AM

 

 

well-written code realizes a certain architecture.

 

True, but it also provides me the flexibility to change things if I desire. It's very frustrating to spend 20 minutes thinking about how I'm supposed to do a simple switch statement or increment a variable in a Behavior Tree when such a thing could be done with one line of code otherwise. It's also extremely frustrating to spend all of my time writing code about checking which state the agent is in, and formally defining state transitions in a state machine.

 

Overall, you guys make good points about things like predictability, balance, and formally verifying systems.

 

I guess what I really want is this:

 

A behavior architecture which doesn't require me to write thousands of lines of bloated window dressing just to get started, which allows me to do if, else, foreach, while, and switch statements, and which allows me to pass data between behaviors in a natural, easy way.

 

My preferred method of programming is something like this:

// Just a complicated function
function Example(arguments)
{

// I want to be able to evaluate arbitrary arguments.
// Also, I should be able to block for as long as I want
// while waiting on a result.
result = DoSomething(arguments);

// I want to be able to do branching
if(MeetsCondition(result))
{
   result2 = DoSomething2(result);
   
   // I want to be able to short circuit and return
   // something if it needs no further processing.
   if(MeetsCondition(result2))
   {
       return result 2;
   }
   // I should be able to simply pass a variable through
   // as many functions as I please and get a processed result out.
   else return DoSomething4(DoSomething3(result2));
}
else if(!MeetsOtherCondition(result))
{
   // I should be able to dynamically generate lists
   // of results and evaluate them.
   list = ComputeList(result);
   
   // I should be able to easily iterate through lists
   // of results.
   foreach(element in list)
   {
      elementResult = DoSomething2(element);
      
      if(MeetsCondition(elementResult))
      {
          return elementResult
      }
   }
   // Here, nothing in the list met some condition.
   return error1; // (or throw an exception)
}
// I should be able to evaluate error conditions
else
{
  return error2; // (or throw an exception)
}

}

I.e., I like to think somewhat functionally, with a very clear flow of data into and out of functions. I like to be able to iterate over the results of functions. I like to be able to return whatever I please from a function. If I wanted to do something like the above in a Behavior Tree, for example, I would need to do one of two things: 1. turn this into a complex leaf behavior and throw away the return value (or write it to some kind of shared state), 2. I could spend hours upon hours trying to refactor it so it works with the three or four operations I have with a behavior tree, and the fact that I simply can't pass the result of one behavior into another one without serious work.



#6 LorenzoGatti   Crossbones+   -  Reputation: 2458

Like
1Likes
Like

Posted 02 September 2013 - 10:30 AM

I don't know what horrible languages and frameworks you have endured, and how much you have suffered, to consider somewhat uncluttered syntax a success rather than a basic expectation and to associate a rigid (but appropriate) architecture with "thousands of lines of bloated window dressing just to get started", but you are mistaken on both counts.

 

Your pseudocode example is only the bare minimum expectation for a decent programming language; learn nice languages like Python or Lisp variants to see how far good language design can help you.

Regarding architecture, you can implement AI techniques in your own style without bloat (it's entirely possible) but also without allowing them to degenerate into unreliable algorithmic anarchy. The design effort will be repaid the first time you don't throw away an entire incomprehensible, inextricable module because you suddenly find yourself unable to make a change or locate a bug.


Produci, consuma, crepa

#7 mklingen   Members   -  Reputation: 162

Like
2Likes
Like

Posted 02 September 2013 - 10:55 AM

I recently went through 3ish years of a large robotics project where the main focus was on doing complex robotic tasks through behavior trees. There were a couple of limitations on the trees:

  • They had to be binary.
  • They had to return either true or false
  • They could not pass information at runtime between each other as arguments.
  • We had the following conditional operators: Sequence (&&), Select (||), Parallel (*), While, For, and Match (which is a sort of switch).

Each behavior was a C++ class with a single function called "execute" which returned true or false. This function was then called in a thread. To develop behavior trees, we used a horrible combination of C++ operator overloading, macros, and so on. We could then view the resulting behavior tree in a little window with colorful boxes and arrows. The resulting code ended up looking something like this:

// A very high level robotics task. Robot initializes, searches for a rock, and tries to pick it up
// with either its right or left hand.
Behavior& PickUpRock()
{
    return 
        // These are examples of behavior creation macros which take in an ordinary C++ function. They get expanded
        // into something along the lines of Behavior(name, boost::bind(function, argument 1, argument 2, ...))
           BEHAVIOR(InitializeSystem)
        && BEHAVIOR1(SearchFor,"table")
        && BEHAVIOR1(SearchFor,"rock")

        // Choosing left or right hand involves the usage of a cryptic switch
        // statement substitute.
        && Match(IsOnLeft("rock"), 1,
                 Grasp(LEFT_ARM, "rock")
                 BEHAVIOR1(GoHome, LEFT_ARM)
                 )

        || Match(IsOnLeft("rock"), 0,
                 Grasp(RIGHT_ARM, "rock")
                 BEHAVIOR1(GoHome, RIGHT_ARM)
                 );
         
                         
       
}

// This is an example of a sub-behavior which uses arguments
// It is just a sequence of less abstract sub-behaviors.
Behavior& Grasp(Arm arm, string object)
{
  return  CreateGraspSet(arm)
       && PlanToGrasp(arm)
       && GraspPreshape(arm, object)
       && ServoToTarget(arm)
       && CloseHand(arm);
}

// Many thousands of lines defining all the sub-behaviors follow in multiple files... 
// At the very bottom we finally get to write straight C++ code. It will usually be just a dozen or so lines. 
// If the Behaviors fail to compile you will get very cryptic error messages from boost and STL.

You can see that what's happened is we've just created a less useful, harder to write meta-language on top of C++, instead of using C++ directly. Even worse, we were forced to use static singletons everywhere just to transfer data between behaviors. This led to things being extremely hard to debug, since we couldn't easily infer what data was getting changed where by which behavior. Contrast this with simply writing the whole thing in an ad-hoc script, where you can store local data and very clearly see where the data is going to and where it comes from.

 

I've yet to find a BT implementation which doesn't involve either extreme verbosity or crypitc meta-language symbols.

 

Take for example this library, which in its main example, takes dozens upon dozens of cryptic lines full of "news"  to make what is equivalent to a few function calls and a while loop within if/else brackets -- or perhaps this library, which uses cryptic C# operators to make a meta-language, much like in my example. I'm beginning to suspect that the whole drive behind BT is to make it easy to create plug-and-play graphical programming in an editor (why you would want to do this if you're not writing middleware for non-programmer designers I have no idea).

 

Is this how BTs are really used in the industry? Is there a better way?


Edited by mklingen, 02 September 2013 - 11:54 AM.


#8 AngleWyrm   Members   -  Reputation: 554

Like
1Likes
Like

Posted 02 September 2013 - 05:25 PM

I guess what I really want is a behavior architecture ... which allows me to do if, else, foreach, while, and switch statements, and which allows me to pass data between behaviors in a natural, easy way.

 

I notice the above desires describe almost exclusively one type of thought process: Production Rules. Production Rules represent procedural knowledge, and generally take the form of "if-then" propositions. Given a scenario, draw an appropriate response. Production rules are a variant of memorization; they involve storing information and then later retrieving that information for use when conditions are met. So if you find that your application has a lot of use for that type of thinking, then it might be appropriate to investigate advances in information storage and retrieval.

 

For example, let's say that our application examines an entity and activates a response based on that observation. A nieve and rather poor implementation would be a long string of If/then statements. A sleightly better version of the same thing would be a long switch statement. A much better version is an associative array, such as a dictionary or hash map which encapsulates the key->value storage and look-up association.

 

Note that Production Rule thinking is only one of several types of thought processes we use. There's also the "is-a" Semantic Network relationships, the "has-a" Object Frame relationships, minimally detailed Mental Models of "how" stuff works, and Memory Organization Packet lists.


Edited by AngleWyrm, 02 September 2013 - 05:52 PM.

--"I'm not at home right now, but" = lights on, but no ones home

#9 mklingen   Members   -  Reputation: 162

Like
0Likes
Like

Posted 02 September 2013 - 06:10 PM

I'm not saying that's the only way I wish to do things, but rather that I would like to be able to do it easily within the confines of a behavior architecture. Production rules are a basic building block of computer programs. They should be in any behavior meta language as well. They live in BTs as selectors and sequences. They live in FSMs as state transitions. In my opinion, not only should they be in such an architecture, they should be very easy and intuitive to implement. 



#10 IADaveMark   Moderators   -  Reputation: 2300

Like
0Likes
Like

Posted 03 September 2013 - 12:47 PM

I could make the case that programming languages and compilers add limitations onto what you could do writing straight up machine code. After all, aren't "if/then" statements just a branch in machine code? Why deal with all that messy stuff with variable passing when I can simply look something up at a memory location or in a register? I mean, do programming languages and compilers offer any value whatsoever? It all seems so complicated. 


Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
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!"

#11 mklingen   Members   -  Reputation: 162

Like
2Likes
Like

Posted 03 September 2013 - 02:17 PM

A better analogy would be *writing the entirety of a programming language and a compiler* every time I want to start a new project. By hand. And then debugging the underlying compiler and programming language before I even begin writing applications. And worse, the rest of my software is still all written in machine code.

 

Then, I've got to write tools for my new language in machine code. I've got to write authoring software. Debuggers. I've got to teach new people on the project my fancy new language. I've got to come up with style conventions. I have to handle corner cases.

 

Luckily, with high level programming languages, somebody already did that stuff for me decades ago.

 

Not so for these hand-rolled meta languages.


Edited by mklingen, 03 September 2013 - 02:20 PM.


#12 VReality   Members   -  Reputation: 434

Like
0Likes
Like

Posted 03 September 2013 - 05:59 PM

Perhaps state machine mechanics, decision trees, etc., should be provided as optional tools, rather than as a framework - er - into which - you must plug.

 

My team once implemented co-routines (that is, the ability to "Yield" and have processing resume from the same spot next frame- so as to wait, in the middle of a logical flow - for a condition to be met) because we were sure it would make behaviors easier to write.  It didn't really.  A stone-age switch-statement state-machine was just as clear, and effectively as simple to use.

 

Although I have to admit, I have occasionally daydreamed about a graphical state machine tool.



#13 IADaveMark   Moderators   -  Reputation: 2300

Like
0Likes
Like

Posted 07 September 2013 - 09:20 AM


Although I have to admit, I have occasionally daydreamed about a graphical state machine tool.

They exist.


Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
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!"




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS