當大型災難發生時，搜尋與救難團隊通常必須面對地形與障礙物的限制與挑戰，也因為這樣的限制無人飛行載具，例如:四軸飛行器，開始被運用到災難現場的資料探勘與蒐集。本篇研究提出了多無人機協作以協助搜尋與救援任務，利用無人機間飛行路徑的演算法設計，以達到用最少的無人機達到最高的區域覆蓋率（Coverage），同時還可以最小化重複覆蓋（Overlap）與搜尋時間。當通訊狀況良好時，中控式（Centralized）演算法藉由遠端控制中心（Remote control center）及時計算並控制每一台無人機飛行的路徑；此演算法仰賴無人機與遠端控制中心間的通訊連線，在災難發生時並無法確保通訊是不中斷的，因此我們也提出分散式演算法（Distributed Solution）以解決通訊中斷時飛行路徑的規劃。混合式演算法（Hybrid Solution）則利用無人機與與人機之間的通訊（Drone to drone, D2D）分享地圖資訊（例如：已拜訪過的區域）；除此之外，貪婪策略（Greedy Strategy）與優先權策略（Priority Strategy）也被運用在混合式演算法上，用以提高覆蓋率同時減少重複覆蓋與區域轉換的飛行距離。最後，由實驗結果得知我們所提出的演算法效能非常接近於最佳解（中控式演算法）

During search and rescue (SAR) operations in a large disaster occur, SAR teams often face the challenges of terrain restrictions. Unmanned Aerial Vehicles (UAVs), such as drones, have been used to support such operations to explore and collect information regarding the disaster area. In this research, we propose Multi-Drone Collaboration to support search and rescue (SAR) operations with cooperating flying path algorithms which require the least number of drones to achieve maximum coverage area while minimize overlapping and searching time. In the case of communication is available, Centralized algorithm is proposed to control all drone’s flying path with remote control center in real time. However, this approach required communication connection between drones and remote control center. When communication is interrupted in a disaster area, Distributed Solution can overcome the issue. In Hybrid Solution, drone-to-drone (D2D) communication is used to share local map (i.e., searched regions) with other drones. In addition, Greedy Strategy and Priority Strategy are applied to Hybrid Solution to increase coverage while minimize overlapping and moving distance between sub-regions. Finally, simulation results show that the proposed solution performs closely to the best case (i.e. Centralized Solution).

[1] M. A. Goodrich, B. S. Morse, D. Gerhardt, J. L. Cooper, M. Quigley, J. A.Adams, and C. Humphrey, “Supporting wilderness search and rescue using a camera-equipped mini UAV, ” Journal of Field Robotics, vol. 25, pp. 89-110. 2008.
[2] I. Maza and A. Ollero, “Multiple UAV cooperative searching operation using polygon area decomposition and efficient coverage algorithms,” Distributed Autonomous Robotic Systems , pp. 221–230, 2007.
[3] J. Ousingsawat, “UAV Path Planning for Maximum Coverage Surveillance of Area with Different Priorities,” The 20th Conference of Mechanical Engineering(COMS), 2006.
[4] J.F. Araujo, P.B. Sujit, J.B. Sousa “Multiple UAV area decomposition and coverage” in Symposium on Computational Intelligence for Security and Defense Applications(CISDA), 2013
[5] W. H. Huang, “Optimal line-sweep-based decompositions for coverage algorithms,” in IEEE International Conference on Robotics and Automation, 2001.
[6] M. Mehdizade, “ A Decomposition Strategy for Optimal Coverage of an Area of Interest using Heterogeneous Team of UAVs, “ Concordia University, Quebec, Canada, pp. 77-100, 2012:
[7] J. Yining, W. Yanxuan, F. Ningjun, “Research on Distributed Cooperative Control of Swarm UAVs for Persistent Coverage,” Proceedings of the 33rd Chinese Control Conference(CCC), 2014
[8] T. Trimble, “How to Mow a Lown: Rows or Spirals?, ” – [Online]. Available: http://www.popularmechanics.com/home/lawn-garden/how-to/a5935/how-to-mow-a-lawn-patterns
[9] J. Jinfang, H. Guangjie, X. Huihui, “LMAT: Localization with a Mobile Anchor Node Based on Trilateration in Wireless Sensor Networks,” Global Telecommunications Conference (GLOBECOM), 2011
[10] S. Ferreira, G. Carvalho, F. Ferreira and J. Sousa “Assessing the capacity of man-portable UAVs for network access point localization, using RSSI link data” in International Conference on Unmanned Aircraft Systems(ICUAS), 2014.