main page |
GDC 2005 Slides with Talk Transcript |
||||
Slide |
Talk Transcript |
|||
1 | An Orwellian Approach to AI ArchitectureIgor BorovikovSony 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:
|
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 its 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)
Offer a metaphor to lead through design process
|
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. 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 dont matter - No free will No voluntary cooperation, hence no horizontal communication. |
Lets 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 dont come up with initiatives. All they do is perform commands. They dont 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 dont 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, lets 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 agents 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: |
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: 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:
|
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
|
|||
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. Its easy. The second issue is not so easy to address. Suppose that the enemy is killed during attack. Because of that the enemy wouldnt 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 didnt 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 doesnt 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 wouldnt 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 its simple formulation its 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 |
Lets 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. Its 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 agents 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 dont have time to dive deep into Lefebvre polynomials. Its 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
|
Lets 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. 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. 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 cant 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 cant. 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 cant 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 its 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 its 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 doesnt really need to know how). - If a door is broken employee notifies equity manager but doesnt 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 doesnt 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 dont 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 dont 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. Lets 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 dont 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 its 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
|
|||
49 |
|
|||
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 | Agents 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 dont 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 |
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 dont own subordinate members. Dispatchers hierarchy dont form a tree, but rather Directed Acyclic Graph. | ||
54 | Subordinates' Properties: - Subordinates dont 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 dont have to be of exactly the same type. Lets consider a rather typical example with Collision Response dispatcher and Damage dispatcher. | ||
55 | Example 1. Collision and Damage
dispatchers
|
|||
56 | Example 2. Truck Driver and
Transportation Company
|
|||
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 agents 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 didnt mention is scriptable agent. It is nothing else but an extension of FSM with scripting capabilities. Unfortunately we dont 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 agents 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 agents 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 agents 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. Its 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 dont 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. Id 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 |