Navigation: Overview >> Working Group on Rule-based Systems

Working Group on Rule-based Systems

In this report we introduce the work carried-out by the Artificial Intelligence Interface Standards Committee (AIISC) working group on Rule-based Systems (RBS). A significant topic of discussion during the 2004-2005 period has been to identify the relationship between Rule-based Systems and in Game Artificial Intelligence. When are Rule-based Systems and rule programming used in Game Artificial Intelligence? How does this relate to scripting, and for what types of games?

Most of the discussion/work conducted in this period is a continuation of previous years. Unique to this year we conducted an in-depth examination of Age of Empires rule scripts (from mods). We also garnered additional insight from discussion at the Game Developers Conference.

Presented here are background concepts and issues discussed on the aspects of specification, design and development of a Rule-based System for game Artificial Intelligence (AI) to implement challenging game agents (i.e., NPCs - "Non-Player Characters"). We are investigating the components and possible architectures of RBS, and the different applications of game AI in general and of RBS in particular, depending on game genres.

Goals

Rule-based Systems can be used to encode behavioral rules that capture knowledge about a particular game scenario and the agents that inhabit it (e.g., game NPC opponents). In all but the simplest of games, rules that govern the behavior of entities within the virtual world of a game need to embody complex relationships between large numbers of rapidly changing aspects of the overall game state. Programming these behavioral rules is an acknowledged problem in computer game construction.

We expect a trend in the games industry towards more rule-based styles of AI programming. At recent Game Developer Conferences, speakers (e.g., Peter Molyneux and Will Wright) indicated that game AI will play an increasingly important role as a source of "dynamics" and "emergent behavior" that leads to new (generated/emergent) content within games. We believe that this trend will drive game development towards more sustainable programming styles based on "rules." This report introduces the work carried-out by the AIISC's working group on Rule-Based Systems (RBS) to date.

Rule-based Systems are comprised of a database of associated rules. Rules are conditional program statements with consequent actions that are performed if the specified conditions are satisfied.

The aims of the group are to discuss and develop a set of standard on RBS applications and architectures suitable to games. This is a preliminary report on the current work of the RBS group, and which will be followed-up by recommendation and a proposal for a game-AI RBS interface standard in future reports.

The effort of this working group will also indirectly assist the game developer community in other ways:

Major Findings Updated

In the 2003-2004 final report we presented four major findings, representing the conclusions of the group to date. In this year's report we updated them with amendments and new detail.

[1.] Increased use of rule-based programming in game Artificial Intelligence expected.

We believe that game AI will rely increasingly upon rule-based and declarative programming techniques in the future. Our expectation is that rules adoption will likely occur first with server-based games (e.g., online multiplayer games), for a couple of reasons. First, server architectures tend to be already largely componentized (e.g., database, login, etc.) - adding a new RBS component on the server is likely more feasible than on highly optimized clients. Second, server-resident games share a number of requirements with commercial server applications, e.g., performance, scalability, and supporting dynamic loading and "hot swapping" of AI logic.

[2.] Rule-based Systems can be integrated into games using industry compatible interfaces.

At the level of integration, script interpreters and RBSs pose similar problems. They both have to relate to the game engine. Is their relationship synchronous? Where is the game state? Will they support functional call-backs? Etc. Should the game engine be able to reach-in and tune performance? We have hypothesized how these approaches might ultimately converge behind an interface rooted in an industry standard, JSR-94 (Java Specification Requests). We believe that a JSR-94-based interface can support a range of RBS middleware (more powerful to less powerful RBS components). We start with the view that an RBS is a rule-engine that (words adapted from JSR-94):

From the commercial applications sector we see a trend towards merging rules with scripting (or "rule-based scripting"). This sector has evolved a range of products that uses rule-based scripting to customize middleware. Consider large system architectures servicing business processes. Typically such architectures integrate a range of products and contain much "glue code" (including scripts) whose behavior is conditioned on the values in the data as it passes through, e.g., real-time data feeds etc. Such systems often represent metadata using rules: by separating the representation from the implementation (code) it simplifies maintenance.

While rule-scripting for single-player games can be simple, RBS integration with multi-player online game servers will require considerations beyond a JSR-94-based interface. For example, discussion in games technical forums have from time-to-time suggested that RBS optimizations that work well in commercial business domains may need to be modified for use in online games (e.g., RETE-based rule matching). By first agreeing upon the interface, however, the games industry can then let the middleware providers compete on specific solutions.

[3.] The JSR-4 RBS interface is a good foundation, but will likely need to be extended to support game Artificial Intelligence.

Within the RBS working group, we discussed what interface extensions to the JSR-94 will we likely need to support in an RBS API proposal. Specific dicsussions included:

