Behavior Simulation for Autonomous Agents in Crowded Environment
Tao Yu
Department of Computer Science
Abstract
In this report we present an approach for simulating natural behavior of individual agent in crowded environment. These agents are autonomous in the sense that they have the ability to navigate around the environment in a life-like and improvisational manner. To generate natural agent motion a hierarchical behavior model is used to determine the action and configuration for the agents at runtime. During each simulation step high level behavior for every agent is determined by a behavior planner based on sensed environment information. The planned behavior is realized by a behavior steering method which is capable of composing the low-level behaviors and generating smooth collision-free path. Given an individual goal for each agent, realistic crowd motion is formed as the composition of natural behaviors of each agent.
1. Introduction
Human beings are arguably the most complex known creatures, therefore their behaviors are also the most complex ones to simulate. Especially when simulating the densely populated environment the interactions between people increase the complexity of behavior simulation substantially. To address this issue we adopt a similar hierarchical behavior model proposed by Reynolds [1]. The behavior of an autonomous character can be divided into three layers: action selection, steering, and locomotion (Figure 1).
Figure 1: A hierarchy of autonomous agent behaviors [1]
In this behavior model the autonomous characters are procedurally driven by a control program which maps the environment into characters＊ actions. We assume individual agent has high-level spatial information of the environment, i.e. a pre-computed roadmap providing macroscopic, global connectivity information and serving as a way-finding aid to guide agent to its goal. The spatial information combined with dynamic environment properties such as crowd density and flow velocity is then used as the basis to determine High-level behavior by behavior planner. Then the local situation, such as the configuration of static or dynamic obstacles, nearby agents, is taken into account to plan the second level behaviors which deal with collision avoidance and return smooth and valid motion path while keeping agents confined to the planned high-level behavior.
Finally the third level behavior is implemented by taking the generated path as control signal to animate the articulated human model in locomotion. The input path includes the position, velocity and type of the agent locomotion given specified time instances thru the simulation. The target of the third level behavior implementation is visually-plausible and physically-viable local of articulated humanoid figure which is deformed with many Degree-of-Freedoms. We can use a simple locomotion model which consists of pre-animated motion segment of different locomotion types. While the action required by current high-level behavior changes as the simulation proceeds, agents switch among corresponding the motion segments which are selected or blended together. Assuming the path and locomotion specification resulting from the first two high-level behaviors are smooth and natural, visualization of the simulation can be realized so that agents are animated with high-quality human motion while exhibiting reasonable and realistic individual behavior.
In this project we focus on behavior simulation, i.e. the first two levels in the hierarchical behavior model. Locomotion generation is left as stand-alone problem and touched only slightly.
2. Simulation Overview
In our approach the simulation process is divided into three phases: environment sensing, behavior planning, behavior steering. This simulation scheme is depicted in Figure 2. In real world human beings normally sense surrounding environment, make decision on behavior, then take action accordingly to complete a behavior-performing cycle. Therefore the proposed scheme models human behavior in a way similar to how humans act in real world. In every simulation step these three phases are executed sequentially.
Updated agent
configuration
Figure 2: Simulation scheme overview. Autonomous agents follow this simulation scheme
Environment sensing: This phase computes the crowd density and flow velocity which are modeled as scalar field and vector field respectively. Given a specific location these two fields estimate the crowd density and average crowd flow velocity there.
Behavior planning: Taking the crowd density and flow speed as input as well as the pre-computed roadmap as well as global path planned at runtime, high-level behavior is planned to determine the action to take in next simulation step. Additionally the preferred locomotion velocity for selected action is computed too.
Behavior steering: With the action specified by behavior planning phase, this phase aims at updating the motion configurations including path (position, velocity), motion type. The output is subject to constraints posed by the input action and collision-free property, which can be achieved through combination of steering behaviors [1] and RVO [2].
3. Hierarchical Behavior Simulation
The simulation process can broke down into 3 phases that can be analogous to the steps humans usually take to perform appropriate behaviors when navigating the environment.
3.1 Environment sensing
Distribution of the agents in the environment is calculated as crowd density field. The crowd density at certain location is measured and used in calculation of the crowd flow velocity field. [3] also computes crowd density and speed field in their crowd model. In [3] each agent is converted into an individual density field which peaks at its location and falls off radially. The average velocity field is computed by dividing weighted sum of each agent＊s velocity with the sum of each individual＊s density field.
Our method employs a more straightforward approach to compute the density and velocity field. The agents in a circle with radius r centered at a specified location are sampled to calculate the crowd density and velocity. The density is proportional to the number of sampled agents and the velocity is measured as the average velocity of sampled agents.
3.2 Behavior planning
The high level behavior of an autonomous agent is formed as sequence of actions. When taking a certain action the agent is considered as in a distinct behavioral state. The set of actions forms a Finite State Machine (FSM), the nodes of which represent states where different choices are available. In our simulation scheme, the high level behavior model relies on a 3-node behavior Finite State Machine (Figure 3). Note that when taking congesting action agents would be stationary or move in a very slow pace (usually less than 1 step every second in average). An action selection algorithm is needed for making decision on whether to stay in current state or to transition to another state. Input to this algorithm is the information sensed in the environment, i.e. the crow flow density and velocity.
Figure 3: Behavior Finite State Machine adopted in our simulation. An agent can transition between any two of the three actions according to
Humans plan their actions according to surrounding world, e.g. when surrounding environment is densely packed and crow flow speed is very low people would slow down their movement generally. In this case they would switch to walking motion if running action is taken at that time. The planning process is governed by a set of behavior rules which take sensed environment information as input and can be formulated quantitatively as follows.
With the crowd density and flow velocity fields we can measure the predicted maximum speed of movement for each agent. This value is density dependent [3] and dynamically adjusted with crowd flow velocity:
- 老 < 老min
- 老min < 老 < 老max
- 老 > 老max
is the average
crowd flow speed measured at the position the agent would reach if it keeps
moving in current velocity.
The following behavior rules are specified to determine conditions under which state transitions should be made.
From Walking to Running: 老 < 老c
and ||fv|| > Vrun
From Walking to Congesting: 老 > 老c and ||fv||< Vwalk
From Running to Walking: 老 < 老c and ||fv||< Vrun
From Running to Congesting: 老 > 老c or ||fv||< Vwalk
From Congesting to Running: 老 < 老c and ||fv||> Vrun
From Congesting to Walking: 老 < 老c and ||fv||> Vwalk
3.3 Behavior Steering
With the action selected and potential maximum speed predicted, we use the steering behavior model [1] to make agents to move along paths that conform to planned action meanwhile preserve the collision-free property.
3.3.1 Steering Behavior Model
According to [1] steering behaviors can be completely independent of the specific locomotion scheme. But it is necessary to consider the kineodynamic constraints a virtual human model. This can be done by adjusting tuning parameters for a given locomotion scheme. In our simulation the simple vehicle model presented in [1] is adapted as an approximation to virtual human locomotion model. Specifically maximum speed and acceleration are enforced for the vehicle model. These constraints are not constant but can change in accordance with current high level behavior. For example, the kineodynamic constraints for walking action differ with those for running action.
3.3.2 Collision Avoidance Steering Behavior
Collision avoidance with other agents is realized as one of those steering behaviors in [1]. To implement this behavior, each agent determines potential collisions with other agents in neighborhood based on current velocities. The nearest of these potential collisions is determined and the character steers to avoid the site of predicted collision. The steering force is applied to make agent turn away laterally from the potential collision site. With this steering behavior agent only considers potential collision with smallest estimated collision time and steers laterally in attempt to avoid collision. Agent is still likely to collide with other agent in neighborhood even though it can avoid collision with agent showing largest threat.
This artifact can be eliminated by incorporating local navigation algorithm that enforces local collision avoidance. Here we use Reciprocal Velocity Obstacle (RVO) [2]. While assuming all neighboring agents would make the same effort to avoid collision, RVO realizes collision avoidance by predicting collision time with them and selecting velocity that minimize the possibility of collision with others. Steering force is calculated in accordance with the new optimal velocity computed by RVO. Specifically the steering direction is simply the difference between current velocity and desired velocity calculated by RVO. Note that this steering behavior would be combined with a path following steering behavior (See section 3.3.3) which tries to make agent maintain preferred velocity in the same direction of planned global path. Therefore when computing penalty for candidate new velocity, the component penalizing its deviation from preferred velocity is ruled out.
3.3.3 Combining Steering Behaviors
Basically there are two steering behaviors combined to generate path configuration for agents. One is path following behavior with the path pre-computed via global path planning. The other is RVO-based collision avoidance steering behavior. Furthermore the predicted maximum speed computed in previous phase is used to constrain the new velocity. Therefore the smoothness and collision-free properties are both ensured in this scheme.
4. Implementation
4.1 Global Path Planning
We use the same global path planning algorithm described in [2].
4.2 Space Discretization
The space is discretized into regular grid, with environment information defined within each grid cell. A list of agents that locate in it as well as the crowd density and velocity field value is stored in each grid cell. This space discretization serves as the basis for optimized locality query [4].
4.3 Simulation
The behavior model proposed here indicates that the "brain" of an autonomous character is a program that must be run to determine what actions to take based on its current environment [4]. The behavior planning part, however, does need to be called frequently according to common sense since human behavior changes in a relatively low rate. The final simulation step is given below:
5. Result and Conclusion
So far the new collision avoidance steering behavior using RVO has been implemented and experimented in OpenSteer which is an open source implementation of [1]. In the simulation 100 autonomous agents follow a path (the red line) and try not to collide with each other or two large spherical obstacles. A agent's direction is reversed when reaches the end of the path. The video is available here.
In this project a framework to simulate natural behavior of autonomous agents in crowded environment is proposed. Based on a hierarchical behavior model, smooth and natural motion representing appropriate behavior of agents in dense environment is output. To verify the effectiveness of the proposed simulation method, we need to integrate it with concrete humanoid animation model which associates pre-animated motion segments (mocap) to see whether high-quality human motion in crowd can be generated.
References
[1]
Reynolds, C. W. (1999) Steering Behaviors For Autonomous Characters, in the
proceedings of Game Developers Conference 1999 held in
[2] Jur van den Berg, Sachin Patil, Jason Sewall, Dinesh Manocha, Ming Lin "Interactive Navigation of Individual Agents in Crowded Environments" Technical Report, Department of Computer Science, UNC 2007
[3] TREUILLE, A., COOPER, S., AND POPOVIC, Z. 2006. Continuum crowds. Proc. Of ACM SIGGRAPH.
[4] Reynolds, C. W. (2000) Interaction with Groups of Autonomous Characters, in the proceedings of Game Developers Conference 2000, CMP Game Media Group (formerly: Miller Freeman Game Group), San Francisco, California, pages 449-460.