臺灣博碩士論文加值系統

近年來無人載具的發展呈現指數性的成長，不論是飛行載具或是水下載具皆有突破性的發展。由於無人載具能夠到達地形崎嶇，環境較為險惡的地區，因此自主性高的無人載具能夠降低任務於執行上的困難度。若要設計自主性高的無人載具必須有完善的自主路徑規劃演算法，有鑒於此，本文重點在於設計能夠符合不同載具運動限制需求，且具備運算效率高、總路徑距離短、與路徑平滑三大指標的路徑規劃演算法。本研究基於混合雙向搜索技術與傳統路徑規劃演算法(Goal-bias RRT*)，提出一種新的演算法，稱之為Parent Revisited Goal and Parent Bias RRT* (PRGPB-RRT*)，藉由不同的拘束條件以及不同的雙向連接方式，使前述三大性能指標皆得到顯著的改善。此外，為因應任務需求的不同，演算法必須克服環境範圍過大使運算效率變差或是任務目標臨時異動須進行路徑即時變換的問題。本研究也進一步提出藉由尋找階段性目標點的動態路徑規劃方法，使演算法只需藉由局部環境資料與目標點資訊，即可在全域環境中規劃出一條安全無碰撞的路徑。為應用方便，路徑規劃於物件避障方法也是很重要的一環。本文基於空間點雲感知的方法來偵測障礙物位置，而離散點雲不容易進行避障，據此本研究提出加入不同判斷條件的Fitting-Octree，使離散點雲能夠被精確分割成多個立方體所疊合成的障礙物地圖。研究中也加入了將點雲分群的方法，使點雲格點化及路徑規劃效率能在點數較高的環境中亦能高效實現。最後，本方法透過了真實世界中的3D點雲完成可行性驗證。實驗證明所提出方法具有效率高、路徑短且符合載具運動學限制的優點，可應用於無人載具大尺度動態路徑規劃任務，延伸應用於不同之智慧無人移動載具。

The technology of unmanned vehicles has been growing rapidly in recent years. Highly autonomous unmanned vehicles can reach rough terrain and reduce the difficulty of the mission. Based on the Goal-bias RRT*, with the aid of a bidirectional search technique, a new constrained path planning algorithm, Parent Revisited Goal and Parent Bias RRT* (PRGPB-RRT*), is proposed concerning three major objectives: shorter total distance, smoother path, and high computational efficiency. To meet different task requirements, a dynamic path planning method is proposed to diminish the high costs due to large-scale environments and keep track of the changing destination by finding local target points. In addition, object avoidance is an essential part of path planning. As a consequence, the Fitting-Octree is presented to partition the point clouds into multiple cubes representing the obstacles. Moreover, the method of grouping point clouds into clusters effectively increases the efficiency of the implementation under a large number of obstacles. Finally, the feasibility of the proposed method is verified by a real-world 3D point cloud map. The proposed method successfully enhances the efficiency as well as the trajectory, and can be applied to different intelligent unmanned vehicles.

摘要 i
Extended Abstract ii
致謝 xiii
目錄 xiv
表目錄 xvi
圖目錄 xvii
第1章 緒論 1
1.1. 研究動機與目的 1
1.2. 文獻回顧 2
1.3. 論文架構 4
第2章 環境建置 6
2.1. 八叉樹(Octree)之原理 6
2.2. 擬合八叉樹(Fitting Octree)之原理 8
第3章 路徑規劃方法 10
3.1. 傳統路徑規劃方法 10
3.1.1. 快速搜索隨機樹(RRT) 10
3.1.2. 快速搜索隨機樹星(RRT*) 15
3.1.3. 偏向終點快速搜索隨機樹星(Goal Bias RRT*) 20
3.2. 改進之路徑規劃方法 25
3.2.1. 偏向目標點與父節點快速搜索隨機樹星(Goal and Parent Bias RRT*) 25
3.2.2. 父節點重新搜索的偏向父節點與目標點快速搜索隨機樹星(Parent Revisited Goal and Parent Bias RRT*) 30
第4章 障礙物碰撞檢測方法 38
4.1. 碰撞檢測方法 38
4.2. 碰撞偵測方法 41
第5章 運動學限制及路徑平滑化方法 47
5.1. 轉角限制方法 48
5.2. 路徑平滑化方法 51
第6章 大尺度動態路徑規劃方法 57
第7章 實驗結果與分析 64
7.1. 地圖格點化之比較 64
7.2. 路徑規劃演算法之比較 66
7.3. 加入分群方法之驗證 76
7.4. 載具運動學限制與路徑平滑化驗證 82
7.5. 大尺度動態路徑規劃方法驗證 86
第8章 結論 91
附錄A 實驗影片 92
參考文獻 93

