近年來，虛擬世界的研究與發展持續進行，各種虛擬世界的應用也越來越廣泛。在可預期的未來，在虛擬世界進行各種模擬實驗及工作，或是在虛擬世界中進行人與人之間的交流將是一項趨勢。
虛擬環境中除了行為代理人之外，還有著其他各式各樣的物件、地形、道具、障礙物等等。在一個具合作競爭性質的互動式虛擬環境中，行為代理人時時刻刻都必須注意周圍環境的變化，以自己的存活為第一優先考量，並持續與環境中之物件進行互動，掌握虛擬環境中的所有資訊，以期能在第一時間之內做出適當的反應。當行為代理人與其他行為代理人組成隊伍時，會與同伴們互相合作，以達到彼此間的共同目的。除此之外，行為代理人可能隨時都會接收到隊伍的隊長的命令，行為代理人在接到命令之後就會依照接到命令種類的不同，照著行為特徵以及流程依序去完成隊長所交付的任務。
本篇論文提出一個方法，當使用者的行為代理人在隊伍中扮演一個攻擊者的角色時，在接收到隊長的攻擊命令之後，該如何以安全且有效率的方式去完成此項任務。

In the recent past, the research and development of virtual environment are continuously, and application is widely. In the future, it will be a trend that simulating, experimentation, working, and communication among human beings in the virtual environment.
There are several types of landform and object in the environment. For example, obstacle and item, etc. Avatars are pay attention to the situation in a cooperative and rival interactive virtual environment. Keeping alive is the most important thing for avatars in this environment. An avatar makes decision in real-time depends on the information searching and collecting. An avatar cooperatives with its teammates. When an avatar receive a command of the leader of a team, it executes commands in different method with the different command.
This thesis proposes a method, how an avatar which plays a role of an attacker finishes the mission that received by the leader of the team with safe and efficient way.

目錄

第一章 序論...............................................1
1.1 研究動機..........................................1
1.2 研究目的..........................................1
1.3 論文架構..........................................2

第二章 相關背景知識與技術.................................4
2.1 互動式虛擬環境（Interactive Virtual Environment）..................................................4
2.2 Smart Object......................................5
2.3 智慧型行為代理人（Intelligent Behavior Avatar）...6
2.4 人工位能場方法（Potential Field Method）..........7
2.5 擴散現象（Diffusion）............................10
2.6 滲透現象（Osmosis）..............................11

第三章 研究內容與方法....................................13
3.1 系統架構（System Architecture）..................13
3.2 選擇適當的攻擊位置（Choose Attack Position）.....17
3.2.1 選擇適合之攻擊區域（Choose Attack Area）...19
3.2.2 規劃適合掩蔽的區域（Plan Cover Area）......23
3.2.3 選擇適當的攻擊位置（Choose Attack Position）.............................................25
3.3 規劃路徑前往目的地（Path Planning）..............27
3.3.1 使用PFM規劃路徑（Path Planning with Potential Field Method）.....................27
3.3.2 使用Diffusion Method規劃路徑（Path Planning with Diffusion Method）......................36
3.3.3 使用Diffusion Method並加入Osmosis機制規劃路徑（Path Planning with Diffusion Method combining with Osmosis Mechanism）...........44

第四章 模擬實作與結果討論................................48
4.1 模擬實作說明.....................................48
4.1.1 模擬實作目標...............................49
4.1.2 模擬環境說明...............................49
4.2 模擬過程.........................................53
4.2.1 模擬決定攻擊位置...........................53
4.2.2 模擬路徑規劃...............................60
4.2.2.1 使用Potential Field Method模擬路徑規劃.............................................60
4.2.2.2 使用Diffusion Method模擬路徑規劃........75
4.2.2.3 使用Diffusion Method combining with Osmosis Mechanism模擬路徑規劃...............84
4.3 結果討論.........................................87
4.3.1 選擇適合的攻擊位置.........................87
4.3.2 規劃路徑前往目的地.........................87
4.3.2.1 Potential Field Method...................88
4.3.2.2 Diffusion Method.........................88

第五章 結論及未來研究方向................................90

附錄.....................................................93
附錄1 Potential Field Method Pseudo Code............93
附錄2 Difgfusion Method Pseudo Code.................97
附錄3 Diffusion Method combining with Osmosis Mechanism Pseudo Code...........................101

參考文獻................................................106



圖目錄

