main page

back to computer sicence
back to osm

GDC 2005 Slides with Talk Transcript

 

Slide

Talk Transcript

1

An Orwellian Approach to AI Architecture

Igor Borovikov

Sony Computer Entertainment America

 
2 How to build better AI? The question I will try to answer during this talk is “how to build better AI?"
3 What is the source of complexity in game AI?
- interactions of game objects
Why is it difficult to build good AI? Where from comes the complexity? It is the complexity of interactions of game objects that makes AI implementation complex.
4 Games are about interacting objects:
  • Dozens and hundreds of objects
  • Variety of interactions
  • Concurrent objects
Of course, games are about interacting objects. There are dozens and hundreds of them and they participate in very diverse interactions. Complexity grows even more if the objects are concurrent or distributed. By concurrent objects we understand those that function in parallel. Distributed objects are those that work together over the network.
5 AI interactions are:
• Most diverse and dynamic
• Crucial for fun gameplay
AI interactions are probably the most complex and diverse. They are least formalized of all interactions. And at the same time they are responsible for delivering fun gameplay.
6 Hard to answer questions:
- What are responsibilities of personal AI?
- Is group AI really necessary?
- How many other AI subsystems are needed?
- What exactly is handled by different AI subsystem?
- How AI subsystems work together?
When designing AI engine we often face hard questions like on the slide. There are always many opinions on each of these questions. The correct answer often evades developers until it’s too late. Breaking AI into components and organizing them was never easy.

The goal of this talk is to present a uniform approach to answering these questions.

7 Goals:
• Introduce a new architecture for building AI (and game in general)

– It features an effective way to deal with complexity of objects interactions

• Offer a metaphor to lead through design process

– Use the metaphor when in doubt!

Namely I am going to present a new architecture for building AI engine. Its main goal is to manage complexity of interactions.

The architecture itself is derived from a metaphor. We will use the metaphor to answer to the questions like those on the previous slide.

8 Standard building blocks:
• Finite State Machine (FSM)
• Hierarchies:
- Command Hierarchy,
- Hierarchical State Machine (HSM)
• Messaging
+ their combinations
But what is the methodology?
The architecture we are going to discuss is based on standard building blocks. These blocks are:

Finite State Machine.
Hierarchy. Mostly we will rely on command hierarchy.
And the last but not the least is messaging.

These blocks are present in many games. They are combined in different, sometimes very inventive, fashion.

However there is no universal recipe on how to do it in every particular case. We are missing an important piece - a methodology - from the list of building blocks.

9 Interacting Agents deja vue:
• Human society organizes interactions.
• It is a good place to look for a metaphor.
Poles: Democracy --- Dictatorship
Bureaucratic Dictatorship:
• Hierarchy of control
• Strict communication rules
• Absence of free will
To fill in the missing piece of the puzzle we will look for real-life examples. In particular, we need an example of numerous agents participating in complex interactions. Obviously the human society is the most well known example. On the large scale its organization ranges from democracy to dictatorship. We will choose bureaucratic dictatorship. And we will show that it fits game AI needs very well.

There is a good reason for that. Bureaucratic dictatorship already has features present in the software. These features are: Hierarchy of control, Strict communication rules and absence of free will.

10 Bureaucratic Dictatorship Examples:
Totalitarian states
(For the lack of personal experience watch movie 'Brazil' by Terry Gilliam!)
An Army
(Familiar to some people)
Some corporations
(An experience familiar to many people)
Some religious sects or organizations
(Anyone?)
Examples of bureaucratic dictatorship are actually more numerous than one can expect. It is not necessary to live in a totalitarian state to get some personal experience.

An army provides a good example of organization featuring rules of bureaucratic dictatorship.

Yet the most common example is an exaggerated corporate structure. Even if you happen to work for a nice company you can extrapolate some of the common corporate rules to get the idea.

11 Common Features
- Hierarchy
with clearly defined chain of command
- No free communication
commands and reports only, opinions of subordinates don’t matter
- No free will
No voluntary cooperation, hence no “horizontal” communication.

Let’s look at the main features of the bureaucratic dictatorship.

Hierarchy. It clearly defines subordination and chain of command.

Strict communication rules. The only accepted communication is based on reports and commands. There is no room for opinions, suggestions or voting.

No free will. Agents don’t come up with initiatives. All they do is perform commands. They don’t try to cooperate with anybody in a voluntary creative fashion.

12 Bureaucratic Dictatorship makes most people unhappy
But game objects are different!
- Artificial agents have no free will
- Artificial agents don’t communicate unless ordered to

 

