臺灣博碩士論文加值系統

無人機具有低成本、高機動性之特性。相較於傳統飛行器，對於起降地點的要求更為寬鬆，且操作門檻不高，同時又可避免人員飛安事故之風險，非常適於替代人員進行多類高風險之飛行任務。在這些任務中，空中攝影是無人機最熱門的一種應用。

本論文所要探討的問題，是在一個有限的區域範圍內，使得多台異質性的無人機協同飛行完成被賦予的巡航拍攝任務。而在過往的研究中，已有眾多有關無人機路徑規劃的問題已被提出並深入討論，例如添加無人機的飛行參數控制、單台或是多台無人機的飛行路徑規劃…等等。但卻缺乏討論異質性無人機協同飛行。

本論文提出飛行路徑不等同於巡航路徑的概念，路徑規劃的目的主要是為了滿足巡航任務的監控需求並同時追求成本最小化。因此本論文以無人機鏡頭覆蓋範圍的觀點來探討巡航任務的路徑規劃。並引入攝影鏡頭可隨之變換角度的概念，除了飛行距離與能源耗損的考量，同時也追求不同異質性無人機型的最佳配置，以期做到花費最少的飛行成本。

本論文提出一個多目標最佳化的方式解決此一多目標最佳化問題。實驗結果顯示本論文之方法可以獲得多個非支配解。並且染色體解碼後的飛行路徑都十分接近需求模型的樣貌。表示本論文設計的演算法與參數，在求解混合型視角可調之無人機隊路徑規劃問題上，具有一定成效。

Unmanned Aerial Vehicle (UAV) with the characteristic of low cost and high mobility. Compared to flying traditional aircraft, the requirements of landing UAV site is low, the skill of UAV operation is ease, and UAV is capable to avoid the risk of human accident. Therefore, it is very suitable for alternative personnel to carry out a variety kinds of high-risk missions. Among these missions, aerial photography is one of the most popular application of unmanned aerial vehicles.

In this paper, we investigated the uses of heterogeneous UAVs in aerial photography mission within a limited area. In the literature, numerous approaches have been proposed in UAV path planning, such as adding UAV flight parameter control, single or multiple UAVs flight path planning ... and so on. However, none of them discussed heterogeneous UAVs.

In this paper, the concept of flying path is not equivalent to the cruise path is proposed. The objective of UAV path planning should meet the requirement of aerial photography mission while optimizes the mission costs. Therefore, we investigated the heterogeneous UAVs with adjustable image angle in aerial photography mission. A multiobjective optimization problem is formulated, considering the coverage of UAV camera, flight distance of UAVs, energy consumption, and the configuration of heterogeneous UAVs.

In this paper, we proposed a multi-objective evolutionary approach to solve the investigated problem. From the experimental results, the proposed approach can effectively obtain multiple non-dominated solutions. The solutions also shows that the decoded routes of UAVs path is very similar to the appearance of the demand model.

摘要 i
ABSTRACT ii
誌謝 iii
目錄 iv
表目錄 vii
圖目錄 viii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 問題描述 1
1.3 研究目標 2
1.4 論文架構 2
第二章 文獻探討 3
2.1 無人飛行載具 3
2.2 路徑規劃問題 4
2.3 遺傳演算法 5
2.3.1 染色體編碼 6
2.3.2 產生初始族群 7
2.3.3 評估適應值 7
2.3.4 選擇 7
2.3.5 交配 8
2.3.6 突變 10
2.4 多目標最佳化 11
2.4.1 權重法 11
2.4.2 柏拉圖最佳解 12
2.5 Hypervolume 12
第三章 混合型視角可調之無人機隊路徑規劃問題 14
3.1 實驗環境定義 14
3.2 符號說明與目標函數 17
3.2.1 符號說明 17
3.2.2 目標函數說明 18
第四章 設計多目標遺傳演算法求解混合型視角可調之無人機隊路徑規劃問題 20
4.1 演算法流程說明 20
4.2 多目標遺傳演算法 21
4.2.1 染色體編碼 21
4.2.2 多目標適應函數 23
4.2.3 選擇 23
4.2.4 交配 23
4.2.5 突變 24
4.2.6 修補機制 25
4.2.7 μ＋λ選擇法 26
第五章 實驗及結果 27
5.1 實驗參數設定 27
5.1.1 實驗一 28
5.1.2 實驗二 28
5.1.3 實驗三 29
5.1.4 實驗四 29
5.2 實驗結果分析 29
5.2.1 實驗一 29
5.2.2 實驗二 34
5.2.3 實驗三 40
5.2.3.1 指數需求模型 40
5.2.3.2 線性需求模型 43
5.2.3.3 常態需求模型 46
5.2.3.4 泊松需求模型 49
5.2.3.5 平面需求模型 52
5.2.3.6 中華大學需求模型 55
5.2.4 實驗四 58
第六章 結論 92
參考文獻 93

