學術產出-學位論文
文章檢視/開啟
書目匯出
-
題名 不確定的環境中無人機的階層式協力運動規劃
A Collaborative Hierarchical Online Motion Planner for UAV in an Uncertainty Environment作者 蔡苡雋
Tsai, Yi-Chuan貢獻者 李蔡彥
Li, Tsai-Yen
蔡苡雋
Tsai, Yi-Chuan關鍵詞 無人機
運動規劃
路徑規劃
快速搜索隨機樹
UAV
Hierarchical Motion Planning
Path Planning
Rapidly-exploring Random Tree日期 2021 上傳時間 1-七月-2021 19:57:18 (UTC+8) 摘要 路徑規劃一直是無人機自動化研究中重要的課題，其目的在於確保無人機的安全性及效率，在移動中隨時更新與即時規劃路徑，讓無人機順利到達目標點。無人機的機上運算對於複雜或廣大的區域，需要消耗很多計算時間，而對於無人機的安全性來說，需要較短的規劃時間來達到飛行安全的目的。在本論文中，我們探討了不同的路徑規劃演算法的優劣勢，並決定採用快速搜索隨機樹(RRT)作為無人機的路徑規劃演算法，且提出了一種階層式協力計算架構，此架構利用機上運算與基地台的非同步合作規劃，嘗試解決在單層路徑規劃上較難同時確保規劃即時性與路徑最優性的問題。本系統可用於無人機行駛在不確定的環境中即時規劃路徑，並確保無人機在飛行時的安全，及產出有效率的路徑。我們以四種不同環境條件下進行即時模擬飛行實驗，實驗結果顯示本架構可有效降低飛行花費時間或是飛行路徑長度，並且能在有提供風場資訊的環境中，選擇更順風的路徑飛行。
Path planning has always been an important topic in the research of UAV automated navigation. The purpose of this work is to consider the safety and efficiency of UAVs when planning and updating the path in real-time during the movement such that the UAV can reach the goal configuration successfully. Global path planning usually requires a great amount of computing for complex or large areas, which may be beyond the onboard computing power of many UAVs. Even if the computation can be done on board, the long planning time may not guarantee the safety of UAV navigation. In this paper, we investigate the pros and cons of various path planning algorithms and choose Rapidly-exploring Random Tree (RRT) as a base planning algorithm for UAVs. We proposed a collaborative hierarchical computing architecture, which uses asynchronous cooperative planning of the computing resources onboard and at the base station. Our architecture aims to tackle the difficulty in single-layer path planning where the immediacy of planning and the optimality of the path can not be ensured at the same time. Our system can be used to plan the path for a UAV in an uncertain environment in real-time and ensure its safety during the flight and the effectiveness of the output path. We have conducted experiments in simulation for a typical UAV under four different environmental conditions. The experimental results show that our method can effectively reduce flight time or path length and choose a more downwind path if the wind field information is provided.參考文獻 [1] Wikipedia. "Unmanned aerial vehicle." Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=Unmanned_aerial_vehicle&oldid=955084723 (accessed 7 May 2020 05:46 UTC.[2] Wikipedia. "Motion planning." Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=Motion_planning&oldid=950519176 (accessed 7 May 2020 05:25 UTC.[3] H. Yang, Q. Jia, and W. Zhang, "An Environmental Potential Field Based RRT Algorithm for UAV Path Planning," in 2018 37th Chinese Control Conference (CCC), 2018: IEEE, pp. 9922-9927.[4] L. Yang, J. Qi, J. Xiao, and X. Yong, "A literature review of UAV 3D path planning," in Proceeding of the 11th World Congress on Intelligent Control and Automation, 2014: IEEE, pp. 2376-2381.[5] G. A. Thanellas, V. C. Moulianitis, and N. A. Aspragathos, "A spatially wind aware quadcopter (UAV) path planning approach," IFAC-PapersOnLine, vol. 52, no. 8, pp. 283-288, 2019/01/01/ 2019, doi: https://doi.org/10.1016/j.ifacol.2019.08.084.[6] K. Yang, S. Keat Gan, and S. Sukkarieh, "A Gaussian process-based RRT planner for the exploration of an unknown and cluttered environment with a UAV," Advanced Robotics, vol. 27, no. 6, pp. 431-443, 2013.[7] W. Zu, G. Fan, Y. Gao, Y. Ma, H. Zhang, and H. Zeng, "Multi-uavs cooperative path planning method based on improved rrt algorithm," in 2018 IEEE International Conference on Mechatronics and Automation (ICMA), 2018: IEEE, pp. 1563-1567.[8] L. De Filippis, G. Guglieri, and F. Quagliotti, "A minimum risk approach for path planning of UAVs," Journal of Intelligent & Robotic Systems, vol. 61, no. 1-4, pp. 203-219, 2011.[9] A. González-Sieira, M. Mucientes, and A. Bugarín, "Motion planning under uncertainty in graduated fidelity lattices," Robotics and Autonomous Systems, vol. 109, pp. 168-182, 2018.[10] F. Li, S. Zlatanova, M. Koopman, X. Bai, and A. Diakité, "Universal path planning for an indoor drone," Automation in Construction, vol. 95, pp. 275-283, 2018.[11] Z. Beck, W. T. L. Teacy, A. Rogers, and N. R. Jennings, "Collaborative online planning for automated victim search in disaster response," Robotics and Autonomous Systems, vol. 100, pp. 251-266, 2018/02/01/ 2018, doi: https://doi.org/10.1016/j.robot.2017.09.014.[12] S. M. LaValle, J. J. Kuffner, and B. Donald, "Rapidly-exploring random trees: Progress and prospects," Algorithmic and computational robotics: new directions, no. 5, pp. 293-308, 2001.[13] S. Karaman and E. Frazzoli, "Incremental sampling-based algorithms for optimal motion planning," Robotics Science and Systems VI, vol. 104, no. 2, 2010.[14] 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), 2000, vol. 2: IEEE, pp. 995-1001.[15] T.-Y. Li and Y.-C. Shie, "An incremental learning approach to motion planning with roadmap management," in Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No. 02CH37292), 2002, vol. 4: IEEE, pp. 3411-3416.[16] K. Liang, Z. Chun-xia, and G. Jian-hui, "Path Planning Based on Fuzzy Rolling Rapidly-exploring Random Tree for Mobile Robot," School of Computer Science and Technology,NUST,Nanjing 210094,China, vol. 34, no. 5, pp. 642-648, 2010.[17] A. Ravankar, A. A. Ravankar, Y. Kobayashi, Y. Hoshino, and C. Peng, "Path Smoothing Techniques in Robot Navigation: State-of-the-Art, Current and Future Challenges," Sensors (Basel, Switzerland), vol. 18, 2018.[18] Wikipedia. "Robot Operating System." Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=Robot_Operating_System&oldid=985900454 (accessed 4 November 2020 02:47 UTC. 描述 碩士
國立政治大學
資訊科學系
107753044資料來源 http://thesis.lib.nccu.edu.tw/record/#G0107753044 資料類型 thesis dc.contributor.advisor 李蔡彥 zh_TW dc.contributor.advisor Li, Tsai-Yen en_US dc.contributor.author (Authors) 蔡苡雋 zh_TW dc.contributor.author (Authors) Tsai, Yi-Chuan en_US dc.creator (作者) 蔡苡雋 zh_TW dc.creator (作者) Tsai, Yi-Chuan en_US dc.date (日期) 2021 en_US dc.date.accessioned 1-七月-2021 19:57:18 (UTC+8) - dc.date.available 1-七月-2021 19:57:18 (UTC+8) - dc.date.issued (上傳時間) 1-七月-2021 19:57:18 (UTC+8) - dc.identifier (Other Identifiers) G0107753044 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/135982 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學系 zh_TW dc.description (描述) 107753044 zh_TW dc.description.abstract (摘要) 路徑規劃一直是無人機自動化研究中重要的課題，其目的在於確保無人機的安全性及效率，在移動中隨時更新與即時規劃路徑，讓無人機順利到達目標點。無人機的機上運算對於複雜或廣大的區域，需要消耗很多計算時間，而對於無人機的安全性來說，需要較短的規劃時間來達到飛行安全的目的。在本論文中，我們探討了不同的路徑規劃演算法的優劣勢，並決定採用快速搜索隨機樹(RRT)作為無人機的路徑規劃演算法，且提出了一種階層式協力計算架構，此架構利用機上運算與基地台的非同步合作規劃，嘗試解決在單層路徑規劃上較難同時確保規劃即時性與路徑最優性的問題。本系統可用於無人機行駛在不確定的環境中即時規劃路徑，並確保無人機在飛行時的安全，及產出有效率的路徑。我們以四種不同環境條件下進行即時模擬飛行實驗，實驗結果顯示本架構可有效降低飛行花費時間或是飛行路徑長度，並且能在有提供風場資訊的環境中，選擇更順風的路徑飛行。 zh_TW dc.description.abstract (摘要) Path planning has always been an important topic in the research of UAV automated navigation. The purpose of this work is to consider the safety and efficiency of UAVs when planning and updating the path in real-time during the movement such that the UAV can reach the goal configuration successfully. Global path planning usually requires a great amount of computing for complex or large areas, which may be beyond the onboard computing power of many UAVs. Even if the computation can be done on board, the long planning time may not guarantee the safety of UAV navigation. In this paper, we investigate the pros and cons of various path planning algorithms and choose Rapidly-exploring Random Tree (RRT) as a base planning algorithm for UAVs. We proposed a collaborative hierarchical computing architecture, which uses asynchronous cooperative planning of the computing resources onboard and at the base station. Our architecture aims to tackle the difficulty in single-layer path planning where the immediacy of planning and the optimality of the path can not be ensured at the same time. Our system can be used to plan the path for a UAV in an uncertain environment in real-time and ensure its safety during the flight and the effectiveness of the output path. We have conducted experiments in simulation for a typical UAV under four different environmental conditions. The experimental results show that our method can effectively reduce flight time or path length and choose a more downwind path if the wind field information is provided. en_US dc.description.tableofcontents 致謝 i摘要 iiAbstract iii目錄 iv圖目錄 vi表目錄 viii第1章 緒論 11.1 研究背景 11.2 研究動機與目標 21.3 論文貢獻 31.4 論文架構 4第2章 背景知識與相關研究 52.1 運動規劃 52.2 路徑規劃演算法 72.3 快速搜索隨機樹 82.4 路徑平滑化 132.5 演算法測試實驗與結論 14第3章 研究方法 163.1 問題定義 163.2 系統架構流程 193.3 系統通訊架構 213.4 系統架構模組 23第4章 實驗與分析 284.1 實驗說明 284.2 系統展示 344.3 實驗結果分析 39第5章 結論 505.1 研究結論 505.2 未來展望 52參考文獻 53附錄 55 zh_TW dc.format.extent 4364334 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0107753044 en_US dc.subject (關鍵詞) 無人機 zh_TW dc.subject (關鍵詞) 運動規劃 zh_TW dc.subject (關鍵詞) 路徑規劃 zh_TW dc.subject (關鍵詞) 快速搜索隨機樹 zh_TW dc.subject (關鍵詞) UAV en_US dc.subject (關鍵詞) Hierarchical Motion Planning en_US dc.subject (關鍵詞) Path Planning en_US dc.subject (關鍵詞) Rapidly-exploring Random Tree en_US dc.title (題名) 不確定的環境中無人機的階層式協力運動規劃 zh_TW dc.title (題名) A Collaborative Hierarchical Online Motion Planner for UAV in an Uncertainty Environment en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] Wikipedia. "Unmanned aerial vehicle." Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=Unmanned_aerial_vehicle&oldid=955084723 (accessed 7 May 2020 05:46 UTC.[2] Wikipedia. "Motion planning." Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=Motion_planning&oldid=950519176 (accessed 7 May 2020 05:25 UTC.[3] H. Yang, Q. Jia, and W. Zhang, "An Environmental Potential Field Based RRT Algorithm for UAV Path Planning," in 2018 37th Chinese Control Conference (CCC), 2018: IEEE, pp. 9922-9927.[4] L. Yang, J. Qi, J. Xiao, and X. Yong, "A literature review of UAV 3D path planning," in Proceeding of the 11th World Congress on Intelligent Control and Automation, 2014: IEEE, pp. 2376-2381.[5] G. A. Thanellas, V. C. Moulianitis, and N. A. Aspragathos, "A spatially wind aware quadcopter (UAV) path planning approach," IFAC-PapersOnLine, vol. 52, no. 8, pp. 283-288, 2019/01/01/ 2019, doi: https://doi.org/10.1016/j.ifacol.2019.08.084.[6] K. Yang, S. Keat Gan, and S. Sukkarieh, "A Gaussian process-based RRT planner for the exploration of an unknown and cluttered environment with a UAV," Advanced Robotics, vol. 27, no. 6, pp. 431-443, 2013.[7] W. Zu, G. Fan, Y. Gao, Y. Ma, H. Zhang, and H. Zeng, "Multi-uavs cooperative path planning method based on improved rrt algorithm," in 2018 IEEE International Conference on Mechatronics and Automation (ICMA), 2018: IEEE, pp. 1563-1567.[8] L. De Filippis, G. Guglieri, and F. Quagliotti, "A minimum risk approach for path planning of UAVs," Journal of Intelligent & Robotic Systems, vol. 61, no. 1-4, pp. 203-219, 2011.[9] A. González-Sieira, M. Mucientes, and A. Bugarín, "Motion planning under uncertainty in graduated fidelity lattices," Robotics and Autonomous Systems, vol. 109, pp. 168-182, 2018.[10] F. Li, S. Zlatanova, M. Koopman, X. Bai, and A. Diakité, "Universal path planning for an indoor drone," Automation in Construction, vol. 95, pp. 275-283, 2018.[11] Z. Beck, W. T. L. Teacy, A. Rogers, and N. R. Jennings, "Collaborative online planning for automated victim search in disaster response," Robotics and Autonomous Systems, vol. 100, pp. 251-266, 2018/02/01/ 2018, doi: https://doi.org/10.1016/j.robot.2017.09.014.[12] S. M. LaValle, J. J. Kuffner, and B. Donald, "Rapidly-exploring random trees: Progress and prospects," Algorithmic and computational robotics: new directions, no. 5, pp. 293-308, 2001.[13] S. Karaman and E. Frazzoli, "Incremental sampling-based algorithms for optimal motion planning," Robotics Science and Systems VI, vol. 104, no. 2, 2010.[14] 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), 2000, vol. 2: IEEE, pp. 995-1001.[15] T.-Y. Li and Y.-C. Shie, "An incremental learning approach to motion planning with roadmap management," in Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No. 02CH37292), 2002, vol. 4: IEEE, pp. 3411-3416.[16] K. Liang, Z. Chun-xia, and G. Jian-hui, "Path Planning Based on Fuzzy Rolling Rapidly-exploring Random Tree for Mobile Robot," School of Computer Science and Technology,NUST,Nanjing 210094,China, vol. 34, no. 5, pp. 642-648, 2010.[17] A. Ravankar, A. A. Ravankar, Y. Kobayashi, Y. Hoshino, and C. Peng, "Path Smoothing Techniques in Robot Navigation: State-of-the-Art, Current and Future Challenges," Sensors (Basel, Switzerland), vol. 18, 2018.[18] Wikipedia. "Robot Operating System." Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=Robot_Operating_System&oldid=985900454 (accessed 4 November 2020 02:47 UTC. zh_TW dc.identifier.doi (DOI) 10.6814/NCCU202100475 en_US
