臺灣博碩士論文加值系統

無人機（UAV）可能是欲在短期間內完成大片地域全面搜索掃描（亦即覆蓋）任務的唯一手段，這些區域覆蓋任務若僅靠地面人力將難以快速完成，這是因為地面區域之間可能沒有方便的道路連結；反之，空中UAV之移動不受地域連結的障礙，較可輕易地自空中對目標地面區域展開搜索、監視或拍攝照片。然而UAV必須擔心續航力是否足夠，若欲持續其覆蓋任務，必須同時規劃其充換電行程；本研究擬以載有充換電設施的車輛（GV）當成行動式的動態充換電基地，讓UAV可在GV上進行充換電作業。因此，GV與UAV兩者的路線必須聯合規劃。
假設我們將空域劃分割成數個可覆蓋所有目標地面區域的虛擬空間單元（空域節點），而相鄰的空域節點間構成空域節線，則目標地面區域上的掃描任務，將可使用UAV在其相應的空域節點滯空巡邏（亦即覆蓋）一段特定時間來完成。因此，在給定必須被覆蓋的地面區域後，本研究擬規劃最佳無人機路線，以在最短時間內可覆蓋所有必要的空域節點，同時其飛行路線必須隨時顧及足夠的續航力。由於無人機的電池功率有限，它們可先由GV攜帶，GV在地面道路可停靠之點為地域節點，而GV在地面可能移動的路網稱為地域網路。UAV可由GV在其地域網路的某些地域節點上發射、降落以充換電池。以網路圖形而言，共有UAV的空域網路與GV的地域網路，而這兩層網路間再由UAV可能的起飛或降落之地空節線所串接。因此，GV路線僅在地域網路上，而UAV路線則橫跨空域與地域網路，UAV與GV路線重合即可充換電。
本研究探討GV和UAV的最佳路線規劃方式，以便UAV在最短總時間內能掃描完所有目標地面區域，並考量UAV的續航力限制。為了模擬UAV和GV的聯合作業方式，我們將原問題轉換成在空地兩層網路與其間連結上的「覆蓋路徑規劃問題」以及「二階層式路徑規劃問題」，以時空網路為基礎提出兩種整數規劃數學模型：單一GV配單一UAV（ ）、以及多台UAV（ ）等兩種情境。其中， 可能是第一個可以同時處理單一GV配多台UAV路線的數學規劃模型。雖然上述模型可精準地規劃出最佳GV與UAV的詳細動態，但其求解十分耗時。
為了在更短的時間內計算好路線，我們針對 設計了一個在時空網路中以深度優先演算法為基礎的貪婪算法，試圖在T期限內為UAV找到一條可覆蓋所有目標空城節點的可行路線，再用類似二分搜尋法概念以逼近最佳之T值。數值測試結果顯示，我們的貪婪算法通常能在短時間內獲得不錯的可行解，至於多台UAV的啟發式演算法則有賴未來能發展更有效率的責任區域劃分方式來加以處理。

The Unmanned Aerial Vehicles (UAVs) may be the only means by which to conduct coverage missions that search, monitor, or take photos from the air space over target ground areas that are too difficult to reach by ground manpower. Suppose we divided the air space into several virtual cells that cover all the target ground areas. Then, a scan mission on a target ground area can be done by a UAV flying over (i.e., covering) its corresponding virtual cell in air space for a specific period of time. In this research, we plan to route UAVs to cover all necessary virtual cells. Since UAVs have limited battery power, they can be carried by some mobile Ground Vehicles (GVs) and then be launched from and retrieved by GVs on some nodes in the ground road networks.
This thesis investigates how to calculate optimal routes for both GVs and UAVs so that all the target ground areas can be scanned by UAVs within a minimum total time subject to the battery limitation of the UAVs. To model the combined operations by the UAVs and GVs, we use the coverage path planning (CPP) and two-echelon routing problems as our approaches. We propose two mathematical models based on integer programming techniques over a time-space network. We consider one GV with one UAV case ( ) and one GV with multiple UAVs case ( ). To the best of our knowledge, might arguably be the first mathematical programming model that can deal with routings for both GV and multiple UAVs at the same time. Our proposed model can calculate the detailed movement for both UAVs and GV, yet it is very time-consuming.
To calculate good routings in shorter time, we also designed a greedy algorithm for the one GV with one UAV case, where a depth-first search mechanism is exploited to find a feasible UAV route in the time-pace network that covers all target areas within the time limit T. The computational experiments indicate our greedy algorithm calculates a good solution faster than the proposed integer programming model.

