簡易檢索 / 詳目顯示

研究生: 侯如瑜
論文名稱: 改良型螞蟻演算法之路徑規劃及其在FPGA之實現
FPGA Realization of an Improved Ant Colony Optimization Algorithm for Path Planning
指導教授: 許陳鑑
學位類別: 碩士
Master
系所名稱: 電機工程學系
Department of Electrical Engineering
論文出版年: 2014
畢業學年度: 102
語文別: 中文
論文頁數: 77
中文關鍵詞: 路徑規劃螞蟻演算法機器人導航移動式機器人FPGA
英文關鍵詞: Path planning, Ant colony algorithm, Navigation, Mobile robot, FPGA.
論文種類: 學術論文
相關次數: 點閱:225下載:7
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 本論文所提出一改良型螞蟻演算法應用於路徑規劃,解決規劃最佳路徑時容易出現區域最佳解的問題。原先的蟻群系統演算法(Ant Colony System , ACS)雖收斂快速,卻極易陷入區域解,因此,本論文將提出一種改良型螞蟻演算法,透過所提出之費洛蒙更新機制,包含部分費洛蒙更新以及反向費洛蒙更新,使得螞蟻具有更多探索新路徑的能力,減少只追隨同一路徑的機會。為了驗證論文中所提出之方法可以確實提升路徑規劃之精確度,將會與傳統ACS比較,以多種不同路徑進行規劃與比較其性能。為了縮短運算時間,提升計算的效率,本論文所提出之改良型螞蟻演算法將以DE2-70多媒體開發平台,利用FPGA電路加以實現。實驗結果證明以全硬體設計方式可以用較少的處理時間獲得路徑規劃結果,確實提升嵌入式應用系統之效能。

    Although traditional ant colony system (ACS) has the ability of fast convergence, it tends to fail into local optima. To solve this problem, this thesis proposes an improved ant colony system algorithm for path planning by establishing two new mechanisms for pheromone updating, including partial pheromone updating and opposite pheromone updating. As a result, the ability of global searching of the improved ACS can be significantly enhanced in comparison to the traditional ACS algorithms in deriving an optimal path. Simulation results show the proposed approach has a better performance in terms of shortest distance, mean distance, and successful rate of the optimal paths than those obtained by the traditional ACS algorithms. To further reduce the computation time, the improved ant colony system algorithm for path planning is realized on FPGA circuit using a DE2-70 multimedia development board to verify the practicability of the proposed algorithm. Experimental results show that the execution efficiency of path planning is significantly improved by the full hardware design for embedded applications.

    摘   要 i ABSTRACT ii 致   謝 iii 表目錄 vii 圖目錄 ix 第一章 緒論 1 1.1研究背景與動機 1 1.2論文架構 4 第二章 傳統與改良型螞蟻演算法 5 2.1.螞蟻演算法簡介 5 2.2.傳統螞蟻演算法 8 2.2.1建立路徑 8 2.2.2費洛蒙更新 10 2.2.3輪盤法 11 2.3.改良型螞蟻演算法 12 第三章 基於改良型螞蟻演算法之路徑規劃 18 3.1 路徑規劃之地圖描述 18 3.2 路徑規劃之問題描述 20 3.3 路徑規劃流程 22 第四章 硬體設計平台 24 4.1 DE2-70多媒體開發平台 24 4.2 LTM觸碰面板模組 27 4.2.1 LTM顯示模組腳位說明 29 4.2.2 LTM顯示模組訊號時序圖 31 第五章 路徑規劃演算法之硬體電路設計 33 5.1硬體電路架構 33 5.2螞蟻演算法硬體電路設計 34 5.2.1距離模組 34 5.2.2費洛蒙模組 37 5.2.3轉換機率模組 39 5.2.4路徑建立模組 41 5.2.5終點判斷模組 45 5.2.6距離計算模組 46 5.2.7路徑比對模組 48 5.2.8路徑暫存模組 49 5.3其他應用模組 50 5.3.1隨機亂數模組 50 5.3.2 RAM 51 5.3.3 Control panel 52 5.3.4 lcd_timing controller 53 5.3.5 adc_spi_controller 53 5.3.6 flash_to_sdram_controller 53 5.3.7 touch_point_detector 53 第六章 模擬與實驗結果 54 6.1改良型蟻群演算法之模擬結果 54 6.1.1 傳統演算法與改良型演算法模擬圖 54 6.1.2 傳統演算法與改良型演算法精確度 56 6.2軟硬體設計之路徑規劃效能比較結果 63 6.3實際應用於路徑規劃之實驗結果 67 第七章 結論 72 參考文獻 73

    [1] J. Barraquand, B. Langois, and J. C. Latombe, “Numerical potential field techniques for robot path planning,” IEEE Trans. on System, Man and Cybernetics, vol. 22, no. 2, pp. 224-241, 1992.
    [2] M. Bennewitz, W. Burgard, and S. Thrun, “Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots,” Robotics and Autonomous Systems, vol. 41, pp. 89-99, 2002.
    [3] J. Guo, L. Liu, Q. Liu, and Y. Qu, “An improvement of D* algorithm for mobile robot path planning in partial unknown environment,” in Proc. of the Second International Conference on Intelligent Computation Technology and Automation, Wuhan, China, 10-11 Oct. 2009, vol. 3, pp. 394-397.
    [4] S. Liu, Y. Tian, and J. F. Liu, “Multi mobile robot path planning based on genetic algorithm,” Intelligent Control and Automation, WCICA, China, 2004, pp. 4706-4709.
    [5] C. H. Fan, W. D. Chen, and Y. Xi, “Hopfield neural networks for path planning in dynamic and unknown environments,” Control Theory and Applications, vol. 21, no. 3, pp. 345-350, 2004.
    [6] M. Dorigo, “The ant system: Optimization by a colony of cooperating agents,” IEEE Trans. on Systems, Man, and Cybernetics Part B: Cybernetics, vol. 26, no. 2, pp. 1-13, 1996.
    [7] M. Dorigo and L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Trans. on Evolutionary Computation, vol. 1, no. 1, pp. 53-66, 1997.
    [8] J. P Laumond, “Finding collision-free smooth trajectories for a non-holonomic mobile robot,” in Proc. of the 10th Int. Joint Conf. Artificial Intelligence, France, 1987, pp. 1120-1123.
    [9] D. Gong and X. Ruan, “A hybrid approach of GA and ACO for TSP,” in Proc. of the World Congress on Intelligent Control and Automation, Beijing, China, Jun. 2004, pp. 2068-2072.
    [10] S. Zhao and M. Li, “Path planning of inspection robot based on ant colony optimization algorithm,” in Proc. of the International Conference on Electrical and Control Engineering (ICECE), China, Jun. 2010, pp. 1474-1477.
    [11] M. Yuan, S. Wang, and P. Li, “A model of ant colony and immune network and its application in path planning,” Industrial Electronics and Applications, China, Jun. 2008, pp. 102-107.
    [12] Y. Z. Cong and S. G. Ponnambalam, “Mobile robot path planning using ant colony optimization,” in Proc. of the International Conference on Advanced Intelligent Mechatronics, Singapore, July 14-17, 2009, pp. 851-856.
    [13] http://sjchen.im.nuu.edu.tw/MachineLearning/final/Opt_AntAlgo.pdf
    [14] H. D. Pour and N. Mostafa, “Solving the facility and layout and location problem by ant-colony optimization-meta heuristic,” International Journal of Production Research, vol. 44, no. 23, pp. 5187-5196, Dec, 2006.
    [15] B. Bullnheimer, R. F. Hartl, and C. Strauss, “An improved ant system algorithm for vehicle routing problem,” Sixth Viennese workshop on Optimal Control Dynamic Games, Nonlinear Dynamics and Adaptive Systems, Vienna, Austria, May 1999, pp.319-328.
    [16] K. M. Sim and W. H. Sun, “Ant colony optimization for routing and load-balancing: Survey and new directions,” IEEE Trans. on Systems, Man, and Cybernetics Part A: Systems and Humans, vol. 33, no.5, pp. 560-572, Sep. 2003
    [17] S. Y. Lee, E. K. Kim, and H. G. Yun “DNA computing adopting DNA coding method for Hamiltonian path problem,” in Proc. of the International Conference on Artificial Intelligence IC-AI 2003, Las Vegas, Nevada, USA, 2003, pp. 154-157.
    [18] 黃建富,以蟻群演算法為基礎之群組機器人路徑規劃,國立雲林科技大學電機工程系碩士班碩士論文,2008。
    [19] 林玟玲,以軟硬體協同設計之混合型即時影像物體追蹤系統,淡江大學電機工程學系碩士班碩士論文,2011。
    [20] Altera Corporation, SOPC Builder User Guide, 2003.
    [21] Altera Corporation, Designing With Nios & SOPC Builder, 2003。
    [22] 李世安、翁仲緯、賴鈺婷、翁慶昌,“影像硬體加速器之設計”,2009 中華民國系統科學與工程研討會,淡江大學,2009年6月。
    [23] C. C. Hsu, S. A. Li, and W. L. Lin “Real-time object tracking based on hardware/software co-design,” in Proc. of the 2011 International conference on Service and Interactive Robotics (SIRCON 2011), Taichung, Taiwan, Dec. 20-21, 2011, pp. 167-170.
    [24] C. C. Hsu, R. Y. Hou, and W. Y. Wang “Path planning for mobile robots based on improved ant colony optimization,” in Proc. of the 2013 IEEE International Conference on Systems, Man, and Cybernetics (SMC), Manchester, Oct. 13-16, 2013, pp. 2777-2782.
    [25] 李世安,即時目標影像追蹤之SoPC設計,淡江大學電機工程學系博士班博士論文,2008。
    [26] C. C. Tsai, H. C. Huang, and C. K. Chan “Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation” IEEE Trans. on industrial electronics, vol. 58, no. 10, pp. 4813-4821, 2011.
    [27] M. Danesh and M. R. Abazari “Optimize path planning of a planar parallel robot to avoid obstacle collision using genetic algorithm,” in Proc. of the 2014 Iranian Conference on Intelligent Systems, Bam, Feb. 4-6, 2014, pp. 1-4.
    [28] Altera多媒體發展平台DE2-70網址,網址: http://www.altera.com/education/univ/materials/boards/de2-70/unv-de2-70-board
    [29] Altera Corporation, URL:http://www.terasic.com.tw/tw/
    [30] Terasic, THDB_LTM_User Manual, Document Version 1.4.1, 2011.
    [31] K. Sugihara and J. Smith “Genetic algorithms for adaptive motion planning of an autonomous mobile robot,” in Proc. of the 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation, Monterey, Jul. 10-11, 1997, pp.138-143.

    下載圖示
    QR CODE