本研究探討一個多架無人機的感測數據收集路線規劃問題，為一個「合作式數據傳輸模式」，旨在指派無人機群自基地起飛，行經一或數個散在各處的感測站附近，以收集感測數據，再將收集到的數據藉由無線傳輸，以傳到其通信範圍內的另一架無人機或基地，此資料的收集與傳輸必須足設定的感測數據空窗與延遲時長限制。其中，各筆感測數據的「空窗時長」代表從同一感測站收集而得的連續兩筆數據之間的最大時間間隔長度；而「延遲時長」則代表該筆感測數據自其來源的感測站開始，直至基地接收到的總時間歷程長度，亦即類似數據「新鮮度」的概念。在滿足上述兩類時長限制的假設下，本研究擬規劃各架無人機路線，以在指定的規劃期間內，藉由合作協同傳遞資料的方式，重複執行上述任務，達成能於基地接收到最多數據的目的。
本研究以時空網路為基礎，提出一個整數規劃模型來追踪感測站所產生的各筆數據被收集和傳輸的過程。為檢驗使用無線通訊方式協同合作傳輸數據的效益，本研究亦提出一個單獨收集傳送資料的「非合作式數據傳輸模式」來對比，在該設定下，每架無人機都必須獨力收集數據，不得使用無線通訊將數據轉傳給他架無人機。實測結果顯示，合作式數據傳輸模式可以達到在更少的數據延遲下，仍能傳輸更多數據的不錯效果。
雖然本研究所提出的整數規劃模型可以求解出理論最佳解，但其求解過程十分耗時。為能在更短的時間內計算出好的解，本研究亦設計了一個直覺式的啟發式演算法，該演算法先計算出一條連接基地與所有感測站的短哈密頓迴圈，並於其上均勻分佈無人機。由初步的數值測試結果看來，該演算法能處理較大的測資，但其求解效能仍有改善的空間。

We discuss a multi-UAV surveillance routing problem that routes a UAV fleet from a base station (i.e., depot) to repeatedly collect data from sensing locations during a specific planning horizon. The data in a sensing area is generated and ready to be collected periodically in a store-and-forward fashion. A UAV has to pass through some nodes within the communication range to collect data from a sensing location. It then carries the data and wirelessly transfers it to another UAV as long as that UAV is located within its communication range.
We seek the maximum collected data that the base station can receive during the planning horizon. Specifically, we calculate the optimal flight paths for UAVs over the space and time necessary to transfer the maximum amount of collected data. Furthermore, it is hoped that the idleness and latency, defined as the maximum length of time between consecutive data collected from a sensing location and the length of time (i.e., freshness) required for the data traveling from a sensing location to the base station, respectively, necessary to satisfy the given upper bounds.
We proposed an integer programming model on a time-space network to track how the generated surveillance data is collected and transferred. Implementation of the model is provided and compared to an uncooperative data transport model. Each UAV has to transfer the data individually to demonstrate the applicability of the proposed model and possible extensions. The results show that the cooperative data transport model can transfer more collected data with less latency than the uncooperative data transport model.
Although a mathematical model can be used to calculate an optimal solution, it is quite time-consuming. To calculate a good solution in a shorter time, we proposed a heuristic algorithm that evenly distributes UAVs on a short Hamiltonian cycle connecting the depot and all sensing locations. Computational experiments indicate that the proposed algorithm calculates good solutions and can deal with larger cases but still has room to improve in terms of its solution quality.

