Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Multi-UAV planning for cooperative wildfire coverage and tracking with quality-of-service guarantees

  • Published:
Autonomous Agents and Multi-Agent Systems Aims and scope Submit manuscript

Abstract

In recent years, teams of robot and Unmanned Aerial Vehicles (UAVs) have been commissioned by researchers to enable accurate, online wildfire coverage and tracking. While the majority of prior work focuses on the coordination and control of such multi-robot systems, to date, these UAV teams have not been given the ability to reason about a fire’s track (i.e., location and propagation dynamics) to provide performance guarantee over a time horizon. Motivated by the problem of aerial wildfire monitoring, we propose a predictive framework which enables cooperation in multi-UAV teams towards collaborative field coverage and fire tracking with probabilistic performance guarantee. Our approach enables UAVs to infer the latent fire propagation dynamics for time-extended coordination in safety-critical conditions. We derive a set of novel, analytical temporal, and tracking-error bounds to enable the UAV-team to distribute their limited resources and cover the entire fire area according to the case-specific estimated states and provide a probabilistic performance guarantee. Our results are not limited to the aerial wildfire monitoring case-study and are generally applicable to problems, such as search-and-rescue, target tracking and border patrol. We evaluate our approach in simulation and provide demonstrations of the proposed framework on a physical multi-robot testbed to account for real robot dynamics and restrictions. Our quantitative evaluations validate the performance of our method accumulating \(7.5\times\) and \(9.0\times\) smaller tracking-error than state-of-the-art model-based and reinforcement learning benchmarks, respectively.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. Note that the state variables in \(\mathbf {\Theta }_t\) and \(\mathbf {\Phi }_t\) include firespot and UAV positions, \(q_t\) and \(p_t\), as well as \(R_t, U_t\) and \(\theta _t\) which are the FARSITE wildfire propagation model parameters. While these variables are generally application-dependent, we emphasis that \(R_t, U_t\) and \(\theta _t\) are specific to FARSITE (see Sect. 3) model and can be replaced with other measurable model parameters, in case FARSITE is replaced with other fire propagation models such as the correctable fire simulation model in [88].

  2. Note that, this step might not be required in applications other than aerial wildfire monitoring, in which instead of \(N_h\) fire areas, \(N_h\) specific moving points/targets need to be monitored. Accordingly, the CE-TSP step in our framework can be replaced with a regular TSP [93].

  3. The scenario designs are motivated such that they expand the applicability of our framework to domains other than wildfire monitoring, and thus, here we use the term target points instead of firespots.

  4. We explicitly estimate the latent fire dynamics in our AEKF model.

  5. Here, we used the FARSITE model which can be replaced with any other parameterized fire propagation model, such as the correctable fire simulation model introduced in [88].

