Natural Behavior Planning for Autonomous Agents in Dense Environments

COMP 790-058: Robot Motion Planning

Course Project    Yu Tao

PROJECT PRESENTATION

│

Proposal

│

Final Report

│

Final Presentation

•	Introduction

Crowd simulation have applications not only in entertainment industry including movie, game but also in many other areas including transportation research, military and architecture. Typically many methods on crowd simulation fall into the agent-based category where the motion of each agent is computed individually. Agent-based method is able to generate heterogeneous crowd where each agent may have unique goal and make independent decision. Such method generally can be divided into 3 parts: global path planning, local collision avoidance and human behavior. In this project we intend to mostly focus on the third part on the basis of some existing multi-agent navigation method [1].

Human beings always perform appropriate behavior according to surrounding environment and their own status. Given the environmental information (including the situation, nearby agent status) and the agent configuration state (position, orientation, etc.) determined by navigation algorithm, we can build a model to plan the behavior for each simulated agent. Here the behavior planning is further divided into two levels: high level action which is more like semantic description and specific motion executed by articulated body. The high level action can be determined according to current situation and environment by variable models ranging from social psychology model to rule based model. Existing Mocap data is a promising source for the low level part of planned behavior. The synthesis of actual motion performed by character should satisfy given constraints. Particularly in dense environment the interaction among agents becomes more challenging issue on both parts of behavior planning.

•	Related work

Manfred Lau and James Kuffner [2][3] have done some work on behavior modeling and planning for multiple virtual agents. Their planner searches in behavior FSM for appropriate behavior which the agent can perform to achieve desired goal ultimately. However the output behavior sequences do not account for agent interaction and may not applicable to dense environment.

Some recent works employ empirical data or examples observed in real world to build the behavior model [4][5].

Pelechano et al. [6] builds a HiDAC (High-Density Autonomous Crowds) system addresses the problem of simulating high-density crowds of autonomous agents moving in a natural manner in dynamically changing virtual environments.

Motion graph proves to be effective in synthesizing realistic motion continuously for single character. The similar idea also works in crowd simulation according to Mankyu et al[7]. In their work, a fast path planner based on probabilistic roadmaps is used to navigate characters through complex environments while motion graph is constructed to represent the space of possible actions and search algorithms is used to generate motion.

•

Goals

1. The human motion generated for the agent should be visually appealing and natural-looking. By natural-looking it means the character animation created for the agents not only is realistic (no foot-skating, joint-flipping etc.) but also conforms to normal behaviors human beings usually perform under simulated scenarios.

2. Especially in dense crowd simulation the interaction between agents might be of more importance when viewer watching the simulation.

3. The motion synthesis process can be realized in real time or at least with reasonable frame rate if delay in motion synthesis occurs during simulation.

•

Reference

[1] Reciprocal Velocity Obstacles for Real-Time Multi-Agent Planning. Jur van den Berg, Ming Lin, Dinesh Manocha. Technical Report, Department of Computer Science, UNC

[2] Precomputed search trees: Planning for interactive goal-driven animation. M. Lau and J.J. Kuffner. SCA 2006

[3] Behavior planning for character animation. M. Lau and J. Kuffner. SCA 2005

[4] Crowds by Example. Alon Lerner and Yiorgos Chrysanthou and Dani Lischinski. Eurographics 2007

[5] Group Behavior from Video: A Data-driven Approach to Crowd Simulation. Kang Hoon Lee, Myung Geol Choi, Qyoun Hong and Jehee Lee, SCA 2007.

[6] Controlling Individual Agents in High-Density Crowd Simulation. N. Pelechano, J.M. Allbeck and N.I. Badler. SCA 2007

[7] Fast and Accurate Goal-Directed Motion Synthesis for Crowds. Mankyu Sung, Locas Kovar, and Michael Gleicher. SCA 2005.