One objective of our research is to develop efficient techniques for simulating complex behaviors. In our research, we integrate adaptive roadmaps with traditional flocking techniques to generate complex global behaviors that are difficult to generate using traditional emergent approaches such as flocking. An adaptive roadmap is a roadmap (graph) containing representative paths in the environment whose edge values can be updated according to information gathered by the flock members.

We extend ideas from cognitive modeling, and embed behavior rules in individual flock members and in the nodes and edges of the roadmap. We find that the global information provided by our rule-based roadmaps improves the behavior of autonomous characters, and in particular, enables more sophisticated group behaviors than are possible using traditional (local) flocking methods. Key features of our approach include:

• The roadmap provides a convenient abstract representation of global information in complex environments.
• Adaptive roadmaps (e.g., modifying node and edge weights) enable communication between agents.
• Associating rules with roadmap nodes and edges enables local customization of behaviors.

The rule-based framework is designed to facilitate the creation of complex behavior rules. The rules given to an agent reflect the agent's behavior. The agent react to a variety of situations based on the state in the environment, nearby agents and other sensory input. The framework contains a hierarchy of general behavior rules that add upon the previous level to make the behavior more specified to a common goal, such as exploration. The framework makes use of dynamic group creation and management.

• The initial behavior rule contains only the most basic functionality and structure that is unrelated to the purpose of the behavior.
• Each of the level in the hierarchy adds structure and functionality to the previous level, which is common to the particular category of the behavior.
• General behavior rules also provide a general algorithm for the execution of the behaviors of that category.
• Individual behaviors implement the specific details to the general algorithm in the previous level to make decisions for the action of the agents.
• The hierarchy can be extended to encompass new categories of behaviors.

An integral part of the rule-based framework is the capability to dynamically create and manage groups and subgroups of agents. For example, a subgroup may be formed among agents in a group that are carrying out a cooperative task in the same local area of the environment. Furthermore, groups may be used for other purposes besides specifying the particular behavior of its member agents. It is possible to create groups for other purposes, such as if a location in the environment provides a specific effect on the agents within that location, or to keep track of a set of representatives from the various behavioral groups.

Each group will keep track of several key bits of information. These include their parent group, any subgroups created, and the members of the group. Agents may be added and removed from existing subgroups as needed, based on the groups specific criteria for modifing its subgroups. The subgroups can be created and removed at any time.

The agents in our simulations have several ways to take advantage of the framework that we provide. The agents are able to use the shared information provided from the behavior, such as the manner in which the agents communicate or create and manage a memory of other agents that have been encountered. The agents can also take advantage of the grouping that the behaviors use. For example, a more general behavior can provide the ability to divide the a behavior's group into subgroups of individual agents, and thus provide each agent the option to have a local version of the roadmap. Then, a more specialized behaviors can specify how the agents in different subgroups communicate with each other, enabling the use of a global version of the behavior's roadmap.

Our composable framework is designed to decide between several basic actions, based on past actions and the location in the environment. The performance value of each of the actions will vary as the agents proceed throughout the simulation, so the framework also provides a means for learning. Agents will alter their actions, performance values and behavior preference as they proceed through the simulation. In this way we want to eventually allow a means of learning for the agent.

Composable Framework
We have looked at a composable framework where agents will adapt their behaviors throughout a simulation. The adaptation of behaviors is based on what has been encountered throughout the simulation and information provided by other cooperative agents. This framework is built on top of a roadmap based system.

• In addition to representing the connectivity of the feasible space in a given environment, the roadmap also functions as an internal representation of the world for agents.
• Agents can modify the properties of the roadmap.
• An agent can store location-specific information, such as the action that the agent takes, in a node of a roadmap.
• The result of an action will be evaluated by a user-defined utility function. The agent will select an action based on the past performances of the available actions.
• The learned information can also be shared between agents when their relative states allow communication (e.g. proximity and other values).

More information on this technique can be found at the composable page.

Behavior Selection
The simplest method of handling multiple behaviors is to simply select one behavior to employ at a given time. The selection-base approach that we employ here decides which behavior should be active based upon the current state of the agent or group of agents.

Path Modification
Many of the behaviors we create find a path in the roadmap for an agent to follow. The path modification algorithm modifies the output paths from one behavior with respect to the constraints from other behaviors. In particular, this behavior blender combines the path obtained from one behavior (the main behavior) with constraints from other sub-behaviors to create an action for an agent that attempts to satisfy a number of its goals. The combination done will alter or deform the paths the agents are following.

Examples of where we have employed these behavior combining techiques can be seen in some of our pursuit evasion scenarios.

The idea of scalability of the group size is always a concern with any implemenation of group behaviors. Currently, our frameworks consider complex behaviors of agents on a mostly small scale. However, it is our intention to expand the capabilties of the behaviors and grouping to extend to much larger number of agents. Of particular interest is the simulation and control of large crowds, such as for testing evacuation procedures at a large event.