圖2-1 Interactive Virtual Environment示意圖.............5
圖2-2 Intelligent Behavior Avatar示意圖[Chao, 2004].....6
圖2-3 空間中位能場示意圖[Khatib, 1986]..................8
圖2-4 規劃機器人手臂進入封閉空間示意圖[Khatib, 1986]....8
圖2-5 機器人迴避持續移動之障礙物前往目標地點示意圖[Spence, 1995].......................................9
圖2-6 機械手臂迴避朝自己接近中之障礙物示意圖[Spence, 1995]................................................9
圖2-7 機器人規劃射門路徑示意圖[Tews, 1999], [Tews, 2000] ....................................................10
圖2-8 擴散現象示意圖...................................11
圖2-9 滲透現象示意圖...................................12
圖3-1 互助競爭模式下之IVE示意圖.......................15
圖3-2 Avatar行為流程圖.................................16
圖3-3 Avatar選擇攻擊點流程圖...........................18
圖3-4 以Obstacle為中心劃分虛擬環境圖..................19
圖3-5 由Attack Area與Firing Line規劃出之Cover Area...24
圖3-6 Avatar選擇之Attack Position示意圖...............25
圖3-7 Avatar規劃路徑前往Attack Position示意圖.........26
圖3-8 虛擬環境中之Object產生位能場示意圖..............28
圖3-9 Potential Field Method流程圖.....................29
圖3-10 Avatar利用Potential Field Method規劃移動路徑示意圖..................................................33
圖3-11 吸引類型之位能值遠大於排斥類型之位能值示意圖....34
圖3-12 吸引類型與排斥類型之位能值加總之後，導致Avatar無法判斷路徑示意圖....................................34
圖3-13 Avatar規劃路徑時產生震盪情形示意圖..............35
圖3-14 老鼠走迷宮之Shortest Path示意圖................37
圖3-15 老鼠走迷宮時使用Exploitation和Exploration示意圖....................................................38
圖3-16 起司散發香味路徑示意圖..........................38
圖3-17 Diffusion Method流程圖..........................40
圖3-18 使用Queue模擬擴散現象示意圖....................41
圖3-19 Avatar利用擴散方法找出通往Goal之路徑示意圖.....41
圖3-20 無法使用Diffusion Method規劃路徑示意圖.........42
圖3-21 Diffusion Method combining with Osmosis Mechanism流程圖..............................................45
圖4-1 虛擬環境中敵方Avatar位於Area02時，己方Avatar與障礙物分布圖..........................................54
圖4-2 虛擬環境中敵方Avatar位於Area02時，Avatar規劃之適合攻擊區域與Target Avatar之Firing Line............55
圖4-3 虛擬環境中敵方Avatar位於Area02時，依據攻擊區域以及Firing Line所規劃出之掩蔽區域及其命中率圖........55
圖4-4 Avatar規劃路徑前往攻擊位置圖.....................56
圖4-5 敵方Avatar位於Area01時所規劃出之掩蔽區域及其命中率圖................................................57
圖4-6 敵方Avatar位於Area03時所規劃出之掩蔽區域及其命中率圖................................................57
圖4-7 敵方Avatar位於Area04時所規劃出之掩蔽區域及其命中率圖................................................58
圖4-8 敵方Avatar位於Area06時所規劃出之掩蔽區域及其命中率圖................................................58
圖4-9 敵方Avatar位於Area07時所規劃出之掩蔽區域及其命中率圖................................................59
圖4-10 敵方Avatar位於Area08時所規劃出之掩蔽區域及其命中率圖................................................59
圖4-11 敵方Avatar位於Area09時所規劃出之掩蔽區域及其命中率圖................................................60
圖4-12 虛擬環境中Avatar與Goal之示意圖................61
圖4-13 Avatar計算虛擬環境中Object產生PFM分佈圖.......62
圖4-14 Avatar規劃路徑圖................................62
圖4-15 有障礙物存在之虛擬環境示意圖....................63
圖4-16 虛擬環境中有障礙物之PFM所形成之區域圖..........64
圖4-17 虛擬環境中有障礙物時規劃之路徑圖................64
圖4-18 有敵人存在之虛擬環境示意圖......................65
圖4-19 虛擬環境中有敵人之PFM所形成之區域圖............65
圖4-20 虛擬環境中有敵人時規劃之路徑圖..................66
圖4-21 虛擬環境中同時存在有障礙物及敵人示意圖..........66
圖4-22 虛擬環境中同時存在有障礙物及敵人時所形成之PFM區域圖..................................................67
圖4-23 虛擬環境中同時有障礙物及敵人時規劃之路徑圖......67
圖4-24 一般在實際情形下之虛擬環境中的Object分佈圖.....68
圖4-25 利用PFM實際模擬路徑規劃時之PFM區域圖..........69
圖4-26 利用PFM實際模擬路徑規劃圖......................69
圖4-27 原先規劃之路徑被阻擋時，重新規劃之PFM區域圖....70
圖4-28 原先規劃之路徑被阻擋時，重新規劃之路徑圖........71
圖4-29 PFM無法規劃路徑之虛擬環境示意圖.................72
圖4-30 無法規劃路徑之PFM區域圖........................72
圖4-31 PFM規劃之路徑圖.................................73
圖4-32 將吸引性質之位能值的參數調高後之PFM區域圖......74
圖4-33 將吸引性質之位能值的參數調高後規劃出之路徑圖....74
圖4-34 Diffusion Method擴散至全虛擬環境圖（1）.........76
圖4-35 使用Diffusion Method規劃路徑圖（1）............76
圖4-36 Diffusion Method擴散至全虛擬環境圖（2）.........77
圖4-37 使用Diffusion Method規劃路徑圖（2）............78
圖4-38 Diffusion Method擴散至全虛擬環境圖（3）.........78
圖4-39 使用Diffusion Method規劃路徑圖（3）............79
圖4-40 Diffusion Method擴散至全虛擬環境圖（4）.........79
圖4-41 使用Diffusion Method規劃路徑圖（4）............80
圖4-42 Diffusion Method規劃出複數路徑圖................81
圖4-43 使用Diffusion Method並依據環境中之風險值選取最安全的路徑圖..........................................81
圖4-44 利用Diffusion Method在一般的虛擬環境中之擴散圖....................................................82
圖4-45 利用Diffusion Method在一般的虛擬環境中之規劃路徑圖..................................................83
圖4-46 利用Diffusion Method擴散至全虛擬環境圖.........83
圖4-47 利用Diffusion Method規劃路徑圖.................84
圖4-48 Diffusion Method規劃路徑圖......................85
圖4-49 Diffusion Method combining with Osmosis Mechanism擴散圖..............................................85
圖4-50 Diffusion Method combining with Osmosis Mechanism規劃路徑圖..........................................86 