Bagherian, M., & Alos, A. (2015). 3D UAV trajectory planning using evolutionary algorithms: A comparison study. The Aeronautical Journal, 119(1220), 1271-1285.
Bao, Y., Fu, X., & Gao, X. (2010). Path planning for reconnaissance UAV based on particle swarm optimization. Paper presented at the Computational Intelligence and Natural Computing Proceedings (CINC), 2010 Second International Conference on.
Bottasso, C. L., Leonello, D., & Savini, B. (2008). Path planning for autonomous vehicles by trajectory smoothing using motion primitives. IEEE Transactions on Control Systems Technology, 16(6), 1152-1168.
De Filippis, L., Guglieri, G., & Quagliotti, F. (2012). Path planning strategies for UAVS in 3D environments. Journal of Intelligent & Robotic Systems, 65(1), 247-264.
Deb, K. (2001). Multi-objective optimization using evolutionary algorithms, 2001. Chicheter, John-Wiley.
Diaz-Gomez, P. A., & Hougen, D. F. Initial Population for Genetic Algorithms: A Metric Approach.
Eiben, A. E., & Smith, J. E. (2003). Introduction to evolutionary computing (Vol. 53): Springer.
Grefenstette, J. J. (1986). Optimization of control parameters for genetic algorithms. IEEE Transactions on systems, man, and cybernetics, 16(1), 122-128.
Guermonprez, P. (2016). 無人機起飛：從軍事任務到民用空拍，無人機的未來與創新應用. In 謝孟渝 (Ed.). 台中市: 晨星出版社.
Hajela, P., & Lin, C.-Y. (1992). Genetic search strategies in multicriterion optimal design. Structural optimization, 4(2), 99-107.
Ho, S.-Y., Shu, L.-S., & Chen, J.-H. (2004). Intelligent evolutionary algorithms for large parameter optimization problems. IEEE Transactions on Evolutionary Computation, 8(6), 522-541.
Horn, J., Nafpliotis, N., & Goldberg, D. E. (1994). A niched Pareto genetic algorithm for multiobjective optimization. Paper presented at the Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on.
Konak, A., Coit, D. W., & Smith, A. E. (2006). Multi-objective optimization using genetic algorithms: A tutorial. Reliability Engineering & System Safety, 91(9), 992-1007.
Koumousis, V. K., & Katsaras, C. P. (2006). A saw-tooth genetic algorithm combining the effects of variable population size and reinitialization to enhance performance. IEEE Transactions on Evolutionary Computation, 10(1), 19-28.
Li, X., Xie, J., Cai, M., Xie, M., & Wang, Z. (2009). Path planning for UAV based on improved heuristic A∗ algorithm. Paper presented at the Electronic Measurement & Instruments, 2009. ICEMI'09. 9th International Conference on.
Macharet, D. G., Neto, A. A., & Campos, M. F. M. (2010). Feasible UAV path planning using genetic algorithms and Bézier curves. Paper presented at the Brazilian Symposium on Artificial Intelligence.
Masehian, E., & Sedighizadeh, D. (2007). Classic and heuristic approaches in robot motion planning-a chronological review. World Academy of Science, Engineering and Technology, 23, 101-106.
Nikolos, I. K., Valavanis, K. P., Tsourveloudis, N. C., & Kostaras, A. N. (2003). Evolutionary algorithm based offline/online path planner for UAV navigation. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 33(6), 898-912.
Pehlivanoglu, Y. V. (2012). A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV. Aerospace Science and Technology, 16(1), 47-55.
Roberge, V., Tarbouchi, M., & Labonté, G. (2013). Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning. IEEE Transactions on Industrial Informatics, 9(1), 132-141.
Savla, K., Frazzoli, E., & Bullo, F. (2008). Traveling salesperson problems for the Dubins vehicle. IEEE Transactions on Automatic Control, 53(6), 1378-1391.
Tseng, F.-H., Liang, T.-T., Lee, C.-H., Chou, L.-D., & Chao, H.-C. (2014). A star search algorithm for civil UAV path planning with 3G communication. Paper presented at the Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP), 2014 Tenth International Conference on.
Tuncer, A., & Yildirim, M. (2012). Dynamic path planning of mobile robots with improved genetic algorithm. Computers & Electrical Engineering, 38(6), 1564-1572.
Wang, G., Li, Q., & Guo, L. (2010). Multiple UAVs routes planning based on particle swarm optimization algorithm. Paper presented at the Information Engineering and Electronic Commerce (IEEC), 2010 2nd International Symposium on.
Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C. M., & Da Fonseca, V. G. (2003). Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on Evolutionary Computation, 7(2), 117-132.
白絜成, 劉益誠, 蕭宇伸, 連惠邦, & 林秉賢. (2015). 無人飛行載具掛載消費型攝影機應用於防災可行性研究. [Analysis of Accuracy for UAV-derived Topography from a GoPro Camera]. 中華水土保持學報, 46(3), 142-149.
林豐澤. (2005a). 演化式計算上篇：演化式演算法的三種理論模式. [Evolutionary Computation Part 1: Three Theoretic Models of Evolutionary Algorithms]. 智慧科技與應用統計學報, 3(1), 1-28.
林豐澤. (2005b). 演化式計算下篇：基因演算法以及三種應用實例. [Evolutionary Computation Part 2: Genetic Algorithms and Their Three Applications]. 智慧科技與應用統計學報, 3(1), 29-56.
施錦揮, 游政恭, 鄒慶敏, 蔡季欣, 林志清, & 林燕山. (2010). 無人飛行載具應用於防救災圖資供應之研究-以北二高崩塌地為例. 地籍測量: 中華民國地籍測量學會會刊, 29(3), 17-36.
陳冠㞶. (2016). 基於多目標演化式演算法的視角可調之無人機路徑規劃. (碩士), 中華大學, 新竹市.
楊宗岳, 羅國峯, 林永仁, & 黃勤財. (2009). 應用無人飛機於公路防、救災之可行性探討 臺灣公路工程 (Vol. 35, pp. 2-9).