1. NCCU Academic Hub
  2. 學術產出
  3. College of Informatics
  4. Theses
  5. Item

學術產出-Theses

Article View/Open

Publication Export

Google ScholarTM

政大圖書館

Citation Infomation

  • No doi shows Citation Infomation
題名 以演化方式模擬人群運動行為
Simulating Crowd Motion with Evolutionary Computation
作者 王智賢
Wang, Chih-Chien
貢獻者 李蔡彥
Li, Tsai-Yen
王智賢
Wang, Chih-Chien
關鍵詞 電腦動畫
人群運動模擬
基因演算法
多代理人系統
運動隊伍組態
computer animation
crowd motion simulation
genetic algorithm
Multiple Agent System
Motion Formation
日期 2005
上傳時間 17-Sep-2009 14:05:57 (UTC+8)
摘要 近年來，在電腦動畫的應用中，虛擬人群模擬的需求越來越多；但人群運動的模擬對於動畫設計師而言，仍是一件十分繁瑣耗時的工作。過去有許多研究曾以虛擬力場模擬簡單的生物群聚行為，但所模擬出的動畫品質與虛擬力場的參數及虛擬環境息息相關，因此經常需要以人工的方式耗時地調整出適當的虛擬力場參數。因此，我們提議以此問題定義成一個基因演算法的問題，針對不同的移動行為，定義適切的適應函數，再由系統根據不同環境自動演化出適當的虛擬力權重組合，以供產生不同人群移動行為之動畫時參考。在本篇論文中，我們已完成基因演算法的設計及人群動畫模擬系統，並設計了不同的典型環境進行電腦模擬實驗，以驗證此方法的可行性。
The demands for virtual crowd simulation have been increasing in recent years but creating realistic crowd motions remains a complex and time-consuming task for a computer animator. In the literature、much work has been proposed to use virtual forces to simulate the motion of a group of virtual creatures such as birds and fishes. However、the quality of the simulations largely depends on the weights of the component virtual forces as well as the scene where the agents are situated. Usually it requires the animator to tune these parameters for a specific scene in order to obtain the desired result. In this thesis、we propose to use genetic algorithm to generate an optimal set of weighting parameters for composing virtual forces according to the given environment and desired movement behavior. We have implemented the proposed genetic algorithm as well as the crowd simulation system. Extensive experiments have also been conducted to study the effects of typical scenes and behaviors on the parameter sets and verify the feasibility of the approach.
參考文獻 [1] AntZ.、http://www.antz.com
[2] ActiveWorld、http://www.activeworlds.com/
[3] R. Aylett and M. Cavazza、「Intelligent Virtual Environment a State of the Art Report,」 Proceedings of Eurographics 2001-STARs、2001.
[4] M. Anderson、E. McDaniel、and S. Chenney、「Constrained Animation of Flocks,」 Proceedings of ACM SIGGRAPH/Eurographics Symposium on Computer Animation 2003、pp. 286–297、2003.
[5] Bugs Life.、http://bugslife.com
[6] O. B. Bayazit、J.-M. Lien、and N. M. Amato,「Better Flocking Behaviors in Complex Environments Using Global Roadmaps,」 Proceedings of the 1995 IEEE/RSJ International Conference on Intelligent Robots and Systems、pp. 528-534、1995.
[7] E. Bouvier、E. Cohen、and L. Najman.、「From Crowd Simulation to Airbag Deployment: Particle Systems、a New Paradigm of Simulation,」 Journal of Electronic Imaging、Vol. 6、No.1、pp. 94-107、1997.
[8] D. Brogan and J. Hodgins、「Group Behaviors for Systems with Significant Dynamics,」 Autonomous Robots、4、pp. 137-153、1997.
[9] D.C. Brogan、R.A. Metoyer、and J.K. Hodgins、「Dynamically Simulated Characters in Virtual Environments,」 IEEE Computer Graphics and Applications、Vol. 18、No5、pp. 58-69、1998.
[10] A. Braun、S. R. Musse、L. P. L. de Oliveira、and B. E. J. Bodmann、「Modeling Individual Behaviors in Crowd Simulation,」 Proceedings of CASA: Computer Animation & Social Agents、pp. 143-148、2003.
[11] J. J. Fruin、Pedestrian Planning and Design. Metropolitan Association of Urban Designers and Environmental Planners、1971.
[12] J. Funge、X. Tu、and D. Terzopoulos、「Cognitive Model: Knowledge、Reasoning、and Planning for Intelligent Characters,」 Proceedings of ACM SIGGRAPH、pp. 29-38、1999.
[13] N. Farenc、R. Boulic、and D. Thalman、「An Informed Environment Dedicated to the Simulation of Virtual Humans in Urban Context,」 Proceedings of EUROGRAPHICS、pp. 309-318、1999.
[14] N.Farenc、S. Musse、and E. Schweiss、「A Paradigm for Controlling Virtual Humans in Urban Environment Simulations,」 Applied Artificial Intelligence、Vol. 14、pp. 69-91、2000.
[15] J. Grefenstette、「Optimization of Control Parameters for Genetic Algorithms」、IEEE Transactions on Systems、Man and Cybernetics、Vol.16 、pp. 122-128、1986.
[16] J.H. Holland、Adaptation in Natural and Artificial Systems. The University of Michigan Press、Ann Arbor、MI、1975.
[17] D. Helbing and P. Molnar、「Social Force Model for Pedestrian Dynamics,」 Physical Review、pp. 4282-4286、1995.
[18] D. Helbing、I. Farkas、and T. Vicsek、「Simulating Dynamical Features of Escape Panic,」 Nature、407(28):487–490、2000.
[19] J.C. Latombe、Robot Motion Planning、Kluwer、Boston、MA、1991.
[20] T.Y. Li、Y.J Jeng、and S.I Chang、「Simulating Virtual Human Crowds with a Leader-Follower Model,」 Proceedings of the Computer Animation Conference、pp. 93-102、2001.
[21] J.R. Koza、Genetic Programming： On the Programming of Computers by Means of Natural Selection、Cambridge、MA、MIT Press、1992.
[22] M. Kallmann、A. Aubel、T. Abaci、and D. Thalmann、「Planning Collision-Free Reaching Motions for Interactive Object Manipulation and Grasping,」 Computer 86 Graphic Forum、Vol. 22、pp. 313-322、2003.
[23] A. Kamphuis and M. H. Overmars、「Finding Path for Coherent Groups using Clearance,」 ACM SIGGRAPH/Eurographics Symposium on Computer Animation、pp.193-202、2004.
[24] M. Mitchell、An Introduction to Genetic Algorithms、Cambridge、MA 、MIT Press、1998.
[25] G. A. Miller、「The Magical Number Seven、Plus or Minus Two: Some :Limits on Our Capacity for Processing Information」 Psychological Review、Vol. 63、pp. 81–97、1956.
[26] Massive、http://www.massivesoftware.com
[27] S.R. Musse and D. Thalmann、「Hierarchical Model for Real Time Simulation of Virtual Human Crowds,」 IEEE Transactions on Visualization and Computer Graphics、7(2)、pp. 152–164、2001.
[28] G. Mitsuo and C. Runwei、Gentic Algorithms & Engineering Design、John Wily & Sons. Inc、1997.
[29] T.Osaragi、「Modeling of Pedestrian Behavior and Its Application to Spatial Evaluation,」 Proceedings of Autonomous Agents and Multiagent Systems、Vol. 2、pp. 836–843、2004.
[30] C.W. Reynolds、「Flocks、Herds、and Schools: A Distributed Behavioral Model,」 Computer Graphics、pp. 25-34、1987.
[31] C.W. Reynolds、「Steering Behaviors for Autonomous Characters,」 Proceedings of Game Developers Conference、pp. 763-782、1999.
[32] S. J. Rymill and N. A. Dodgson、「Psychologically-Based Vision and Attention for the Simulation of Human Behaviour,」 Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia、pp. 229-236、2005.
[33] M. Sung、M. Gleicher、and S. Chenney.、「Scalable Behaviors for Crowd Simulation,」 Computer Graphics Forum、23(3):519–528、2004.
[34] G. K. Still、Crowd Dynamics、PhD thesis、University of Warwick、UK、2000.
[35] N. Saiwaki、T. Komatsu、T. Yoshida、and S. Nishida、「Automatic Generation of Moving Crowd Using Chaos Model,」 Proceedings of IEEE Conference on System、Man and Cybernetics、pp. 3715-3721、1997.
[36] F. Tecchia、C. Loscos、Y. Chrysanthou、「Visualizing Crowds in Real-Time,」 Computer Graphics Forum、Vol. 21、2002.
[37] Takeshi Sakuma、Tomohiko Mukai、and Shigeru Kuriyama、「Psychological Model for Animating Crowded Pedestrians,」 Proceedings of CASA: Computer Animation & Social Agents、pp. 343-351、2005.
[38] J.B. Victor and J.L. Adler、「Emergent Fundamental Pedestrian Flows from Cellular Automata Microsimulation,」 Transportation Research Record 1644、pp. 29-36、1998.
[39] J.B. Victor and J.L. Adler、「Cellular Automata Microsimulation for Modeling Bi-directional Pedestrian Walkways,」 Transportation Research Part B、35、pp. 293-312、2001.
描述 碩士
國立政治大學
資訊科學學系
90750322
94
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0907530222
資料類型 thesis
dc.contributor.advisor 李蔡彥zh_TW
dc.contributor.advisor Li, Tsai-Yenen_US
dc.contributor.author (Authors) 王智賢zh_TW
dc.contributor.author (Authors) Wang, Chih-Chienen_US
dc.creator (作者) 王智賢zh_TW
dc.creator (作者) Wang, Chih-Chienen_US
dc.date (日期) 2005en_US
dc.date.accessioned 17-Sep-2009 14:05:57 (UTC+8)-
dc.date.available 17-Sep-2009 14:05:57 (UTC+8)-
dc.date.issued (上傳時間) 17-Sep-2009 14:05:57 (UTC+8)-
dc.identifier (Other Identifiers) G0907530222en_US
dc.identifier.uri (URI) https://nccur.lib.nccu.edu.tw/handle/140.119/32705-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 90750322zh_TW
dc.description (描述) 94zh_TW
dc.description.abstract (摘要) 近年來，在電腦動畫的應用中，虛擬人群模擬的需求越來越多；但人群運動的模擬對於動畫設計師而言，仍是一件十分繁瑣耗時的工作。過去有許多研究曾以虛擬力場模擬簡單的生物群聚行為，但所模擬出的動畫品質與虛擬力場的參數及虛擬環境息息相關，因此經常需要以人工的方式耗時地調整出適當的虛擬力場參數。因此，我們提議以此問題定義成一個基因演算法的問題，針對不同的移動行為，定義適切的適應函數，再由系統根據不同環境自動演化出適當的虛擬力權重組合，以供產生不同人群移動行為之動畫時參考。在本篇論文中，我們已完成基因演算法的設計及人群動畫模擬系統，並設計了不同的典型環境進行電腦模擬實驗，以驗證此方法的可行性。zh_TW
dc.description.abstract (摘要) The demands for virtual crowd simulation have been increasing in recent years but creating realistic crowd motions remains a complex and time-consuming task for a computer animator. In the literature、much work has been proposed to use virtual forces to simulate the motion of a group of virtual creatures such as birds and fishes. However、the quality of the simulations largely depends on the weights of the component virtual forces as well as the scene where the agents are situated. Usually it requires the animator to tune these parameters for a specific scene in order to obtain the desired result. In this thesis、we propose to use genetic algorithm to generate an optimal set of weighting parameters for composing virtual forces according to the given environment and desired movement behavior. We have implemented the proposed genetic algorithm as well as the crowd simulation system. Extensive experiments have also been conducted to study the effects of typical scenes and behaviors on the parameter sets and verify the feasibility of the approach.en_US
dc.description.tableofcontents 第一章 導論 1
1.1研究動機 1
1.2 研究目標 3
1.3系統架構與流程說明 4
1.3.1人群的定義 4
1.3.2系統模組說明 5
1.4本論文的貢獻 9
1.5本研究的限制 9
1.6論文章節架構 10
第二章 相關研究 11
2.1分子系統 11
2.2行為系統 14
2.3機器人運動計畫演算法 16
第三章 虛擬人個體運動模型 19
3.1群眾的個體設計架構 19
3.2虛擬力的設計 21
3.3碰撞機制設計 29
3.3.1調準力策略 30
3.3.2四方向策略 31
3.3.3群體軌道參考策略 32
3.3.4七方向策略 33
第四章 人群移動行為的演化機制 34
4.1基因演算法 35
4.1.1演算法流程說明 36
4.1.2編碼方式 37
4.1.3適應函數 37
4.1.4族群初始化 37
4.1.5基因演算法的基本運算元說明 38
4.2人群移動的演化機制 39
4.3人群移動的適應函數定義 40
4.3.1群眾之間所保持的相對距離 42
4.3.2群眾與目標物的相對距離 43
4.3.3模擬過程中人群移動所發生的碰撞次數 44
4.3.4人群面向角度在時間上的一致性 45
4.3.5人群相對距離的恆常性 46
第五章 實驗設計 48
5.1情境環境的說明 48
5.2實驗設計與實驗結果 51
5.2.1群聚移動行為 53
5.2.2鬆散移動行為 58
5.2.3追隨移動行為 61
5.2.4包圍移動行為 64
5.2.5移動一致性行為 67
第六章 結論與未來研究方向 76
6.1結論 76
6.2未來研究方向 76
參考文獻 78		zh_TW
dc.format.extent 47207 bytes-
dc.format.extent 72996 bytes-
dc.format.extent 59058 bytes-
dc.format.extent 75859 bytes-
dc.format.extent 169300 bytes-
dc.format.extent 259609 bytes-
dc.format.extent 212214 bytes-
dc.format.extent 244756 bytes-
dc.format.extent 551775 bytes-
dc.format.extent 73816 bytes-
dc.format.extent 44553 bytes-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0907530222en_US
dc.subject (關鍵詞) 電腦動畫zh_TW
dc.subject (關鍵詞) 人群運動模擬zh_TW
dc.subject (關鍵詞) 基因演算法zh_TW
dc.subject (關鍵詞) 多代理人系統zh_TW
dc.subject (關鍵詞) 運動隊伍組態zh_TW
dc.subject (關鍵詞) computer animationen_US
dc.subject (關鍵詞) crowd motion simulationen_US
dc.subject (關鍵詞) genetic algorithmen_US
dc.subject (關鍵詞) Multiple Agent Systemen_US
dc.subject (關鍵詞) Motion Formationen_US
dc.title (題名) 以演化方式模擬人群運動行為zh_TW
dc.title (題名) Simulating Crowd Motion with Evolutionary Computationen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] AntZ.、http://www.antz.comzh_TW
dc.relation.reference (參考文獻) [2] ActiveWorld、http://www.activeworlds.com/zh_TW
dc.relation.reference (參考文獻) [3] R. Aylett and M. Cavazza、「Intelligent Virtual Environment a State of the Art Report,」 Proceedings of Eurographics 2001-STARs、2001.zh_TW
dc.relation.reference (參考文獻) [4] M. Anderson、E. McDaniel、and S. Chenney、「Constrained Animation of Flocks,」 Proceedings of ACM SIGGRAPH/Eurographics Symposium on Computer Animation 2003、pp. 286–297、2003.zh_TW
dc.relation.reference (參考文獻) [5] Bugs Life.、http://bugslife.comzh_TW
dc.relation.reference (參考文獻) [6] O. B. Bayazit、J.-M. Lien、and N. M. Amato,「Better Flocking Behaviors in Complex Environments Using Global Roadmaps,」 Proceedings of the 1995 IEEE/RSJ International Conference on Intelligent Robots and Systems、pp. 528-534、1995.zh_TW
dc.relation.reference (參考文獻) [7] E. Bouvier、E. Cohen、and L. Najman.、「From Crowd Simulation to Airbag Deployment: Particle Systems、a New Paradigm of Simulation,」 Journal of Electronic Imaging、Vol. 6、No.1、pp. 94-107、1997.zh_TW
dc.relation.reference (參考文獻) [8] D. Brogan and J. Hodgins、「Group Behaviors for Systems with Significant Dynamics,」 Autonomous Robots、4、pp. 137-153、1997.zh_TW
dc.relation.reference (參考文獻) [9] D.C. Brogan、R.A. Metoyer、and J.K. Hodgins、「Dynamically Simulated Characters in Virtual Environments,」 IEEE Computer Graphics and Applications、Vol. 18、No5、pp. 58-69、1998.zh_TW
dc.relation.reference (參考文獻) [10] A. Braun、S. R. Musse、L. P. L. de Oliveira、and B. E. J. Bodmann、「Modeling Individual Behaviors in Crowd Simulation,」 Proceedings of CASA: Computer Animation & Social Agents、pp. 143-148、2003.zh_TW
dc.relation.reference (參考文獻) [11] J. J. Fruin、Pedestrian Planning and Design. Metropolitan Association of Urban Designers and Environmental Planners、1971.zh_TW
dc.relation.reference (參考文獻) [12] J. Funge、X. Tu、and D. Terzopoulos、「Cognitive Model: Knowledge、Reasoning、and Planning for Intelligent Characters,」 Proceedings of ACM SIGGRAPH、pp. 29-38、1999.zh_TW
dc.relation.reference (參考文獻) [13] N. Farenc、R. Boulic、and D. Thalman、「An Informed Environment Dedicated to the Simulation of Virtual Humans in Urban Context,」 Proceedings of EUROGRAPHICS、pp. 309-318、1999.zh_TW
dc.relation.reference (參考文獻) [14] N.Farenc、S. Musse、and E. Schweiss、「A Paradigm for Controlling Virtual Humans in Urban Environment Simulations,」 Applied Artificial Intelligence、Vol. 14、pp. 69-91、2000.zh_TW
dc.relation.reference (參考文獻) [15] J. Grefenstette、「Optimization of Control Parameters for Genetic Algorithms」、IEEE Transactions on Systems、Man and Cybernetics、Vol.16 、pp. 122-128、1986.zh_TW
dc.relation.reference (參考文獻) [16] J.H. Holland、Adaptation in Natural and Artificial Systems. The University of Michigan Press、Ann Arbor、MI、1975.zh_TW
dc.relation.reference (參考文獻) [17] D. Helbing and P. Molnar、「Social Force Model for Pedestrian Dynamics,」 Physical Review、pp. 4282-4286、1995.zh_TW
dc.relation.reference (參考文獻) [18] D. Helbing、I. Farkas、and T. Vicsek、「Simulating Dynamical Features of Escape Panic,」 Nature、407(28):487–490、2000.zh_TW
dc.relation.reference (參考文獻) [19] J.C. Latombe、Robot Motion Planning、Kluwer、Boston、MA、1991.zh_TW
dc.relation.reference (參考文獻) [20] T.Y. Li、Y.J Jeng、and S.I Chang、「Simulating Virtual Human Crowds with a Leader-Follower Model,」 Proceedings of the Computer Animation Conference、pp. 93-102、2001.zh_TW
dc.relation.reference (參考文獻) [21] J.R. Koza、Genetic Programming： On the Programming of Computers by Means of Natural Selection、Cambridge、MA、MIT Press、1992.zh_TW
dc.relation.reference (參考文獻) [22] M. Kallmann、A. Aubel、T. Abaci、and D. Thalmann、「Planning Collision-Free Reaching Motions for Interactive Object Manipulation and Grasping,」 Computer 86 Graphic Forum、Vol. 22、pp. 313-322、2003.zh_TW
dc.relation.reference (參考文獻) [23] A. Kamphuis and M. H. Overmars、「Finding Path for Coherent Groups using Clearance,」 ACM SIGGRAPH/Eurographics Symposium on Computer Animation、pp.193-202、2004.zh_TW
dc.relation.reference (參考文獻) [24] M. Mitchell、An Introduction to Genetic Algorithms、Cambridge、MA 、MIT Press、1998.zh_TW
dc.relation.reference (參考文獻) [25] G. A. Miller、「The Magical Number Seven、Plus or Minus Two: Some :Limits on Our Capacity for Processing Information」 Psychological Review、Vol. 63、pp. 81–97、1956.zh_TW
dc.relation.reference (參考文獻) [26] Massive、http://www.massivesoftware.comzh_TW
dc.relation.reference (參考文獻) [27] S.R. Musse and D. Thalmann、「Hierarchical Model for Real Time Simulation of Virtual Human Crowds,」 IEEE Transactions on Visualization and Computer Graphics、7(2)、pp. 152–164、2001.zh_TW
dc.relation.reference (參考文獻) [28] G. Mitsuo and C. Runwei、Gentic Algorithms & Engineering Design、John Wily & Sons. Inc、1997.zh_TW
dc.relation.reference (參考文獻) [29] T.Osaragi、「Modeling of Pedestrian Behavior and Its Application to Spatial Evaluation,」 Proceedings of Autonomous Agents and Multiagent Systems、Vol. 2、pp. 836–843、2004.zh_TW
dc.relation.reference (參考文獻) [30] C.W. Reynolds、「Flocks、Herds、and Schools: A Distributed Behavioral Model,」 Computer Graphics、pp. 25-34、1987.zh_TW
dc.relation.reference (參考文獻) [31] C.W. Reynolds、「Steering Behaviors for Autonomous Characters,」 Proceedings of Game Developers Conference、pp. 763-782、1999.zh_TW
dc.relation.reference (參考文獻) [32] S. J. Rymill and N. A. Dodgson、「Psychologically-Based Vision and Attention for the Simulation of Human Behaviour,」 Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia、pp. 229-236、2005.zh_TW
dc.relation.reference (參考文獻) [33] M. Sung、M. Gleicher、and S. Chenney.、「Scalable Behaviors for Crowd Simulation,」 Computer Graphics Forum、23(3):519–528、2004.zh_TW
dc.relation.reference (參考文獻) [34] G. K. Still、Crowd Dynamics、PhD thesis、University of Warwick、UK、2000.zh_TW
dc.relation.reference (參考文獻) [35] N. Saiwaki、T. Komatsu、T. Yoshida、and S. Nishida、「Automatic Generation of Moving Crowd Using Chaos Model,」 Proceedings of IEEE Conference on System、Man and Cybernetics、pp. 3715-3721、1997.zh_TW
dc.relation.reference (參考文獻) [36] F. Tecchia、C. Loscos、Y. Chrysanthou、「Visualizing Crowds in Real-Time,」 Computer Graphics Forum、Vol. 21、2002.zh_TW
dc.relation.reference (參考文獻) [37] Takeshi Sakuma、Tomohiko Mukai、and Shigeru Kuriyama、「Psychological Model for Animating Crowded Pedestrians,」 Proceedings of CASA: Computer Animation & Social Agents、pp. 343-351、2005.zh_TW
dc.relation.reference (參考文獻) [38] J.B. Victor and J.L. Adler、「Emergent Fundamental Pedestrian Flows from Cellular Automata Microsimulation,」 Transportation Research Record 1644、pp. 29-36、1998.zh_TW
dc.relation.reference (參考文獻) [39] J.B. Victor and J.L. Adler、「Cellular Automata Microsimulation for Modeling Bi-directional Pedestrian Walkways,」 Transportation Research Part B、35、pp. 293-312、2001.zh_TW