基於能量螞蟻演算法之路徑規劃與其在雲端平台運算的實現

Cloud Computing Realization of an Energy-Based Ant Colony Optimization Algorithm for Path Planning

孫仕勳(Shih-Hsun Sun)

指導教授 ： 呂藝光

國立臺灣師範大學/科技與工程學院/電機工程學系/碩士(2015年)

https://doi.org/10.6345/NTNU202205514

摘要

本研究以能量觀點並透過針對能量修正的螞蟻演算法來進行最佳路徑路徑規劃。因應電動車在道路上行駛可能面臨爬坡或是各種材質不同的路面，最短路徑並不一定等於最節省能量的路徑，故定義出能量消耗的公式，結合網頁伺服器的運算，如此就讓使用者在行駛中透過可攜式行動裝置得知目前考量最佳能量路徑之下的結果。演算法以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.

並列關鍵字

Ant Colony Optimization ； Path-Planning ； Cloud Computing

參考文獻

[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。