簡易檢索 / 詳目顯示

回結果列表
研究生： 鍾秉剛
論文名稱： 基於向量模型設計與實現蒙地卡羅定位與路徑規劃於輪型移動機器人
Design and Implementation of Monte-Carlo Localization and Path Planning for Wheeled Mobile Robot Based on Vector Model
指導教授： 陳美勇
學位類別： 碩士
Master
系所名稱： 機電工程學系
Department of Mechatronic Engineering
論文出版年： 2015
畢業學年度： 103
語文別： 中文
論文頁數： 114
中文關鍵詞： 蒙地卡羅定位法 、Ａ*演算法 、地圖向量化
英文關鍵詞： Monte Carlo localization, A* algorithm, map vectorization
DOI URL： https://doi.org/10.6345/NTNU202205515
論文種類： 學術論文
相關次數： 點閱：212  下載：28 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 本論文主要研究之目的是改良輪型機器人的定位與路徑規畫演算法。在定位
    方面，本論文克服定點定位、路徑追蹤與機器人綁架所面臨之問題，並且提出了基於向量模型的改良式蒙地卡羅定位演算法。具體的改善措施包含以下內容：第一，引入離散形式的輪型機器人運動模型進行動態更新；第二，以向量模型取代柵格地圖，解決定位的解析度問題；第三，除了使用競爭法與菁英保留策略外，在重新採樣的程序中引入了粒子變異機制，其變異程度由當前粒子的分佈情形決定，使演算法可以保持指數地收斂；最後，粒子重新分佈的機制亦被納入演算法中，使得演算法具備更佳的強健性針對定位失敗與綁架問題。在路徑規劃方面，本論文將A*演算法建立於向量地圖中，使用地圖中的角點為此演算法內的節點，藉以改善在A*演算法面臨移動方向限制的困擾與大量轉折點的問題。為使上述方法可行，本文修改A*演算法流程並加入判別節點間移動可行性的函數，只有獲得許可的路徑會被納入花費函數的考量以確保能正確地規劃路徑。為避免路徑過於靠近障礙物而發生碰撞，本文引入影像侵蝕方法去除過於接近障礙物的區域，使機器人在移動過程中能與障礙物保持適當距離。此外，本文亦加入一項路徑圓弧優化方法讓路徑更為平順，使機器人以弧型移動通過各節點而降低整體移動花費時間。整體而言，本論文的定位演算法可以更有效率地提供機器人定位結果，
    提供的路徑能在最短路徑與避障能力上保持良好的平衡，並使機器人除了避障外亦能快速到達終點。

    The main purpose of research is to improve the localization performance and result of path planning of wheeled mobile robot. In the area of localization, we solve the problems from localization, path tracking and robot kidnapped, and propose an improved Monte Carlo localization based on vector model. The specific improvements of the method are as follows: First, we include the discrete kinematic model of
    wheeled mobile robot in prediction process. Second, use vector model instead of bitmap to solve the resolution problem. Third, not only tournament selection and elitism, but also variation mechanism are used in the resampling process. The extent of Variation is decided by distribution of particles. Last, the re-initialize process is added
    into the algorithm, so that the system can be more robust and better to robot kidnapped problem. In the area of path planning, we include A* algorithm into vector model instead of traditional bitmap, and use the corners as nodes in A* algorithm to solve the limited of orientation of robot problem, and reduce the amount of turning points. To do this, we modify the process of A* algorithm and add the function that checks particles are moveable or not. Only pass particles can be considered into cost function. To avoid collision, we include the image erosion to remove the area which is too close to obstacles, so there is enough distance between robot and obstacles. In addition, path smoothing process is added into the algorithm to get smoother path after planning, so that the robot can pass through all nodes more efficiently. Overall, our research can let the localization algorithm be with more efficacy, and plan a path with good balance in shortest path and avoidance ability, so the robot can move quickly and stably to the goal.

    摘要………………………………………………………………………………………………………………………………………i Abstract …………………………………………………………………………………………………………………………ii 致謝………………………………………………………………………………………………………………………………………iii 目錄………………………………………………………………………………………………………………………………………iv 圖目錄…………………………………………………………………………………………………………………………………viii 表目錄…………………………………………………………………………………………………………………………………xiii 第一章 緒論………………………………………………………………………………………………………………………1 1.1 前言……………………………………………………………………………………………………………………………1 1.2 文獻回顧……………………………………………………………………………………………………………………4 1.2.1 定位研究之回顧………………………………………………………………………………………………4 1.2.2 規劃研究之回顧………………………………………………………………………………………………11 1.2.3 控制研究之回顧………………………………………………………………………………………………13 1.3 研究動機與目的……………………………………………………………………………………………………14 1.4 本論文之貢獻…………………………………………………………………………………………………………14 1.5 本論文之架構…………………………………………………………………………………………………………15 第二章 理論基礎……………………………………………………………………………………………………………16 2.1 蒙地卡羅方法…………………………………………………………………………………………………………16 2.2.1 預測………………………………………………………………………………………………………………………17 2.2.2 權重分配……………………………………………………………………………………………………………17 2.2.3 重新採樣……………………………………………………………………………………………………………18 2.2 A*演算法…………………………………………………………………………………………………………………19 2.3 點陣圖與向量圖轉換機制…………………………………………………………………………………23 2.4 輪型機器人之結構分析並以約束條件推導運動模型……………………………24 2.5 離散型輪型機器人運動模型……………………………………………………………………………25 2.6 梯形與S 形速度控制訊號設計方法……………………………………………………………31 第三章 機器人控制………………………………………………………………………………………………………37 3.1 機器人控制架構……………………………………………………………………………………………………37 3.2 地圖向量化………………………………………………………………………………………………………………37 3.2.1 角點偵測……………………………………………………………………………………………………………38 3.2.1.1 邊緣偵測………………………………………………………………………………………………………38 3.1.1.2 搜尋候選點…………………………………………………………………………………………………40 3.1.1.3 集合候選點…………………………………………………………………………………………………42 3.1.1.4 決定角點………………………………………………………………………………………………………42 3.1.2 形狀構成……………………………………………………………………………………………………………43 3.1.3 地圖建立……………………………………………………………………………………………………………44 3.2 機器人定位……………………………………………………………………………………………………………44 3.2.1 演算法初始化……………………………………………………………………………………………………45 3.2.2 預測(prediction)………………………………………………………………………………………46 3.2.3 權重分配(weight assignment)…………………………………………………………47 3.2.3.1 環境模擬………………………………………………………………………………………………………48 3.2.3.2 誤差計算………………………………………………………………………………………………………51 3.2.3.3 權重計算………………………………………………………………………………………………………53 3.2.4 重新採樣(resampling)……………………………………………………………………………54 3.2.5 重新分佈……………………………………………………………………………………………………………56 3.2.6 逆向收斂……………………………………………………………………………………………………………58 3.3 機器人路徑規劃…………………………………………………………………………………………………59 3.3.1 移動通行性函數設計…………………………………………………………………………………59 3.3.2 基於向量模型A*路徑規劃演算法…………………………………………………………60 3.3.3 路徑之避障設計……………………………………………………………………………………………61 3.3.4 路徑弧形優化…………………………………………………………………………………………………62 3.3.5 馬達參考轉速轉換機制………………………………………………………………………………64 第四章 實驗設備…………………………………………………………………………………………………………65 第五章 實驗結果與討論…………………………………………………………………………………………67 5.1 角點偵測與地圖向量化…………………………………………………………………………………67 5.2 不同繪圖法在matlab 上之時間花費比較……………………………………………69 5.3 不同數量粒子隨機分布在地圖上………………………………………………………………70 5.4 比較有無去頭之均方根誤差於估算誤差之表現差異…………………………70 5.5 重新採樣參數對收斂速度影響之研究………………………………………………………72 5.6 重新採樣參數對收斂成功率影響之研究…………………………………………………81 5.7 本論文提出之改定位法與其他定位演算法之性能比較……………………85 5.8 本論文路徑規劃之表現……………………………………………………………………………………107 第六章 結論及未來展望..………………………………………………………………………………………109 參考文獻……………………………………………………………………………………………………………………………111

    [1] M. Nicholas, and S. Ulam, “The Monte Carlo method,” Journal of the American statistical association, vol. 44, no. 247, pp. 335-341, Sep. 1949.
    [2] X. Kang, K. Li, and W. Zhu, “A New Localization Method for Mobile Robots Using Genetic Simulated Annealing Monte Carlo Localization,” International Conference on Mechatronics and Automation, Beijing, China, Aug. 2011, pp.1780-1785.
    [3] Fallon, M. F., Johannsson, H., & Leonard, J. J., “Efficient scene simulation for robust Monte Carlo localization using an RGB-D camera,” International
    Conference on Robotics and Automation, Saint Paul, MN, May 2012, pp. 1663-1670.
    [4] T. G. Kim and N. Y. Ko, “Experiments and Analysis of MCL Based Localization for Mobile Robot Navigation,” International Conference on Intelligent Systems, Kuala Lumpur, Malaysia, Jan. 2011, pp. 221-227.
    [5] C.-C. Hsu, C-J. K., and W.-C. Kao, “Improved Monte Carlo Localization with Robust Orientation Estimation for Mobile Robots,” International Conference on Systems, Man, and Cybernetics, Manchester, UK, Oct. 2013, pp. 3651-3656.
    [6] Y. Liu, H. Wang and J. Xie, “A New Path Planning Method Based on Vector Models in a Strait Static Environment,” International conference on Chinese Control and Decision Conference, NJ, USA, June 2009, pp. 1109-1112.
    [7] C.-J. Yu, Y.-H. Chen, and C.-C. Wong, “Path Planning Method Design for Mobile Robots,” SICE Annual Conference, Tokyo, Japan, Sep. 2011, pp. 1681-1686.
    [8] W.-C. Ming, “Location estimation and uncertainty analysis for mobile robots,” IEEE International Conference on Robotics and Automation, Philadelphia, PA, Apr. 1988, pp. 1231-1235.
    [9] J. Xu, F. Bu, W. Si, Y. Qiu, and Z. Chen, “An Algorithm of Weighted Monte Carlo Localization Based on Smallest Enclosing Circle,” International Conference on Internet of Things and Cyber, Physical and Social Computing, Dalian, China, Oct. 2011, pp. 157-161.
    [10] P. Yang, “Efficient particle filter algorithm for ultrasonic sensor-based 2D range-only simultaneous localisation and mapping application,” IET Wireless
    Sensor Systems, vol. 2, no. 4, pp. 394-401, Dec. 2012.
    [11] P. Yang, “Efficient Particle Filter Localization Algorithm in Dense Passive RFID Tag Environment,” IEEE Transactions on Industrial Electronics, vol. 61, no. 10, Oct. 2014, pp. 5641-5651.
    [12] P. Corke, C. Detweiler, M Dumbabin, M. Hamilton, D. Rus, and I. Vasilescu, “Experiments with Underwater Robot Localization and Tracking,” International Conference on Robotics and Automation, Roma, Italiana, Apr. 2007, pp. 4556-4561.
    [13] G. Grisetti, C. Stachniss, and W. Burgard, “Improved techniques for grid mapping with rao-blackwellized particle filters,” IEEE Transactions on Robotics, vol. 23, no. 1, Feb. 2007, pp. 34-46.
    [14] C. C. Hsu, C. C. Wong, H. C. Teng, N. J. Li, and C. Y. Ho, “Localization of Mobile Robots via an Enhanced Particle Filter,” Instrumentation and Measurement Technology Conference, Austin, TX, May 2010, pp. 323-327.
    [15] A. Bais, R. Sablatning, J. Gu, Y. M. Khawaja, “Location tracker for a mobile robot,” International Conference on Industrial Informatics, vol. 1, Vienna, Austria, June 2007, pp.479-484.
    [16] Y. Fu, Stephen Tully, G. Kantor, and H. Choset, “Monte Carlo Localization using 3D Texture Maps,” International Conference on Intelligent Robots and Systems, San Francisco, USA, Sep. 2011, pp. 482-487.
    [17] L. Zhang, R. Zapata, P. Lepinay, “Self-Adaptive Monte Carlo for Single-Robot and Multi-Robot Localization,” International Conference on Automation and Logistics Shenyang, Shenyang, China, Aug. 2009, pp. 1927-1933.
    [18] H. J. Zhou and S. Sakane, “Sensor planning for mobile robot localization - A hierarchical approach using a Bayesian network and a particle filter,” IEEE Transactions on Robotics, vol. 24, no. 2, Apr. 2008, pp. 481-487.
    [19] W. Wang and Q. Zhu, “Varying the Sample Number for Monte Carlo Localization in Mobile Sensor Networks,” Second International Multisymposium on Computer and Computational Sciences, Iowa City, IA, Aug. 2007, pp. 490-495.
    [20] M. Nakamiya, Y. Kishino, T. Terada, and S. Nishio, “A route planning method using cost map for mobile sensor nodes,” International Symposium on Wireless Pervasive Computing, San Juan, USA, Feb. 2007, pp. 169-174.
    [21] P. S. Tsai, Y. H. Lin, and L. W. Chou, “Constrained Optimization Method for Collision-Free B-spline Trajectory Planning,” Journal of China Institute of Technology, vol. 36, pp. 247-260, June 2007.
    [22] H. Hu, M. Brady, “Dynamic Global Planning with Uncertainty for Mobile Robots in Manufacturing,” IEEE Transactions on Robotics and Automation, vol. 13, no. 5, Oct. 1997, pp. 760-767.
    [23] G. E. Jan, K. Y. Chang, and I. Parberry, “Optimal path planning for mobile robot navigation,” IEEE/ASME Transactions on Mechatronics, vol. 13, no. 4, Aug. 2008, pp. 451-460.
    [24] 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 Transactions on Industrial Electronics, vol. 58, no. 10, Oct. 2011, pp.
    4813-4821.
    [25] ] J. Yao, C. Lin, X. Xie, A. Wang, and C.-C. Hung, “Path planning for virtual human motion using improved A* star algorithm,” International Conference on Information Technology, Las Vegas, USA, Apr. 2010, pp. 1154-1158.
    [26] P. S. Tsai, Y. H. Lin, and C. F. Tsai, “Implementation of Trajectory Tracking Control for Wheeled Mobile Robots Based on Fuzzy Controller,” Journal of China Institute of Technology, vol. 41, pp. 45-65, Nov. 2009.

    下載圖示
    QR CODE