基於最佳化之多台無人機系統無碰撞軌跡規劃

Optimization-based Collision-free Trajectory Planning for Multiple Unmanned Aerial Vehicles System

王捷(Jie Wang)

指導教授 ： 連豊力

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2022年)

https://doi.org/10.6342/NTU202204238

摘要

本篇論文為多台無人機的導航系統提出一個完整的系統架構，在此架構中有以下三個主要探討議題: (1) 所產生出來的軌跡能避免無人機之間發生碰撞，並抵達目標位置 (2) 適合群體系統的計算效率 (3) 飛行器的動態特性。本篇論文提出了一個能夠解決上述三個課題的多台無人機軌跡規劃系統。
其軌跡規劃系統可分為兩部分，基於標誌物的視覺定位系統以及基於最佳化的路徑規劃系統。視覺定位系統主要負責提供無人機自體定位資訊。在這個系統中，每台無人機所搭載的相機會偵測已知位置的標誌物，並利用影像中的標誌物來估測出其之間的轉換關係。由於標誌物容易因為丟失影像造成無法取得定位資訊，因此本系統中使用了卡爾曼濾波器估測位置狀態，並透過融合慣性測量單元提升定位的穩定性與精準度。而軌跡規劃系統則根據視覺定位系統所提供的無人機位置資訊，計算出移動到目標位置最佳的軌跡。由於多台無人機導航系統需要良好的計算效率，因此所提出的軌跡規劃系統，首先採用全局路徑規劃器產生離散路徑並分解為局部目標點。局部規劃器再根據此目標點規劃出平滑且符合飛行器動態特性的軌跡。此局部規劃採用分布式模型預測的方式，且無人機群體之間彼此能夠交換軌跡的資訊，因此可以通過預測軌跡來檢測和避免可能發生的碰撞。
最後，本論文展示了多項模擬結果，以證明此系統的可行性以及性能。

關鍵字

無人飛行器 ； 多智能體系統 ； 即時系統 ； 最佳化路徑規劃 ； 碰撞避免 ； 模型預測控制

並列摘要

In this thesis, a complete system architecture for the navigation system of multiple UAVs is proposed. There are three main topics discussed in this system architecture: (1) the generated trajectory can avoid collisions between UAVs and reach the target position (2) computational efficiency of the multiple UAV system (3) dynamics of the system. This thesis proposes a trajectory planning system that can solve the above three issues.
The trajectory planning system can be divided into two parts, a marker-based visual positioning system and an optimization-based path planning system. The visual positioning system is responsible for providing UAV position information. In this system, each UAV uses camera to detect markers, which were deployed at known locations. The markers in the image are used for estimating the transformation relationship between UAV and them. Since it is easy to lose the image of the marker and thus cannot obtain the positioning information, the system uses a Kalman filter to estimate the position state and enhances the stability and accuracy by fusing with the inertial measurement unit. The trajectory planning system finds out the best trajectory for moving to the target position according to the position information of the UAV provided by the visual positioning system. Since multiple UAV navigation systems require computational efficiency, the proposed trajectory planning system first uses a global path planner to generate discrete paths and decompose them into local goals. Based on the local goals, the local planner plans a smooth trajectory that satisfies to the dynamic characteristics of the UAV. The local planning adopts the distributed model prediction approach, in which UAVs exchange trajectory information with other; therefore, the possible collision can be detected and avoided through the predicted trajectory.
Finally, this thesis presents a number of simulation to demonstrate the feasibility and performance of the proposed system.

並列關鍵字

Unmanned aerial vehicles ； multi-agent systems ； real-time systems ； optimal trajectory planning ； collision avoidance ； model predictive control

參考文獻

[1: Tomic et al. 2012]Teodor Tomic, Korbinian Schmid, Philipp Lutz, Andreas Domel, Michael Kassecker, Elmar Mair, Iris Lynne Grixa, Felix Ruess, Michael Suppa, and Darius Burschka, “Toward a Fully Autonomous UAV: Research Platform for Indoor and Outdoor Urban Search and Rescue,” IEEE Robotics and Automation Magazine, Vol. 19, No. 3, pp. 44-56, Oct. 2012.

[2: Sung Nielsen 2020]Inkyung Sung, and Peter Nielsen, “Zoning a Service Area of Unmanned Aerial Vehicles for Package Delivery Services,” Journal of Intelligent Robotic Systems, Vol. 97, No. 1, pp. 719–731, March 2020.

[3: Das et al. 2021]Dyutimoy Nirupam Das, Rohan Sewani, Junwei Wang, and Manoj Kumar Tiwari, “Synchronized Truck and Drone Routing in Package Delivery Logistics,” IEEE Transactions on Intelligent Transportation Systems, Vol. 22, No. 9, pp. 5772-5782, Sept. 2021.

[4: Bryson et al. 2010]Mitch Bryson, Alistair Reid, Fabio Ramos, and Salah Sukkarieh, “Airborne Vision-Based Mapping and Classification of Large Farmland Environments,” Journal of Field Robotics, Vol. 27, No. 5, pp. 632-655, Aug. 2010.

[5: Motlagh et al. 2017]Naser Hossein Motlagh, Miloud Bagaa, and Tarik Taleb, “UAV-Based IoT Platform: A Crowd Surveillance Use Case,” IEEE Communications Magazine, Vol. 55, No. 2, pp. 128-134, Feb. 2017.