[4.] Caveats with using rule-based systems with game Artificial Intelligence.

Within the RBS working group, we identified a number of issues that developers and middleware implementers will need to consider and address long-term in the game Artificial Intelligence domain:

Towards an Interface Specification

This year at the 2005 Game Developer Conference we discussed porting the JSR-94 Java interface into C++. We're waiting upon resolution of the group discussion upon the right use of C vs. C++ within the standard group interface (e.g. maximize portability between console and PC games).

We discussed the minimal demands of the JSR-94 interface. On the one hand this enhances the potential for broad adoption in the industry. On the other hand a thin interface also means that there are likely to be few "game-specific" features in the final specification. However, given the broad range of games, platforms, and rule-uses, we felt that it is better to "keep it stupid simple" and aim for a broader adoption.

We also discussed the differences and preferences of game developers towards "stateless" or "stateful" interactions with RBSs. With stateless interaction the rule engine can be used as a way to implement a function or a service. You call it, passing parameters to it. It returns a result as an object. The rule engine doesn’t keep any knowledge of previous calls (statelessness). With a stateful interaction the rule engine permits a client to have a prolonged interaction with a rule engine within a single session. Input objects can be progressively added to the session and output objects can be queried repeatedly. Based on the GDC discussion, we concluded that both interaction models (which JSR-94 supports) should be supported.

To illustrate the simplicity of an AIISC interface based on the JSR-94 pattern, we also discussed a number of minimal examples of how a game engine would interact with the RBS via a JSR-94 interface, e.g. (Note the example below is Java):

// Get the rule service provider from RuleServiceProvider manager. 
RuleServiceProvider serviceProvider = RuleServiceProviderManager.getRuleServiceProvider(RULE_SERVICE_PROVIDER ); 
 
 
// Obtain runtime instance from provider 
RuleRuntime ruleRuntime = serviceProvider.getRuleRuntime(); 
 
 
// create a StatelessRuleSession from runtime 
StatelessRuleSession statelessRuleSession =  
(StatelessRuleSession) ruleRuntime.createRuleSession(uri,
new HashMap(), RuleRuntime.STATELESS_SESSION_TYPE);
 
 
// Create a input list/ Populate it 
List input = new ArrayList(); input.add(inputCustomer); input.add(inputInvoice); //… 
 
 
// Execute the rules without a filter. 
List results = statelessRuleSession.executeRules(input); 
 
// Obtain results – Iterator interface 
Iterator itr = results.iterator(); 
while(itr.hasNext()) { 
      object obj = itr.next(); 
      // Do something 
      
}

Again to reinforce the simplicity of the JSR-94 interface, we also discussed (Java) UML class diagrams (below). Note that approximately 1/2 of the classes defined here are Exceptions - emphasizing the simplicity of the core classes.
(click on images for a larger version)

Components of rule-based systems. Components of rule-based systems.

RBS Introduction

Rule-based systems differ from standard procedural or object-oriented programs in that there is no clear order in which code executes. Instead, the knowledge of the expert is captured in a set of rules, each of which encodes a small piece of the expert's knowledge.

Each rule has a left hand side and a ride hand side. The left hand side contains information about certain facts and objects which must be true in order for the rule to potentially fire (that is, execute).

Any rules whose left hand sides match in this manner at a given time are placed on an agenda. One of the rules on the agenda is picked (there is no way of predicting which one), and its right hand side is executed, and then it is removed from the agenda. The agenda is then updated (generally using a special algorithm called the RETE algorithm), and a new rules is picked to execute. This continues until there are no more rules on the agenda.

Rule-based Systems Components

Rule-based systems consist of a set of rules, a working memory and an inference engine. The rules encode domain knowledge as simple condition-action pairs. The working memory initially represents the input to the system, but the actions that occur when rules are fired can cause the state of working memory to change. The inference engine must have a conflict resolution strategy to handle cases where more than one rule is eligible to fire.

A rule-based system consists of:

The inference mechanisms that can be used by inference engines are:

Discussion: Game-AI Behavior as Rules or Not?

One of the most significant problems in NPC behavior control construction is that procedural programming languages such as C, C++ and Java that are typically used in the implementation of computer games are not suitable for implementing large sets of complex behavioral rules. Attempting to construct complex behavioral rules in a language such as C++ tends to result in an impenetrable code involving large numbers of if-then-else constructs, switch, case and loop statements. The programmer is responsible not only for defining the conditions under which a behavioral rule is to be applied, and the action to be taken when it does apply, but must also deal with deciding all of the circumstances under which to check the game state against the behavioral rule’s pre-conditions. Many of the behavioral rules required for game play will interact with one another in ways which cannot easily be determined a-priori. A game continuously changes during development, and having an easily adaptable system for changing/adding/removing rules is of significant benefit.

