臺灣博碩士論文加值系統

我們研究在虛擬世界中，利用加強式學習實作 avatar ，使之能夠
自主探索環境，並且找出自目前所在地到達指定目標的路徑出來。
我們的 avatar 所面對的為動態、可變、範圍廣大且複雜的環境；而這
樣的環境存在著一些問題：維度的困擾及如何適應新環境。
在範圍廣大且複雜的環境之中的學習，我們使用了將 inputs 構
成 state-space ，然後將 state-space 分割為 cells 的方法，取代在廣大且複雜的環境裡隨著範圍的增廣， inputs 的增加而呈指數性成長
的 states ，以達成降低運算、儲存資源的目標。
然後再提出一系列的 cells 的操作，使得當環境發生改變時 cells 的
範圍可以動態修正、調整以適應新的環境；更進一步提出一個概念
上的 global-cell ，藉由調整 global-cell 的比重，控制 avatar 的探險的傾向，以應變環境改變可能造成的新的行進路線。

The main topic in this thesis is to implement an avatar using reinforcement-learning such that it can explore the environment, and find the way out to reach the goal we assigned. We focus on the environment which is dynamicallly changable, continuous and large-scaled. There is some problems in such environment, like “curse of dimensionality”and how to adapt the changed environment.

1 序論1
1.1 研究動機. . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 研究內容. . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 相關研究4
2.1 Reinforcement-learning . . . . . . . . . . . . . . . . . . . . 4
2.2 The Parti-game Algorithm for Variable Resolution Reinforcement
Learning in Multidimensional State-spaces . . . . . . . 6
2.3 Coordination of Exploration and Exploitation in a Dynamic
Environment . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 系統架構11
3.1 Cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Transitions . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3 Cells Establishment and Manipulation . . . . . . . . . . . . 17
3.3.1 以Min-Max Hyperbox 實作. . . . . . . . . . . . . 19
3.4 Reinforcement-Learning on Cells . . . . . . . . . . . . . . . 27
3.5 Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.6 Exploitation and Exploration . . . . . . . . . . . . . . . . . 32
3.7 系統概觀. . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.7.1 探險新環境. . . . . . . . . . . . . . . . . . . . . 41
3.7.2 已經充分學習過後的環境. . . . . . . . . . . . . 42
3.7.3 當環境發生改變. . . . . . . . . . . . . . . . . . . 43
4 實驗與研究成果44
4.1 實驗環境. . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 First Try . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3 繼續學習. . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.4 環境改變. . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5 結論與未來研究57
5.1 本系統的優點. . . . . . . . . . . . . . . . . . . . . . . . 57
5.1.1 降低龐大的記憶及運算資源. . . . . . . . . . . . 57
5.1.2 對動態環境的適應良好. . . . . . . . . . . . . . . 57
5.2 目前已知問題與未來研究方向. . . . . . . . . . . . . . . 58

R. E. Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, 1957.
Andrew W. Moore, Leslie Pack Kaelbling, and Michael L. Littman. Reinforcement learning: A survey. Journal of Artificial Intelligence Research, 4:237—285, 1996.
A. W. MOORE. The parti-game algorithm for variable resolution reinforcement learning in multidimensional state-spaces. In Cowan, J. D., Tesauro, G., & Alspector, L.(Eds.), Advances in Neural Information Processing System 6, pages 711—718. San Mateo, CA. Morgan Kaufmann., 1994.
P. K. Simpson. Fuzzy min-max neural networks. I. Classification. Neural Networks, IEEE Transactions, 3:776—786, 1992.
Gary Yen, Fengmin Yang, Travis Hickey, and Michel Goldstein. Coordination of exploration and exploitation in a dynamic environment,
2001.