Acevedo, J. J., Arrue, B. C., Diaz-Bañez, J. M., Ventura, I., Maza, I., & Ollero, A. (2014). One-to-One Coordination Algorithm for Decentralized Area Partition in Surveillance Missions with a Team of Aerial Robots. Journal of Intelligent & Robotic Systems, 74(1), 269–285. https://doi.org/10.1007/s10846-013-9938-z
Acevedo, J. J., Arrue, B. C., Diaz-Banez, J. M., Ventura, I., Maza, I., & Ollero, A. (2013). Decentralized strategy to ensure information propagation in area monitoring missions with a team of UAVs under limited communications. 2013 International Conference on Unmanned Aircraft Systems (ICUAS), 565–574. https://doi.org/10.1109/ICUAS.2013.6564734
Amigoni, F., Banfi, J., & Basilico, N. (2017). Multirobot Exploration of Communication-Restricted Environments: A Survey. IEEE Intelligent Systems, 32(6), 48–57. https://doi.org/10.1109/MIS.2017.4531226
Baldacci, R., Bartolini, E., Mingozzi, A., & Valletta, A. (2011). An Exact Algorithm for the Period Routing Problem. Operations Research, 59, 228–241. https://doi.org/10.1287/opre.1100.0875
Banfi, J., Basilico, N., & Amigoni, F. (2015). Minimizing communication latency in multirobot situation-aware patrolling. 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 616–622. https://doi.org/10.1109/IROS.2015.7353436
Banfi, J., Li, A. Q., Basilico, N., Rekleitis, I., & Amigoni, F. (2016). Asynchronous multirobot exploration under recurrent connectivity constraints. 2016 IEEE International Conference on Robotics and Automation (ICRA), 5491–5498. https://doi.org/10.1109/ICRA.2016.7487763
Banfi, J., Quattrini Li, A., Rekleitis, I., Amigoni, F., & Basilico, N. (2018). Strategies for coordinated multirobot exploration with recurrent connectivity constraints. Autonomous Robots, 42(4), 875–894. https://doi.org/10.1007/s10514-017-9652-y
Coelho, B. N., Coelho, V. N., Coelho, I. M., Ochi, L. S., Haghnazar K., R., Zuidema, D., Lima, M. S. F., & da Costa, A. R. (2017). A multi-objective green UAV routing problem. Computers & Operations Research, 88, 306–315. https://doi.org/10.1016/j.cor.2017.04.011
Fu, Z., Chen, Y., Ding, Y., & He, D. (2019). Pollution Source Localization Based on Multi-UAV Cooperative Communication. IEEE Access, 7, 29304–29312. https://doi.org/10.1109/ACCESS.2019.2900475
Grotli, E. I., & Johansen, T. A. (2012). Path- and data transmission planning for cooperating UAVs in delay tolerant network. 2012 IEEE Globecom Workshops, 1568–1573. https://doi.org/10.1109/GLOCOMW.2012.6477819
Kantaros, Y., Guo, M., & Zavlanos, M. (2019). Temporal Logic Task Planning and Intermittent Connectivity Control of Mobile Robot Networks. https://doi.org/10.1109/TAC.2019.2893161
Kuznetsov, N. A., Myasnikov, D. V., & Semenikhin, K. V. (2016). Optimal control of data transmission in a mobile two-agent robotic system. Journal of Communications Technology and Electronics, 61(12), 1456–1465. https://doi.org/10.1134/S1064226916120159
Manyam, S. G., Rasmussen, S., Casbeer, D. W., Kalyanam, K., & Manickam, S. (2017). Multi-UAV routing for persistent intelligence surveillance & reconnaissance missions. 2017 International Conference on Unmanned Aircraft Systems (ICUAS), 573–580. https://doi.org/10.1109/ICUAS.2017.7991314
Nigam, N., Bieniawski, S., Kroo, I., & Vian, J. (2012). Control of Multiple UAVs for Persistent Surveillance: Algorithm and Flight Test Results. IEEE Transactions on Control Systems Technology - IEEE TRANS CONTROL SYST TECHN, 20, 1236–1251. https://doi.org/10.1109/TCST.2011.2167331
Pasqualetti, F., Durham, J. W., & Bullo, F. (2012). Cooperative Patrolling via Weighted Tours: Performance Analysis and Distributed Algorithms. Robotics, IEEE Transactions On, 28, 1181–1188. https://doi.org/10.1109/TRO.2012.2201293
Pasqualetti, F., Franchi, A., & Bullo, F. (2012). On cooperative patrolling: Optimal trajectories, complexity analysis, and approximation algorithms. IEEE Transactions on Robotics, 28(3), 592–606. https://doi.org/10.1109/TRO.2011.2179580
Ponda, S. S., Johnson, L. B., Kopeikin, A. N., Choi, H., & How, J. P. (2012). Distributed Planning Strategies to Ensure Network Connectivity for Dynamic Heterogeneous Teams. IEEE Journal on Selected Areas in Communications, 30(5), 861–869. https://doi.org/10.1109/JSAC.2012.120603
Scherer, J., & Rinner, B. (2019). Persistent Multi-UAV Surveillance with Data Latency Constraints. ArXiv:1907.01205 [Cs, Eess]. http://arxiv.org/abs/1907.01205
Scherer, J., & Rinner, B. (2020a). Multi-Robot Persistent Surveillance With Connectivity Constraints. IEEE Access, 8, 15093–15109. https://doi.org/10.1109/ACCESS.2020.2967650
Scherer, J., & Rinner, B. (2020b). Multi-UAV Surveillance With Minimum Information Idleness and Latency Constraints. IEEE Robotics and Automation Letters, 5(3), 4812–4819. https://doi.org/10.1109/LRA.2020.3003884
Scherer, J., & Rinner, B. (2020). Multi-Robot Patrolling with Sensing Idleness and Data Delay Objectives. Journal of Intelligent & Robotic Systems, 99(3–4), 949–967. https://doi.org/10.1007/s10846-020-01156-6
Scherer, J., & Rinner, B. (2016). Persistent multi-UAV surveillance with energy and communication constraints. 2016 IEEE International Conference on Automation Science and Engineering (CASE), 1225–1230. https://doi.org/10.1109/COASE.2016.7743546
Scherer, J., & Rinner, B. (2017). Short and full horizon motion planning for persistent multi-UAV surveillance with energy and communication constraints. 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 230–235. https://doi.org/10.1109/IROS.2017.8202162
Spirin, V., & Cameron, S. (2014). Rendezvous through obstacles in multi-agent exploration. 2014 IEEE International Symposium on Safety, Security, and Rescue Robotics (2014), 1–6. https://doi.org/10.1109/SSRR.2014.7017656
Spirin, Victor, Cameron, S., & de Hoog, J. (2014). Time Preference for Information in Multi-agent Exploration with Limited Communication. In A. Natraj, S. Cameron, C. Melhuish, & M. Witkowski (Eds.), Towards Autonomous Robotic Systems (pp. 34–45). Springer. https://doi.org/10.1007/978-3-662-43645-5_5
Tsai, F.-M., Lu, C.-C., & Chang, Y.-M. (2016). A network model for solving the yard truck routing and scheduling problem. The International Journal of Logistics Management, 27(2), 353–370. https://doi.org/10.1108/IJLM-09-2014-0158
Wu, Y., Ren, X., Zhou, H., Wang, Y., & Yi, X. (2020). A Survey on Multi-Robot Coordination in Electromagnetic Adversarial Environment: Challenges and Techniques. IEEE Access, 8, 53484–53497. https://doi.org/10.1109/ACCESS.2020.2981408
Zhang, M., & Kingston, D. (2015). Time-space network based exact models for periodical monitoring routing problem. 2015 American Control Conference (ACC), 5264–5269. https://doi.org/10.1109/ACC.2015.7172161