臺灣博碩士論文加值系統

本篇論文針對協調多追捕者在動態的環境中合作追捕獵物提出追捕策略，我們的方法考慮不確定的環境因素將策略使用機率公式化，判斷代理人間彼此合作與否分成兩種不同的策略，並結合案例式推論使代理人能夠擁有記憶能力，最後運用皮亞傑同化調適的概念，透過我們所提出正角策略與斜角策略的組合對於代理人的認知架構進行同化調適，使其更能適應環境，我們將我們的方法應用在追捕遊戲中，並使用Repast(The Recursive Porous Agent Simulation Toolkit)實際模擬多代理人的情境。

This paper examines the problem of coordinating multiple robotic pursuers in locating and tracking a non-adversarial mobile evader in a dynamic environment. We have proposed two kinds of pursue strategies. One is for agents cooperate with one another. The other is for agents do not cooperate with each other. We consider the uncertain state information of the pursuers and the evaders, and we use a probabilistic formulation of the pursuit-evasion problem. We apply Case-based Reasoning to equip agents with memory and learning ability, and then we use the methods of positive-angle strategy and bevel-angle strategy based on the concept of Piaget’s assimilation and accommodation to let agents be able to adapt to environment easily and effectively.
We demonstrate our approach by a pursuit-evasion game, and then we use Repast (The Recursive Porous Agent Simulation Toolkit) as the agent platform to implement our multi-agent system.

摘 要 i
ABSTRACT ii
致謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 前言 1
1.2 研究動機與目的 1
1.3 研究貢獻 2
1.4 章節編排 3
第二章 文獻探討 4
2.1 BDI代理人模型 4
2.2 案例式推論 7
2.3 同化與調適 9
2.4 多代理人系統 10
2.5 追捕遊戲 11
第三章 代理人適應與合作學習方法 13
3.1 代理人模組 13
3.1.1 信念(Belief) 14
3.1.2 目標(Goal) 14
3.1.3 動作(Basic Action) 15
3.1.4 策略(Strategy) 15
3.1.5 計畫(Plan) 15
3.2 案例式推論 16
3.2.1 案例表示 16
3.2.2 案例擷取 17
3.2.3 案例重用與案例修改 17
3.3 策略模組產生計畫 19
3.3.1 機率架構 19
3.3.2 Local-max Strategy 20
3.3.3 Local-cooperative Strategy 20
3.4 計畫演化程序 21
3.5 回饋值計算 25
3.6 同化調適 25
3.6.1 策略調適 26
3.6.2 四斜角策略 26
3.6.3 四正角策略 28
3.6.4 策略組合 30
第四章 案例研究 32
4.1 問題描述 32
4.2 追捕者的心智狀態 32
4.3 獵物的逃跑策略 34
4.3.1 隨機移動 35
4.3.2 順時鐘移動 35
4.3.3 逆時鐘移動 36
4.3.4 智慧型移動 36
4.4 系統架構圖 37
4.5 系統實作 39
4.6 相關研究比較 41
4.7 實驗結果 43
4.7.1 實驗一 43
4.7.2 實驗二 44
4.7.3 實驗三 45
4.7.4 實驗四 46
第五章 結論與未來展望 48
參考文獻 49

