隨著時代的發展，科技智能家居產品也逐漸普及化，近年來自主性機器人相關研究文獻可說是呈現指數型成長，尤其是大部分的自主性機器人都離不開同步定位與建置（Simultaneous Localization and Mapping, SLAM）的技術應用。而對於一個完整性高的自主機器人，除了要具備自身定位的能力外，最重要的是還必須具備自主移動的能力，因此路徑規劃演算法是非常重要的一環。對於現有路徑規劃演算法之相關研究，雖然能解決最佳路徑之問題，但大多數都假設在靜態理想環境下才能實現，對於實際應用價值並不高。對此，本論文會基於SLAM所提供的格點地圖為基礎，針對目前應用廣泛的路徑規劃演算法進行相關的深入探討，透過了解路徑規劃演算法的特性並在其架構基礎上進行優化及改良，並考慮具有移動情況下之動態路徑規劃，整合成一個能夠在實際環境下擁有更高強健性的路徑規劃演算法。此外本論文也會基於所開發的路徑規劃演算法進行不同策略的路徑規劃應用，並與目前比較熱門的沿邊路徑巡邏檢測、全域路徑巡邏檢測、動態避障策略做一個實際應用的結合，並透過幾種不同的規劃策略進行其細節上的比較。本論文也將透過模擬，完成路徑規劃演算法之效率比較，進而驗證本研究之可行性。

Owing to new technological advances, smart home has popularized in middle-class family. In recently years, a numerous research related to autonomous robots are emerge in endlessly, and most of them are inseparable from Simultaneous Localization and Mapping (SLAM). For an autonomous robots with high integrity, in addition to the ability of positioning, the most important thing is to have the ability moving autonomously, therefore path planning algorithm is a very important part. Compared with many existing literatures and papers in regard to path planning, most of them are making an assumption in a static and ideal environment, the algorithm feasibility is very low. In this regard, this paper will have an in-depth discussions on the currently widely used path planning algorithms based on the grid map provided by SLAM. Besides, this paper will present some optimization idea of path planning algorithm and integrated into different methodology that can have higher robustness in the actual environment. In addition, the simulation part will demonstrate different optimization result and discussing the efficiency of different path planning methodology which has mentioned in previous chapter.

[1] X. Guo, "The history of robot & a pioneer of human-computer interfacing (Raymond Kurzweil)", 資訊社會研究, no. 11, pp. 1-36, 2006.
[2] 劍. 柴, "智能掃地機器人技術的研究與實現", 碩士, 西安電子科技大學, 2014.
[3] 浩. 張, "地面移動機器人安全路徑規劃研究", 碩士, 安徽工業大學, 2015.
[4] X. Bo and B. Hong, "A method of collision avoidance planning for multi-robots in dynamic environment", ROBOT, vol. 23, no. 5, pp. 407-410, 2001.
[5] E. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik, vol. 1, no. 1, pp. 269-271, 1959.
[6] Wikipedia, "Dijkstra's algorithm", En.wikipedia.org, 2018. [Online]. Available: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm. [Accessed: 15- May- 2018].
[7] H. Wang, Y. Yu and Q. Yuan, "Application of Dijkstra algorithm in robot path-planning," 2011 Second International Conference on Mechanic Automation and Control Engineering, Hohhot, 2011, pp. 1067-1069.
[8] Z. Z and Z. Z, "A multiple mobile robots path planning algorithm based on A-star and Dijkstra algorithm", International Journal of Smart Home, vol. 8, no. 3, pp. 75-86, 2014.
[9] Wikipedia, "A* search algorithm", En.wikipedia.org, 2018. [Online]. Available: https://en.wikipedia.org/wiki/A*_search_algorithm. [Accessed: 18- May- 2018].
[10] K. Sven, L. Maxim, F. David and Y. Liu, "Incremental heuristic search in artificial intelligence", AI Magazine, vol. 25, no. 2, pp. 99-122, 2004.
[11] L. Maxim and K. Sven, "Incremental heuristic search in games: The quest for speed", AIIDE, pp. 118-120, 2006.
[12] L. Maxim and K. Sven, "A generalized framework for lifelong planning A* search", ICAPS, pp. 99-108, 2005.
[13] K. Sven, L. Maxim and F. David, "Lifelong planning A*", Artificial Intelligence, vol. 155, no. 1-2, pp. 93-146, 2004.
[14] K. Sven, Y. William and X. Sun, "Real-time adaptive A", in Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, 2006, pp. 281-288.
[15] A. Stentz, "Optimal and efficient path planning for partially-known environments," Proceedings of the 1994 IEEE International Conference on Robotics and Automation, San Diego, CA, 1994, pp. 3310-3317 vol.4.
[16] A. Stentz, "The focussed D* algorithm for real-time replanning", IJCAI, vol. 95, pp. 1652-1659, 1995.
[17] S. Koenig and M. Likhachev, "Fast replanning for navigation in unknown terrain," in IEEE Transactions on Robotics, vol. 21, no. 3, pp. 354-363, June 2005.
[18] T. Stentz, " Real-Time replanning in dynamic and unknown environments", Frc.ri.cmu.edu. [Online]. Available: http://www.frc.ri.cmu.edu/~axs/dynamic_plan.html. [Accessed: 18- May- 2018].
[19] L. Maxim and K. Sven, "D* Lite", AAAI/IAAI, p. 28, 2002.
[20] L. Maxim, F. David and B. C, "Heuristic search-based replanning", AIPS, pp. 294-301, 2002.
[21] K. Sven, L. Maxim and X. Sun, "Speeding up moving-target search", Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, p. 188, 2007.
[22] K. Sven, Y. William and X. Sun, "Efficient incremental search for moving target search", IJCAI, pp. 615-620, 2009.
[23] K. Sven, Y. William and X. Sun, "Moving target D* lite", in Proceedings of the 9th International Conference Autonomous Agents and Multiagent Systems, 2010, pp. 67-74.
[24] K. Sven, Y. William and X. Sun, "Adaptive A", in Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, 2005, pp. 1311-1312.
[25] Sina Weibo, "效果滿意！米家掃地機器人半個月清掃體驗", Weibo.com, 2018. [Online]. Available: https://weibo.com/ttarticle/p/show?id=2309404027549050112627. [Accessed: 16- Dec- 2017].
[26] Wikipedia, "K-means clustering", En.wikipedia.org, 2018. [Online]. Available: https://en.wikipedia.org/wiki/K-means_clustering. [Accessed: 18- May- 2018].
[27] Wikipedia, "DBSCAN", En.wikipedia.org, 2018. [Online]. Available: https://en.wikipedia.org/wiki/DBSCAN. [Accessed: 18- May- 2018].