In general, the result of attempting to construct complex NPC behavior using procedural programming techniques will be complex code which is incomprehensible and difficult to maintain, leading to an unavoidable increase in development time and requirements for large memory space and processing power. A Rule-based System enables a more flexible, scalable, robust way to design such behavior. The reasons are grounded in pragmatics, of scalability, of usability, and of logic expressiveness.

Programming game AI using rules can be more pragmatic than scripting because it separates implementation from the logic of the behavior. This can lead to more maintainable engineering and code. Furthermore, a rule-based representation can provide a more concise and direct relationship between specification and implementation that would simplify testing. Separating the game engine from the game rules allows independent simulation and testing of each. Separating the logic from the implementation also enables reasoning about the logic by itself:

The earlier sections illustrate some of the possible application for AI in game in general and RBS in particular. These are the creation of interesting opponents, realistic and engaging NPCs and maintaining consistency in dynamic storylines.

To help in making the game immersive and allow suspension of disbelief, the creation of the NPCs must provide different types of behavior. Two categories of generic behavior in NPCs are commonly used: reactionary and spontaneous.

NPCs behave in a reactionary manner whenever they are responding to a change in their environment. If an enemy spots you and starts to run towards you and shoot, then they have acted as a reaction to seeing you.

NPCs behave in a spontaneous manner when they perform an action that is not based on any change in their environment. A NPC that decides to move from his standing guard post to a walking sentry around the base has made a spontaneous action.

SOAR-BOT Example

Example: SOAR-Quake, courtesy of J. Laird.

SOAR-BOT example. 
IF  enemy visible and my health is < very-low-health-value (20%)
OR
his weapon is much better than mine
THEN propose retreat

RBS Programming

Rule-Based programming is based on a simple model of computation in which knowledge is encoded in the form of sets of condition-action pairs known as production rules. The condition part of a production rule represents the pattern which must be matched in order for the rule to be applied, and the action part of the production rule represents the response that is to be made when the rule is applied. In a game application, the condition part of the production rule might involve interrogating the current state of the game, using virtual sensors and the action part of the rule might involve some response to the game state, effected via virtual actuators. Rules might also embody intelligent behavioral knowledge at a much higher level, involving planning actions to enable a game agent to achieve high level strategic goals, for example.

Many rule-based programming languages have been implemented, such as OPS5, CLIPS, Jess or RC++, for use in a large number of intelligent systems applications, including Expert Systems and Intelligent Software Agents.

A program written in a rule-based programming language is executed by using a working memory of assertions about the state of the world within which the program is operating, and an interpreter, which matches rules to the working memory, and adds to and removes assertions in response to the actions undertaken by rules that have been executed. A program expressed as a set of production rules is entirely declarative; production rules embody no procedural knowledge. It is the responsibility of the interpreter to control the execution of the rules. This is one of the principal advantages of rule-based programming. The programmer can concentrate on producing a discrete body of rule logic, separated from other aspects of the system, by writing a set of modular rules that are easily understood, easily extended, and easily modified.

Interface with the Game World

An important aspect of the architecture of the RBS is the interface with the game world and how they should be integrated. The world interface is still at a specification stage. However the components proposed in the current report, such as events, actions and sensors are the main information required from the RBS to enable the NPCs to have the appropriate behavior and interact with the world in a suitable way. The details of the integration are of course very dependent on what the final world interface will look like.

Research Extensions to Rule-based Systems

Rule-based systems support formalisms with different level of expressiveness. Examples of these include:

All of these can be used to provide better AIs, e.g., you can imagine a bot that hides when it is being shot at. Then it waits for five seconds before trying to shoot back if there is no other shooting and no incoming noise.

RETE Algorithm

The RETE Algorithm is widely used in commercial RBS implementations - it is regarded as the most efficient algorithm for optimizing mainstream commercial RBS systems. Because of its importance we introduce it here. However, as we have discussed within the working group, the RETE algorithm may not be optimal for game AI applications. We highlight this particular concern by this discussion, as it has been a recurring topic of discussion over the past year.

The efficiency of the RETE algorithm is asymptotically independent of the number of rules. Although a number algorithms implementing production rules have been considered, based on actual, empirical evidence, the RETE Algorithm is orders of magnitude faster than all published algorithms with the exception of TREAT algorithm. RETE is usually several times faster than TREAT for small numbers of rules with RETE's performance becoming increasingly dominant as the number of rules increases.

