臺灣博碩士論文加值系統

多代理人系統(Multi-Agent system)在動態變化的環境中，能夠透過學習而做出最佳的回應動作是個極具挑戰性的問題。本研究運用機率架構與心理學家皮亞傑認知發展理論，發展一個認知行為學習方法，提供代理人區分動態環境的能力。根據皮亞傑認知發展理論將知識架構分成行為架構與認知架構，行為架構根據代理人間搜尋、合作與否區分成三種不同的策略並透過機率的方式推斷代理人可能行徑的路徑；認知架構透過案例庫方式儲存代理人的執行前狀態與執行的動作和執行後的狀態，當代理人遇到新的情況時，會先採用同化(Assimilation)技術解釋目前的現況，當發現架構不符合現況時，運用調適(Accommodation)調整代理人的認知架構，使得代理人更能適應多變的環境。最後使用Repast(The Recursive Porous Agent Simulation Toolkit)模擬多代理人的追捕競賽。

Multi-Agent system use learning to make the best response action is a challenging problem in a dynamic environment. This study use probabilistic formulation and Piaget‘s schema theory to develop Cognitive Behavioral Learning in a dynamic environment of pursuit-evasion game. We divide Piaget''s original schema into two parts; one is a perceptional schema and the other is an intentional schema. According to the agent’s state(search evader、individual learning、cooperative learning), Intentional schema proposes three strategy and uses probabilistic formulation to guess the evader’s position in next time steps; Perceptional schema use case base to save the agent’s state before action、action、state after action. When an agent faces a new situation, it might use assimilation to address the situation. If the current cognitive structure cannot explain the environment, Accommodation refers to the realization that the current structure is insufficient for ad-equate understanding of the world and that they must be changed until it can be assimilated. This study used the Recursive Porous Agent Simulation Toolkit (Repast) as the agent platform for implementing a multiagent system to demonstrate the proposed approach for the pursuit-evasion game.

摘 要 ii
ABSTRACT iii
致 謝 iv
目 錄 v
表目錄 vii
圖目錄 viii
第一章 緒論 1
1.1 前言 1
1.2 研究動機與目的 1
1.3 研究貢獻 2
1.4 章節編排 3
第二章 文獻探討 4
2.1多代理人系統 4
2.2 追捕競賽 5
2.3 案例式推論 7
2.4 同化與調適 9
2.5輕量雙架構模型(Light Dual-Schema Model) 10
第三章 代理人學習與合作方法 13
3.1案例新增 14
3.2 自信參數(Self-Confidence Parameter) 20
3.3案例學習 21
3.4代理人學習流程 25
第四章 案例研究 28
4.1問題描述 28
4.2系統架構圖 28
4.3系統實作 30
4.4獵物的逃跑策略 32
4.5實驗結果 36
4.6 相關研究比較 42
第五章 結論與未來展望 44
參考文獻 45