13 Orwellian State Machine – a software model of Bureaucratic Dictatorship
The main components:
- Agent
- Dispatcher
- Collective
OSM is a state machine built using these components according to the rules we are going to explore…
An Orwellian State Machine is a software model of bureaucratic dictatorship.
The main components of OSM are: Agent, Dispatcher and Collective. These components interact according to the Orwellian rules that we are going to explore in details.

But first, let’s take a closer look at OSM components themselves.

14 Agent:
- FSM
- Messaging:
accepts commands and issues reports
- Scripting
- Reports to Dispatcher
Metaphor:
- Private in an army
- Junior employee
Agent represents the layer of personal AI
Agents, according to the metaphor, correspond to privates in the army of junior employees in corporation. An agent is an FSM with messaging capabilities. Messaging is limited to accepting and executing commands and issuing reports.

Agents represent the layer of personal AI. They are absolutely incapable of cooperation by themselves. To cooperate they need help. Such help is provided by dispatchers. Thus, to be able to cooperate, agents need to report to a dispatcher.

15 Dispatcher: inherits Agent
- Has subordinate agents
- Sends commands to agents
- Receives reports from agents
Metaphor:
- Officer in army
- Manager in corporation

Dispatcher inherits agent. On top of the agent’s capabilities, dispatcher has subordinate agents. It can send commands and receive reports from them. In terms of the metaphor dispatchers are like managers or officers in the army.

16 Collective: inherits Dispatcher
- Owns subordinates, i.e. is responsible for spawning and deleting of subordinate agents

Metaphor:
- Recruiting manager

Collective is a specialization of dispatcher that can owns subordinate members. Ownership means that collective can spawn and delete subordinate agents. In other words it manages their lifecycle.

The metaphor suggests that collective is like a manager with a power to hire and fire.

17 Putting elements together, or Orwellian communication
Why is it wrong to let OSM agents to:
- Know too much about each other
- Assume other agents’ existence
- Allow “suggesting” or requesting cooperative actions instead of just following orders?

To put these three types of elements together we need to establish some rules of their communication. We are going to follow the Orwellian approach inspired, by the bureaucratic dictatorship metaphor. In particular it tells us that agents:
- shouldn’t know too much about each other,
- often they shouldn’t even assume each other existence in the first place,
- there shouldn’t be initiative or suggestion coming from subordinates regarding cooperation of agents.

To show the importance of these limitations we are going to explore two classical problems.

18 Two Model Cases
- Scheduler
- Dining Philosophers Problem

Typical for synchronization, sharing resource or tight cooperation in general.

We will explore and evaluate how mutual awareness of agents influence solution of these problems. The problems are: a scheduler and dining philosophers problem. Both are classical problems used in studying of agents’ cooperation.

The cooperation here is understood in quite general way: it could be synchronization, sharing resource, or any other coordinated action.

19 Scheduler: several NPCs attack player in turns one at a time

if message received:

attack;
pass message to the next NPC;

Scheduler problem formulated in terms of a fighting game sounds like this. There are several NPCs attacking the player. The goal is to make them attack in turns, one at a time.

Suppose we are going to use only personal AI level to solve this problem. Then the logic of the agent behavior is very straightforward. An agent waits for attack message and then starts attack. When the attack is finished the message is passed to the next npc.

20,
21
Scheduler: agents update cycle

This logic of Scheduler is illustrated with the UML diagram. A message comes in and if the enemy is idle it starts attacking. When done npc sends message to the next attacker. The diagram describes three agents performing in such manner, trying to solve the scheduler problem.

22 Scheduler circular list problems:
- Maintaining circular list (easy)
- Making sure messages are not lost (not so easy)
…and we assumed no concurrency!

A couple of issues are immediately obvious with this implementation.

First of all, we need to support circular list and repair it when one of the enemies is killed. It’s easy.

The second issue is not so easy to address. Suppose that the enemy is killed during attack. Because of that the enemy wouldn’t be able to pass the event to the next one. The remaining npcs will stay idle after that.

We run into a problem in a relatively simple situation. And we didn’t even assume concurrency or a more complex attack pattern for the npcs.

23 Dining Philosophers Problem (DPP)
(Edsger W. Dijkstra, 1971)
Cooperating Concurrent Agents
Philosopher has states:
- Eating
- Thinking
Philosopher needs two forks (left and right) to eat slippery pasta.

Another important example is Dining Philosophers problem. It was introduced by Edsger Dejkstra in 1971 as an ultimate model case for concurrent programming.

The dining philosophers are agents that have two states: eating and thinking.

