本研究主要探討無人機在室內進行搜索的演算法。現今無人機的應用越來越廣泛，然而，過去受限於無人機的導航方式多靠 GPS 訊號，使得無人機僅能在室外的空間使用，對於室內空間的自主飛行與應用則少見於文獻。李和蕭在 2016 年提出並驗證使用立體視覺進行無人機導航的可行性，使得無人機在室內自主飛行的可行性大增，因此本論文主要探討無人機如何在通道曲折，並有多個房間與叉路的室內，將飛行器飛至特定地點的路徑規畫方式。由於室內環境常常有多通道連通，本研究將之類比於迷宮，並把目前人工智慧對於機器鼠走迷宮的研究，應用到本主題。在本問題中，由於建築物可能有許多層，因此本研究把建築物的內部視為一立體迷宮，使用增強學習中的 Q-Learning 求解。此研究成果將大幅增加無人機的室內應用性。

This paper investigates the indoor path planning of an autonomous drone. Nowadays, drones have wider and wider applicability. However, due to the limitation of GPS navigation, drones are usually applied in an outdoor environment. Lee and Hsiao proposed an algorithm regarding indoor navigation using a stereo vision system in 2016, and this extends the application of drones to indoor environments. Hence, this paper investigates the path planning of a drone based on the stereo-vision navigation. The characteristics that there exist hallways, rooms, and folks in the road is similar to that of a maze. Therefore, algorithm of the path planning in a maze for a robot is employed in this paper. In our research, we apply the Q-Learning in the enforced learning to solve the indoor searching problem, and try to extend this algorithm to a 3D maze in the future. The result of our research will extend the applicability of drones to indoor domain in the future.

目錄
1 緒論 1
1.1 研究動機 ............................... 1 
1.2 文獻回顧 ............................... 2 
1.3 研究方法 ............................... 2
2 機器學習 4 
2.1 概述.................................. 4 
2.2 增強學習 ............................... 5 
2.3 馬可夫決策過程(MDPs)....................... 6 
2.4 Q-Learning .............................. 7 
2.5 Q-Learning演算法與樓層探索....................10
3 模擬環境與參數 14 
3.1 測試環境 ...............................14 
3.2 建築物搜索..............................16 
3.3 參數調校 ...............................17
4 迷宮模擬 27 
4.1 模擬結果 ...............................27 
4.1.1 10×10模擬結果 .......................27 
4.1.2 建築物模擬..........................36
5 結論與未來展望 42 
5.1 結論..................................42 
5.2 未來展望 ...............................43
參考文獻 44
附錄 A 47

圖目錄
2.1 增強學習系統............................. 6 
2.2 馬可夫鍊/馬可夫過程 ........................ 6 
2.3 馬可夫決策過程............................ 7 
2.4 Q-LearningAlgorithm ........................10 
2.5 Q-Learning環境 ...........................11 
2.6 流程圖.................................13
3.1 迷宮環境-第一層 ...........................14 
3.2 迷宮環境-第二層 ...........................15 
3.3 淡江大學新工學大樓四樓3D圖...................16 
3.4 淡江大學新工學大樓四樓平面圖 ..................16 
3.5 α=0.1 ................................17 
3.6 α=0.3 ................................18 
3.7 α=0.5 ................................18 
3.8 α=0.7 ................................19 
3.9 α=0.9 ................................19 
3.10 γ = 0.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 
3.11 γ = 0.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 
3.12 γ = 0.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 
3.13 γ = 0.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.14 γ = 0.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 
3.15 γ = 0.99 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 
3.16 ε = 0.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 
3.17 ε = 0.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 
3.18 ε = 0.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 
3.19 ε = 0.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 
3.20 ε = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1 學習次數:100 ............................29 
4.2 學習次數:300 ............................29 
4.3 學習次數:500 ............................30 
4.4 學習次數:1000............................30
4.5 學習次數:1500............................31 
4.6 學習後路徑..............................32 
4.7 學習次數:2000(目標為樓梯) ....................33 
4.8 第二層學習次數:2000........................34 
4.9 第二層學習次數:2000(死路) ....................34 
4.10 第一層學習路徑 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 
4.11第二層學習後路徑 ..........................35 
4.12縮小比例的建築物 ..........................36 
4.13 建築物學習次數:15000 . . . . . . . . . . . . . . . . . . . . . . . 36 
4.14 建築物學習次數:20000 . . . . . . . . . . . . . . . . . . . . . . . 37 
4.15 3 樓學習次數:30000 . . . . . . . . . . . . . . . . . . . . . . . . . 38 
4.16 4 樓學習次數:30000 . . . . . . . . . . . . . . . . . . . . . . . . . 38 
4.17 5 樓學習次數:30000 . . . . . . . . . . . . . . . . . . . . . . . . . 39 
4.18 6 樓學習次數:30000 . . . . . . . . . . . . . . . . . . . . . . . . . 39 
4.19 8 樓學習次數:30000 . . . . . . . . . . . . . . . . . . . . . . . . . 40 
4.20 8 樓學習次數:30000 . . . . . . . . . . . . . . . . . . . . . . . . . 40 
4.21 4樓路徑圖 ..............................41 
4.22 5樓路徑圖 ..............................41
A1 工學大樓3F..............................47
A2 工學大樓4F..............................48
A3 工學大樓5F..............................48
A4 工學大樓6F..............................49
A5 工學大樓7F..............................49
A6 工學大樓8F..............................50