Abstract in Chinese ii
Abstract iv
Acknowledgments v
Table of Contents vi
List of Figure viii
List of Table ix
Chapter 1 Introduction 1
1.1. Research Background 1
1.2. Research Objective 3
1.3. Research Scope 3
1.4. Thesis Outline 3
Chapter 2 Literature Review 4
2.1. Unmanned Aerial Vehicles (UAVs) 4
2.1.1. UAV Characteristics 4
2.1.2. UAV Applications 5
2.2. The Combined Operation of GVs and UAVs 6
2.3. Two-Echelon Location Routing Problem 8
2.4. Coverage Path Planning 11
2.5. Research Contribution 13
Chapter 3 Mathematical Programming Models for Planning the Joint UAV and GV Paths 15
3.1. Modeling Approach 15
3.2. Problem Definition 18
3.3. Mathematical Models 20
3.3.1. Notation 20
3.3.2. The one-GV-one-UAV model 21
3.3.3. The one-GV-multiple-UAV model 26
Chapter 4 Heuristic Algorithms for Planning the Joint UAV and GV Paths 29
4.1. Greedy Algorithm for the one-GV-one-UAV case 29
4.1.1. UAV path planning heuristic 31
4.1.2. GV path planning heuristic 33
4.2. Estimation on T and cases of multiple UAVs 33
Chapter 5 Computational Experiments 35
5.1. Settings in the Computational Environment 35
5.2. Settings of Experimental Cases 35
5.3. Experimental Results 36
5.3.1. Mathematical Models Result 36
5.3.2. Results for the Proposed Algorithm 39
5.3.3. Performance Comparison 41
5.4. Additional Experiment 43
5.5. Summary 46
Chapter 6 Conclusions and Suggested Future Research 47
6.1. Conclusions 47
6.2. Suggested Future Research 48
Reference 51