24 While thinking a philosopher doesn’t need anything. After thinking for some time a philosopher becomes hungry.

And when hungry, a philosopher eats pasta. But the pasta is very slippery. Because of that a philosopher needs two forks to eat. When done eating he places forks back on the table.

Unfortunately there is same number of forks as there are philosophers. In our particular case there are five philosophers and five forks.

Imagine that philosopher number 1 reaches for forks at the same time as philosopher number 2. If they both reach for the fork on the right first and then try to acquire fork on the left, then the philosopher 1 wouldn’t be able to eat.

Imagine that all philosophers do this simultaneously. Apparently they will get into a deadlock and will starve to death.

25 Dining Philosophers
Philosophers need to share forks:
- A philosopher need to obtain two forks to eat
- A philosopher places both forks back on table when done eating
- No forks required for thinking
A recap of DPP rules.
26 Dining Philosophers
- The classical problem for distributed and concurrent programming
- Simple to formulate yet subtle
- Multiple solutions

Dining Philosophers is a classical problem for distributed programming. Despite of it’s simple formulation it’s very subtle and allows multiple solutions.

27 Anthropomorphic approach
- How would real people behave to solve Scheduler and DPP?
- What kind of mutual awareness they need to communicate and cooperate?

=>leads to awareness analysis

Let’s try to imagine how real humans would try to solve Scheduler and Dining Philosophers problems.

The question we need to solve is what kind of mutual awareness they need to have to communicate and cooperate efficiently?

That brings up an issue of awareness analysis.

28 Awareness analysis: reflexive polynomials
Vladimir Lefebvre
“Conflicting Structures”, 1973
Algebraic vs. graphical:
- “A is aware of B” – a simple drawing. But:
- ”B is aware of A being aware of B” is not simple!
There is a neat algebraic tool for such analysis. It’s called Lefebvre polynomials. They were introduced by Vladimir Lefebvre and were used to replace graphical representation of situations like “A is aware of B”, or “B is aware of A being aware of B”, etc.
29 Reflexive polynomials
T denotes a scene
T+a+b is a scene with two agents
T+a+b+Ta agent a is aware of the scene
T+a+b+(T+b)a agent a is aware of the scene and agent b in the scene
- First order terms (a and b) are not very interesting; later we will keep T only
An informal introduction of Lefebvre polynomials is like this.

Let T denote the scene were interaction of agents a and b unfolds. The polynomial T+a+b describes the scene with both agents present in it. Next, an agent a becomes aware of the scene and that changes the polynomial to T+a+b+Ta. The next polynomial describes situation when agent a is also aware of agent b in the scene.

First order terms are not very interesting so we will keep only T and will drop a and b.

30 Reflexive polynomials
T+Ta+Tb+Tab+Tba – both agents know about each other
Taa –agent’s a first-order “self awareness”
Here is a polynomial for two agents being aware of each other and the scene.

From programmer's point of view "an agent a is aware of agent b" means that a has a pointer on b and can access b.

31 Reflexive polynomials
Practical application: estimation of interaction complexity by evaluating the structure of the polynomial.
More information: http://3dmatics.com/compsci/osm/lefebvre.htm
We don’t have time to dive deep into Lefebvre polynomials. It’s enough for us that Lefebvre polynomials help to evaluate complexity of mutual awareness for interacting agents. Some extra information is available from this url on the slide.
32 Scheduler and DPP analysis with reflexive polynomials

Solution 1. Ramping up personal intelligence of the agents.

- All agents ai are all aware of each other and can communicate freely:

T + i=1,N Tai + i,j=1,N Taiaj

Let’s return back to Scheduler and Dining Philosophers.

One way to solve both problems is to ramp up personal intelligence of each agent. The agent can be aware of each other and can communicate freely.

Such situation is described by the polynomial at the bottom of the slide. Notice that the polynomial has N square quadratic terms.

Basically, more complex polynomial means more complex code with more dependences between objects.

33 Scheduler and DPP analysis with reflexive polynomials

Solution 1.
Pros:
- Easy to implement in the beginning, when some basic AI is already in place
Cons:
- Second order reflexive polynomial, number of quadratic terms grows as N2
- Agents’ personal intelligence has to overcome quadratic complexity

Complexity managed poorly!

Ramping up personal intelligence while not imposing any restrictions on the communication or awareness is one of the ways to solve the problem.

It is easy to implemented for small number of agents. It is tempting to follow such way under the pressure of deadlines, when some basic personal AI is in place. All we need is just throw in some messaging and the agents will start cooperate.

However this approach faces inherent N square complexity, which personal AI has to overcome. No wonder it fails pretty soon with the growth of N.

