沈宇婷
2015年6月
中图分类号：TQ028.1UDC分类号：540
人工智能社会的可视化方法研究
作 者 姓 名学 院 名 称 指 导 教 师
杨林 软件学院
丁刚毅 郑澎 工程硕士
答辩委员会主席 申 请 学 位 学 科 专 业学位授予单位 论文答辩日期
软件工程 北京理工大学 2014年6月
Visual Analysis of Artificial Intelegent Society
Candidate Name:School or Department:Faculty Mentor:
Chair, Thesis Committee:Degree Applied: Major:Degree by:
The Date of Defence:
YangLinSchool of SoftwareDingGangyiZhengPengMaster of EngineeringSoftware EngineeringBeijing Institute of TechnologyJune，2014人工智能社会的可视化方法研究 北京理工大学研究成果声明
本人郑重声明：所提交的学位论文是我本人在指导教师的指导下进行的研究工作获得的研究成果。尽我所知，文中除特别标注和致谢的地方外，学位论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京理工大学或其它教育机构的学位或证书所使用过的材料。与我一同工作的合作者对此研究工作所做的任何贡献均已在学位论文中作了明确的说明并表示了谢意。
特此申明。
签 名： 日期：
关于学位论文使用权的说明
本人完全了解北京理工大学有关保管、使用学位论文的规定，其中包括：①学校有权保管、并向有关部门送交学位论文的原件与复印件；②学校可以采用影印、缩印或其它复制手段复制并保存学位论文；③学校可允许学位论文被查阅或借阅；④学校可以学术交流为目的,复制赠送和交换学位论文；⑤学校可以公布学位论文的全部或部分内容（保密学位论文在解密后遵守此规定）。
签 名： 导师签名： 日期：
日期：
北京理工大学硕士学位论文
摘要
人工智能社会研究与人群仿真广泛应用于公共安全、计算机游戏、电影动画、社会学心理学等领域。人群仿真领域的研究工作可以根据仿真策略划分为离散人群仿真和连续人群仿真，也可以根据仿真粒度划分为宏观人群仿真和微观人群仿真。以上的独立仿真策略，比如离散人群仿真和微观人群仿真只能较好的体现个体运动特征，很难体现群体运动趋势。而连续人群仿真和宏观人群仿真对具有全局影响力的物理现象能够精确描述，同时能够体现群体行为协作。
对大规模、高密度人群进行真实性较高的仿真与模拟一直以来都是计算机图形学领域的一个研究热点。传统的仿真方法具有人群运动更像是粒子运动（虚拟人会出现颤抖现象）、高密度人群运动因素考虑不全（没有考虑虚拟人间的推搡行为）等问题。本研究的目的在于在动态的复杂环境中实现较为真实的人群自身运动模型。在传统的社会驱动力模型基础上综合了一些心理学研究和几何规则来实现这一点。
为了在复杂的大场景中准确的模拟人群行为，光考虑虚拟人自身的运动模型是不够的；虚拟人必须有能力自主的在未知环境中进行导航。在人群的导航过程中不是所有的虚拟人都掌握着仿真环境的全部信息。在虚拟人对环境进行探索的过程中，允许他们互相交流分享自己已知的路径和环境信息。
研究了虚拟人在探索环境的过程中交流分享环境路径和事故情况对整个人群仿真结果的影响。同时还将虚拟人分成了三类经过训练的虚拟人、领导者和跟随者。
关键词：人工智能社会；人群仿真；人群运动模型；仿真系统UI设计
I
北京理工大学硕士学位论文
Abstract
Crowd Simulation has widely applied in Public Security, computer games, movies, sociology and psychology. We can divide crowd simulation into four aspects, discrete crowd simulation, continuum crowd simulation, macroscopic crowd simulation and microcosmic crowd simulation. Each method has its drawback. Discrete crowd simulation embodies motion of each agent, but it’s difficult to develop behavioral rules that consistently produce realistic motion. And continuum crowd simulation method can support the group collaboration. To solve those problems and combine the advantages of those methods, we propose a crowd simulation method based on hybrid model, this can integrate individual human motion and crowd interactions.
The simulation of realistic, large, dense crowds of autonomous agents is still a challenge for the computer graphics community.Typical approaches either look like particle simulation (where agents ‘vibrate’back and forth) or are conservative in the range of motion possible (agent aren’t allowed to ‘push’ each other). Our system focuses on the problem of simulating the local motion behaviors of crowds moving in a natural manner withing dynamically changing virtual environments. This is achieved by applying a combination of psychological and geometrical rules layerd on top of a social forces model.
To accurately simulate crowds in large, complex environments, it is not enough to only model local motion; agents must also have the ability to navigate the unknown virtual environment. We therefore address the problems that arise during crowd navigation where not all individuals have complete knowledge of the building’s internal structure. In addition, we simulate the effects of communication on the behavior of agents while exploring the building.
We study the emergent behavior during building evacuation under different
conditions such as agents using communication to share their knowledge of the environment, and agents taking different roles such as trained personnel, leaders and followers.
Key Words: Artificial society; Crowd Simulation; Drowd Movement Model; Simulation System UI Design
II
北京理工大学硕士学位论文
目录
第1章 绪论..................................................................................................1
1.1 论文研究的目的和意义...................................................................................11.2 国内外研究现状及发展趋势...........................................................................21.3 本文的研究内容...............................................................................................31.4 本文的组织结构...............................................................................................4
第2章 人群仿真技术与仿真引擎介绍......................................................6
2.1 人群仿真技术的分类.......................................................................................62.2 社会驱动力模型...............................................................................................72.3 元胞自动机模型...............................................................................................82.4 基于规则的模型...............................................................................................92.5 CryEngine3 游戏引擎...................................................................................102.6 本章小结.........................................................................................................13
第3章 虚拟环境的抽象方法....................................................................14
3.1 虚拟环境抽象方法概述.................................................................................143.2 自动生成虚拟环境抽象信息方法.................................................................14
3.2.1建筑物单层环境信息的抽象...............................................................153.2.2 建筑物多层环境信息的抽象..............................................................163.2.3 抽象环境信息的存储..........................................................................163.3 导航信息的预计算.........................................................................................17
3.3.1 导航信息预计算的流程.....................................................................173.3.2 Delaunay三角剖分..............................................................................17
III
北京理工大学硕士学位论文
3.3.3 A-Star寻路算法...................................................................................213.3.4 路径优化方法.....................................................................................223.4 本章小结.........................................................................................................22
第4章 运动模型的构建............................................................................23
4.1 运动模型概述.................................................................................................234.2 虚拟人的速度和密度.....................................................................................244.3 环境感知.........................................................................................................254.4 基础社会驱动力模型.....................................................................................264.5 拓展社会驱动力模型.....................................................................................26
4.5.1 运动规则..............................................................................................264.5.2 碰撞反弹力的计算..............................................................................274.5.2 规避障碍物力的计算..........................................................................304.5.3 虚拟人之间的推搡行为......................................................................314.5.4 惊慌情绪在人群中的传递..................................................................324.6 验证与小结.....................................................................................................33
第5章 自主环境探索模型的构建............................................................35
5.1 自主环境探索方法.........................................................................................355.2 心理模型建模.................................................................................................385.3 验证与小结.....................................................................................................40
第6章 原型系统实现与运行....................................................................43
6.1 原型系统实现.................................................................................................43
6.1.1 系统框架..............................................................................................44
IV
北京理工大学硕士学位论文
6.1.2 系统流程..............................................................................................456.1.3 系统模块..............................................................................................466.2 环境配置.........................................................................................................476.3 原型系统运行分析.........................................................................................476.4 仿真效率分析.................................................................................................516.5 本章小结.........................................................................................................52
总结与展望...............................................................................................53参考文献...................................................................................................56致谢...........................................................................................................59
V
第1章 绪论
1.1 论文研究的背景
1.2 论文研究的目的与意义
1.3 论文研究的主要内容和重点
1.4 本文的组织结构
第2章 基于LVC的军事仿真体系结构关键技术分析
1
2.1 公共对象模型
2.1.1 公共对象模型的目标和基本原则2.1.2 公共对象模型原型模型2.1.3 公共对象模型改进原型模型
2.2 中间件技术
2.2.1 服务于公共对象模型的中间件2.2.2 模型加工中间件2.2.3 时间管理中间件
2.2.3.1 时钟同步2.2.3.2 优先级管理2.2.3.3其它管理方案2.3 网络同步技术
2.3.1 数据同步2.3.2 模型同步2.3.3 画面同步2.3.4 多系统网络同步
2.4 本章小结
第3章 基于LVC的军事仿真系统架构研究与设计
2
3.1 基于公共对象模型的模型设计
3.1.1 基于公共对象模型的模型结构设计3.1.2 基于设计模型的数据流转
3.2 中间件层及其公共服务
3.2.1 中间件层结构设计3.2.2 中间件层功能设计
3.3 总体设计3.4 本章小结
第4章 基于3D引擎的军事仿真系统实现
4.1 Unigine引擎简介
4.2 基于Unigine的关键技术实现方案
4.2.1 模型实现方案4.2.2 显示实现方案4.2.3 同步实现方案
4.2.4 异构系统互操作实现方案
4.3 基于Unigine的军事仿真系统架构方案
4.4 基于Unigine的军事仿真系统实现方案分析与总结4.5 本章小结
3
总结与展望
4
参考文献
[1] 毛海力. 大规模人群仿真技术研究, 工业控制计算机, 2010(7)[2] 王鑫. 数据驱动的人群动画仿真技术研究, 浙江大学, 2009
[3] 邵明. 基于GPU的运动路径匹配及人群仿真研究, 浙江大学, 2010[4] 李晓娜; 孙立博; 秦文虎. 虚拟人群仿真的路径规划新算法, 东南大学学报(自然科学版),2011(2)
[5] 李延峰; 潘志庚. 虚拟人群仿真技术的研究, 杭州电子科技大学学报, 2005(1)[6] 刘涛; 孙守迁; 潘云鹤. 面向艺术与设计的虚拟人技术研究, 计算机辅助设计与图形学学报, 2004(11)
[7] 孙立博. 虚拟人群行为建模及仿真技术研究, 天津大学[8] 何江华著. 计算机仿真导论[M], 北京：科学出版社,2001
[9] 李琪. 一种基于空间划分的人群仿真混合模型, 软件导刊, 2013(5)
[10] 岳翠苹, 基于Vicrowd模型的大规模人群仿真技术的研究, 电子科技大学, 2010[11] 熊慕舟, 骆文振. 一种基于多Agent的人群仿真多机并行平台研究, 2012(10)[12] 陈岩, 丁刚毅, 黄天羽. 数字表演时代的崭新呈现[J], 现代电视技术, 2010(5):131～133
[13] 丁刚毅, 李红松, 黄天羽, 张龙飞, 高婧, 彰大为.
大型广场文艺表演的虚拟编排原型系统[j], 系统仿真学报, 2008(9):136～140
[14] 周晓莉. 车站环境下旅客行为仿真平台的开发与应用, 西南交通大学[15] 邵明; 孙守迁. 基于GPU的并行化人群实时仿真, 计算机应用与软件
[16][Blue and Adler 2000] V. Blue, J. Adler, Cellular Automata Microsimulationof Bi-Directional Pedestrian Flows, Journal of the TransportationResearch Board, 1678:135-141, 2000.
[17][Bouvier et al. 1997] E. Bouvier, E. Cohen, L. Najman, From Crowd Simulationto Airbag Deployment: Particle Systems, a New Paradigm ofSimulation, J. Electronic Imaging, 6(1):94-107, 1997.
[18][Braun et al. 2003] A. Braun, S. Musse, L. de Oliveira, B. Bodmann, ModelingIndividual Behaviors in Crowd Simulation, Proc. of ComputerAnimation and Social Agents, 143-148, 2003.
[19][Dijkstra et al. 2000] J. Dijkstra, H. Timmermans, A. Jessurun, A Multi-AgentCellular Automata System for Visualising Simulated Pedestrian Acitivity,Proc. of the Fourth International Conference on CellularAutomata for Research and Industry, 29-36, 2000.
[20][Feurtey 2000] F. Feurtey, Simulating the Collision Avoidance Behavior ofPedestrians, Master thesis, The University of Tokyo, School of Engeenering,2000.
[21][Foley et al. 1994] J. Foley, A. van Dam, S. Feiner, J. Hughes, R. Phillips, Introductionto Computer Graphics, Addison-Wesley, 1994.
[22][Gardner 1970] M. Gardner, Mathematical Games: Conway’s Game of Life,Scientific American, 224:120-123, October 1970.
[23][Helbing and Moln´ar 1998] D. Helbing, P. Moln´ar, Social force model for pedestriandynamics, Physical Review, 51:4282-4286, 1998.
[24][Helbing et al. 2000] D. Helbing, I. Farkas, T. Vicsek, Simulating DynamicalFeatures of Escape Panic, Nature, 407:487-490, 2000.
5
[25][Helbing et al. 2001] D. Helbing, P. Molnar, I. Farkas, K. Bolay, Self-organizingPedestrian Movement, Environment and Planning B: Planning andDesign, 28:361-383, 2001.
[27] Parisi D R, Dorso C O. Microscopic dynamics of pedestrian evacuation[J]. Physica A: Statistical Mechanics and its Applications, 2005, 354(0): 606-618.
[28] Braun A, Bodmann B, Musse S. Simulating virtual crowds in emergency situations. ACM symposium on Virtual reality software and technology[C]. 2005: 244-252。
[29] Roger L, Hughes. A Continuum Theory for the Flow of Pedestrian[J]. Transportation Research Part B, 2002, 36(6): 507-535.
[30] Roger L, Hughes. The Flow of Human Crowds[J]．Annual Review of Fluid Mechanics, 2003,35(35): 69-182.
[31] Hoppe H. Progressive meshes. ACM SIGGRAPH[C]. 1996: 99-108.
[32] Hoppe H. View-Dependent refinement of progressive meshes. ACM SIGGRAPH[C]. 1997: 189-198.
[33] Hoppe H. New quadric metric for simplification meshes with appearance attributes. IEEE Visualization[C]. 1999: 59-66.
[34] Finkel R. A. and J. L. Bentley. Quad trees: a data structure for retrieval on composite keys[J].Acta Informatica, 1974, 4(0): 1-9.
[35] Gargantini I. An effective way to represent quadtrees[J]. Communications of the ACM, 1982, 905-10.
[36] Samet H. Neighbor finding techniques for images represented by quadtrees[J]. Computer Graphics and Image Processing, 1982, 35-57.
[37] Schrack G. Finding neighbors of equal size in linear quadtrees and octrees in constant time[J].CVGIP: Image Understanding, 1992, 221-230.
[38] Aizawa K, Tanaka S. A constant time algorithm for finding neighbors in quadtrees[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 1178-1183.
[39] O’Rourke J, Badler N. Decomposition of three-dimensional objects into spheres[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979, 1(3): 295-305.
[40] Featherstone R. Swept bubbles: A method of representing swept volume and space
occupancy[R].North American Philips Corporation, briarcliff Manor, New York 10510: Philips Laboratories, 1990.
[41] Fiorini P, Shiller Z. Motion planning in dynamic environments using the relative velocity paradigm. IEEE International Conference of Automation and Robotics[C]. 1993: 560-566.
[42] Lozano-Perez T. Spatial planning: a configuration space approach[J]. IEEE Transaction on Computer, 1983: C-32(2): 108-120.
[43] Burke W. Applied Differential Geometry[M]. Cambridge University Press, 1985.
[44] Bentley L J. Multidimensional Divide and Conquer[J]. Communications of the ACM, 1980, 23(4): 214-229.
[45] Friedman H J, Bentley J L, Finkel R A. An Algorithm for Finding Best Matches in Logarithmic Expected Time[J]. ACM Transaction on Mathematical Software, 1977, 3(3): 209-226.
[46] Omohundro S M. Efficient Algorithms with Nerual Network Behaviour[J]. Journal of Complex Systems, 1987, 1(2): 273-347.
[47] WouterG.vanToll,Altas F Cook, Roland Gerserts. A navigation mesh for dynamic environments[J]. Computer Animation and Virtual Worlds, 2012, 23(6): 535-546.
6
[48] Bourg D M, Seemann Glenn. AI for Game Developers[M]. O’Relly Press, 2004.[49] Devillers O. On deletion in Delaunay triangulations. Symposium on Computational Geometry[C].1999: 181-188.
7
致谢
时光荏苒，岁月如梭，在硕士两年的学习生活即将结束时，在本论文完成之际，我首先向我的导师XXX、XXX、XXX、XX、XX致以衷心的感谢！本论文的工作是在老师们的悉心指导下完成的。老师敏锐的洞察力、渊博的专业知识及严谨的教学态度、以及精益求精的工作作风给我留下了深刻的印象，并使我受益匪浅，成为我努力的目标。其次，我要向项目组老师XX和XX表示感谢，两位老师带领完成项目具体内容，老师思考问题的全面性，解决问题的方法都教会了我遇到实际问题时应考虑的关键要素，为以后在工作的方方面面打下基础。最后，我要向实验室项目组的同学表示真诚的感谢，项目的完成离不开大家的共同努力，在论文完成阶段遇到的困难，项目组的同学提供了很大的帮助，大家互帮互助的友情使我终身难忘。
在攻读硕士的这两年里，导师不仅为我提供了优越的学习环境和实验条件，而且在思想品德，人生态度上的谆谆教诲也必将激励着我在今后的人生道路上奋勇向前。
8
因篇幅问题不能全部显示，请点此查看更多更全内容