[1]A. Rao, and M. Georgeff, “BDI Agents: From Theory to Practice”, International Conference on Multi-Agent Systems, 1995.
[2]A. S. Rao and M. P. Georgeff, “Modeling Rational Agents within a BDI-Architecture”, International Conference on Principles of Knowledge Representation and Reasoning, 1991.
[3]Marko Verbeek. “3APL as Programming Language for Cognitive Robots”, Master’s thesis, Utrecht University, 2003.
[4]E.C ten Hoeve, “3APL Platform”, Master’s thesis Computer Science, Utrecht University, 2003
[5]J. Y. Kuo, M. L. Tsai, and N. L. Hsueh, “Goal Evolution based on Adaptive Q-learning for Intelligent Agent”, IEEE International Conference on Systems, Man and Cybernetics. Taipei, Taiwan, 2006.
[6]R. C. Schank, R. P. Abelson, “Scripts, Plans, Goals and Understanding”, Erlbaum, Hillsdale, New Jersey, US, 1972.
[7]R. C. Schank, “Dynamic Memory: A Theory of Reminding and Learning in Computers and People”, Cambridge University Press, 1982.
[8]R. Schmidt, S. Montani, R. Bellazzi, L. Portinale and L. Gierl, “Cased-Based Reasoning for Medical Knowledge-Based Systems”, International Journal of Medical Informatics, Vol. 64, pp. 355-367, 2001.
[9]B. Bartsch-Spörl, M.Lenz, A. Hübner, “Case-Based Reasoning: Survey and Future Directions”, Proceedings of the 5th Biannual German Conference on Knowledge-Based Systems, Würzburg, Germany, pp. 67-89, 1999.
[10]P. Koton, “Reasoning about Evidence in Causal Explanations”, In Proceedings of the Seventh National Conference on Artificial Intelligence, pp. 260-270, 1988,
[11]Nguyen Hoang Phuong, N.R. Prasad, Dang Huu Hung; J.T. Drake, “Approach to Combining Case Based Reasoning with Rule Based Reasoning for Lung Disease Diagnosis”, International Conference on IFCA World Congress, Vol. 2, pp. 883-888, 2001.
[12]C. Vasudevan, “An Experience-Based Approach to Software Project Management”, International Conference on Tools with Artificial Intelligence. pp. 624-630, 1994.
[13]A. Hajipour, Y. Heydarzadeh, A.T. Haghighat, A. Bastanfard, "An Efficient Method for Logging Strategy Using Case Based Reasoning in Soccer Simulation", Third Asia International Conference on Modelling & Simulation, pp. 67-72, 2009.
[14]Jong Yih Kuo, He Zhi Lin, "Cooperative RoboCup Agents Using Genetic Case-Based Reasoning", IEEE International Conference on Digital Object Identifier Systems, Man and Cybernetics, pp. 613-618, 2008.
[15]A. Swaminathan, and K. S. Barber, “An Experience-Based Assembly Sequence Planner for Mechanical Assemblies”, IEEE Transactions on Robotics and Automation, Vol. 12, pp. 252-267, 1996.
[16]J. Piaget, “Cognitive Development in Children: Development and Learning”, Science teaching and the development of reasoning, University of California, Berkeley. 1964.
[17]J. Piaget. “The Equilibration of Cognitive Structures: a Central Problem of Intellectual Development”, Chicago: University of Chicago Press, 1985.
[18]S. Gebhardt, P. Grant, R. Georgi, M.T. Huber. “Aspects of Piaget’s Cognitive Developmental Psychology and Neurobiology of Psychotic Disorders – An Integrative Model”, Medical Hypotheses, Vol. 71, Issue 3, pp. 426-433, September 2008.
[19]Richard D. Mitchell. “Learning through Play and Pleasure Travel: Using Play Literature to Enhance Research into Touristic Learning”. Current Issues in Tourism. Vol. 1, Issue 2, pp. 176-188, July 1998.
[20]S. Takamuku, R.C. Arkin. “Multi-Method Learning and Assimilation”, Robotics and Autonomous Systems, 2007.
[21]Rajlich, V. Shaochun Xu. “Analogy of Incremental Program Development and Constructivist Learning”, The Second IEEE International Conference on Cognitive Informatics. pp. 98-105, 2003.
[22]M.J. Santofimia, F. Moya, F.J. Villanueva, D. Villa, J.C. Lopez, “Integration of Intelligent Agents Supporting Automatic Service Composition in Ambient Intelligence”, IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, pp. 504-507, 2008.
[23]L. Fei, Z. Guangzhou, “Multi-agent Cooperative Learning Research Based on Reinforcement Learning”, International Conference on Digital Object Identifier, pp. 1-6, 2006.
[24]R. Ueda, K. Sakamoto, K. Takeshita, T. Arai, “Dynamic Programming for Creating Cooperative Behavior of Two Soccer Robots - Part 1: Computation of State-Action Map”, IEEE International Conference on Robotics and Automation, pp. 1-7, 2007.
[25]T. Parsons, “Pursuit-Evasion in a Graph”, Theory and Applications of Graphs, Springer-Verlag, pp. 426-441, 1976.
[26]R. Breisch, “An Intuitive Approach to Speleotopology”, Southwestern Cavers (A publication of the Southwestern Region of the National Speleological Society), pp. 72-78, 1967.
[27]L.M. Kirousis, C.H. Papadimitriou, “Interval Graphs and Searching”, Discrete Math. Vol. 55, pp. 181-184, 1985.
[28]L.M. Kirousis, C.H. Papadimitriou, “Searching and Pebbling”, Theoretical Computer Science. Vol.47, pp. 205-218, 1986.
[29]D. Bienstock, P. Seymour, “Monotonicity in Graph Searching”, Journal of Algorithms. Vol. 12, pp. 239-245, 1991.
[30]G. Gottlob, N. Leone, F. Scarcello, “Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width”, Journal of Computer and System Sciences. Vol. 66, pp. 775-808, 2003.
[31]R. Nowakowski, P. Winkler, “Vertex-to-Vertex Pursuit in a Graph”, Discrete Math. Vol. 43, pp. 235-239, 1983.
[32]M. Aigner, M. Fromme, “A Game of Cops and Robbers”, Discrete Applied Mathematics. Vol. 8, pp. 1-11. 1984.
[33]R. Vidal, O. Shakernia, H.J. Kim, D.H. Shim, S. Sastry, “Probabilistic Pursuit-Evasion Games: Theory, Implementation, and Experimental Evaluation”, IEEE Transactions on Robotics and Automation. Vol. 18, pp. 662-669, 2002.
[34]A. Antoniades, H.J. Kim, S. Sastry, “Pursuit-Evasion Strategies for Teams of Multiple Agents with Incomplete Information”, IEEE Conference on Decision and Control. Vol. 1, pp. 756-761, 2003.
[35]N.N. Petrov, M.A. Teteryatnikova, “Some Problems of the Search on Graphs with Retaliation”, Vestnik St. Petersburg University Mathmatic. Vol. 37, pp. 37-43, 2004.
[36]V.Y. Andrianov, N.N. Petrov, “Graph Searching Problems with the Counteraction, in: Game Theory and Applications”, Game theory and applications, Vol.10, pp. 1-12, 2005.
[37]L. Matignon, G.J. Laurent, N. Le Fort-Piat, “Hysteretic Q-Learning: an Algorithm for Decentralized Reinforcement Learning in Cooperative Multi-Agent Teams.” International Conference on Intelligent Robots and Systems, pp. 64-69, 2007.
[38]Ioannis Partalas, Ioannis Feneris, Ioannis P. Vlahavas, “A Hybrid Multi-Agent Reinforcement Learning Approach Using Strategies and Fusion.” International Journal on Artificial Intelligence Tools. Vol. 17, No. 5, pp. 945-962, 2008.
[39]K. P. Sycara, “Multiagent Systems”, AI Magazine. Vol. 19, pp. 79-92, 1998.
[40]N. Vlassis. “A Concise Introduction to Multi-agent Systems and Distributed Artificial Intelligence”, Synthesis Lectures on Artificial Intelligence and Machine Learning. 2007.
[41]L. J. Guibas, J.-C. Latombe, S. M. LaValle, D. Lin, and R. Motwani. “A Visibility-Based Pursuit-Evasion Problem.” International Journal of Computational Geometry and Applications. Vol. 9, pp. 471-493, 1999.
[42]J. P. Hespanha, G. J. Pappas, and M. Prandini. “Greedy Control for Hybrid Pursuit-Evasion Games.” In Proceedings of the European Control Conference, pp. 2621-2626, 2001.
[43]Korf R. E. “A Simple Solution to Pursuit Games.” In Working Papers of the 11th International Workshop on Distributed Artificial Intelligence, pp. 183-194, 1992.
[44]Stefano Nolfi, Dario Floreano. “Coevolving Predator and Prey Robots: Do”Arms Races” Arise in Artificial Evolution?” Artificial Life, Vol. 4, pp. 337-357, 1998.
[45]J. Savill Nicholas, Paulien Hogeweg. “Evolutionary Stagnation due to Pattern-Pattern Interactions in a Co-Evolutionary Predator-Prey Model.” Artificial Life, Vol. 3, pp. 81-100, 1997.
[46]Shin I. Nishimura, Takashi Ikegami. “Emergence of Collective Strategies in a Prey-Predator Game Model.” Artificial Life, Vol. 3, pp. 243-260, 1997.
[47]Larry M. Stephens, Matthias B. Merx. “The Effect of Agent Control Strategy on the Performance of a dai Pursuit Problem.” In Proceedings of the 10th International Workshop on DAI, 1990.
[48]T. Haynes, S. Sen, “Evolving Behavioral Strategies in Predators and Prey.” Adaptation and Learning in Multiagent Systems, Lecture Notes in Artificial Intelligence. Springer Verlag: Berlin, Germany, pp. 113-126, 1995.
[49]D. Hladek, J. Vascak, P. Sincak. “Hierarchical Fuzzy Inference System for Robotic Pursuit Evasion Task.” International Symposium on Applied Machine Intelligence and Informatics. pp. 273-277, 2008.
[50]R. G. Smith, “The Contract-Net Protocol: High-Level Communication and Control in a Distributed Problem Solver”, IEEE Transaction on Computers, Vo1. 19, No. 12, pp. 1104-1113, 1980.
[51]Pu-Cheng Zhou, Bing-Rong Hong, Yue-Hai Wang, Tong Zhou. “Multi-Agent Cooperative Pursuit Based On Extended Contract Net Protocol.” International Conference on Machine Learning and Cybernetics, Vol. 1, pp. 169-173, 2004.
[52]S.F. Railsback, S.L. Lytinen, S.K. Jackson, “Agent-Based Simulation Platforms: Review and Development Recommendations.” SIMULATION. Vol. 82, pp. 609-623, 2006.
[53]Fan Jiancong, Ruan Jiuhong, Liang Yongquan, Tang Leiyu. “A PSO Solution for Pursuit-Evasion Problem of Randomly Mobile Agents”, Conference on Control and Decision, 2009.
[54]http://education.mit.edu/starlogo
[55]http://www.swarm.org
[56]http://ccl.northwestern.edu/netlogo
[57]http://repast.sourceforge.net/