This is the case when interaction complexity is managed poorly.

34 Scheduler and DPP analysis with reflexive polynomials

Solution 2. Group AI (Hierarchical Control): agents cooperation handled on a layer higher.
- Agents ai are not aware of each other; only the agent in charge A is aware of its subordinates:

T + TA + i=1,N Tai + i=1,N TaiA

The second solution is to introduce group layer to help personal AIs.

That can be done with introducing a special agent A capital that is aware of all of the cooperating agents. The regular agents are not aware of A capital. The A capital takes responsibility to orchestrate cooperation of regular agents.

Lefebvre polynomial for such hierarchical situation looks differently. As you can see it has only N second-order terms.

35 Scheduler and DPP analysis with reflexive polynomials
Solution 2. Hierarchical control.
Cons:
- Extra work in the beginning to setup group layer of AI
Pros:
- Only N second-order members

Complexity managed better!

That presents second approach to the problems. The approach uses group AI and hierarchical control.

The downside of this approach is that developer need to invest some extra time to create group layer for AI .

The advantage is obvious: the complexity is managed much better. It grows linearly with the number of agents.

36 OSM similarities to Command Hierarchy:
- Hierarchical control is based on similar metaphors
- Messaging built on commands and reports

“AI Game Programming Wisdom”, 2002:
William van der Sterren,
John Reynolds.
This discussion explains importance of the hierarchical control. The similarity of the second approach to the command hierarchy is obvious. The command hierarchy was proposed in the book AI Game Programming wisdom, the very first book in the series. The similarities are in using similar metaphors and in the commands/reports-based communication.

However OSM is not boiling down to just command hierarchy.

37 OSM is more than Command Hierarchy:
- Clear distinction between Dispatchers and Collectives
- Explicit rule when create new Dispatchers or Collectives
- Generality going beyond AI applications
- OSM is not a tree but DAG, several hierarchies can co-exist

In OSM we apply the metaphor consistently to all types of agents interactions.

Here are some of the more important differences from just command hierarchy:

- We made clear distinction between Collective and Dispatcher.

- OSM sets clear rules on when new dispatchers are needed.

- Dispatchers are more flexible in terms of hierarchy. They form DAG instead of a tree.

The consistent application of the metaphor actually promotes OSM to quite general design pattern.

38 OSM communication rules
Subordinate agent:
- Can send reports only by placing them into outbox
- Is not aware of the dispatcher in charge or same-layer subordinates
- Hence, agent can’t send commands, requests or “suggestions” to the dispatcher in charge
Purpose: killing quadratic terms in reflexive polynomial (complexity management)
Earlier we established main building blocks of OSM and now we are ready to describe how they communicate. The communication rules for OSM are aimed at killing quadratic terms in the reflexive polynomial. The rules are quite simple. They tell what exactly a subordinate agent can do and what it can’t.

Agents can send reports. They do it by placing reports into outbox.

An agent is not aware of the dispatcher in charge.

An agent is not aware of same-layer subordinates

Hence, an agent can’t send commands, requests or “suggestions” to the dispatcher in charge or to other same-layer agents.

Once again the purpose of these rules is complexity management done by killing quadratic terms in reflexive polynomial.

39 OSM communication rules
Dispatcher:
- Can access subordinates’ outbox to retrieve reports
- Sends commands to the subordinates by placing them into their inbox

Dispatchers are agents in charge of organizing interaction of subordinate agents. Dispatchers can access outboxes of subordinates and read reports. Dispatchers can place commands into inbox of the subordinates.

40 The Metaphor in Details

Goal:
fill in details of the metaphor by exaggerating familiar rules and situations.
After establishing formal rules it would be good to see how they are supported by a metaphor. We will explore some familiar situations and real life rules to see how dispatchers and collectives are present in our everyday experience.

One of the most resourceful areas is the corporate structure, familiar to many game developers. By exaggerating it rules we can extrapolate it to almost ideal bureaucratic dictatorship.

41 Hierarchy:
• Every employee has one or more managers. They map to Dispatcher (or Collective, if it’s a hiring manager).
Examples of Dispatchers and Collectives
- Direct manager: tells what work to do,
- HR: sets rules of conduct,
- Security: tells to wear the badge
- Equity management: tells where to park.
The hierarchy is the most prominent features of human society. In a big corporation there is a hierarchy of managers that maps to hierarchy of dispatchers and collectives. Every agent (an employee) reports to some manager. A president of a company reports to the board of directors.

The direct manager is a guy who tells employees what to do. It is the most obvious example of a dispatcher.