References

  1. Caillouet, C., Giroire, F., & Razafindralambo, T. (2018). Optimization of mobile sensor coverage with uavs. In IEEE INFOCOM 2018-IEEE conference on computer communications workshops (INFOCOM WKSHPS) (pp. 622–627). IEEE.

  2. Zhao, Y., Wang, X., Wang, C., Cong, Y., & Shen, L. (2019). Systemic design of distributed multi-uav cooperative decision-making for multi-target tracking. Autonomous Agents and Multi-Agent Systems, 33(1), 132–158.

    Article  Google Scholar 

  3. Akyildiz, I. F., & Kasimoglu, I. H. (2004). Wireless sensor and actor networks: Research challenges. Ad Hoc Networks, 2(4), 351–367.

    Article  Google Scholar 

  4. Liu, M., Gong, H., Wen, Y., Chen, G., & Cao, J. (2011). The last minute: Efficient data evacuation strategy for sensor networks in post-disaster applications. In 2011 Proceedings IEEE INFOCOM (pp. 291–295). IEEE.

  5. Afghah, F., Razi, A., Chakareski, J., & Ashdown, J. (2019). Wildfire monitoring in remote areas using autonomous unmanned aerial vehicles. In IEEE INFOCOM 2019-IEEE conference on computer communications workshops (INFOCOM WKSHPS) (pp. 835–840). IEEE.

  6. Doherty, P., Kvarnström, J., & Heintz, F. (2009). A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems. Autonomous Agents and Multi-Agent Systems, 19(3), 332–377.

    Article  Google Scholar 

  7. Li, M., Liu, Y., & Chen, L. (2008). Nonthreshold-based event detection for 3d environment monitoring in sensor networks. IEEE Transactions on Knowledge and Data Engineering, 20(12), 1699–1711.

    Article  Google Scholar 

  8. Ota, K., Dong, M., Cheng, Z., Wang, J., Li, X., & Shen, X. S. (2012). Oracle: Mobility control in wireless sensor and actor networks. Computer Communications, 35(9), 1029–1037.

    Article  Google Scholar 

  9. Seraj, E., & Gombolay, M. (2020). Coordinated control of uavs for human-centered active sensing of wildfires. In 2020 American control conference (ACC) (pp. 1845–1852). IEEE.

  10. Pham, H. X., La, H. M., Feil-Seifer, D., & Deans, M. (2017). A distributed control framework for a team of unmanned aerial vehicles for dynamic wildfire tracking. In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 6648–6653). IEEE.

  11. Pham, H. X., La, H. M., Feil-Seifer, D., & Deans, M. C. (2018). A distributed control framework of multiple unmanned aerial vehicles for dynamic wildfire tracking. In IEEE transactions on systems, man, and cybernetics: Systems.

  12. Bays, M. J., Wettergren, T. A. (2015). A solution to the service agent transport problem. In 2015 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 6443–6450). IEEE.

  13. Mozaffari, M., Saad, W., Bennis, M., & Debbah, M. (2016). Efficient deployment of multiple unmanned aerial vehicles for optimal wireless coverage. IEEE Communications Letters, 20(8), 1647–1650.

    Article  Google Scholar 

  14. Ahmadzadeh, A., Buchman, G., Cheng, P., Jadbabaie, A., Keller, J., Kumar, V., & Pappas, G. (2006). Cooperative control of uavs for search and coverage. In Proceedings of the AUVSI conference on unmanned systems (Vol. 2).

  15. Xia, F., Tian, Y.-C., Li, Y., & Sung, Y. (2007). Wireless sensor/actuator network design for mobile control applications. Sensors, 7(10), 2157–2173.

    Article  Google Scholar 

  16. Seraj, E., Chen, L., & Gombolay, M. C. (2021). A hierarchical coordination framework for joint perception-action tasks in composite robot teams. IEEE Transactions on Robotics.

  17. Konan, S., Seraj, E., & Gombolay, M. (2022). Iterated reasoning with mutual information in cooperative and byzantine decentralized teaming, arXiv preprintarXiv:2201.08484.

  18. Brenner, M., & Nebel, B. (2009). Continual planning and acting in dynamic multiagent environments. Autonomous Agents and Multi-agent Systems, 19(3), 297–331.

    Article  Google Scholar 

  19. Undeger, C., & Polat, F. (2010). Multi-agent real-time pursuit. Autonomous Agents and Multi-agent Systems, 21(1), 69–107.

    Article  Google Scholar 

  20. Ravichandar, H., Shaw, K., & Chernova, S. (2020). Strata: Unified framework for task assignments in large teams of heterogeneous agents. Autonomous Agents and Multi-Agent Systems, 34, 1–25.

    Article  Google Scholar 

  21. Sarne, D., & Grosz, B. J. (2013). Determining the value of information for collaborative multi-agent planning. Autonomous Agents and Multi-agent Systems, 26(3), 456–496.

    Article  Google Scholar 

  22. Panait, L., & Luke, S. (2005). Cooperative multi-agent learning: The state of the art. Autonomous Agents and Multi-agent Systems, 11(3), 387–434.

    Article  Google Scholar 

  23. Prasad, M. N., & Lesser, V. R. (1999). Learning situation-specific coordination in cooperative multi-agent systems. Autonomous Agents and Multi-agent Systems, 2(2), 173–207.

    Article  Google Scholar 

  24. de Sousa, J. V. R., & Gamboa, P. V. (2020). Aerial forest fire detection and monitoring using a small uav. KnE Engineering (pp. 242–256).

  25. Xing, Z., Zhang, Y., Su, C.-Y., Qu, Y., & Yu, Z. (2019). Kalman filter-based wind estimation for forest fire monitoring with a quadrotor uav. In 2019 IEEE conference on control technology and applications (CCTA) (pp. 783–788). IEEE.

  26. Beard, R., Kingston, D., McLain, T. W. & Nelson, D. (2006). Decentralized cooperative aerial surveillance using fixed-wing miniature uavs.

  27. McIntire, M., Nunes, E., & Gini, M. (2016). Iterated multi-robot auctions for precedence-constrained task scheduling. In Proceedings of the 2016 international conference on autonomous agents & multiagent systems. International Foundation for Autonomous Agents and Multiagent Systems (pp. 1078–1086).

  28. Nunes, E. & Gini, M. (2015). Multi-robot auctions for allocation of tasks with temporal constraints. In Twenty-Ninth AAAI conference on artificial intelligence.

  29. Choi, H.-L., Brunet, L., & How, J. P. (2009). Consensus-based decentralized auctions for robust task allocation. IEEE Transactions on Robotics, 25(4), 912–926.

    Article  Google Scholar 

  30. Allison, R. S., Johnston, J. M., Craig, G., & Jennings, S. (2016). Airborne optical and thermal remote sensing for wildfire detection and monitoring. Sensors, 16(8), 1310.

    Article  Google Scholar 

  31. Martinez-de Dios, J. R., Arrue, B. C., Ollero, A., Merino, L., & Gómez-Rodríguez, F. (2008). Computer vision techniques for forest fire perception. Image and Vision Computing, 26(4), 550–562.

    Article  Google Scholar 

  32. Stipanicev, D., Stula, M., Krstinic, D., Seric, L., Jakovcevic, T., & Bugaric, M. (2010). Advanced automatic wildfire surveillance and monitoring network. In D. Viegas (ed.), 6th international conference on forest fire research, Coimbra, Portugal.

  33. Sujit, P., Kingston, D., & Beard, R. (2007). Cooperative forest fire monitoring using multiple uavs. In 2007 46th IEEE conference on decision and control (pp. 4875–4880). IEEE.

  34. Fujiwara, K., & Kudoh, J.-I. (2002). Forest fire detection in 2001 using three-dimensional histogram. In Geoscience and remote sensing symposium, 2002. IGARSS’02. 2002 IEEE international (Vol. 4, pp. 2057–2059). IEEE.

  35. Kudoh, J.-I., & Hosoi, K. (2003). Two dimensional forest fire detection method by using noaa avhrr images. In Geoscience and remote sensing symposium 2003. IGARSS’03. Proceedings. 2003 IEEE International (Vol. 4, pp. 2494–2495). IEEE.

  36. Casbeer, D. W., Kingston, D. B., Beard, R. W., & McLain, T. W. (2006). Cooperative forest fire surveillance using a team of small unmanned air vehicles. International Journal of Systems Science, 37(6), 351–360.

    Article  MATH  Google Scholar 

  37. Haksar, R. N. & Schwager,M., (2018). Distributed deep reinforcement learning for fighting forest fires with a network of aerial robots. In 2018 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 1067–1074). IEEE.

  38. Finney, M. A. (1998). Farsite: Fire area simulator-model development and evaluation. In Res. Pap. RMRS-RP-4, Revised 2004. Ogden, UT: US Department of Agriculture, Forest Service, Rocky Mountain Research Station (Vol. 4).

  39. Freed, M., Fitzgerald, W., & Harris, R. (2005). Intelligent autonomous surveillance of many targets with few uavs. In Proceedings of the research and development partnering conference. Department of Homeland Security, Boston, MA.

  40. Waharte, S., & Trigoni, N. (2010). Supporting search and rescue operations with uavs. In 2010 international conference on emerging security technologies (pp. 142–147). IEEE.

  41. Rudol, P., & Doherty, P. (2008). Human body detection and geolocalization for uav search and rescue missions using color and thermal imagery. In 2008 IEEE aerospace conference. IEEE (pp. 1–8).

  42. Tomic, T., Schmid, K., Lutz, P., Domel, A., Kassecker, M., Mair, E., et al. (2012). Toward a fully autonomous uav: Research platform for indoor and outdoor urban search and rescue. IEEE Robotics and Automation Magazine, 19(3), 46–56.

    Article  Google Scholar 

  43. Olivares-Mendez, M. A., Fu, C., Ludivig, P., Bissyandé, T. F., Kannan, S., Zurad, M., et al. (2015). Towards an autonomous vision-based unmanned aerial system against wildlife poachers. Sensors, 15(12), 31362–31391.

    Article  Google Scholar 

  44. Gonzalez, L. F., Montes, G. A., Puig, E., Johnson, S., Mengersen, K., & Gaston, K. J. (2016). Unmanned aerial vehicles (uavs) and artificial intelligence revolutionizing wildlife monitoring and conservation. Sensors, 16(1), 97.

    Article  Google Scholar 

  45. Bondi, E., Kapoor, A., Dey, D., Piavis, J., Shah, S., Hannaford, R., Iyer, A., Joppa, L., & Tambe, M. (2018). Near real-time detection of poachers from drones in airsim. In IJCAI, (pp. 5814–5816).

  46. Klemas, V. V. (2015). Coastal and environmental remote sensing from unmanned aerial vehicles: An overview. Journal of Coastal Research, 31(5), 1260–1267.

    Article  Google Scholar 

  47. Marques, M. M., Lobo, V., Batista, R., Almeida, J., de Fátima Nunes, M., Ribeiro, R., & Bernardino, A. (2016). Oil spills detection: Challenges addressed in the scope of the seagull project. In OCEANS 2016 MTS/IEEE Monterey (pp. 1–6). IEEE.

  48. Allen J. & Walsh, B. (2008). Enhanced oil spill surveillance, detection and monitoring through the applied technology of unmanned air systems. In International oil spill conference (Vol. 2008, no. 1, pp. 113–120). American Petroleum Institute.

  49. Haddal, C. C., & Gertler, J. (2010). Homeland security: Unmanned aerial vehicles and border surveillance. Library of Congress, Washington, DC. Congressional Research Service.

  50. Vascik, P. D., Balakrishnan, H., & Hansman, R. J. (2018). Assessment of air traffic control for urban air mobility and unmanned systems.

  51. Thipphavong, D. P., Apaza, R., Barmore, B., Battiste, V., Burian, B., Dao, Q., Feary, M., Go, S., Goodrich, K. H., Homola, J., & Idris, H. R. (2018). Urban air mobility airspace integration concepts and considerations. In 2018 aviation technology, integration, and operations conference (p. 3676).

  52. Vascik, P. D., & Hansman, R. J. (2018). Scaling constraints for urban air mobility operations: Air traffic control, ground infrastructure, and noise. In 2018 aviation technology, integration, and operations conference (p. 3849).

  53. De Vivo, F., Battipede, M., Gili, P., Yezzi, A. J., Feron, E., & Johnson, E. (2018). Real-time fire segmentation via active contours for uav integrated wildfire propagation prediction. In 2018 AIAA information systems-AIAA Infotech@ Aerospace (p. 1488).

  54. Chamoso, P., González-Briones, A., De La Prieta, F., & Corchado, J. M. (2018). Computer vision system for fire detection and report using uavs. In RSFF (pp. 40–49).

  55. Merino, L., Caballero, F., Martínez-De-Dios, J. R., Maza, I., & Ollero, A. (2012). An unmanned aircraft system for automatic forest fire monitoring and measurement. Journal of Intelligent and Robotic Systems, 65(1–4), 533–548.

    Article  Google Scholar 

  56. Merino, L., Caballero, F., de Dios, J. R. M., Maza, I., Ollero, A. (2010). Automatic forest fire monitoring and measurement using unmanned aerial vehicles. In D. X. Viegas (Ed.), Proceedings of the 6th international congress on forest fire research, Coimbra, Portugal. Citeseer.

  57. Yuan, C., Zhang, Y., & Liu, Z. (2015). A survey on technologies for automatic forest fire monitoring, detection, and fighting using unmanned aerial vehicles and remote sensing techniques. Canadian Journal of Forest Research, 45(7), 783–792.

    Article  Google Scholar 

  58. Robin, C., & Lacroix, S. (2016). Multi-robot target detection and tracking: Taxonomy and survey. Autonomous Robots, 40(4), 729–760.

    Article  Google Scholar 

  59. Jung, B., & Sukhatme, G. S. (2006). Cooperative multi-robot target tracking. In Distributed autonomous robotic systems (Vol. 7, pp. 81–90). Springer.

  60. Jin, L., Li, S., La, H. M., Zhang, X., & Hu, B. (2019). Dynamic task allocation in multi-robot coordination for moving target tracking: A distributed approach. Automatica, 100, 75–81.

    Article  MathSciNet  MATH  Google Scholar 

  61. Mottaghi, R., & Vaughan, R. (2007). An integrated particle filter and potential field method applied to cooperative multi-robot target tracking. Autonomous Robots, 23(1), 19–35.

    Article  Google Scholar 

  62. Hausman, K., Müller, J., Hariharan, A., Ayanian, N., & Sukhatme, G. S. (2015). Cooperative multi-robot control for target tracking with onboard sensing. The International Journal of Robotics Research, 34(13), 1660–1677.

    Article  Google Scholar 

  63. Bailon-Ruiz, R., & Lacroix, S. (2020). Wildfire remote sensing with uavs: A review from the autonomy point of view. In 2020 international conference on unmanned aircraft systems (ICUAS) (pp. 412–420). IEEE.

  64. Kumar, M., Cohen, K., & Homchaudhuri, B. (2011). Cooperative control of multiple uninhabited aerial vehicles for monitoring and fighting wildfires. Journal of Aerospace Computing, Information, and Communication, 8(1), 1–16.

    Article  Google Scholar 

  65. Ghamry, K. A., & Zhang, Y. (2016). Cooperative control of multiple uavs for forest fire monitoring and detection. In 2016 12th IEEE/ASME international conference on mechatronic and embedded systems and applications (MESA) (pp. 1–6). IEEE.

  66. Harikumar, K., Senthilnath, J., Sundaram, S. (2018). Multi-uav oxyrrhis marina-inspired search and dynamic formation control for forest firefighting. In IEEE Transactions on Automation Science and Engineering.

  67. Lee, S. G., Diaz-Mercado, Y., & Egerstedt, M. (2015). Multirobot control using time-varying density functions. IEEE Transactions on Robotics, 31(2), 489–493.

    Article  Google Scholar 

  68. Lin, X., & Cassandras, C. G. (2014). An optimal control approach to the multi-agent persistent monitoring problem in two-dimensional spaces. IEEE Transactions on Automatic Control, 60(6), 1659–1664.

    Article  MathSciNet  MATH  Google Scholar 

  69. Li, W., & Cassandras, C. G. (2005). Distributed cooperative coverage control of sensor networks. In Proceedings of the 44th IEEE conference on decision and control (pp. 2542–2547). IEEE.

  70. Zuo, L., Yan, M., Guo, Y., & Ma, W. (2019). An improved kf-rbf based estimation algorithm for coverage control with unknown density function. In Complexity, 2019.

  71. Santos, M., Mayya, S., Notomista, G., & Egerstedt, M. (2019). Decentralized minimum-energy coverage control for time-varying density functions. In 2019 international symposium on multi-robot and multi-agent systems (MRS) (pp. 155–161). IEEE.

  72. Schwager, M., Julian, B. J., Angermann, M., & Rus, D. (2011). Eyes in the sky: Decentralized control for the deployment of robotic camera networks.

  73. Morvan, D. (2011). Physical phenomena and length scales governing the behaviour of wildfires: A case for physical modelling. Fire Technology, 47(2), 437–460.

    Article  Google Scholar 

  74. Pastor, E., Zárate, L., Planas, E., & Arnaldos, J. (2003). Mathematical models and calculation systems for the study of wildland fire behaviour. Progress in Energy and Combustion Science, 29(2), 139–153.

    Article  Google Scholar 

  75. Bailon-Ruiz, R., Lacroix, S., & Bit-Monnot, A. (2018). Planning to monitor wildfires with a fleet of uavs. In 2018 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 4729–4734). IEEE.

  76. Xiao, J., Wang, G., Zhang, Y., & Cheng, L. (2020). A distributed multi-agent dynamic area coverage algorithm based on reinforcement learning. IEEE Access, 8, 33511–33521.

    Article  Google Scholar 

  77. Adepegba, A. A., Miah, S., & Spinello, D. (2016). Multi-agent area coverage control using reinforcement learning. In The twenty-ninth international flairs conference.

  78. Seraj, E., Wu, X., & Gombolay, M. C. (2020). Firecommander: An interactive, probabilistic multi-agent environment for joint perception-action tasks. In arXiv preprint arXiv:2011.00165.

  79. Zanol, R., Chiariotti, F., & Zanella, A. (2019). Drone mapping through multi-agent reinforcement learning. In 2019 IEEE wireless communications and networking conference (WCNC) (pp. 1–7). IEEE.

  80. Seraj, E. (2022). Embodied team intelligence in multi-robot systems. In Proceedings of the 21st international conference on autonomous agents and multiagent systems (pp. 1869–1871).

  81. Julian, K. D., & Kochenderfer, M. J. (2019). Distributed wildfire surveillance with autonomous aircraft using deep reinforcement learning. Journal of Guidance, Control, and Dynamics, 42(8), 1768–1778.

    Article  Google Scholar 

  82. Julian, K. D., & Kochenderfer, M. J. (2018). Autonomous distributed wildfire surveillance using deep reinforcement learning. In 2018 AIAA guidance, navigation, and control conference (p. 1589).

  83. Viseras, A., Meissner, M., & Marchal, J. (2021). Wildfire front monitoring with multiple uavs using deep q-learning. IEEE Access.

  84. Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction. MIT Press.

    MATH  Google Scholar 

  85. Ure, N. K., Omidshafiei, S., Lopez, B. T., Agha-Mohammadi, A.-A., How, J. P., & Vian, J. (2015). Online heterogeneous multiagent learning under limited communication with applications to forest fire management. In 2015 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 5181–5188). IEEE.

  86. Seraj, E., Wang, Z., Paleja, R., Martin, D., Sklar, M., Patel, A., & Gombolay, M. (2022). Learning efficient diverse communication for cooperative heterogeneous teaming. In Proceedings of the 21st international conference on autonomous agents and multiagent systems (pp. 1173–1182).

  87. Seraj, E., Wang, Z., Paleja, R., Sklar, M., Patel, A., & Gombolay, M. (2021)Heterogeneous graph attention networks for learning diverse communication. arXiv preprint arXiv:2108.09568.

  88. Beachly, E., Detweiler, C., Elbaum, S., Duncan, B., Hildebrandt, C., Twidwell, D., & Allen, C. (2018). Fire-aware planning of aerial trajectories and ignitions. In 2018 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 685–692). IEEE.

  89. Kalman, R. E., & Bucy, R. S. (1961). New results in linear filtering and prediction theory. Journal of Basic Engineering, 83(1), 95–108.

    Article  MathSciNet  Google Scholar 

  90. Akhlaghi, S., Zhou, N., & Huang, Z. (2017). Adaptive adjustment of noise covariance in Kalman filter for dynamic state estimation. In 2017 IEEE power and energy society general meeting (pp. 1–5). IEEE.

  91. Simon, D. (2006). Optimal state estimation: Kalman, H infinity, and nonlinear approaches. Wiley.

    Book  Google Scholar 

  92. Wang, X., Golden, B., & Wasil, E. (2019). A Steiner zone variable neighborhood search heuristic for the close-enough traveling salesman problem. Computers and Operations Research, 101, 200–219.

    Article  MathSciNet  MATH  Google Scholar 

  93. Applegate, D. L., Bixby, R. E., Chvatal, V., & Cook, W. J. (2006). The traveling salesman problem: A computational study. Princeton University Press.

    MATH  Google Scholar 

  94. Kraemer, L., & Banerjee, B. (2016). Multi-agent reinforcement learning as a rehearsal for decentralized planning. Neurocomputing, 190, 82–94.

    Article  Google Scholar 

  95. Foerster, J., Assael, I. A. , De Freitas, N., & Whiteson, S. (2016). Learning to communicate with deep multi-agent reinforcement learning. In Advances in neural information processing systems (pp. 2137–2145).

  96. Seraj, E., Azimi, V., Abdallah, C., Hutchinson, S., Gombolay, M. (2021). Adaptive leader–follower control for multi-robot teams with uncertain network structure. In 2021 American control conference (ACC). IEEE.

  97. Pickem, D., Glotfelter, P., Wang, L., Mote, M., Ames, A., Feron, E., & Egerstedt, M. (2017). The robotarium: A remotely accessible swarm robotics research testbed. In 2017 IEEE international conference on robotics and automation (ICRA) (pp. 1699–1706). IEEE.

  98. Danoy, G., Brust, M. R., & Bouvry, P. (2015). Connectivity stability in autonomous multi-level uav swarms for wide area monitoring. In Proceedings of the 5th ACM symposium on development and analysis of intelligent vehicular networks and applications (pp. 1–8). ACM.

  99. Li, M., Lu, K., Zhu, H., Chen, M., Mao, S., & Prabhakaran, B. (2008 ). Robot swarm communication networks: Architectures, protocols, and applications. In 2008 third international conference on communications and networking in China (pp. 162–166). IEEE.

  100. Seraj, E., Silva, A., & Gombolay, M. (2019). Safe coordination of human–robot firefighting teams, arXiv preprint arXiv:1903.06847.

  101. Delamatar, P., Finley, A., & Babcock, C. (2013). Downloading and processing noaa hourly weather station data. Dim (ST), 1(30538), 12.

    Google Scholar 

