大规模群体运动的实时模拟研究与实现
|
摘要
鸟群、鱼群和人群等集群运动是自然界最美丽也最常见的景象之一。但是这些复杂的集群运动在计算机动画领域却不多见。近几十年来,由于影视动画、虚拟现实和计算机游戏等领域的不断发展,群体动画也成为人们研究的热点方向。尤其是对大量人群聚集的实时交互性行为的研究,在虚拟训练、安全预演、数字游戏等领域都得到了广泛的应用。它通过探索真实世界中群体行为的物理本质和生物学、社会学特性,利用计算机为生物体建立行为模型,从而更加逼真的表现生物体的群体行为。与典型的计算机动画建模只关注角色外形和物理性质相比,基于智能体角色的行为动画专注于角色行为的建模,处理角色的行为和运动细节。这些行为包括了从低级的路径规划到高级的情感交互等行为。但是由于群体中个体行为的复杂性和多样性,大规模群体中对每个个体的行为控制带来的计算量巨大,难以满足实时模拟的应用需求。本文以万人级大规模群体为研究对象,试图在群体行为模拟的真实感和效率之间寻求一个良好的平衡点。
本文展示了具有代表性的群体行为模型,包括粒子系统、集群系统、行为系统、混合系统、混乱模型等行为模型和认知模型;介绍了角色动画系统的架构,并说明了群体动画子系统的框架以及在整个系统中所处的地位;提出了群体动画建模方法,并在此基础上实现了万人级群体运动实时模拟,展现了真实感的群体行为,包括路径规划、碰撞避免、运动跟随等。
一课题的研究着重集中在以下两个方面:
第一,对群体动画模拟方法作出了全面的研究和透彻的分析,在此基础上提出了一种基于行为模型的大规模群体实时模拟框架。这种框架具有分层结构,信息在层级之间共享具有较高的效率。并且其固有的有限逻辑顺序,大大减少了行为之间的矛盾。
第二,针对万人级群体动画的核心问题,提出了一种基于动态场景的局部路径规划改进算法。这种改进的享有全局知识的动态局部路径规划算法,既能够提供类似全局规划的最优路径,又具有基于局部知识动态更新的高效性,且统一规划,免去为每个个体单独计算的开销,有效地减少了计算量,提高了计算效率。
The aggregate motion of a flock of birds, a herd of land animals, or a school of fish is a beautiful and familiar part of the natural world. But this type of complex motion is rarely seen in computer animation. In recent decades, due to the continuous development of the field such as film, television, animation, virtual reality and computer games, crowd animation has become a hot research field. Especially the research about behaviors while large crowds interactive in real-time, have been widely used in the field of training systems, safety science, computer games and so on. It does this by exploring the physical, biology and sociology nature of crowd behavior in the real world, and the use of computer to establish models, and thus making the behavior of the crowds more realistic. Agent-based behavioral animation focus on the behavior modeling, handing details of behaviors and movements, Compared with typical computer animation modeling which only concerned with the appearance of characters and physical properties. These behaviors include low-level path planning, high-level emotional interaction and so on. However, due to the complexity and diversity of individual behavior in crowds, control of each individual in crowds brings expensive computation, so it’s difficult to meet the real-time simulation applications. This paper, as study thousands of individuals, is attempted to find a good balance between realism and efficiency of crowd behavior simulation.
It shows some representative crowd behavior models, including particle system, flocking system, behavior system, hybrid system, chaos system, cognitive model and so on; describes the architecture of character animation system, the framework of crowd animation sub-system and its position in the whole system; presents a method of crowd animation modeling, and on the basis to implement a large crowd simulation in real-time, which displays the realistic crowd behavior, including path planning, collision avoidance, and path following.
The study focuses on the following two aspects:
First, making a comprehensive research and thorough analysis with the method of crowd simulation, and proposing a framework of large-scale crowd real-time simulation base on behavior model. Such a framework has a hierarchical structure, and information sharing between levels with high efficiency. And its inherent limited logical sequence has greatly reduces the contradiction between behaviors.
Second, for the core issue of large crowd animation, this paper presents an improved algorithm of local path planning based on dynamic environment, improves dynamic local path planning algorithm with global knowledge, provides the optimal path similar to global planning, but also has efficiency according to dynamically updated based on local knowledge, and unified planning, replacing the cost of calculating separately for each individual, effectively reducing the computation and improve the computation efficiency.
本文展示了具有代表性的群体行为模型,包括粒子系统、集群系统、行为系统、混合系统、混乱模型等行为模型和认知模型;介绍了角色动画系统的架构,并说明了群体动画子系统的框架以及在整个系统中所处的地位;提出了群体动画建模方法,并在此基础上实现了万人级群体运动实时模拟,展现了真实感的群体行为,包括路径规划、碰撞避免、运动跟随等。
一课题的研究着重集中在以下两个方面:
第一,对群体动画模拟方法作出了全面的研究和透彻的分析,在此基础上提出了一种基于行为模型的大规模群体实时模拟框架。这种框架具有分层结构,信息在层级之间共享具有较高的效率。并且其固有的有限逻辑顺序,大大减少了行为之间的矛盾。
第二,针对万人级群体动画的核心问题,提出了一种基于动态场景的局部路径规划改进算法。这种改进的享有全局知识的动态局部路径规划算法,既能够提供类似全局规划的最优路径,又具有基于局部知识动态更新的高效性,且统一规划,免去为每个个体单独计算的开销,有效地减少了计算量,提高了计算效率。
The aggregate motion of a flock of birds, a herd of land animals, or a school of fish is a beautiful and familiar part of the natural world. But this type of complex motion is rarely seen in computer animation. In recent decades, due to the continuous development of the field such as film, television, animation, virtual reality and computer games, crowd animation has become a hot research field. Especially the research about behaviors while large crowds interactive in real-time, have been widely used in the field of training systems, safety science, computer games and so on. It does this by exploring the physical, biology and sociology nature of crowd behavior in the real world, and the use of computer to establish models, and thus making the behavior of the crowds more realistic. Agent-based behavioral animation focus on the behavior modeling, handing details of behaviors and movements, Compared with typical computer animation modeling which only concerned with the appearance of characters and physical properties. These behaviors include low-level path planning, high-level emotional interaction and so on. However, due to the complexity and diversity of individual behavior in crowds, control of each individual in crowds brings expensive computation, so it’s difficult to meet the real-time simulation applications. This paper, as study thousands of individuals, is attempted to find a good balance between realism and efficiency of crowd behavior simulation.
It shows some representative crowd behavior models, including particle system, flocking system, behavior system, hybrid system, chaos system, cognitive model and so on; describes the architecture of character animation system, the framework of crowd animation sub-system and its position in the whole system; presents a method of crowd animation modeling, and on the basis to implement a large crowd simulation in real-time, which displays the realistic crowd behavior, including path planning, collision avoidance, and path following.
The study focuses on the following two aspects:
First, making a comprehensive research and thorough analysis with the method of crowd simulation, and proposing a framework of large-scale crowd real-time simulation base on behavior model. Such a framework has a hierarchical structure, and information sharing between levels with high efficiency. And its inherent limited logical sequence has greatly reduces the contradiction between behaviors.
Second, for the core issue of large crowd animation, this paper presents an improved algorithm of local path planning based on dynamic environment, improves dynamic local path planning algorithm with global knowledge, provides the optimal path similar to global planning, but also has efficiency according to dynamically updated based on local knowledge, and unified planning, replacing the cost of calculating separately for each individual, effectively reducing the computation and improve the computation efficiency.
引文
[1] Rome: Total War, 2004. Game homepage, http://www.totalwar.com.
[2] The Lord of the Rings, The Battle for Middle Earth, 2004. Game homepage, http://www.eagames.com/pccd/lotr bfme.
[3] Thompson P.,Marchant E.: A computer-model for the evacuation of large building population. Fire Safety Journal24,2(1995),131-148.1,3.
[4] Hareesh P.: Evacuation simulation: Visualisation using virtual humans in a distributed multi-user immersive VR system. In Proc. VSMM‘00(2000).
[5] KLUPFEL H., MEYER-KONIG M., WAHLEJ., SCHRECKENBERG M.: Microscopicsimulation of evacuation processes on passenger ships. In Theoretical and Practical Issues on Cellular Automata (2000), Bandini S.,Worsch T., (Eds.), Springer, London, pp. 63–71.3
[6] OWEN M., GALEA E. R., LAWRENCE P. J., FILIPPIDIS L.: The numerical simulation of aircraft evacuation and its application to aircraft design and certification. The Aeronautical Journal 102, 1016 (1998), 301–312.
[7] ROBBINS C.: Computer simulation of crowd behaviour and evacuation. ECMI Newsletter, 25 (March 1999).
[8] Simulex, 2004. evacuation modeling software, product information, http://www.ies4d.com.
[9] WILLIAMS J.: A Simulation Environment to Support Training for Large Scale Command and Control Tasks. PhD thesis, University of Leeds, 1995.
[10]MCPHAIL C., POWERS W., TUCKER C.: Simulating individual and collective actions in temporary gatherings. Social Science Computer Review 10, 1 (Spring 1992), 1–28.
[11]POWERS W. T.: The Control of Perception. Aldine, Chicago, 1973.
[12]TAKAHASHI T. S. H.: Behavior simulation by network model. Memoirs of Kougakuin University, 73 (1992), 213–220.
[13]HELBING D., FARKAS I., VICSEK T.: Simulating dynamical features of escape panic. Nature 407 (2000), 487–490.
[14]HOSOI M., ISHIJIMA S., KOJIMA A.: Dynamical model of a pedestrian in a crowd. In Proc. IEEE International Workshop on Robot and Human Communication’96 (1996).
[15]SAIWAKI N., KOMATSU T., NISHIDA S.: Automatic generation of moving crowds in the virtual environments. In Proc. AMCP’98 (1998).
[16]Reynolds C. W.: Flocks, herds, and schools: A distributed behavioral model. In Computer Graphics (ACM SIGGRAPH’87 Conference Proceedings) (Anaheim, CA, USA, 1987), Vol. 21, ACM,pp. 25–34)
[17]Tu,X. -Y. and Terzopoulos,D.: Artificial fishes: Physics,locomotion,perception,behavior. In Proceedings of SIGGRAPH 94,Computer Graphics Proceedings,Annual Conference Series,43-50,1994.
[18]Brogan D., Hodgins J.: Group behaviors for systems with significantdynamics. Autonomous Robots 4 (1997), 137–153.
[19]Musse S. R., Thalmann D.: A hierarchical model for realtime simulation of virtual human crowds. IEEE Transactions on Visualization and Computer Graphics 7, 2 (April-June 2001),152–164.
[20]纪庆革,潘志庚,梅林,杨世琦,李祥晨.团体操虚拟编排和演练原型系统.计算机辅助设计与图形学学报,2004 16(9).
[21]J. Funge. Making Them Behave: Cognitive Models for Computer Animation. PhD thesis, Graduate Department of Computer Science, University of Toronto, 1998.
[22]J. Funge. Cognitive modeling for games and animation. Communications of the ACM, 43(7):41-48, 2000.
[23]J. Funge, X. Tu, and D. Terzopoulos. Cognitive modeling: Knowledge, reasoning and planning for intelligent characters. ACM Computer Graphics (Proceedings of SIGGRAPH'99), pages 29-38, 1999.
[24]S. Shanbhag. Behavioral animation : A report. In Proceedings of the Inter Research Institute Student Seminar in Computer Science (IRISS'02),2002.
[25]A. Stentz, Optimal and efficient path planning for partially-known environments, in Proc. IEEE Int. Conf. Robot. Autom., 1994,pp. 3310–3317
[26]C. W. Reynolds. Steering behaviors for autonomos characters. In Proceedings of Game Developers Conference, pages 763{782, San Jose, California,1999.
[27]R. Millar, J. Hanna, and S. Kealy. A review of behavioural animation.Computers and Graphics, 23(1):127-143, 1999.
[28]R. Parent. Computer Animation: Algorithms and Techniques. MorganKaufmann, 2001.
[29]A. Stentz, Optimal and efficient path planning for unknown and dynamic environments,CarnegieMellon Univ., Robot. Inst., Pittsburgh, PA,Tech.Rep. CMU-RI-TR-93-20, Aug. 1993.
[30]E. Bouvier, E. Cohen, , and L. Najman. From crowd simulation to airbag deployment: particle systems, a new paradigm of simulation. Journal of Electronic Imaging, 6(1):94-107, 1997.
[31]D. C. Brogan and J. K. Hodgins. Group behaviors for systems with significant dynamics. Autonomous Robots, 4:137-153, 1997.
[32]D. C. Brogan, R. A. Metoyer, and J. K.Hodgins. Dynamically simulated characters in virtual environments. IEEE Comput. Graph. Appl., 18(5):58-69, 1998.
[33]R. L. Hughes. The flow of human crowds. Annual Review of Fluid Mechanics, 35:169-182, 2003.
[34]S. Chenney. Flow tiles. In Proceedings of Eurographics/ACM SIGGRAPH Symposium on Computer Animation, pages 233-242, 2004.
[35]A. Treuille, S. Cooper, and Z. Popovic. Continuum crowds. ACM Transactions on Graphics (SIGGRAPH '06),. 25(3):1160 -1168, 2006.
[36]M. J. Mataric. Learning to behave socially. In D. Cli?, P. Husbands,J. Meyer, and S. Wilson, editors, From Animals to Animats: International Conference on Simulation of Adaptive Behavior, pages 453-462, 1994.
[37]B. M. Blumberg and T. A. Galyean. Multi-level direction of autonomous creatures for real-time virtual environments. ACM Computer Graphics(Proceedings of SIGGRAPH'95), pages 47-54, 1995.
[38]M. Anderson, E. McDaniel, and S. Chenney. Constrained animation of flocks. In D. Breen and M. Lin, editors, Proceedings of Eurographics/ACM SIGGRAPH Symposium on Computer Animation, pages 286-297, 2003.
[39]S. R. Musse, C. Babski, T. Capin, and D. Thalmann. Crowd modeling in collaborative virtual environments. In Proceedings of VRST'98, pages 115-124, Taipei, Taiwan, 1998.
[40]M. Sung, M. Gleicher, and S. Chenney. Scalable behaviors for crowd simulation. In Proceedings of Eurographics/ACM SIGGRAPH Symposium on Computer Animation, volume 23, pages 519-528, 2004.
[41]K. Perlin and A. Goldberg. Improv: A system for scripting interactive actors in virtual worlds. Computer Graphics, 29(3), 1996.
[42]D. Thalmann, S. R. Musse, and M. Kallmann. Virtual humans' behaviour:Individuals, groups, and crowds. In Proceedings of Digital Media Futures,1999.
[43]Y. Hijikata, T. Komatsu, N. Saiwaki, and S. Nishida. Automatic generation of moving crowdusing chaos and electric charge model. In Proceedings of the IEEE International Conference on Systems,Man and Cybernetics,volume 2, pages 342-347, 2002.
[44]C. Soh, P. Raveendran, and Z. Taha. Automatic generation of selforganized virtual crowd using chaotic perturbation. In Proceedings of TENCON 2004, 2004 IEEE Region 10 Conference, volume 2, pages 124-127, 2004.
[45]N. Saiwaki, T. Komatsu, T. Yoshida, S., and Nishida. Automatic generation of moving crowd using chaos model. In Proceedings of the IEEE International Conference on System, Man and Cybernetics, volume 4, pages 3715-3721, 1997.
[46]J.-S. Monzani, A. Caicedo, and D. Thalmann. Integrating behavioural animation techniques. In A. Chalmers and T. Rhyne, editors, Proceedings of Eurographics/ACM SIGGRAPH Symposium on Computer Animation, volume 20, 2001.
[47]R. Burke, D. Isla, M. Downie, Y. Ivanov, and B. Blumberg. Creature smarts: The art and architecture of a virtual brain. In Proceedings of the Computer Game Developers Conference, pages 147-166, 2001.
[48]B. M. Blumberg, M. Downie, Y. Ivanov, M. Berlin, M. Johnson, and B. Tomlinson. Integrated learning for interactive synthetic characters. ACM Computer Graphics (Proceedings of SIGGRAPH'02), pages 417-426, 2002.
[49]B. Tomlinson and B. Blumberg. Alphawolf: Social learning, emotion and development in autonomous virtual agents. In Proceedings of First GSFC/JPL Workshop on Radical Agent Concepts, pages 35-45, 2002.
[50]T. Conde, W. Tambellini, and D. Thalmann. Behavioral animation for autonomous virtual agents helped by reinforcement learning. In T. Rist, editor, Proceedings of IVA'03, pages 175{180, Berlin, Heidelberg, 2003.
[51]T. Conde and D. Thalmann. Autonomous virtual agents learning a cognitive model and evolving. In Lecture Notes in Computer Science, volume 3631, pages 88-98. Springer-Verlag, Berlin, 2005.
[52]T. Conde and D. Thalmann. Learnable behavioral model for autonomous virtual agents: Low-level learning. In Proceedings of Embodied Conversational Agents at AAMAS'06, pages 89{96, Hakodate, Hokkaido, Japan, May 8-12 2006.
[53]J. Allbeck and N. Badler. Toward representing agent behaviors modified by personality and emotion. In Proceedings of Embodied Conversational Agents at AAMAS'02, Bologna, Italy, July 2002.
[54]B. G. Silverman, G. Bharathy, K. O'Brien, and J. Cornwell. Human behavior models for agents in simulators and games: Part I-enabling science with PMFserv. Presence: Teleoperators. and Virtual Environments, 15(2), 2006.
[55]B. G. Silverman. More realistic human behavior models for agents in virtual worlds: Emotion, stress and value ontologies. Technical report, Systems Engineering Department, University of Pennsylvania, 2001.
[56]N. Pelechano, K. O'Brien, B. Silverman, and N. Badler. Crowd simulation incorporating agent psychological models, roles and communication. In Proceedings of First International Workshop on Crowd Simulation (VCROWDS'05), Lausanne, Switzerland, 2005.
[57]C.Watkins and P. Dayan. Q-learning. Machine Learning, 8:279-292, 1992.
[58]S. M. LaValle. Planning algorithms. Cambridge University Press, 2006.
[59]M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin Heidelberg New York, second edition, 1998.
[60]J.-C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, Boston, 1991.
[61]M. H. Overmars. Recent developments in motion planning. In International Conference on Computational Science, volume 3, pages 3{13, 2002.
[62]O. Arikan, S. Chenney, and D. A. Forsyth. E±cient multi-agent path planning. In Proceedings of the Eurographic workshop on Computer animation and simulation, pages 151{162, 2001.
[63]O. Bayazit, J. Lien, and N. Amato. Better group behaviors in complex environments with global roadmaps. In Proceedings of Int. Conf. on the Sim. and Syn. of Living Sys. (Alife), pages 362{370, 2002.
[64]O. Bayazit, J. Lien, and N. Amato. Better group behaviors using rule-based roadmaps. In Proceedings of International Workshop on Algorithmic Foundations of Robotics (WAFR), Nice, France, 2002.
[65]A. Kamphuis and M. H. Overmars. Finding paths for coherent groups using clearance. In Proceedings of Eurographics/ACM SIGGRAPH Symposium on Computer Animation, 2004.
[66]Y.-C. Lai, S. Chenney, and S. Fan. Group motion graphs. In Proceedings of Eurographics/ACM SIGGRAPH Symposium on Computer Animation, volume 23, 2005.
[67]M. S. A. Latif and S. Widyarto. The crowd simulation for interactive virtual environments. In ACM SIGGRAPH International Conference on Virtual Reality Continuum and its Appications in Industry (VRCAI'04), pages 278{281, Singapore, 2004.
[68]S. Paris, S. Donikian, and N. Bonvalet. Environmental abstraction and path planning techniques for realistic crowd simulation. Computer Animation and Virtual Worlds, 17:325-335, 2006.
[69]Q. Khatib. Real-time obstacle avoidance for manipulators and mobile robots. The International Journal of Robotics Research, 5(1):90-98, 1986.
[70]Mataric, M. 1994. Interaction and Intelligent Behavior. PHD Thesis, Department of EECS, MIT, Cambridge, MA
[71]McKenna, M., Pieper, S., and Zeltzer, D. 1990. Control of a virtual actor: The roach. ACM SIGGRAPH’90 Symposium on Interactive 3D Graphics, 24(2)
[72]Renalt, O., Magnenat-Thalmann, N., and Thalmann, D. 1990. A vision-based approach to behavioural animation. Visualization and Computer Animation, 1:18-21
[73]Tsotsos, J., Culhane, S., Wai, W., Lai, Y., Davis, N., and Nuflo, F. 1995. Modeling visual attention via selective tuning.. Artificial Intelligence.
[74]Manning, A. 1979. An Introduction to Animal Behavior. 3rd edition. Reading, MA:Addison-Wesley.
[75]Gilbert E G,Johnson D.W. Distance functions and their application to robot path planning in the presence of obstacles. IEEE J Robotics and Automation 1985,RA-1(1):21-30
[76]DORIGO M, CARO G D, GAMBARDELLA L M. Ant algorithms for discrete optimization [J]. Artificial Life, 1999, 5(3): 137-172.
[77]A. R. Willms and S. X. Yang, An efficient dynamic system for real-time robot path planning, IEEE Trans. Syst., Man, Cybern. B, Cybern, vol. 36, no. 4, pp. 755–766, Aug. 2006.
[78]A. R. Willms and S. X. Yang,“Real-Time Robot Path Planning via a Distance-Propagating Dynamic System with Obstacle Clearance”. IEEE Trans. Syst., Man, Cybern. B, Cybern. Jun 2008.
[79]C. W. Warren, Fast path planning using modified a method, in Proc.IEEE Int. Conf. Robotics and Automation, Atlanta, GA, May 1993,pp. 662–667
[2] The Lord of the Rings, The Battle for Middle Earth, 2004. Game homepage, http://www.eagames.com/pccd/lotr bfme.
[3] Thompson P.,Marchant E.: A computer-model for the evacuation of large building population. Fire Safety Journal24,2(1995),131-148.1,3.
[4] Hareesh P.: Evacuation simulation: Visualisation using virtual humans in a distributed multi-user immersive VR system. In Proc. VSMM‘00(2000).
[5] KLUPFEL H., MEYER-KONIG M., WAHLEJ., SCHRECKENBERG M.: Microscopicsimulation of evacuation processes on passenger ships. In Theoretical and Practical Issues on Cellular Automata (2000), Bandini S.,Worsch T., (Eds.), Springer, London, pp. 63–71.3
[6] OWEN M., GALEA E. R., LAWRENCE P. J., FILIPPIDIS L.: The numerical simulation of aircraft evacuation and its application to aircraft design and certification. The Aeronautical Journal 102, 1016 (1998), 301–312.
[7] ROBBINS C.: Computer simulation of crowd behaviour and evacuation. ECMI Newsletter, 25 (March 1999).
[8] Simulex, 2004. evacuation modeling software, product information, http://www.ies4d.com.
[9] WILLIAMS J.: A Simulation Environment to Support Training for Large Scale Command and Control Tasks. PhD thesis, University of Leeds, 1995.
[10]MCPHAIL C., POWERS W., TUCKER C.: Simulating individual and collective actions in temporary gatherings. Social Science Computer Review 10, 1 (Spring 1992), 1–28.
[11]POWERS W. T.: The Control of Perception. Aldine, Chicago, 1973.
[12]TAKAHASHI T. S. H.: Behavior simulation by network model. Memoirs of Kougakuin University, 73 (1992), 213–220.
[13]HELBING D., FARKAS I., VICSEK T.: Simulating dynamical features of escape panic. Nature 407 (2000), 487–490.
[14]HOSOI M., ISHIJIMA S., KOJIMA A.: Dynamical model of a pedestrian in a crowd. In Proc. IEEE International Workshop on Robot and Human Communication’96 (1996).
[15]SAIWAKI N., KOMATSU T., NISHIDA S.: Automatic generation of moving crowds in the virtual environments. In Proc. AMCP’98 (1998).
[16]Reynolds C. W.: Flocks, herds, and schools: A distributed behavioral model. In Computer Graphics (ACM SIGGRAPH’87 Conference Proceedings) (Anaheim, CA, USA, 1987), Vol. 21, ACM,pp. 25–34)
[17]Tu,X. -Y. and Terzopoulos,D.: Artificial fishes: Physics,locomotion,perception,behavior. In Proceedings of SIGGRAPH 94,Computer Graphics Proceedings,Annual Conference Series,43-50,1994.
[18]Brogan D., Hodgins J.: Group behaviors for systems with significantdynamics. Autonomous Robots 4 (1997), 137–153.
[19]Musse S. R., Thalmann D.: A hierarchical model for realtime simulation of virtual human crowds. IEEE Transactions on Visualization and Computer Graphics 7, 2 (April-June 2001),152–164.
[20]纪庆革,潘志庚,梅林,杨世琦,李祥晨.团体操虚拟编排和演练原型系统.计算机辅助设计与图形学学报,2004 16(9).
[21]J. Funge. Making Them Behave: Cognitive Models for Computer Animation. PhD thesis, Graduate Department of Computer Science, University of Toronto, 1998.
[22]J. Funge. Cognitive modeling for games and animation. Communications of the ACM, 43(7):41-48, 2000.
[23]J. Funge, X. Tu, and D. Terzopoulos. Cognitive modeling: Knowledge, reasoning and planning for intelligent characters. ACM Computer Graphics (Proceedings of SIGGRAPH'99), pages 29-38, 1999.
[24]S. Shanbhag. Behavioral animation : A report. In Proceedings of the Inter Research Institute Student Seminar in Computer Science (IRISS'02),2002.
[25]A. Stentz, Optimal and efficient path planning for partially-known environments, in Proc. IEEE Int. Conf. Robot. Autom., 1994,pp. 3310–3317
[26]C. W. Reynolds. Steering behaviors for autonomos characters. In Proceedings of Game Developers Conference, pages 763{782, San Jose, California,1999.
[27]R. Millar, J. Hanna, and S. Kealy. A review of behavioural animation.Computers and Graphics, 23(1):127-143, 1999.
[28]R. Parent. Computer Animation: Algorithms and Techniques. MorganKaufmann, 2001.
[29]A. Stentz, Optimal and efficient path planning for unknown and dynamic environments,CarnegieMellon Univ., Robot. Inst., Pittsburgh, PA,Tech.Rep. CMU-RI-TR-93-20, Aug. 1993.
[30]E. Bouvier, E. Cohen, , and L. Najman. From crowd simulation to airbag deployment: particle systems, a new paradigm of simulation. Journal of Electronic Imaging, 6(1):94-107, 1997.
[31]D. C. Brogan and J. K. Hodgins. Group behaviors for systems with significant dynamics. Autonomous Robots, 4:137-153, 1997.
[32]D. C. Brogan, R. A. Metoyer, and J. K.Hodgins. Dynamically simulated characters in virtual environments. IEEE Comput. Graph. Appl., 18(5):58-69, 1998.
[33]R. L. Hughes. The flow of human crowds. Annual Review of Fluid Mechanics, 35:169-182, 2003.
[34]S. Chenney. Flow tiles. In Proceedings of Eurographics/ACM SIGGRAPH Symposium on Computer Animation, pages 233-242, 2004.
[35]A. Treuille, S. Cooper, and Z. Popovic. Continuum crowds. ACM Transactions on Graphics (SIGGRAPH '06),. 25(3):1160 -1168, 2006.
[36]M. J. Mataric. Learning to behave socially. In D. Cli?, P. Husbands,J. Meyer, and S. Wilson, editors, From Animals to Animats: International Conference on Simulation of Adaptive Behavior, pages 453-462, 1994.
[37]B. M. Blumberg and T. A. Galyean. Multi-level direction of autonomous creatures for real-time virtual environments. ACM Computer Graphics(Proceedings of SIGGRAPH'95), pages 47-54, 1995.
[38]M. Anderson, E. McDaniel, and S. Chenney. Constrained animation of flocks. In D. Breen and M. Lin, editors, Proceedings of Eurographics/ACM SIGGRAPH Symposium on Computer Animation, pages 286-297, 2003.
[39]S. R. Musse, C. Babski, T. Capin, and D. Thalmann. Crowd modeling in collaborative virtual environments. In Proceedings of VRST'98, pages 115-124, Taipei, Taiwan, 1998.
[40]M. Sung, M. Gleicher, and S. Chenney. Scalable behaviors for crowd simulation. In Proceedings of Eurographics/ACM SIGGRAPH Symposium on Computer Animation, volume 23, pages 519-528, 2004.
[41]K. Perlin and A. Goldberg. Improv: A system for scripting interactive actors in virtual worlds. Computer Graphics, 29(3), 1996.
[42]D. Thalmann, S. R. Musse, and M. Kallmann. Virtual humans' behaviour:Individuals, groups, and crowds. In Proceedings of Digital Media Futures,1999.
[43]Y. Hijikata, T. Komatsu, N. Saiwaki, and S. Nishida. Automatic generation of moving crowdusing chaos and electric charge model. In Proceedings of the IEEE International Conference on Systems,Man and Cybernetics,volume 2, pages 342-347, 2002.
[44]C. Soh, P. Raveendran, and Z. Taha. Automatic generation of selforganized virtual crowd using chaotic perturbation. In Proceedings of TENCON 2004, 2004 IEEE Region 10 Conference, volume 2, pages 124-127, 2004.
[45]N. Saiwaki, T. Komatsu, T. Yoshida, S., and Nishida. Automatic generation of moving crowd using chaos model. In Proceedings of the IEEE International Conference on System, Man and Cybernetics, volume 4, pages 3715-3721, 1997.
[46]J.-S. Monzani, A. Caicedo, and D. Thalmann. Integrating behavioural animation techniques. In A. Chalmers and T. Rhyne, editors, Proceedings of Eurographics/ACM SIGGRAPH Symposium on Computer Animation, volume 20, 2001.
[47]R. Burke, D. Isla, M. Downie, Y. Ivanov, and B. Blumberg. Creature smarts: The art and architecture of a virtual brain. In Proceedings of the Computer Game Developers Conference, pages 147-166, 2001.
[48]B. M. Blumberg, M. Downie, Y. Ivanov, M. Berlin, M. Johnson, and B. Tomlinson. Integrated learning for interactive synthetic characters. ACM Computer Graphics (Proceedings of SIGGRAPH'02), pages 417-426, 2002.
[49]B. Tomlinson and B. Blumberg. Alphawolf: Social learning, emotion and development in autonomous virtual agents. In Proceedings of First GSFC/JPL Workshop on Radical Agent Concepts, pages 35-45, 2002.
[50]T. Conde, W. Tambellini, and D. Thalmann. Behavioral animation for autonomous virtual agents helped by reinforcement learning. In T. Rist, editor, Proceedings of IVA'03, pages 175{180, Berlin, Heidelberg, 2003.
[51]T. Conde and D. Thalmann. Autonomous virtual agents learning a cognitive model and evolving. In Lecture Notes in Computer Science, volume 3631, pages 88-98. Springer-Verlag, Berlin, 2005.
[52]T. Conde and D. Thalmann. Learnable behavioral model for autonomous virtual agents: Low-level learning. In Proceedings of Embodied Conversational Agents at AAMAS'06, pages 89{96, Hakodate, Hokkaido, Japan, May 8-12 2006.
[53]J. Allbeck and N. Badler. Toward representing agent behaviors modified by personality and emotion. In Proceedings of Embodied Conversational Agents at AAMAS'02, Bologna, Italy, July 2002.
[54]B. G. Silverman, G. Bharathy, K. O'Brien, and J. Cornwell. Human behavior models for agents in simulators and games: Part I-enabling science with PMFserv. Presence: Teleoperators. and Virtual Environments, 15(2), 2006.
[55]B. G. Silverman. More realistic human behavior models for agents in virtual worlds: Emotion, stress and value ontologies. Technical report, Systems Engineering Department, University of Pennsylvania, 2001.
[56]N. Pelechano, K. O'Brien, B. Silverman, and N. Badler. Crowd simulation incorporating agent psychological models, roles and communication. In Proceedings of First International Workshop on Crowd Simulation (VCROWDS'05), Lausanne, Switzerland, 2005.
[57]C.Watkins and P. Dayan. Q-learning. Machine Learning, 8:279-292, 1992.
[58]S. M. LaValle. Planning algorithms. Cambridge University Press, 2006.
[59]M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin Heidelberg New York, second edition, 1998.
[60]J.-C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, Boston, 1991.
[61]M. H. Overmars. Recent developments in motion planning. In International Conference on Computational Science, volume 3, pages 3{13, 2002.
[62]O. Arikan, S. Chenney, and D. A. Forsyth. E±cient multi-agent path planning. In Proceedings of the Eurographic workshop on Computer animation and simulation, pages 151{162, 2001.
[63]O. Bayazit, J. Lien, and N. Amato. Better group behaviors in complex environments with global roadmaps. In Proceedings of Int. Conf. on the Sim. and Syn. of Living Sys. (Alife), pages 362{370, 2002.
[64]O. Bayazit, J. Lien, and N. Amato. Better group behaviors using rule-based roadmaps. In Proceedings of International Workshop on Algorithmic Foundations of Robotics (WAFR), Nice, France, 2002.
[65]A. Kamphuis and M. H. Overmars. Finding paths for coherent groups using clearance. In Proceedings of Eurographics/ACM SIGGRAPH Symposium on Computer Animation, 2004.
[66]Y.-C. Lai, S. Chenney, and S. Fan. Group motion graphs. In Proceedings of Eurographics/ACM SIGGRAPH Symposium on Computer Animation, volume 23, 2005.
[67]M. S. A. Latif and S. Widyarto. The crowd simulation for interactive virtual environments. In ACM SIGGRAPH International Conference on Virtual Reality Continuum and its Appications in Industry (VRCAI'04), pages 278{281, Singapore, 2004.
[68]S. Paris, S. Donikian, and N. Bonvalet. Environmental abstraction and path planning techniques for realistic crowd simulation. Computer Animation and Virtual Worlds, 17:325-335, 2006.
[69]Q. Khatib. Real-time obstacle avoidance for manipulators and mobile robots. The International Journal of Robotics Research, 5(1):90-98, 1986.
[70]Mataric, M. 1994. Interaction and Intelligent Behavior. PHD Thesis, Department of EECS, MIT, Cambridge, MA
[71]McKenna, M., Pieper, S., and Zeltzer, D. 1990. Control of a virtual actor: The roach. ACM SIGGRAPH’90 Symposium on Interactive 3D Graphics, 24(2)
[72]Renalt, O., Magnenat-Thalmann, N., and Thalmann, D. 1990. A vision-based approach to behavioural animation. Visualization and Computer Animation, 1:18-21
[73]Tsotsos, J., Culhane, S., Wai, W., Lai, Y., Davis, N., and Nuflo, F. 1995. Modeling visual attention via selective tuning.. Artificial Intelligence.
[74]Manning, A. 1979. An Introduction to Animal Behavior. 3rd edition. Reading, MA:Addison-Wesley.
[75]Gilbert E G,Johnson D.W. Distance functions and their application to robot path planning in the presence of obstacles. IEEE J Robotics and Automation 1985,RA-1(1):21-30
[76]DORIGO M, CARO G D, GAMBARDELLA L M. Ant algorithms for discrete optimization [J]. Artificial Life, 1999, 5(3): 137-172.
[77]A. R. Willms and S. X. Yang, An efficient dynamic system for real-time robot path planning, IEEE Trans. Syst., Man, Cybern. B, Cybern, vol. 36, no. 4, pp. 755–766, Aug. 2006.
[78]A. R. Willms and S. X. Yang,“Real-Time Robot Path Planning via a Distance-Propagating Dynamic System with Obstacle Clearance”. IEEE Trans. Syst., Man, Cybern. B, Cybern. Jun 2008.
[79]C. W. Warren, Fast path planning using modified a method, in Proc.IEEE Int. Conf. Robotics and Automation, Atlanta, GA, May 1993,pp. 662–667