群体动力学的群组行为仿真

Group behavior simulation based on group dynamics

目的许多群体动画算法侧重从宏观或微观角度模拟人群运动,而结合两种方法模拟群组动态的算法较少,为解决这个问题,提出一种基于群体动力学的群组行为仿真算法。方法首先,采用连续模型构建动态势能场,为个体计算运动初始速度;然后,基于群体动力学模拟组内跟随和组间避让行为;在组内跟随行为中采用"Carfollowing"模型为个体计算跟随加速度;在组间避让行为中提出群组的凸包表示方法,并引入局部势能场;最后,结合动态势能场和局部势能场实现群组行为仿真。结果在每个仿真循环中动态更新全局势能场信息,对比不同群体规模及网格精度的人群仿真效率。实验结果表明本文算法能用于模拟规模较大的多样性群组运动。在网格分辨率为80×80像素的场景中对5 000个个体的运动进行仿真,平均帧速率为35.7 ms(约28帧/s),与传统的连续模型相比产生了更多的群组行为。采用快速行进法构建全局动态势能场,即使在粗糙网格中也能得到较为平滑的路径。结论提出算法适用于多样性群组行为仿真,同时结合全局规划和局部控制,无需额外碰撞检测便能真实地模拟组内跟随和组间避让行为,仿真效果具有高效性和多样性。

Objective The modeling of virtual crowds has been widely investigated in recent years. Two fundamental approa- ches are used to model human crowds. The first employs microcosmic methods and mainly includes agent-based, force- based, and rule-based models. In these models, each agent perceives environmental information and responses to static or dynamic obstacles on their own. Microscopic models are suitable for small crowds and provide flexibility. The second is ap- plicable in large-crowd simulations, treats the crowd as a whole, uses macroscopic methods, and mainly includes fluid dy- namics, continuum models, and potential fields. However, very few algorithms combine the two aforementioned models to simulate dynamic group behavior. Group dynamics, which has been extensively studied in social psychology, attempts to find the general rule of crowd movement by a dynamic analysis of group phenomenon. The founder of this concept, Kurt Lewin, considers that individual behavior is the result of personality characteristics and environmental influence. Recent re- searchers have proposed different theories to explain group behavior, but current simulation methods cannot generate believ- able and heterogeneous crowd simulation because of the separation of global planning and local motion. This study proposes a new method that combines global path planning and local motion control to simulate diverse group behavior. In particular, group dynamics is introduced into continuum crowd simulation to model the following behavior of intra-group and the avoid- ance behavior of inter-group. Method First, the environment is divided into a series of 2D grids, the target and obstacle grids are specified, the individuals are converted into unit density fields, and crowd flow constraint is introduced to calcu- late the maximum speed field. Second, the unit cost field is computed by minimizing a linear combination of the length of path, amount of time to the destination and discomfort degree per unit time along the path. Second, three lists, namely, known, unknown, and candidate lists, are established, and the target grid is stored into the known list. Finally, fast marc- hing method and upwind difference scheme are used to approximate the gradient for constructing a global potential field and providing each individual with an initial velocity. In the second phase, individuals are assigned into groups depending on their walking speeds, moving directions, and locations. Then, the divide-and-conquer algorithm is employed to construct group convex hull, and the group position is the average position of its edge members. Finally, the convex hull edge is ex- panded to a limited extent and local potential field is constructed by its swept space during a time step. In the local motion control phase, the global potential and local fields are integrated to generate group avoidance behavior and the individual lo- cal motion is adjusted to produce following behavior on the basis of following acceleration. Result After updating the global potential information at each time step, the crowd simulation results in different scale numbers of individuals and grid reso- lution are compared. Experimental results show that the proposed method can model large-scale crowd simulation in an effi- cient and diverse manner. For example, when simulating 5 000 individuals walking in a scenario with the grid resolution of 80 x 80, the average frame rate is 35.7 ms, which is approximately 28 frames per second. Compared with continuum model, the proposed method can produce more group behavior and in the high density area as individuals can dynamically avoid one another because they follow the leader to solve the local interaction. When constructing the global potential field, the fast marching method is influenced by the grid resolution but the coarse grid resolution can be used to compute smooth trajectories. At the same time, the proposed algorithm can generate considerable group behavior on the basis of group dy- namics. Conclusion Existing group behavior models employ additional collision avoidance methods to realize the local movement of a small crowd and thus may sometimes consider several special circumstances. This condition leads to unnec- essary computations. Our proposed method integrates local motion control into global path planning and is thus suitable for large-scale diverse crowd simulation. During the simulation process, the method can produce the following behavior of intra- group and the avoidance behavior of inter-group when using the continuum model. Therefore, the diverse crowd motion sim- ulation algorithm is efficient.