表目錄

表3-1 攻擊目標分析表....................................20
表3-2 遭受反擊分析表....................................21
表3-3 距離目標分析表....................................22
表3-4 攻擊區域分析表....................................22
表3-5 攻擊區域選擇表....................................23
表4-1 模擬環境架設平台所使用之軟硬體設備表..............48
表4-2 虛擬環境之物件屬性說明表..........................50
表4-3 虛擬環境之物件行為說明表..........................51
表4-3虛擬環境中代表各物件之代號對照表...................52
表5-1 PFM與Diffusion Method之優缺點比較表..............91

參考文獻

1.[Brock, 1999], Oliver Brock, Oussama Khatib, "Real-time obstacle avoidance and motion coordination in a multi-robot workcell ", Proceedings of the 1999 IEEE International Symposium on Assembly and Task Planning Proto, Portugal, July 1999.
2.[Chao, 2004], Hsiao-Chuan Chao, "Constructing an Intelligent Behavior Avatar in a Virtual World : A Self-Learning Model based on Reinforcement", Thesis report, University of TamKang, Tamsui, Taiwan, 2004.
3.[Crank, 1979], John Crank, "The Mathematics of Diffusion Second Edition", Oxford University Press, United Kingdom, March 1979.
4.[Ford, 1992], Brian J Ford, "Brownian Movement In Clarkia Pollen: A Reprise Of The First Observations", The Microscope, Vol.40, No.4, pp.235-241, 1992.
5.[Hung, 2003], Haw-Yun Hung, "Building an intelligent Behavior Avatar in a Virtual World", Thesis report, University of TamKang, Tamsui, Taiwan, 2003.
6.[Jensen, 2001], Finn V. Jensen, "Bayesian Networks and Decision Graphs", Springer-Verlag Inc., New York, 2001.
7.[Jiming, 1999], Jiming, Ning Zhong, "Intelligent Agent Technology Systems, Methodologies, and Tools", Proceedings of the 1st Asia-Pacific Conference on Intelligent Agent Technology (IAT '99), Hong Kong, December 1999.
8.[Kent, 1998], Chris Kent, "Basics of Toxicology", Wiley Publishing, Inc., America, September 1998.
9.[Khatib, 1986], Oussama Khatib, "Real-Time Obstacle Avoidance for Manipulators and Bobile Robots", The International Journal of Robotics Research, Vol.5, No.1, pp.90-96, Spring 1986.
10.[Kim, 1997], Heung-Soo Kim, Hyun-Sik Shim, Myung-Jin Jung, Jong-Hwan Kim, "Action Selection Mechanism for Soccer Robot", Proceedings of IEEE international Symposium on Computational Intelligence in Robotics and Automation, pp.390-395, 1997.
11.[Mulder, 1996], Mulder, J., "Basic Principles of Membrane Technology Second Edition", Springer-Verlag Inc., New York, 1996.
12.[Sevin, 2001], E.de Sevin, M.Kallmann, D.Thaimann, "Towards real time virtual human life simulations", Computer Graphics International 2001.Proceedings , pp.31-37, Hong Kong, China, July 2001.
13.[Sng, 2002], Sng H.L., G. Sen Gupta, C.H. Messom, "Strategy for Collaboration in Robot Soccer", Proceedings of the First IEEE International Workshop on Electronic Design, Test and Applications (DELTA.02), Singapore Polytechnic, 2002.
14.[Spence, 1995], Rob Spence, Seth Hutchinson, "An integrated architecture for robot motion planning and control in the presence of obstacles with unknown trajectories", IEEE Transactions on Systems, Man, and Cybernetics., Vol.25, No.1, January 1995.
15.[Sutton, 1998], R.S.Sutton and A.G.Barto, "Reinforcement Learning", MIT Press, Cambridge, MA, 1998.
16.[Tews, 1999], Ashley Tews, Gordon Wyeth, "Multi-Robot Coordination in the Robot Soccer Environment", University of Queensland, Australia, 1999.
17.[Tews, 2000], Ashley Tews, Gordon Wyeth, "MAPS: A System for Multi-Agent Coordination", Revised Paper Submission for Advanced Robotics Journal Special Issue on RoboCup, University of Queensland, Australia, 2000.