There are less obvious examples.

HR works as a dispatcher. It sets rules of conduct. Employees are commanded not to do certain things and do some other things. The relationship here is pure command-and-report.

Security is yet another dispatcher. Security also communicates with employees via commands. For example, they tell everybody to wear a badge.

Equity management is one more dispatcher in charge of employees. For example, they tell where you can park. Again it’s command and report relationship.

42 Awareness rule:
• Every employee minds only her own personal tasks
Examples (sometimes happen in real life):
- An AI programmer needs support for sounds. Instead of writing a sound system (s)he talks to the tech lead. The tech lead makes this system appear somehow (and the AI guy doesn’t really need to know how).
- If a door is broken employee notifies equity manager but doesn’t offer help with fixing it.
Agents’ awareness is based on minding only personal tasks and executing only direct commands.

Here is an example.

Suppose an AI programmer needs support for sounds. Instead of writing a sound system she talks to the tech lead. The tech lead makes the sounds system to appear somehow. The system can be outsourced, or purchased as third party library, or reused from the previous project. The AI guy doesn’t really need to know how the system appears.

Another example.

If on the way for the morning cup of coffee you notice that a door to the kitchen is broken, you would notify equity manager. The equity office sends somebody to fix it. The game developer is not supposed to offer help with fixing the door.

Thus the awareness rule assumes strict division of responsibilities of the agents.

43 All communication is formal:
• it goes via (e)mail
Agents know only about their own in- and out- boxes. They don’t talk to anybody in person.
>Enforces the awareness rules.
To enforce awareness rule even more we can require that all communication between agents is formal. It goes through (e)mail. The agents can access only their inbox and outbox. There is no informal way to communicate or cooperate whatsoever.
44 No free will, no initiative:
• Following commands only.

(also occasionally happens in real life)

- In the movie “Brazil” by Terry Gilliam the main character disobeyed this principle, see what happened!
Another feature of Orwellian State Machine is complete absence of free will. Agents don’t show any initiative. All they do is follow commands.

The movie Brazil by Terri Gilliam shows how breaking this rule is harmful to the bureaucratic dictatorship. The main character breaks about every rule we established, and especially the “no initiative” rule. You really should see what happens.

An interesting observation that you can make when watching the movie is that the bureaucratic dictatorship proved to be rather stable with respect to a single rebel. That is an indication that software built on the same principle can be more robust and tolerant to the isolated problems.

45 New dispatcher for new type of interaction:
• Every new type of cooperation requires new department and a dedicated manager
Types of cooperation:
- Writing game code (Tech Lead)
- Managing project finances (Producer)
- Fire drill: leaving the office in an orderly fashion (Fire Department)
- Driving: sharing road (Highway patrol)
Probably the most important rule is that every new type of interaction requires new dispatcher. In terms of the metaphor it sounds like this: “every new type of cooperation requires new manager and new department.”

Apparently this rule can be derived from division of responsibilities. But because of its methodological importance we will explore separately.

Let’s look at real-life examples.

Writing game code requires tech lead that acts as a dispatcher. You can get away without tech lead only for a small group of programmers. We don’t discuss open source community here.

One more dispatcher is about money. Money is a shareable resource. Normally on a game project a producer is in charge of managing finances.

Game developers share office building, In case of fire they need to know where is the designated fire escape. Fire department is in charge of organizing such cooperation as leaving the building in orderly fashion in case of fire or fire drill.

When driving to the office people share road. To manage such sharing there is DMV and highway patrol to enforce rules of safe driving.

All these examples tell us that in real life every new type of interaction requires new type of dispatcher.

46 Back to OSM
• Bureaucratic Dictatorship is not good for humans but works for game agents
• Purpose: strict decomposition of both data and interactions
What we established so far is that the metaphor tells us how to do decomposition of objects interactions. It tells how to separate and organize interactions.

Even if bureaucratic dictatorship in it’s pure form is not good for people, it can be beneficial for game agents.

Now we are ready to return back to OSM.

47 OSM Implementation  
48 FSM

Finite state machine is at the base of OSM. All agents are derived from FSM.

FSM is nothing else but the class that has table of handlers for each of its states. When in certain state the FSM calls corresponding handler to update its state.

49
An agent is derived directly from FSM. In addition to regular FSM functionality it has inbox and outbox and can handle incoming commands. During update an agent iterates over the commands in the inbox and executes them with the corresponding handlers. The usual different between post and send command allows to get instant result from the command or just leave it in the inbox.
50 Both inbox and outbox of the agent are accessible to the dispatchers that the agent reports to.

