基于統(tǒng)計(jì)的對(duì)手模型及在規(guī)劃中的應(yīng)用

全文42頁(yè) 約20000字 論述翔實(shí)

目 錄
目 錄 2
摘 要 4
ABSTRACT 5
第一章 緒論 6
第二章 對(duì)手建模 9
2.1 對(duì)手模型的起源和研究意義 9
2.1.1 經(jīng)典博奕 9
2.1.2 敵對(duì)搜索中的應(yīng)用 10
2.1.3 多主體環(huán)境中的應(yīng)用 11
2.2 多主體環(huán)境中的對(duì)手建模 11
2.2.1 BDI模型 11
2.2.2 利用信念網(wǎng)絡(luò)從觀察到的情況識(shí)別主體的行為 12
2.2.3 DFA學(xué)習(xí)MAS的對(duì)手建模 13
第三章 ROBOCUP中的對(duì)手模型 14
3.1 ROBOCUP環(huán)境介紹 14
3.1.1 RoboCup 14
3.1.2 仿真機(jī)器人足球 15
3.1.3 對(duì)手建模挑戰(zhàn) 18
3.1.4 在線教練比賽 18
3.2 現(xiàn)有的對(duì)手建模手段 19
3.2.1 理想模型 19
3.2.2 位置概率模型 19
3.2.3 基于特征的模型 20
3.2.4 總結(jié) 21
第四章 基于統(tǒng)計(jì)的對(duì)手模型 22
4.1 思想來(lái)源 22
4.1.1跟蹤多個(gè)主體的思想 22
4.1.2自動(dòng)建模的思想 22
4.1.3將主體行為與環(huán)境結(jié)合形成事件的思想 22
4.1.4非馬爾可夫的思想和統(tǒng)計(jì)方法 23
4.2 模型描述 23
4.2.1主體行為的定義 23
4.2.2事件的定義 23
4.2.3對(duì)手模型的定義 24
4.3 建立對(duì)手模型 24
4.3.1主體行為和事件的識(shí)別 24
4.3.2利用字符樹(shù)（Trie）統(tǒng)計(jì)觀察到的事件序列 25
4.3.3對(duì)手模型預(yù)測(cè)函數(shù) 26
4.3.4和其他相關(guān)工作的比較 30
第五章 在ROBOCUP中的統(tǒng)計(jì)對(duì)手模型建立 31
5.1 球員行為的定義和識(shí)別 31
5.2 具體模型建立過(guò)程算法 33
5.2.1主導(dǎo)行為和輔助行為的區(qū)別 33
5.2.2解決輔助行為在預(yù)測(cè)沖突 34
第六章 ROBOCUP規(guī)劃中的應(yīng)用及實(shí)驗(yàn)結(jié)果 35
6.1 防守盯人規(guī)劃 35
6.2 實(shí)驗(yàn)結(jié)果 36
第七章 總結(jié) 38
參考文獻(xiàn) 39
致 謝 42