The typical RBS has a fixed set of rules while the knowledge base changes continuously. However, it is an empirical fact that, in most RBSs, much of the knowledge base is also fairly fixed from one rule operation to the next. Although new facts arrive and old ones are removed at all times, the percentage of facts that change per unit time is generally fairly small. For this reason, the obvious implementation for an RBS architecture is very inefficient. The obvious implementation would be to keep a list of the rules and continuously cycle through the list, checking each one's left-hand-side (LHS) against the knowledge base and executing the right-hand-side (RHS) of any rules that apply. This is inefficient because most of the tests made on each cycle will have the same results as on the previous iteration. However, since the knowledge base is stable, most of the tests will be repeated. You might call this the rules finding facts approach and its computational complexity is exponential.

A very efficient method known is the RETE algorithm. It became the basis for a whole generation of fast expert system shells: OPS5, its descendant ART, RETE++, CLIPS, JESS, and ILOG-Rules.

For more information on RETE see:

Specification

The aim is to propose a general game AI engine organized around the components mentioned in the RBS definitions section. This should make the implementation of NPCs easier by providing a suitable interface with the game-world, a common inference engine and different knowledge base suitable for a large variety of games.

A summary of RBS components is below with possible choices:

Knowledge Representation

Inference Algorithm

System Architecture

RBS Game AI Cycle

The diagram below shows the "thinking" process.

Thinking process of rule-based systems.

Group Members

Current members of the working group on rule-based systems:

Appendix A: Concepts and Terminology

Blackboard architecture
A Blackboard Architecture is an AI solution where Knowledge for a domain is shared between numerous KS (Knowledge Sources). Each KS represents an expert bringing its own set of knowledge to the blackboard and uses the knowledge published through the blackboard to build assumptions, make deductions etc.
Condition-action rule
A condition-action rule, also called a production or production rule, is a rule of the form: if condition then action.

The condition may be a compound one using connectives like and, or, and not. The action, too, may be compound. The action can affect the value of working memory variables, or take some real world action, or potentially do other things, including stopping the production system. See also inference engine.

Conflict resolution
Conflict resolution in a forward-chaining inference engine decides which of several rules that could be fired (because their condition part matches the contents of working memory should actually be fired.

Conflict resolution proceeds by sorting the rules into some order, and then using the rule that is first in that particular ordering. There are quite a number of possible orderings that could be used.

Frames
Frames are a knowledge representation technique. They resemble an extended form of record (as in Pascal and Modula-2) or struct (using C terminology) or class (in Java) in that they have a number of slots which are like fields in a record or struct, or variable in a class. Unlike a record/struct/class, it is possible to add slots to a frame dynamically (i.e., while the program is executing) and the contents of the slot need not be a simple value. There may be a demon present to help compute a value for the slot.

Demons in frames differ from methods in a Java class in that a demon is associated with a particular slot, whereas a Java method is not so linked to a particular variable.

Heuristic
A heuristic is a fancy name for a "rule of thumb" - a rule or approach that doesn't always work or doesn't always produce completely optimal results, but which goes some way towards solving a particularly difficult problem for which no optimal or perfect solution is available.
Inference engine
A rule-based system requires some kind of program to manipulate the rules - for example to decide which ones are ready to fire (i.e., which ones have conditions that match the contents of working memory). The program that does this is called an inference engine, because in many rule-based systems, the task of the system is to infer something, e.g., a diagnosis, from the data using the rules. See also match-resolve-act cycle.
Knowledge base
Collection of the data and rules that suitably represent the problem domain.
Match-Resolve-Act cycle
The match-resolve-act cycle is the algorithm performed by a forward-chaining inference engine. It can be expressed as follows:

loop

  1. match all condition parts of condition-action rules against working memory and collect all the rules that match;
  2. if more than one match, resolve which to use;
  3. perform the action for the chosen rule until action is STOP or no conditions match.

Step 2 is called "conflict resolution". There are a number of conflict resolution strategies.

RETE
Algorithm used to optimize forward chaining inference engines by optimizing time involved in recomputing a conflict set once a rule is fired.
Rule-based system
A rule-based system is one based on condition-action rules.
Search
Search is a prevalent metaphor in artificial intelligence. Many types of problems that do not immediately present themselves as requiring search can be transformed into search problems. An example is problem solving, which can be viewed in many cases as search a state space, using operators to move from one state to the next.

Particular kinds of search are breadth-first search, depth-first search, and best-first search.

Working memory
The working memory of a rule-based system is a store of information used by the system to decide which of the condition-action rules is able to be fired. The contents of the working memory when the system was started up would normally include the input data - e.g., the patient's symptoms and signs in the case of a medical diagnosis system. Subsequently, the working memory might be used to store intermediate conclusions and any other information inferred by the system from the data (using the condition-action rules).

Appendix B: Online References

Links

Navigation: Overview >> Working Group on Rule-based Systems