[1]A. Antoniades, H.J. Kim, S. Sastry, “Pursuit-Evasion Strategies for Teams of Multiple Agents with Incomplete Information,” in Proceedings of IEEE Conference on Decision and Control . Vol.1, pp. 756-761, 2003.
[2]A. Antoniades, H.J. Kim, S. Sastry, “Pursuit-evasion strategies for teams of multiple agents with incomplete information,” in Proceedings of IEEE Conference on Decision and Control. Vol.1, pp.756-761, 2003.
[3]A. Kumar and A. Ojha, “An Evader-Centric Strategy Against Fast Pursuer in an Unknown Environment with Static Obstacles,” International Conference on Control, Automation, Robotics and Embedded System, 2013
[4]D. J. Kwak, and H. J. Kim, “Probability Map Partitioning for Multi-player Pursuit-Evasion Game,” in Proceedings of International Conference on Control, Automation and Systems, 2010.
[5]E. Raboin, D. S. Nau, U. Kuter, S. K. Gupta, and P. Svec. “Strategy generation in multi-agent imperfect-information pursuit games, ” in Proceedings of International Conference on Autonomous Agents and Multi-agent Systems, pp. 947-954, 2010.
[6]F. Amigoni, and N. Basilico, “A Game Theoretical Approach to Finding Optimal Strategies for Pursuit Evasion in Grid Environments,” in IEEE International Conference on Robotics and Automation RiverCentre, pp. 2155-2162,2012.
[7]Fabricio Ferrari, “A new parameterized potential family for path planning algorithms, ” International Journal on Artificial Intelligence Tools, vol. 18,no.6, pp. 949-957, 2009.
[8]G. Oshanin, O. Vasilyev, P. L. Krapivsky, and J. Klafter, “Survival of an evasive prey, ” Proceedings of the National Academy of Sciences of the United States of America, vol.106, no.33, pp.13696-13701,2009
[9]http://ccl.northwestern.edu/netlogo
[10]http://education.mit.edu/starlogo
[11]http://jade.tilab.com/
[12]http://repast.sourceforge.net/
[13]http://www.swarm.org
[14]I. Partalas, I. Feneris, and I. P. Vlahavas, “A Hybrid Multiagent Reinforcement Learning Approach Using Strategies and Fusion.,” International Journal on Artificial Intelligence Tools, pp. 945-962, 2008.
[15]J. Piaget, “Cognitive Development in Children: Development and Learning,” Science teaching and the development of reasoning, University of California, Berkeley. 1964.
[16]J. Piaget. “The Equilibration of Cognitive Structures: a Central Problem of Intellectual Development”, Chicago: University of Chicago Press, 1985
[17]J. Y. Kuo and H. K. Cheng, “Applying Assimilation and Accommodation for Cooperative Learning of RoboCup Agent,” Machine Learning and Cybernetics, International Conference, vol. 6, pp. 3234 - 3239, 2010.
[18]J. Y. Kuo, Y.-Y. Fanjian, and S.-P. Ma, “A hybrid approach to multi-agent pursuit-evasion game,” in Proceedings of The International Conference on Machine Learning and Cybernetics, 2011.
[19]Jong Yih Kuo, Chien Feng Hsu,“Applying Assimilation and Accommodation for Cooperative Learning of Multi-Agent Pursuit-Evasion Strategies,” in Proceedings of International Conference on Manufacturing and Engineering Systems, 2010.
[20]Jong Yih Kuo, He Zhi Lin, “Cooperative RoboCup Agents Using Genetic Case-Based Reasoning,” in Proceedings of IEEE International Conference on Digital Object Identifier Systems, Man and Cybernetics,pp.613-618,2008.
[21]K. P. Sycara, “Multiagent Systems,” AI Magazine. Vol. 19, pp. 79-92, 1998.
[22]Kyle Walsh, “Fast A* with iterative resolution for navigation,” International Journal on Artificial Intelligence Tools, vol.19, no.1, pp. 101-119, 2010.
[23]L. Matignon, G.J. Laurent, and N. Le Fort-Piat, “Hysteretic q-learning: an algorithm for decentralized reinforcement learning in cooperative multi-agent teams,” in Proceedings of the International Conference on Intelligent Robots and Systems, pp. 64-69, 2007.
[24]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.
[25]Li-Pei Wong, Malcolm Yoke Hean Low, and Chin Soon Chong, “Bee colony optimization with local search for traveling salesman problem,” International Journal on Artificial Intelligence Tools, vol. 19,no.3, pp. 305-334, 2010.
[26]M. J. Santofimia, F. Moya, F. J. Villanueva, D. Villa, and J. C. Lopez, “Integration of Intelligent Agents Supporting Automatic Service Composition in Ambient Intelligence,” in Proceedings of IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, pp. 504 - 507, 2008.
[27]M. Nagao, and t. Miki, “Cooperative behavior generation method using local communication for distributed multi-agent systems ” in Systems Man and Cybernetics 2010, pp. 2886 - 2892.
[28]N. Basilico, N. Gatti, and F. Amigoni. “Leader-follower strategies for robotic patrolling in environments with arbitrary topologies,” in Proceedings of International Conference on Autonomous Agents and Multi-agent Systems, pp. 57-64, 2009.
[29]N. Vlassis. “A Concise Introduction to Multiagent Systems and Distributed Artificial Intelligence,” Synthesis Lectures on Artificial Intelligence and Machine Learning,2007.
[30]Nan-Peng Yu, Chen-Ching Liu, and James Price, “Evaluation of Market Rules Using a Multi-Agent System Method,” IEEE Transactions on Power System, vol.25, pp. 470-479, 2010.
[31]O.P.Rishi, Neelam Chaplot, “Archetype of Astrological Prediction System about Profession of any Persons’ using Case Based Reasoning, ” in Proceedings of International Conference on Communication and Computational Intelligence, pp. 373-377,2010
[32]P.G. Balaji and D. Srinivasa, “Multi-Agent System in Urban Traffic Signal Control, ” IEEE Computational Intelligence Magazine, Vol. 5,no. 4,pp 43-51,2010.
[33]Peitao Cheng, Ke Zhao, Yatao Li, Wei Xu, “Application of Case Based Reasoning in Plane Geometry Intelligent Tutoring System,” in Proceedings of International Conference on Electrical and Control Engineering , pp. 4369-4379,2010
[34]R. C. Schank, “Dynamic Memory: A Theory of Reminding and Learning in Computers and People,” Cambridge University Press, 1982.
[35]R. S. T. Lee and J. N. K. Liu, “iJADE Web-Miner: An Intelligent Agent Framework for Internet Shopping,” IEEE Transactions on knowledge and Data Engineering, vol. 16, pp. 461 - 473, 2004.
[36]Rajlich, V. Shaochun Xu. “Analogy of Incremental Program Development and Constructivist Learning,” The Second IEEE International Conference on Cognitive Informatics. pp. 98-105, 2003.
[37]S. D. Bopardikar, F. Bullo, and J. P. Hespanha, “On Discrete-Time Pursuit-Evasion Games With Sensing Limitations,” IEEE Transactions on Robotics, vol. 24, no. 6, pp. 1429-1439, 2008.
[38]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,2008.
[39]S. Takamuku, R.C. Arkin. “Multi-Method Learning and Assimilation”, Robotics and Autonomous Systems, 2007.
[40]S.Meyer-Nieberg, E Kropat, S. Pickl, and A. Bordetsky, “Intercepting a Target with Sensor Swarms,” International Conference on System Sciences, pp. 1222-1230, 2013
[41]T. Haynes and S. Sen, “Evolving behavioral strategies in predators and prey, ” Adaptation and Learning in Multi-agent Systems, Lecture Notes in Artificial Intelligence, pp. 113-126, 1995.
[42]T. Haynes and S. Sen, “Evolving behavioral strategies in predators and prey, ” Adaptation and Learning in Multi-agent Systems, Lecture Notes in Artificial Intelligence, Springer, pp. 113-126, 1995.
[43]T. Mukhopadhyay, S.S. Vicinanza, and M.J. Prietula, “Examining the Feasibility of a Case-Based Reasoning Model for Software Effort Estimation,” MIS Quarterly, vol.16,no.2, pp.155-171,1992.
[44]T. Parsons, “Pursuit-evasion in a graph,” Theory and Applications of Graphs, pp. 426-441, 1976
[45]T. Taniguchi, and T.Sawaragi, “Design and Performance of Symbols Self-organized within an Autonomous Agent Interacting with Varied Environments,” in Proceedings of the IEEE International Workshop on Robot and Human Interactive Communication Kurashik, pp. 89-94, 2004.
[46]T. Taniguchi, and T.Sawaragi, “Self-Organization of Inner Symbols for Chase: Symbol Organization and Embodiment,” in Proceedings of IEEE International Conference on Systems, Man and Cybernetics, vol. 2, pp. 10-13, 2004.
[47]Xu Chu Ding,Amr R. Rahmani and Magnus Egerstedt, “Multi-UAV Convoy Protection: An Optimal Approach to Path Planning and Coordination,” IEEE Transactions on Robotics, vol.26,no.1, pp. 256-268,2010.
[48]Y. Meng. Multi-robot searching using game-theory based approach. International Journal of Advanced Robotic Systems, vol. 5, no. 4, pp. 341-350, 2008.
[49]Y. Meng., “ Multi-robot searching using game-theory based approach,” International Journal of Advanced Robotic Systems, vol. 5, no.4, pp. 341-350, 2008.
[50]Z. Pucheng, and S. Huiyan, “Multi-agent Cooperation by Reinforcement Learning with Teammate Modeling and Reward Allotment,” International Conference on Fuzzy Systems and Knowledge Discovery, pp. 1316-1319, 2011.