[1]B. D. Song, K. Park, and J. Kim, "Persistent UAV delivery logistics: MILP formulation and efficient heuristic," Computers & Industrial Engineering, vol. 120, pp. 418-428, 2018.
[2]T. Shima and S. Rasmussen, UAV cooperative decision and control: challenges and practical approaches. SIAM, 2009.
[3]M. A. R. Estrada and A. Ndoma, "The uses of unmanned aerial vehicles –UAV’s- (or drones) in social logistic: Natural disasters response and humanitarian relief aid," Procedia Computer Science, vol. 149, pp. 375-383, 2019/01/01/ 2019, doi: https://doi.org/10.1016/j.procs.2019.01.151.
[4]E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik, vol. 1, no. 1, pp. 269-271, 1959/12/01 1959, doi: 10.1007/BF01386390.
[5]P. E. Hart, N. J. Nilsson, and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, 1968, doi: 10.1109/TSSC.1968.300136.
[6]R. Dechter and J. Pearl, "Generalized best-first search strategies and the optimality of A*," J. ACM, vol. 32, no. 3, pp. 505–536, 1985, doi: 10.1145/3828.3830.
[7]A. Stentz, "The focussed d^* algorithm for real-time replanning," in IJCAI, 1995, vol. 95, pp. 1652-1659.
[8]L. E. K. J.-C. Latombe, "Probabilistic roadmaps for robot path planning," Pratical motion planning in robotics: current aproaches and future challenges, pp. 33-53, 1998.
[9]S. M. LaValle, "Rapidly-exploring random trees: A new tool for path planning," 1998.
[10]O. Khatib, "Real-Time Obstacle Avoidance for Manipulators and Mobile Robots," The International Journal of Robotics Research, vol. 5, no. 1, pp. 90-98, 1986/03/01 1986, doi: 10.1177/027836498600500106.
[11]C. Zheyi and X. Bing, "AGV Path Planning Based on Improved Artificial Potential Field Method," in 2021 IEEE International Conference on Power Electronics, Computer Applications (ICPECA), 22-24 Jan. 2021 2021, pp. 32-37, doi: 10.1109/ICPECA51329.2021.9362519.
[12]M. Dorigo, M. Birattari, and T. Stutzle, "Ant colony optimization," IEEE Computational Intelligence Magazine, vol. 1, no. 4, pp. 28-39, 2006, doi: 10.1109/MCI.2006.329691.
[13]X. Fan, Y. Guo, H. Liu, B. Wei, and W. Lyu, "Improved Artificial Potential Field Method Applied for AUV Path Planning," Mathematical Problems in Engineering, vol. 2020, p. 6523158, 2020/04/27 2020, doi: 10.1155/2020/6523158.
[14]Z. Jiao, K. Ma, Y. Rong, P. Wang, H. Zhang, and S. Wang, "A path planning method using adaptive polymorphic ant colony algorithm for smart wheelchairs," Journal of Computational Science, vol. 25, pp. 50-57, 2018/03/01/ 2018, doi: https://doi.org/10.1016/j.jocs.2018.02.004.
[15]S. Karaman and E. Frazzoli, "Sampling-based algorithms for optimal motion planning," The International Journal of Robotics Research, vol. 30, no. 7, pp. 846-894, 2011/06/01 2011, doi: 10.1177/0278364911406761.
[16]J. J. Kuffner and S. M. LaValle, "RRT-connect: An efficient approach to single-query path planning," in Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065), 24-28 April 2000 2000, vol. 2, pp. 995-1001 vol.2, doi: 10.1109/ROBOT.2000.844730.
[17]J. D. Gammell, S. S. Srinivasa, and T. D. Barfoot, "Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic," in 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, 14-18 Sept. 2014 2014, pp. 2997-3004, doi: 10.1109/IROS.2014.6942976.
[18]S. Klemm et al., "RRT∗-Connect: Faster, asymptotically optimal motion planning," in 2015 IEEE International Conference on Robotics and Biomimetics (ROBIO), 6-9 Dec. 2015 2015, pp. 1670-1677, doi: 10.1109/ROBIO.2015.7419012.
[19]A. Qureshi and Y. Ayaz, "Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments," Robotics and Autonomous Systems, vol. 68, 02/23 2015, doi: 10.1016/j.robot.2015.02.007.
[20]C. Wang and M. Q. H. Meng, "Variant step size RRT: An efficient path planner for UAV in complex environments," in 2016 IEEE International Conference on Real-time Computing and Robotics (RCAR), 6-10 June 2016 2016, pp. 555-560, doi: 10.1109/RCAR.2016.7784090.
[21]S. Luo, S. Liu, B. Zhang, and C. Zhong, "Path planning algorithm based on Gb informed RRT∗ with heuristic bias," in 2017 36th Chinese Control Conference (CCC), 26-28 July 2017 2017, pp. 6891-6896, doi: 10.23919/ChiCC.2017.8028443.
[22]B. Liao, F. Wan, Y. Hua, R. Ma, S. Zhu, and X. Qing, "F-RRT*: An improved path planning algorithm with improved initial solution and convergence rate," Expert Systems with Applications, vol. 184, p. 115457, 2021/12/01/ 2021, doi: https://doi.org/10.1016/j.eswa.2021.115457.
[23]X. Gao, T. Zhang, Y. Liu, and Q. Yan, "14 lectures on visual SLAM: from theory to practice," ed: Publishing House of Electronics Industry Beijing, 2017.
[24]B. Han et al., "Grid-optimized UAV indoor path planning algorithms in a complex environment," International Journal of Applied Earth Observation and Geoinformation, vol. 111, p. 102857, 2022/07/01/ 2022, doi: https://doi.org/10.1016/j.jag.2022.102857.
[25]N. Ahuja and C. Nash, "Octree representations of moving objects," Computer Vision, Graphics, and Image Processing, vol. 26, no. 2, pp. 207-216, 1984/05/01/ 1984, doi: https://doi.org/10.1016/0734-189X(84)90183-X.
[26]Z. Duraklı and V. Nabiyev, "A new approach based on Bezier curves to solve path planning problems for mobile robots," Journal of Computational Science, vol. 58, p. 101540, 2022/02/01/ 2022, doi: https://doi.org/10.1016/j.jocs.2021.101540.
[27]E. Almoaili and H. Kurdi, "Path Planning Algorithm for Unmanned Ground Vehicles (UGVs) in Known Static Environments," Procedia Computer Science, vol. 177, pp. 57-63, 2020/01/01/ 2020, doi: https://doi.org/10.1016/j.procs.2020.10.011.
[28]Atarasin. "机器人建模与路径规划." https://blog.csdn.net/azahaxia/category_10418874.html (accessed Apr 12, 2021.
[29]M. S. D. Allen. Public Domain. https://www.youseeandyouhappy.com/ta5/archives/14407 (accessed.