Review
bod-deitic

The Behavior-Oriented Design of Modular Agent Intelligence

Andrew Armstrong on March 20, 2008

To build AI logic, game developers use a variety of different techniques depending on their preferences and the problem at hand. It’s interesting to note, however, that the overall architecture and methodology they use is often similar. Indeed, good techniques are often reinvented and great ideas spread fast in the games industry.

This week’s Thursday Theory article looks into a white paper that may never have been revolutionary, but documents many different techniques and methodologies that have been used in the animat and virtual agent communities as well as in game development. The underlying methodology is called Behavior-Oriented Design (BOD) as developed by Joanna Bryson from the University of Bath. The ideas presented here are related, and applicable to the increasingly popular behavior trees.

This post was created by Andrew Armstrong with insights and analysis by Alex Champandard. Feel free to post a comment below or in the forums to let everyone know what you think about this technology!

Motivation

Building complete, complex agents that can work on their own and manage conflicting goals and multiple mutually-exclusive means of achieving those goals is a hard problem. BOD is designed to help by providing a methodology and a basic architecture for dealing with this.

In particular, the paper covers three major aspects of the problem:

  1. Of course modularity is good for game AI, but how do you make it shine? Modules of behavior are often difficult to define. What part of the behavior should be separate module? It can take time to figure out effective behavior modules.

  2. In practice, behaviors often need a certain level of autonomy to deal with problems, while at the same time solving specific problems in the game. Designing such behaviors can be a challenge too.

  3. In the agent community (and certain games), AI is increasingly built as a three-layer architectures of behavior-based AI, reactive planning and deliberative planning. Although it has its advantages, this hybrid approach can take much longer to implement.

The paper addresses these problems by unifying the different layers in the architecture, thereby making it easier to build behaviors that plug together.

Insect Feelers Reactive Behaviors


Figure 1: An Insect-like robot with no long range sensors using feelers to find its way around a box

Contributions

BOD, as an entire design methodology, advocates a combination of principles that are very reminiscent of agile development applied to AI. Specifically, the following principles:

  • Iterative design is used along with rapid prototyping to develop the behaviors.

  • Changes in architecture, if improvements can be made, are encouraged since they should be simple to do.

  • The use of the fundamental design principle: when in doubt, favor simplicity.

  • Self documentation of code and code reuse are covered.

From a technical perspective, the system is based on hierarchical reactive plans which are very similar to behavior trees as used in the games industry for a few years, and by robotics labs for decades before. In particular, the paper advocates:

  1. Encapsulating perception, action, learning and memory as behavior modules, implemented by programmers in a traditional object oriented language.

  2. Letting designers work with a data-driven layer on top, built up of combinations of the low-level modules. This includes action patterns (a.k.a. sequences) and competences (a.k.a. selectors).

  3. Adding in some learning in certain parts of the tree, when losing some control in the process is acceptable.

  4. Using “drive collections” as the highest layer in the architecture to decide which arbitrate between the different goals that can compete for attention.

The paper also contains many nuggets about using reactive hierarchies to solve many problems from the low-level to the high-level. In many aspects of game logic, it helps to have things like “behavior trees” in place since they provide goal-directed behaviors (with optional memory/state) to solve the problem at hand effectively.

Competences and Dynamic Behavior


Figure 2: A competence reactive plan consisting of several actions that need to be completed to fulfil a goal. The arrow on the left is the rising priority.

Abstract & References

Here’s the abstract for the paper itself:

Behavior-Oriented Design (BOD) is a development methodology for creating complex, complete agents such as virtual-reality characters, autonomous robots, intelligent tutors or intelligent environments. BOD agents are modular, but not multi-agent systems. They use hierarchical reactive plans to perform arbitration between their component modules. BOD provides not only architectural specifications for modules and plans, but a methodology for building them. The BOD methodology is cyclic, consisting of rules for an initial decomposition and heuristics for revising the specification over the process of development.

You can download the paper from the website:

The Behavior-Oriented Design of Modular Agent Intelligence
Joanna J. Bryson
Agent Technology and Software Engineering 2002.
Download PDF (74 KB)

Evaluation

It’s hard to separate ideas in this paper from ones that are generally accepted as good practice already in industry, as well as many opinions you’ll hear on this blog too. So if this paper scores highly, it’s mainly because it documents and unifies techniques from various different places.

Applicability to games: 10/10
The modular approach advocated by BOD is not only useful, but practically a requirement for game developers who want to build simple and scalable designs. Additionally, the reactive hierarchy is by far the most computationally effective way of creating intelligent and responsive logic for a game.
Usefulness for character AI: 9/10
It’s feasible to build most types of NPCs using techniques similar to behavior trees. The approach is a great way to combine designer control with logic and automation. However, this approach doesn’t natively support the rating and comparison of behaviors based on a heuristic (except at the top-level) so it’s requires a certain skillset to scale this up.
Simplicity to implement: 10/10
The methodology itself will appeal to the common sense of the new wave of agile developers, as well as the veterans who prefer to play it by ear! The reactive hierarchy and modular behaviors also require little work, no more than a HFSM.

Another paper inspired by this research is called Behavior Orientated Design of an Unreal Tournament Character. It will be featured in the future on AiGameDev.com, but in the meantime you can sign-up to the forums to find it in the section on White Papers.

Discussion

You’d be hard pressed to find developers not using these ideas in some way. Likewise, if you take the time to read this paper you’ll most likely find a trick or two that you can use directly within your system.

One idea in particular is the concept of competences, which are at the heart of Halo 2’s AI and very useful in robotic teleo-reactive programs. A second idea is also using drive collections at the top of the tree to work out which “goals” and subtrees to activate in a fuzzy fashion.

What’s particularly fascinating about this paper is that it starts to tie together these reactive hierarchies, or behavior trees, with machine learning. Indeed, combining these two techniques may well be The Secret to Building Game AI that Learns Realistically. It combines a structure that the designer has control over, along with statistical learning.

What do you think about Behavior-Oriented Design and its application to game AI? Post a comment below.

Discussion 7 Comments

kfields on March 21st, 2008

Aww ... you guys shouldn't have. Did you post this for me? :) I've been meaning to revisit Joanna Bryson's site. Now I think it's an imperative. Reactive planners like POSH, Spark, & Jason IMHO are what to keep on the radar as far as future game AI. Of course, you still need other types of planners. Thanks!

Andrew on March 25th, 2008

Hey, Joanna, great you're updating things - we'll see about looking at your other papers sooner or later, and I'll check the updates out :) Seems like I'll need to reinstall my old copy of Unreal Tournament now too ;)

kfields on March 25th, 2008

Huh? I'm not her! I just like what she's doing. I guess that's what I get for making a flaky post. :)

Vicente on March 25th, 2008

Andrew was ansering to Joanna comment on the blog ;)

kfields on March 25th, 2008

I'm like ... totally embarrassed. I assumed the forums and the blog comments were in sync. I guess I need to check the blog first from now on. I'm geeked about the new POSH stuff though!

Andrew on March 25th, 2008

Yeah, these forum replies are rather useless at the moment for checking new comments, but it might change in the future. Generally got to keep an eye on the front page article and the comments listing there.

alexovi on June 12th, 2008

Hi. I haven't read document yet, but this looks very similar like GOAP. Where are main diferencies ??

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!