Dispatcher places commands in the inbox of the agent and reads reports from outbox.

51 Agent’s Communication
Messages
No concurrency case:
- Time-stamped messages are placed into in- and out- boxes
- Handled when time comes
- Removed afterwards
The messages are all time stamped and handled at the appropriate time. When message is handled, would it be report or command, it is removed for the box.

That works perfectly simple in the case of centralized update cycle. We can easily track messages that were already handled.

52 Asynchronous messaging
No central update cycle:
- Reports have subscribers’ ids of dispatchers that need to access the report before it is removed
- Each dispatcher removes its id after reading the report
Asynchronous case is a bit trickier.

We can be pretty sure that commands eventually get executed. But reports require some additional care. Each report can have a list of ids of dispatchers that need to read the message. These ids don’t really allow an agent to access to the addressee but allows to keep track of who accessed the message. When addressee accesses the report it removes itself from the list. When list becomes empty, the message can be removed. Thus we can ensure that all reports get to the corresponding dispatchers.

53 class Dispatcher: public Agent

- New type of dispatcher for every new kind of interaction: cooperation, sharing resource, synchronization, etc
- Each dispatcher manages only messages specific to the interaction
- Doesn’t own the members: doesn’t create or delete them
- Reporting forms DAG

Dispatcher class inherits from Agent. The main principle is to introduce new dispatcher for each new type of interaction. The dispatcher holds a list of subordinate agents. It can access both in box and outbox of those agents. Dispatchers don’t own subordinate members. Dispatchers hierarchy don’t form a tree, but rather Directed Acyclic Graph.
54 Subordinates' Properties:
- Subordinates don’t have to be of the same kind
- But all subordinates are derived from Agent
Example: collision dispatcher reports to damage dispatcher since damage needs to know about collision
Note that since all entities in OSM inherit from agent, the subordinates of a dispatcher don’t have to be of exactly the same type. Let’s consider a rather typical example with Collision Response dispatcher and Damage dispatcher.
55 Example 1. Collision and Damage dispatchers

Imagine a game where agents need to respond to collision with geometry and each other. Also they can damage each other by, say, attacking with weapons or spell casting. Also we can add collidable objects that never damage other agents and can’t be damaged themselves. Next we can have traps that don’t participate in collision but can damage other agents.

After presenting this type of objects and their interactions we can conclude that we need two dispatchers: one for managing collision and the other one for managing damage. It is easy to decide what regular game agents report to which dispatcher.

Also it is easy to see that collision dispatcher has to report to damage dispatcher. When objects collide or one object attacks another one, collision dispatcher detects this situation. But it’s not it responsibility to decide whether any of colliding objects get damaged. Instead it sends a report about collisions in the scene.

The damage dispatcher can access this report and decide if any collisions resulted in damage. If this is the case it will send corresponding damages to the agents. In this example damage dispatcher has collision dispatcher as a subordinate, in addition to the number of regular agents. Note that after such decomposition we can reuse collision dispatcher for a more peaceful game where no damage happens. Similarly core of the damage dispatcher can work for the game where agents can damage each other only with spells, without physical contact.

56 Example 2. Truck Driver and Transportation Company

 

The next example shows some more dispatchers.

Imagine a game about truck driver. We can roughly identify interactions that the driver can get involved. First of all it’s driving a truck. A driver would be a dispatcher with respect to the truck. The truck would also report to collision response dispatcher, just like other vehicles on the road. The driver reports to the transportation company that hires him. This actually could even modeled as an ownership relationship. But in any case the transportation company is a dispatcher with respect to the driver. The company tells the driver what cargo to deliver and deliver from where to where. While driving on the road the driver would be reporting to DMV-highway patrol dispatcher. In case of an accident all three dispatchers – the company, the driver and the highway patrol need to report to yet another dispatcher – the court.

Similar relationships exist for other no-player agents in the game.

This example shows more of non-uniform subordinates for dispatcher.

57 Examples: migration between dispatchers
• Changing jobs
• Club Dancing
• Lead (dispatcher) and Follower (subordinate agent)
• Changing followers: migration between dispatchers
• New Lead can dance different style
So far we considered a rigid structure of reporting and ownership. Nothing prevents agents though from migration between dispatchers.

A simplest example is changing jobs.

Club dancing provides a bit more interesting example. First of all, most club dancing styles assume that there is a lead and a follower. The lead sends signals to the follower about upcoming moves and turns. The follower tries to execute those commands to the best of her knowledge of the particular dance style.

In club dancing is also allows possible to change a partner during dance. This is another example of migration between dispatchers.

