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: 271 Downloads: 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.
[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.