Basic Search / Detailed Display

Author: 孫仕勳
Shih-Hsun Sun
Thesis Title: 基於能量螞蟻演算法之路徑規劃與其在雲端平台運算的實現
Cloud Computing Realization of an Energy-Based Ant Colony Optimization Algorithm for Path Planning
Advisor: 呂藝光
Leu, Yih-Guang
Degree: 碩士
Master
Department: 電機工程學系
Department of Electrical Engineering
Thesis Publication Year: 2015
Academic Year: 103
Language: 中文
Number of pages: 79
Keywords (in Chinese): 螞蟻演算法路徑規劃雲端
Keywords (in English): Ant Colony Optimization, Path-Planning, Cloud Computing
DOI URL: https://doi.org/10.6345/NTNU202205514
Thesis Type: Academic thesis/ dissertation
Reference times: Clicks: 271Downloads: 0
Share:
School Collection Retrieve National Library Collection Retrieve Error Report
  • 本研究以能量觀點並透過針對能量修正的螞蟻演算法來進行最佳路徑路徑規劃。因應電動車在道路上行駛可能面臨爬坡或是各種材質不同的路面,最短路徑並不一定等於最節省能量的路徑,故定義出能量消耗的公式,結合網頁伺服器的運算,如此就讓使用者在行駛中透過可攜式行動裝置得知目前考量最佳能量路徑之下的結果。演算法以Javascript 實作,結合Google Map的地圖資訊,使其能夠應用在網頁顯示並做出路徑規劃。並且為降低瀏覽器的運算壓力,將巨量的運算交給雲端伺服器處理。最後透過實際載具的道路行駛數據,驗證其準確性。

    This thesis introduces an energy-based algorithm of Ant Colony Optimization. The algorithm was implemented in javascript. Combining with Google Map informations, it can be used for real-road path-planning through a web page. The algorithm computation was moved to cloud-computing by using Node.js server, which is able to run javascript algorithm in server-side, to decrease the pressure of browser. Moreover, we examine its accuracy by actual on-road driving experiments.

    摘 要 i ABSTRACT ii 誌 謝 iii 目 錄 iv 圖目錄 vii 表目錄 x 第一章 緒論 1 1.1 研究背景與動機 1 1.2 研究方法 3 1.3 研究目的 4 1.4 章節簡述 5 第二章 文獻探討與回顧 6 2.1 路徑規劃 6 2.1.1 路徑問題 6 2.1.2 Dijkstra 演算法 7 2.1.3 A*演算法 7 2.1.4 基因演算法 9 2.2 螞蟻演算法 10 2.2.1 螞蟻演算法起源 10 2.2.2 初始化路徑問題 11 2.2.3 路徑的選擇 11 2.2.4 費洛蒙更新 13 2.2.5 螞蟻演算法流程圖 14 2.2.6 螞蟻演算法改良版 15 第三章 基於能量螞蟻演算法 16 3.1 傳統路徑演算法缺點 16 3.2 基於能量的路徑選擇公式 17 3.3 能量公式 18 3.4 能量費洛蒙更新 19 3.5 演算法虛擬碼 20 3.6 雲端模擬環境建置 21 3.6.1 Google Map與程式語言選用 21 3.6.2 網頁環境 21 3.6.3 地圖節點的建立 22 3.7 能量螞蟻演算法實作架構與API設計 23 3.8 能量螞蟻演算法實作驗證與參數校調 25 3.8.1 地圖節點選定 25 3.8.2 對照組:統一高度路徑分析 26 3.8.3 實驗組:含高度變化路徑分析 27 3.8.4 結果比較與說明 28 3.8.5 本節小結 29 3.9 能量螞蟻演算法道路分析模擬 30 3.9.1 地圖點選擇 30 3.9.2 模擬參數說明與比較方法 30 3.9.3 模擬A 34 3.9.4 模擬B 36 3.9.5 模擬C 38 3.9.6 模擬D 40 第四章 實驗與結果 42 4.1 實驗平台介紹 42 4.2 數據量測方式 43 4.3 Android應用程式撰寫 44 4.4 實驗步驟與載具詳細參數 45 4.5 實驗甲─轉彎能耗實驗 46 4.5.1 實驗地圖選擇 46 4.5.2 路徑說明 46 4.5.3 路徑模擬結果 47 4.5.4 結果與說明 48 4.6 實驗乙─爬坡能耗實驗 51 4.6.1 實驗地圖選擇 51 4.6.2 路徑說明 51 4.6.3 路徑模擬結果 52 4.6.4 結果與說明 53 第五章 結論與未來展望 56 5.1 結論 56 5.2 未來展望 56 參考文獻 57 附錄 61 自傳 67

    [1] Janet Heine Barnett, Early writings on graph theory: Euler circuits and the Königsberg bridge problem, Colorado State University Pueblo, 2005.
    [2] Dijkstra, E. W., A note on two problems in connexion with graphs, Numerische Mathematik, 1959.
    [3] I. Chabini and S. Lan, “Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks,” IEEE Transactions on Intelligent Transportation Systems, vol. 3, no. 1, pp.60-74, Mar. 2002.
    [4]張傑,“以改良的 A*演算法規劃較佳導引路徑之研究”,大同大學
    資訊工程研究所,碩士論文,2009。
    [5] Eiben, Agoston E., P-E. Raue, and Zs Ruttkay., “Genetic algorithms with multi-parent recombination," Parallel Problem Solving from Nature—PPSN III, Springer Berlin Heidelberg, 1994, pp. 78-87.
    [6]曹家瑞,“物流業配送系統之車輛指派與路徑規劃”,國立台北科技大學生產系統工程與管理研究所,碩士論文,1999。
    [7] Dorigo, Marco, Vittorio Maniezzo, and Alberto Colorni, “Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Transactions On System, Man, And Cybernetics-Part B Cybernetics, vol. 26, no. 1, 1996.
    [8] Flood, Merrill M., “The traveling-salesman problem,” Operations Research, 1956, pp, 61-75.
    [9]江冠慶,“蟻拓優化演算法應用於多型態零工式生產排程問題”,國立臺灣大學工業工程學研究所,碩士論文,2013。
    [10] Marco Dorigo, Senior Member, IEEE, and Luca Maria Gambardella, Member, IEEE, “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” Evolutionary Computation, IEEE Transactions, vol. 1.1, pp. 53-66, 1997.
    [11] Duc-Hien Nguyen and Jyh-Ching Juang, “A Refined Ant Colony algorithm for Optimal Path Planning,” Proceedings of 2011 International Conference on System Science and Engineering, China, 2011, pp. 125.
    [12] E.Bonabeau, M.Dorigo, G.Theraulaz, “Swarm Intelligence: From natural
    to artificial systems, ” New York: Oxford University Press. 1999.
    [13] B. Bullnheimer, R.F. Hartl and C. Strauss, “A new rank-based version of
    the ant system: A computational study, ” Central European Journal of
    Operations Research and Economics 7, pp. 25-38, 1999.
    [14] Zhang, Y., Wang, H., Zhang, Y., & Chen, Y., “Best-worst ant system,” In Advanced Computer Control, 2011 3rd International Conference on IEEE, pp. 392-395, 2011.
    [15]林裕勝,“細菌演化模糊控制器及其在兩輪移動載具控制上之應用研究”,國立臺灣師範大學應用電子科技學系,碩士論文,2013。
    [16]溫彥侯,“兩輪式自我平衡車之控制器設計與實現”,國立臺灣師範大學應用電子科技學系,碩士論文,2013。
    [17] Lee, J. W., Choy, Y. I., Sugisakaz, M., & Lee, J. J, “Study of novel heterogene- ous ant colony optimization algorithm for global path planning,” In Industrial Electronics, IEEE International Symposium, 2010, pp. 1961-1966.
    [18] JI, Xiaogang, LI, Nan. “ACO-Based multiple geometric elements measure path planning for CMM,” In Computer Application and System Modeling, 2010 International Conference on IEEE, 2010, pp. V14-539-V14-544.

    [19] Lee, J. W., Kim, J. J., Choi, B. S., & Lee, J. J., “Improved Ant Colony Optimization algorithm by potential field concept for optimal path planning, ” In Humanoid Robots 8th IEEE-RAS International Conference on IEEE, 2008, pp. 662-667.
    [20]王哲,“基於動態規劃法之機器人室內智慧環境路徑規劃研究”,國立成功大學機械工程學系,碩士論文,2014。
    [21]侯如瑜,“改良型螞蟻演算法之路徑規劃及其在FPGA之實現”,國立臺灣師範大學應用電子科技學系,碩士論文,2014。
    [22]蔡佳穎,“以螞蟻演算法求解考量釋放與整備時間之無相關平行機台排程問題”,逢甲大學工業工程與系統管理學系,碩士論文,2014。
    [23]簡誌垚,“根據遺傳演算法、螞蟻演算法、粒子群演算法及模擬退火演算法以處理旅行推銷員問題之新方法”,國立臺灣科技大學資訊工程系,碩士論文,2010。
    [24]Zehua Zhang, Xuejie Zhang, “Realization of open cloud computing federation based on mobile agent,” Intelligent Computing and Intelligent Systems IEEE Inte- rnational Conference, 2009, pp. 642-646.
    [25] Kai Lei, Yining Ma, Zhi Tan, “Performance Comparison and Evaluation of Web Development Technologies in PHP, Python, and Node.js,” Computational Science and Engineering IEEE 17th International Conference, 2014.
    [26] Tilkov, S., Vinoski, S., “Node.js: Using JavaScript to Build High-Performance Network Programs,” Internet Computing IEEE, 2010, pp. 80- 83.
    [27] Jaramillo, D., Nguyen Van Duy, Newhook, R., “Real-time experience techniques for collaborative tools on mobile,” SOUTHEASTCON IEEE, 2014, pp. 1-6.
    [28] Hausladen, J., Pohn, B., Horauer, M., “A cloud-based integrated development environment for embedded systems,” Mechatronic and Embedded Systems and Appl- ications IEEE/ASME 10th International Conference, 2014, pp. 1-5.
    [29] Zhiqiang You, Huaiyu Xu, Jihui Xu, Jinfeng Xu, Dayu Shi, “Micro-Blogging System Based on Geographic Information in Google Map,” Computational Intelli- gence and Communication Networks Fourth International Conference, 2012, pp. 150-153.
    [30] Hao Zhang, Manchun Li, Zhenjie Chen, Zhiliang Bao, Qiuhao Huang, Dong Cai, “Land use information release system based on Google Maps API and XML,” Geo- informatics 18th International Conference, 2010, pp. 1-4.

    無法下載圖示 This full text is not authorized to be published.
    QR CODE