Download references

Acknowledgements

This work was sponsored by ONR under Grant N00014-18-S-B001, MIT Lincoln Laboratory Grant 7000437192, Lockheed Martin Corporation under Grant GR00000509, and GaTech institute funding.

Author information

Authors and Affiliations

  1. Georgia Institute of Technology, Atlanta, GA, 30332, USA

    Esmaeil Seraj, Andrew Silva & Matthew Gombolay

Authors
  1. Esmaeil Seraj
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrew Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Matthew Gombolay
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Esmaeil Seraj.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary Information

Below is the link to the electronic supplementary material.

Supplementary material 1 (MP4 225035 kb)

Appendix

Appendix

1.1 A.1 Time independency of the EKF’s measurement residual

Our analytical URR bound in Eq. 12 depends on the state-estimation measurement residual computed at different time-steps. To maintain control over the measurement uncertainty, we posit that the UAV observers would want the measurement uncertainty residual with respect to a target on the ground not to increase from \(t=t_0\) to \(t=t_0+kT_{UB}\) for any positive integer constant k if the UAV observes the target from the same relative position. Therefore, we examine the time-dependency of the propagated error through our EKF formulation. To this end, we follow the mathematical proof and discussions provided in [16] and [9, 100]. We state that the measurement uncertainty about the states of a dynamic point \(q_t\), observed by a flying UAV is independent of time and is only a function of distance between the observer and the point. In the following, we mathematically proof this point.