58 class Collective: public Dispatcher
- Owns subordinates: can spawn and delete them
- Initiates update cycle of subordinates
- Triggers clearing of outboxes
- Ownership forms a tree
Collective is a specialized dispatcher that has several additional responsibilities.

The main additional responsibility is to manage lifecycle of the subordinates. Collective spawns members and deletes them when necessary.

Ownership forms a tree. The tree structure allows to access all agents in the game. Because of that collective is also responsible for initiating update cycle of the agents and for clearing of outboxes.

59 Spawning and Deleting agents
Problem: reports from marked for deletion object must reach subscribers
- Report has subscribers ids
- Ids use instance counting (to remove dead subscribers)
- Subscriber clears id after reading report
- Reports with no subscribers are removed
- Collective deletes market object with empty outbox
Creating of object is easy: we know all dispatchers in charge in advance.

Deletion of objects must ensure that all reports outcoming from the agent marked for deletion will get to the addressees. We discussed already mechanism that ensures that all reports get to the addresses. It uses ids to keep track of subscribers that already received reports addressed to them.

The agent market for deletion places a special report in its outbox. That message tells all dispatchers that it reports to that the agent is about to be deleted. The message has all the agent’s dispatchers on the list of the recipients. When dispatcher finds such message it removes the agent form the list of members and clears itself from the list of addressees.

When all dispatchers clear themselves from the “market for deletion” message, the object can be safely deleted.

It can happen that one of the dispatchers that need to clear itself from the recipients list is deleted before it has a chance to do that. To handle this situation we can use instance counting for the ids. When there are no more instances associated with the id, the id can be deleted from the recipients list automatically.

60 OSM: inheritance

A bird eye view on the OSM classes is very simple. All inheritance comes in a linear fashion from FSM. Messages are subdivided into reports and commands. The only difference of reports from commands is in the recipients bookkeeping.

The only class here that I didn’t mention is scriptable agent. It is nothing else but an extension of FSM with scripting capabilities. Unfortunately we don’t have enough time to discuss scripting.

61 OSM: associations

Associations of OSM components are also very simple and boil down to report/command relationship and to ownership.

62 Back to model examples: Now with OSM technique in hands we can revisit Scheduler and Dining Philosophers. Both problems will turn out to be nearly trivial.
63 Scheduler with OSM: Dispatcher

A pseudo-code for scheduler breaks into two parts: one is for dispatcher and the other one for the agents.

The dispatcher sends commands to attack and keeps track of the agents in case they are killed. The pseudo-code shows only the part related to sending attack commands. But the other part is equally simple.

64 Scheduler with OSM: Agents

The agent’s code is also very straightforward. Note that reporting about successful attack is really optional. Functioning of the dispatcher does not rely on receiving such reports.
65 Orwellian Dining with OSM
“Dining Server” – a dispatcher to control philosophers
• Dining Server keeps track of forks usage, maintains queue of philosophers ready to eat and send commands to initiate eating.
• Philosophers send reports about status change “hungry” and “done eating”.
Implementation for dining philosophers with dispatcher is also quite simple and straightforward. It is also know as dining server implementation.

The dining server is a dispatcher that keeps track of the free forks and of hungry philosophers. A simple logic allows to send “start eating” commands to the philosophers that have both forks free.

The philosophers send two types of the reports. One is sent when a philosopher gets hungry and the other one when he is done eating.

66 Emergent Behavior with OSM
• Procedural vs. hand-scripting
• Controlled emergency (bugs and emergency are not the same ;-)
Now we will briefly discuss emergent behavior. The main question would be if the emergent behavior is possible with OSM architecture.

Under emergent behavior we will understand a useful complex behavior that was not scripted directly but rather results from interplay of several simple rules.

67 Is OSM too rigid for emergence?
• FSM and emergence
• A rigid structure of report and command
The first impression could be that OSM is too rigid for emergent behavior. It is based on FSM and a number of seemingly restrictive communication rules.
68 Practical tricks for emergent behavior with OSM
• Mutation. Changing of agent’s FSM handlers on- or off- line.
• Morphing of handler sets between agents.
• Migration of agents between dispatchers.
• Migration+Morphing (E.g. recruiting a civilian into a gang)
Lets discuss few practical techniques that can be used to introduce emergence into the OSM based AI.

Mutation is the simplest technique. We can modify agent’s handlers in run time or offline. We can use adaptive rules to chose new handlers, or run genetic algorithm or do other tricks with the handlers.