表目錄
2.1 Q值變化 ...............................12
4.1 參數設定 ...............................27 
4.2 測試硬體 ...............................37

[1] 李柏儀. “使用三維全景重建法進行電腦視覺導航.” 淡江大學航空太空工程學系碩士班學位論文 (2016): 1-86.
[2] Swati Mishra and Pankaj Bande. Maze solving algorithms for micro mouse. Signal Image Technology and Internet Based Systems, 2008. SITIS’08. IEEE International Conference on. IEEE, 2008.
[3] Manoj Sharma. Algorithms for Micro-mouse. Future Computer and Com- munication, 2009. ICFCC 2009. International Conference on. IEEE, 2009.
[4] Cai, Jianping et al. A micromouse maze sovling simulator. Future Com- puter and Communication (ICFCC), 2010 2nd International Conference on. Vol. 3. IEEE, 2010.
[5] Jitin Kumar Goyal and Kuldeep Singh Nagla. A new approach of path planning for mobile robots. Advances in Computing, Communications and Informatics (ICACCI), 2014 International Conference on. IEEE, 2014.
[6] Jianping Cai et al. An algorithm of micromouse maze solving. Computer and Information Technology (CIT), 2010 IEEE 10th International Confer- ence on. IEEE, 2010.
[7] Jie Zhan, Xianchun Li, and Jiawei He. The simulation research of search algorithm for computer mouse maze. Wireless Communications, Network-ing and Mobile Computing (WiCOM 2014), 10th International Conference on. IET, 2014.
[8] Richard Bellman. A Markovian decision process. Journal of Mathematics and Mechanics. 6. 1957.
[9] Richard Bellman. Dynamic Programming. Princeton university press, 1957.
[10] Chris Watkins and Peter Dayan. Q-learning. Machine learning 8.3-4 (1992): 279-292.
[11] Walter Pullen. Maze Classification. from http://www.astrolog.org/ labyrnth/algrithm.htm
[12] José Vidal. Fundamentals of multiagent systems: using netLogo models. system (2006).
[13] Stuart Russell and Peter Norvig. 人工智慧-現代方法(歐崇明、時文中、 陳龍譯)(台北:培生教育,2011)。
[14] Chris Watkins. Learning from delayed rewards. Diss. University of Cam- bridge, 1989.
[15] Tim Eden, Anthony Knittel and Raphael van Uffelen. Reinforcement Learning. from http://www.cse.unsw.edu.au/~cs9417ml/RL1/index.html
[16] David Poole and Mackworth Alan. Artificial Intelligence: foundations of computational agents Cambridge University Press, 2010.
[17] Mehmet Hacibeyoglu and Ahmet Arslan. Reinforcement learning accel- erated with artificial neural network for maze and search problems. 3rd International Conference on Human System Interaction. IEEE, 2010.
[18] Tom Schaul et al. PyBrain. Journal of Machine Learning Research 11.Feb (2010): 743-746.
[19] David Silver. Markov Decision Processes. ULC, 2015
[20] Python Software Foundation. Python Documentation. from https://docs. python.org/3/