First, we present how the uncertainty residual is quantified by an EKF. The total uncertainty residual propagated by EKF is composed of a model and an observation measurement uncertainties, both of which follow the general nonlinear uncertainty propagation law, shown in Eqs. 29 and 30, where \(\Sigma _{t|t-1}\) is the predicted covariance estimate, \(\Lambda _{t|t}\) is the innovation (or residual) covariance, \(F_t\) and \(H_t\) are the process and observation Jacobian matrices, and \(Q_t\) and \(\Gamma _t\) are the process and observation noise covariances, respectively.

$$\begin{aligned} \Sigma _{t|t-1}&= F_t\Sigma _{t-1|t-1}F_t^T + Q_t \end{aligned}$$
(29)
$$\begin{aligned} \Lambda _{t|t}&= H_t\Sigma _{t|t-1}H_t^T + \Gamma _t \end{aligned}$$
(30)

Considering Eqs. 29 and 30, the gradients in the process, \(F_t\), and observation, \(H_t\), Jacobian matrices are responsible for alterations in the uncertainty values. To compute these gradients, we calculate the derivatives of fire’s propagation model, \({\mathcal {M}}_t\), and UAV’s observation model, \({\mathcal {O}}_t\), with respect to the state variables. As discussed in Sect. 5.1 and considering the introduced state vectors, we first derive the process and observation Jacobian matrices (\(F_t\) and \(H_t\)) as follows in Eqs. (31) and (32), respectively. In Eqs. (31) and (32), \(t^\prime = t-1\).

