本論文提出了一種混合型機器人路徑規劃演算法。其作法係利用影像形態學的知識，在已知環境地圖中建立一中軸地圖，並結合所提出的路徑規劃法搭配應用，使機器人可以直接將路徑規劃在地圖的中軸上。藉由此一作法，機器人得以在安全的路徑上移動，不但省去了處理避障或是重新規劃路徑的步驟，大幅減少執行路徑規劃時的計算成本，同時也提升了原始Dijkstra’s演算法與A*演算法的執行效率。最後，本論文也將此演算法實現於Android智慧型平台裝置以及NXT行動機器人上，以驗證所提出之混合型路徑規劃法之可行性。

This thesis proposes a hybrid path planning algorithm for mobile robots. Based on the iterative morphological methods, the hybrid path planning algorithm establishes a backbone path for the map. With the proposed path planning method, the robot can plan paths on the axis of the map. During the process, the hybrid path planning algorithm not only eliminates the need for re-processing obstacle avoidance or re-planning the path but also significantly reduces the cost of path planning computation. Moreover, this method improves the performance of the Dijkstra’s algorithm and the A* algorithm. Finally, this thesis also implements the proposed algorithm on the Android platform and the NXT robots to verify its practicability of the proposed hybrid path planning method.

[1] http://store.irobot.com/shop/index.jsp?categoryId=2804605
[2] http://www.ettoday.net/news/20130506/202648.htm
[3] http://www.pmc.org.tw/tg_view.aspx?type=Product&TGD_NO=103
[4] http://news.gamme.com.tw/423428
[5] http://lookstory.blogspot.tw/2011/05/blog-post_02.html
[6] M. Nakamiya, T. Terada, and S. Nishio, “A route planning method for multiple mobile sensor nodes,” 5th International Conference on Networked Sensing Systems, Osaka, Japan, 17-19 June 2008, pp.103-106.
[7] J. Guo, L. Liu, Q. Liu and Y. Qu, “An Improvement of D* Algorithm for Mobile Robot Path Planning in Partial Unknown Environment,” Second International Conference on Intelligent Computation Technology and Automation, Wuhan, China, 10-11 Oct. 2009,Vol.3, pp.394-397.
[8] Michael A. Goodrich, Potential Fields Tutorial, http://borg.cc.gatech.edu/ipr/files/goodrich_potential_fields.pdf
[9] H.C. Huang and C.C. Tsai,”Global path planning for autonomous robot navigation using hybrid metaheuristic GA-PSO algorithm,” SICE Annual Conference (SICE), Taichung, Taiwan, 13-18 Sept. 2011, pp.1338-1343.
[10] R. Wen, H.Y. Wang and J. Xie, “Path Planning of Mobile Robot Based on Voronoi Diagram by Approximation Structuring and Zonal Ant Colony Algorithm,” International Conference on Computational Intelligence and Software Engineering, Wuhan, China, 11-13 Dec. 2009, pp.1-4.
[11] P. E. Hart, N. J. Nilsson and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, vol.4, no.2, pp.100-107, July 1968.
[12] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol.1, no.1, pp 269-271, 1959.
[13] A Stentz, “Optimal and Efficient Path Planning for Partially-Known Environments,” IEEE International Conference on Robotics and Automation, San Diego, CA, 8-13 May, 1994, vol.4, pp.3310-3317.
[14] H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki and S. Thrun, Principles of Robot Motion: Theory, Algorithms, and Implementations, The MIT Press, 2005.
[15] L. Wang, L. Yong and M. H. Ang, “Hybrid of global path planning and local navigation implemented on a mobile robot in indoor environment,” Proceedings of the 2002 IEEE International Symposium on Intelligent Control, Singapore, 06 Feb., 2002, pp.821-826.
[16] R. Siegwart and I. R. Nourbakhsh, Introduction to Autonomous Mobile Robots, the MIT Press, 2004.
[17] http://www.cs.columbia.edu/~pblaer/projects/path_planner/
[18] C.C. Hsu, Y.J. Chen, M.C. Lu and S.A. Li, “Optimal Path Planning Incorporating Global and Local Search for Mobile Robots,” IEEE 1st Global Conference on Consumer Electronics (GCCE), Tokyo, Japan, 2-5 Oct., 2012, pp. 679-682.
[19] D. E. Shasha, C. A. Lazere, Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists, Copernicus, 1998.
[20] R.C. Prim, “Shortest connection networks and some generalizations,” Bell System Technical Journal, vol.36, no.6, pp. 1389–1401, 1957.
[21] 張真誠、蔡文輝、胡育誠，資料結構導論C語言實作，全華圖書公司，2007。
[22] I. Pohl, “First results on the effect of error in heuristic search,” Machine Intelligence, vol.5, pp.219-236. 1970.
[23] I. Pohl, “The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving,” Proceedings of the Third International Joint Conference on Artificial Intelligence (IJCAI-73), California, USA, August, 1973, pp. 11-17.
[24] D. M. Bourg and B. Seemann, AI for Game Developers, O’REILLY, 2005.
[25] A. McAndrew, An Introduction to Digital Image Processing with MATLAB, THOMSON, 2005.
[26] J. R. Parker, Algorithm for Image Processing and Computer Vision, Wiley Computer Publishing, 2010.
[27] T. Y. Zhang and C. Y. Suen, “A fast parallel algorithm for thinning digital patterns,” Communications of the ACM, vol. 27, no.3, pp. 236-239, 1984.
[28] L. Lam, S. Lee, and C. Suen, “Thinning Methodologies-A Comprehensive Survey,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol 14, no. 9, pp 869 - 885, Sep. 1992.
[29] Y. C. Ho and R. Lee, “A Bayesian approach to problems in stochastic estimation and control,” IEEE Transactions on Automatic Control, vol.9, no.4, pp. 333-339, Oct. 1964.
[30] 鍾鎮謙、宋開泰，運用雷射測距儀之機器人定位設計，國立交通大學電機與控制工程學系碩士論文，台灣，民國96年。
[31] S. Thrun, W. Burgard and D. Fox, Probabilistic Robotics, The MIT Press, 2005.
[32] http://en.wikipedia.org/wiki/Android_(operating_system)
[33] 吳雅峰、蘇亞光，深入淺出Android遊戲程式開發範例大全，博碩文化，2011。
[34] 曾吉弘、林毓祥、Juan Antonio，機器人程式設計與實作--使用JAVA，碁峯資訊，2010。
[35] http://lejos.sourceforge.net/
[36] http://lejos.sourceforge.net/nxt/nxj/api/index.html
[37] http://www.businesswire.com/news/home/20130516005342/en/Android-iOS-Combine-92.3-Smartphone-Operating-System
[38] http://shop.asus.com/store/asustw/zh_TW/pd/ThemeID.31533000/productID.280669900/categoryID.61631300
[39] http://mindstorms.lego.com/en-us/default.aspx
[40] http://en.wikipedia.org/wiki/Lego_Mindstorms_NXT
[41] 林毓祥、曾吉弘、CAVE教育團隊，Android/NXT機器人大戰—智慧型手機控制機器人，2011。
[42] http://www.jstuber.net/lego/nxt-programming/nxt-hardware.html
[43] http://www.mindsensors.com/index.php?module=pagemaster&PAGE_user_op=view_page&PAGE_id=57&MMN_position=24:24