Avellar, G., Pereira, G., Pimenta, L., ＆ Iscold, P. (2015). Multi-UAV routing for area coverage and remote sensing with minimum time. Sensors, 15(11), 27783-27803.
Barrientos, A., Colorado, J., Cerro, J. d., Martinez, A., Rossi, C., Sanz, D., ＆ Valente, J. (2011). Aerial remote sensing in agriculture: A practical approach to area coverage and path planning for fleets of mini aerial robots. Journal of Field Robotics, 28(5), 667-689.
Choi, Y., Choi, Y., Briceno, S., ＆ Mavris, D. N. (2018). Coverage path planning for a UAS imagery mission using column generation with a turn penalty. 2018 International Conference on Unmanned Aircraft Systems (ICUAS).
Cuda, R., Guastaroba, G., ＆ Speranza, M. G. (2015). A survey on two-echelon routing problems. Computers ＆ Operations Research, 55, 185-199.
Dalamagkidis, K. (2015). Definitions and terminology. In K. P. Valavanis ＆ G. J. Vachtsevanos (Eds.), Handbook of unmanned aerial vehicles (pp. 43-55). Dordrecht: Springer Netherlands.
Fondation Suisse de Deminage (FSD). (2016). Drones in humanitarian action. Geneva. Retrieved from https://drones.fsd.ch/wp-content/uploads/2016/11/Drones-in-Humanitarian-Action.pdf
Galceran, E., ＆ Carreras, M. (2013). A survey on coverage path planning for robotics. Robotics and Autonomous Systems, 61(12), 1258-1276.
Garone, E., Naldi, R., Casavola, A., ＆ Frazzoli, E. (2010). Cooperative mission planning for a class of carrier-vehicle systems. In 49th IEEE Conference on Decision and Control (CDC). Atlanta, Georgia, USA: IEEE
Hu, M., Liu, W., Peng, K., Ma, X., Cheng, W., Liu, J., ＆ Li, B. (2018). Joint routing and scheduling for vehicle-assisted multi-drone surveillance. IEEE Internet of Things Journal, 1-1.
Khan, A., Noreen, I., ＆ Habib, Z. (2017). On complete coverage path planning algorithms for non-holonomic mobile robots: Survey and challenges. Journal of Information Science and Engineering, 33(1), 101-121.
Luo, Z., Liu, Z., ＆ Shi, J. (2017). A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle. Sensors, 17(5), 1144.
Luo, Z., Liu, Z., Shi, J., Wang, Q., Zhou, T., ＆ Liu, Y. (2018). The mathematical modeling of the two-echelon ground vehicle and its mounted unmanned aerial vehicle cooperated routing problem. 2018 IEEE Intelligent Vehicles Symposium (IV).
Manyam, S. G., Casbeer, D. W., ＆ Sundar, K. (2016). Path planning for cooperative routing of air-ground vehicles. 2016 American Control Conference (ACC).
Mathew, N., Smith, S. L., ＆ Waslander, S. L. (2013). A graph-based approach to multi-robot rendezvous for recharging in persistent tasks. 2013 IEEE International Conference on Robotics and Automation.
Mathew, N., Smith, S. L., ＆ Waslander, S. L. (2015a). Multirobot rendezvous planning for recharging in persistent tasks. IEEE Transactions on Robotics, 31(1), 128-142.
Mathew, N., Smith, S. L., ＆ Waslander, S. L. (2015b). Planning paths for package delivery in heterogeneous multirobot teams. IEEE Transactions on Automation Science and Engineering, 12(4), 1298-1308.
Moravec, H., ＆ Elfes, A. (1985). High resolution maps from wide angle sonar. Proceedings. 1985 IEEE International Conference on Robotics and Automation.
Mourelo Ferrandez, S., Harbison, T., Weber, T., Sturges, R., ＆ Rich, R. (2016). Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm. Journal of Industrial Engineering and Management, 9(2), 374.
Nam, L. H., Huang, L., Li, X. J., ＆ Xu, J. F. (2016). An approach for coverage path planning for UAVs. 2016 IEEE 14th International Workshop on Advanced Motion Control (AMC).
Nedjati, A., Izbirak, G., Vizvari, B., ＆ Arkat, J. (2016). Complete coverage path planning for a multi-UAV response system in post-earthquake assessment. Robotics, 5(4), 26.
Otto, A., Agatz, N., Campbell, J., Golden, B., ＆ Pesch, E. (2018). Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey. Networks, 72(4), 411-458.
Pham, T. H., Bestaoui, Y., ＆ Mammar, S. (2017). Aerial robot coverage path planning approach with concave obstacles in precision agriculture. 2017 Workshop on Research, Education, and Development of Unmanned Aerial Systems (RED-UAS).
Tokekar, P., Hook, J. V., Mulla, D., ＆ Isler, V. (2016). Sensor planning for a symbiotic UAV and UGV system for precision agriculture. IEEE Transactions on Robotics, 32(6), 1498-1511.
Vachtsevanos, G. J., ＆ Valavanis, K. P. (2015). Military and civilian unmanned aircraft. In K. P. Valavanis ＆ G. J. Vachtsevanos (Eds.), Handbook of unmanned aerial vehicles (pp. 93-103). Dordrecht: Springer Netherlands.
Vergouw, B., Nagel, H., Bondt, G., ＆ Custers, B. (2016). Drone technology: Types, payloads, applications, frequency spectrum issues, and future developments. in b. custers (Ed.), The future of drone use: Opportunities and threats from ethical and legal perspectives (pp. 21-45). The Hague: T.M.C. Asser Press.