(31)
(32)

In Eqs. (31) and (32), we define the process state vector as \(\mathbf {\Theta }_t = \left[ q_t^x, q_t^y, p_t^x, p_t^y, p_t^z, R_t, U_t, \theta _t \right] ^T\) and \(\mathbf {\Phi }_t = \left[ \varphi _t^x, \varphi _t^y, {\hat{R}}_t, {\hat{U}}_t, {\hat{\theta }}_t\right] ^T\) as the mapping vector. As such, we calculate the partial derivatives in Eq. 31 by using Eq. 1–2 and applying the chain-rule to compute the derivatives of \(q_t^x\) and \(q_t^y\) with respect to parameters \(R_{t-1}\), \(U_{t-1}\), and \(\theta _{t-1}\). The partial derivatives are then derived as in Eqs. (33) and (35), where \({\mathcal {D}}(\theta )\) is \(\sin \theta\) and \(\cos \theta\) for X and Y axis, respectively.

$$\begin{aligned} \frac{\partial q_{t}}{\partial \theta _{t-1}} &=~C(R_t, U_t)\frac{\partial {\mathcal {D}}(\theta )}{\partial \theta }\delta t \end{aligned}$$
(33)
$$\begin{aligned} \frac{\partial q_{t}}{\partial R_{t-1}} &=\left( 1-\frac{LB(U_t)}{LB(U_t) + \sqrt{GB(U_t)}}\right) {\mathcal {D}}(\theta )\delta t \end{aligned}$$
(34)
$$\begin{aligned} \frac{\partial q_{t}}{\partial U_{t-1}} &=\frac{R_{t'}\bigg (LB(U_{t'})\frac{\partial GB(U_{t'})}{\partial U_{t'}} - GB(U_{t'})\frac{\partial LB(U_{t'})}{\partial U_{t'}}\bigg )}{\left( LB(U_{t'})+\sqrt{GB(U_{t'})}\right) ^2}{\mathcal {D}}(\theta )\delta t \end{aligned}$$
(35)

To compute the partial derivatives in the observation Jacobian matrix in Eq. 32, we first need to derive the relation between the angle parameters, \(\varphi _t^x\) and \(\varphi _t^y\), and the UAV pose. The angle parameters contain information regarding both firefront location \([q_t^x, q_t^y]\) and UAV coordinates \([p_t^x, p_t^y, p_t^z]\). According to Fig. 3, by projecting the looking vector of UAV to planar coordinates, the angle parameters are calculated as shown in Eqs. (36) and (37) for X and Y axes respectively, where \(q_t = [q_t^x, q_t^y]\) and \(p_t = [p_t^x, p_t^y]\).

$$\begin{aligned} \varphi _t^x&= \tan ^{-1}\left( \frac{p_t^z}{\Vert q_t-p_t\Vert }\right) \end{aligned}$$
(36)
$$\begin{aligned} \varphi _t^y&= \tan ^{-1}\left( \frac{\Vert q_t-p_t\Vert }{p_t^z}\right) \end{aligned}$$
(37)

The partial derivatives in the observation Jacobian matrix \(H_t\) for X-axis, presented in Eq. 32, are derived as in Eqs. 38–40 and for Y-axis derivatives, we can derive as in Eqs. 41–43.

$$\begin{aligned} {{\nabla }}_{q_t}\varphi ^x_t =&\frac{1}{1+\left( \frac{p_t^z}{\Vert q_t-p_t\Vert }\right) ^2}\left( \frac{-p_t^z\left( q_t-p_t\right) }{\Vert q_t-p_t\Vert ^3}\right) =\left[ \frac{\partial \varphi _{t}^x}{\partial q_t^x}, \frac{\partial \varphi _{t}^x}{\partial q_t^y}\right] \end{aligned}$$
(38)
$$\begin{aligned} {{\nabla }}_{p_t}\varphi ^x_t =&\frac{1}{1+\left( \frac{p_t^z}{\Vert q_t-p_t\Vert }\right) ^2}\left( \frac{p_t^z\left( q_t-p_t\right) }{\Vert q_t-p_t\Vert ^3}\right) =\left[ \frac{\partial \varphi _{t}^x}{\partial p_t^x}, \frac{\partial \varphi _{t}^x}{\partial p_t^y}\right] \end{aligned}$$
(39)
$$\begin{aligned} \frac{\partial \varphi _{t}^x}{\partial p_t^z} =&\frac{1}{1+\left( \frac{p_t^z}{\Vert q_t-p_t\Vert }\right) ^2}\left( \frac{1}{\Vert q_t-p_t\Vert }\right) \end{aligned}$$
(40)
$$\begin{aligned} { {\nabla }}_{q_t}\varphi ^y_t =&\frac{1}{1+\left( \frac{\Vert q_t-p_t\Vert }{p_t^z}\right) ^2}\left( \frac{\left( q_t-p_t\right) }{p_t^z\Vert q_t-p_t\Vert }\right) =\left[ \frac{\partial \varphi _{t}^y}{\partial q_t^x}, \frac{\partial \varphi _{t}^y}{\partial q_t^y}\right] \end{aligned}$$
(41)
$$\begin{aligned} { {\nabla }}_{p_t}\varphi ^y_t =&\frac{1}{1+\left( \frac{\Vert q_t-p_t\Vert }{p_t^z}\right) ^2}\left( \frac{-\left( q_t-p_t\right) }{p_t^z\Vert q_t-p_t\Vert }\right) =\left[ \frac{\partial \varphi _{t}^y}{\partial p_t^x}, \frac{\partial \varphi _{t}^y}{\partial p_t^y}\right] \end{aligned}$$
(42)
$$\begin{aligned} \frac{\partial \varphi _{t}^y}{\partial p_t^z} =&\frac{1}{1+\left( \frac{\Vert q_t-p_t\Vert }{p_t^z}\right) ^2}\left( \frac{-\Vert q_t-p_t\Vert }{(p_t^z)^2}\right) \end{aligned}$$
(43)

Now, considering EKF’s covariance propagation equations in Eqs. (29 and 30) as well as the gradients in process Jacobian matrix \(F_t\) as calculated in Eqs. 33–35, we can see that the gradients in process Jacobian matrix are only functions of fire propagation model parameters (e.g., the FARSITE model in this case) such as fuel coefficient, \(R_t\) and wind velocity and direction, \(U_t\) and \(\theta _t\). Consequently, while these parameters do not vary significantly with time, the uncertainty drop due to process model is time-invariant. We note that FARSITE [38] assumes locality in time (i.e., within seconds or few minutes), making the assumption of time-invariant fire parameters fairly acceptable [101]. Moreover, the gradients in the observation Jacobian matrix, Eqs. 38–43, are only functions of the Euclidean distance between the UAV pose and firespot coordinates. We also know that, since at the time of visiting a firespot the planar displacement between UAV and fire locations are approximately zero and the only distance between the two equals to the UAV altitude. Accordingly, both \(F_t\) and \(H_t\) are locally time-invariant and the total measurement uncertainty residual variations between two different time-steps (e.g., \(t=t_0\) and \(t=t_0+kT_{UB}\)) is not a function of time and is only a function of the UAV observer’s altitude.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Seraj, E., Silva, A. & Gombolay, M. Multi-UAV planning for cooperative wildfire coverage and tracking with quality-of-service guarantees. Auton Agent Multi-Agent Syst 36, 39 (2022). https://doi.org/10.1007/s10458-022-09566-6

Download citation

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10458-022-09566-6

Keywords

Search

Navigation