利用改良式A*演算法於無人船的避碰路徑之規劃

Collision-free Path Planning for Unmanned Surface Vehicle by Using Advanced A* Algorithm

本研究旨在探討：無人船的最佳路徑規劃與無人船的控制系統設計與實驗。在地圖中搜尋最短路徑是一熱門問題，其中最被廣泛應用的演算法為A*演算法，然而傳統的A*演算法（A* on Grids）的轉彎角度被限制住，所以無法找到真實最短路徑，因此本研究提出Finite Angle A*（FAA *）演算法來改善傳統A*演算法的缺失，並驗證了FAA*演算法所蒐尋的路徑比A* on Grids以及A*Post-Smoothed還要來的短。除了搜尋最短路徑外，本研究亦探討安全路徑問題，為了避免實際導航時可能會產生碰撞，本研究提出另一個可目視直線定義來規劃出一條與障礙物保持安全距離的最佳路徑。文中利用完整的空照圖庫並配合影像分析技術來獲得FAA*演算法所使用的地圖，此法大量減少製造地圖的成本以及時間，再透過座標轉換將規劃的結果實用於無人船上。為了使無人船能夠自主導航，本文設計了適用於雙直流推進器之無人船的模糊控制器，搭配GPS模組以及電子羅盤則可成功實現無人船的自主導航，最後在安平港實際測試無人船的導航系統，而測試結果顯示出本研究所設計的模糊控制器能夠成功的自主導航無人船。 In recent years, the development of autonomous surface vehicles has been an area of increasing research interest. The presented study focuses on two objectives: the path planning for unmanned surface vehicle (USV) and the design of fuzzy logical controller of USV.Path planning is an essential topic of robotics, and the main purpose in this investigation is to determine approximately the safest and shortest path. A* algorithm is the most commonly used for path finding, but the paths found by A* are not truly the shortest paths because the potential headings of the paths are artificially constrained. To tackle this shortcoming, the Finite Angle A* (FAA*) method is proposed in this study. The experimental results show that FAA* finds shorter paths than both A* on grids and A* with the post-smoothed method. To find a safer path that is as short as possible is our primary goal. The modified definition of line-of-sight is proposed to achieve this objective by adding a variable called ”safe distance” to the line-of-sight formula, and the value of the variable can be decided by its users.