Morphing between two agents is another technique. In this case we do sort of cross-bread handlers. Or we can replace gradually handlers of one agent with handlers of the other agent. Again this can be done according to, say, genetic algorithm.

Migration between dispatchers. We touched it a little bit before. Migration would take an agent from one dispatcher and move it to the other one. We have to be careful though not to break functionality of the game. It’s easy to do inadvertently if we, say, arbitrarily remove or add agents to collision dispatcher.

Migration combined with morphing is even more interesting. Consider two dispatchers – a civilian dispatcher for regular game characters and gang dispatcher for gang members. We can simulate recruiting of a civilian into a gang by moving an agent from civilian dispatcher to gang dispatcher. At the same time we can start gradually mutate the handlers to morph them into handlers of gang agents. Most likely we will observe quite interesting mixture of regular and gang behavior in the character during such transition.

69 Practical tricks (continued):
• Replacing FSM with less rigid system: fuzzy logic, neural network, etc
OSM architecture is not compromised while agents remain in hierarchies and obey ownership and messaging rules.
Finally, it is worth to note that FSM is not actually a mandatory base for all classes in OSM. Instead of FSM we can use any other fancy way to implement personal AI. It could be fuzzy logic, neural network or anything else. While the agent obeys communication and ownership rules it still can be considered as a component of OSM.
70 OSM Prototyping: Lua, Python, etc
• Rapid prototyping benefits
• Python: powerful built-in types
– List: subordinate members list, in- and out- boxes
– Dictionary: FSM handlers table
Now it is time for a little demonstration. I put together a rudimentary application in Python that illustrates principles of OSM with working code.

Python is just one of the rapid prototyping languages. With equal success it could be Lua or Java, or something else.

Python provides two powerful built in types – lists and dictionaries. They make implementation of OSM very compact.

71

The application shows several characters in the scene. There are three thugs doing their workout in the gym. The player can move around the level and can attack one of the thugs. If he does that, the thugs go into formation and start attacking the player. They implement a simple version of scheduler to attack the player in turns.

There is also a number of background npcs that just walk paths and one of them does window-shopping. He stops by the gym and scratches his head thinking about coming in. That guy is controlled by the same dispatcher as the other background characters but due to the specific script, he responds slightly differently to the same commands.

There is also collision dispatcher that prevents characters from walking through the walls.

72

This tab shows hierarchy of dispatchers and collectives in the application. Note that each character is implemented as a dispatcher controlling three agents.

The first atomic agent is visual system responsible for rendering the character on the screen. The other agent is animation player. And the third agent is movement system. Note that besides reporting to the character it also reports to the collision dispatcher. Note that collision dispatcher does not control the character directly. There are three dispatchers directly above the characters. One of them is controlling thugs and decides when to attack.The other one controls background characters. The third one is fight dispatcher responsible for fight interaction.

73

Here is also another tab showing inheritance of scripts but we don’t really have time to discuss it. You can explore it yourself if you download this test application.

74 Closely related works
• John Reynolds “Tactical Team AI Using a Command Hierarchy”, AI Game Programming Wisdom, 2002, pp. 260-271
• William van der Sterren, Squad Tactics: Planned Maneuvers, AI Game Programming Wisdom, 2002.
• William van der Sterren, Squad Tactics: Team AI and Emergent Maneuvers, AI Game Programming Wisdom, 2002.
It is time wrap everything up. I’d like to point at three papers that are closely related to OSM and inspired it to a big extent.
75 Conclusion
• Bureaucratic Dictatorship metaphor is the methodological principle for organizing interacting objects
• Awareness rules aimed to manage interaction complexity (N instead of N2)
Conclusion

We introduced bureaucratic dictatorship as a metaphor for interacting of agents.

We showed that it allowed us to manage interaction complexity in a much better way. In particular it helped to reduce complexity from quadratic to linear.

74 Conclusion (continued):
• OSM is implementation of Bureaucratic Dictatorship
– Command Hierarchy
– Dispatcher for interaction:
new kind of interaction requires new kind of dispatcher
– Collective for ownership
– Report/Command messaging
From the metaphor we derived a software architecture called Orwellian State Machine.

The main features of OSM are:

Command hierarchy with messaging based on reports and commands.

Dispatchers for every new type or interaction like cooperative action, sharing of a resource or synchronization.

Collectives for ownership.

75 Conclusion (continued):
• OSM is a general software design pattern
Additional information and source code:
http://www.3dmatics.com/compsci

Acknowledgements: “Rise to Honor” team at SCEA

OSM can obviously benefit implementation of AI. But it is not limited to AI only and can be viewed as a general software design pattern.
main page

back to computer sicence
back to osm