摘 要
多主體系統(tǒng)（Multi-Agent Systems）是當(dāng)前人工智能研究的主要方向之一，主體和多主體系統(tǒng)在動(dòng)態(tài)、不可預(yù)測(cè)的環(huán)境中的適應(yīng)性將在很大程度上決定其的研究能否滿足實(shí)際應(yīng)用的基本要求。研究在動(dòng)態(tài)的、有競(jìng)爭(zhēng)和合作的多主體的環(huán)境中其他主體的建模，以及基于對(duì)手模型的規(guī)劃是提高主體和多主體系統(tǒng)適應(yīng)性的重要手段，因而對(duì)其他主體的建模和基于該模型的規(guī)劃的研究越來(lái)越受到國(guó)內(nèi)外研究者的重視。
筆者在文中介紹并分析以往研究者相關(guān)工作的優(yōu)點(diǎn)和不足（必須事先假定主體內(nèi)部結(jié)構(gòu)，或者需要事先根據(jù)人的經(jīng)驗(yàn)手工編碼的方式建立可能的模式庫(kù)，和不能跟蹤多個(gè)主體的合作行為），然后在基于統(tǒng)計(jì)的外部建模方法和筆者自己前一階段工作[20][21][22]的基礎(chǔ)上綜合改進(jìn)，提出了一種基于統(tǒng)計(jì)方法的對(duì)手模型(包括模型表示方式、建模算法和用于預(yù)測(cè)時(shí)的算法)。該模型能夠（1）不需事先定義模式庫(kù)，通過(guò)分析觀察輸入在線建模；（2）跟蹤、描述和預(yù)測(cè)多個(gè)主體的合作行為。從而增加了模型的靈活性與可信度，使得分析并預(yù)測(cè)主體的意圖和團(tuán)隊(duì)的策略以及針對(duì)對(duì)手的規(guī)劃成為可能，彌補(bǔ)以往對(duì)手模型的不足。筆者還在RoboCup仿真機(jī)器人足球比賽（一個(gè)近年來(lái)已成檢驗(yàn)多智能系統(tǒng)研究成果的一個(gè)公共平臺(tái)）中實(shí)現(xiàn)了該模型，并將該模型用于球隊(duì)的防守規(guī)劃中，本文介紹了這些工作。
關(guān)鍵字：多主體系統(tǒng)，對(duì)手建模,卡方相關(guān)性檢測(cè)，機(jī)器人足球

ABSTRACT
Multi-Agent Systems (MAS) is now one of the main directions in international Artificial Intelligence research. Whether research on agents and MAS can satisfy the basic requirements of the practical applications depends, to a great extent, on the adaptability of agents and Multi-Agent Systems in dynamic and unexpected environments. It is an effective approach to improve agents’ or MAS’s adaptability to model other agents in dynamic and unexpected Multi-Agent environment in which agents compete or cooperate with each other, and then carry out planning based on the opponent model. Hence, more and more researchers put emphases upon the study of opponent modeling and planning based on opponent model.
Author analyzed both advantages and deficiency (opponent’s reasoning architecture and pattern library have to be defined beforehand or unable to track the cooperative actions of multiple agents) of former researchers’ related works. And then basing on the statistical external modeling method and author’s previous work [20][21][22], this paper present a statistical opponent model, which is composed by the model representation, the model constructing algorithm and the predicting algorithm. Comparing to previous models, this model is more flexible and reliable, and can trace multiple agents’ cooperative actions to make analyzing agent’s intention and team’s strategy and adversarial planning possible. Author implemented this model in RoboCup Simulation Soccer domain, and used it in the defending planning. This thesis will describe above work in details.
Keywords: Multi-Agent Systems, Opponent Modeling, Robot Soccer, Chi-Square Dependency Test

部分參考文獻(xiàn)

[15] D. Carmel and S. Markovitch. Opponent modeling in multi-agent systems. In G. Weiss and S. Sen, editors, Adaptation and Learning in Multi-Agent Systems, Lecture Notes in Artificial Intelligence. IJCAI’95 Workshop, Springer, 1995.

[16] G. A. Kaminka, M. Fidanboylu, A. Chang, and M. Veloso, Learning the Sequential Behavior of Teams from Observations. In Proceedings of the 2002 RoboCup Symposium.

[17] R. L. Kurse, A. J. Ryba. Data Structures and Program Design in C++. Chapter 11, Apr. 2001 published.

[18] 陳小平. 關(guān)于慎思式適應(yīng). 計(jì)算機(jī)科學(xué), Vol.29, No.9(S), 49-51

[19] H. Kitano, M. Tambe, P. Stone, M. Veloso, S. Coradeschi, E. Osawa, H. Matsubara, I. Noda, and M. Asada. The RoboCup synthetic agent challenge 97. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, pages 24–29, San Francisco, CA, 1997. Morgan Kaufmann.

[20] Zhanxiang Huang, Y. Yang, X. Chen, An Approach to Plan Recognition and Retrieval for Multi-agent Systems, accepted by the Workshop on Adaptability in Multi-Agent Systems, Jan.27-Feb.1, 2003, University of New South Wales, Sydney, Australia.