Abstract
Planning for multi-robot coverage seeks to determine collision-free paths for a fleet of robots, enabling them to collectively observe points of interest in an environment. Persistent coverage is a variant of traditional coverage where coverage levels in the environment decay over time. Thus, robots have to continuously revisit parts of the environment to maintain a desired coverage level. Facilitating this in the real world demands we tackle numerous subproblems. While there exist standard solutions to these subproblems, there is no complete framework that addresses all of their individual challenges as a whole in a practical setting. We adapt and combine these solutions to present a planning framework for persistent coverage with multiple unmanned aerial vehicles (UAVs). Specifically, we run a continuous loop of goal assignment and globally deconflicting, kinodynamic path planning for multiple UAVs. We evaluate our framework in simulation as well as the real world. In particular, we demonstrate that (i) our framework exhibits graceful coverage—given sufficient resources, we maintain persistent coverage; if resources are insufficient (e.g., having too few UAVs for a given size of the environment), coverage levels decay slowly and (ii) planning with global deconfliction in our framework incurs a negligibly higher price compared to other weaker, more local collision-checking schemes (Video: https://youtu.be/aqDs6Wymp5Q).
Tushar Kusnur and Shohin Mukherjee are equally contributed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This duration depends on the type and capability of the robots, the number of robots, and the coverage map.
- 2.
Two or more robots are in a deadlock if they are not in collision, but executing any valid action for any one of the robots would cause them to collide with another. Hence, they remain stationary.
- 3.
Our framework also allows for static obstacles and no-coverage zones to change during a mission, but this is beyond the scope of this paper.
- 4.
Task T3 is only done if the selected UAV’s committed plan is shorter than \(t_{\text {max}}\).
- 5.
We lower limit these costs by a constant to ensure they are strictly positive. Moreover, since the UAVs’ sensors cover multiple cells, the cost of an edge between cell \(c_{i,j}\) and the pseudo-goal is the average of \(\ell (u,v)-a(u,v)\) for all cells \(c_{u,v}\) covered when \(U_k^{\text {loc}} = c_{i,j}\).
- 6.
These expansions refer to graph-node expansions in the Weighted-A* search.
References
Ademoye, T.A., Davari, A.: Trajectory planning for multiple autonomous systems using mixed integer linear programming. In: Proceedings of the Thirty-Eighth Southeastern Symposium on System Theory, pp. 175–179. IEEE (2006)
Adler, B., Xiao, J., Zhang, J.: Autonomous exploration of urban environments using unmanned aerial vehicles. J. Field Robot. 31(6), 912–939 (2014)
Arkin, E.M., Hassin, R.: Approximation algorithms for the geometric covering salesman problem. Discrete Appl. Math. 55(3), 197–218 (1994)
Barnier, N., Allignol, C.: Trajectory deconfliction with constraint programming. Knowl. Eng. Rev. 27(3), 291–307 (2012)
Bellingham, J.S.: Coordination and control of UAV fleets using mixed-integer linear programming. Ph.D. Thesis, Massachusetts Institute of Technology (2002)
Butzke, J., Likhachev, M.: Planning for multi-robot exploration with multiple objective utility functions. In: Proceedings of IROS, pp. 3254–3259 (2011)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)
Erdmann, M., Lozano-Perez, T.: On multiple moving objects. Algorithmica 2(1–4), 477 (1987)
Franco, C., López-Nicolás, G., Sagüés, C., Llorente, S.: Persistent coverage control with variable coverage action in multi-robot environment. In: Proceedings of CDC, pp. 6055–6060 (2013)
Galceran, E., Carreras, M.: A survey on coverage path planning for robotics. Robot. Auton. Syst. 61(12), 1258–1276 (2013)
Golden, B.L., Raghavan, S., Wasil, E.A.: The vehicle routing problem: latest advances and new challenges, vol. 43. Springer Science & Business Media (2008)
Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)
Kapoutsis, A.C., Chatzichristofis, S.A., Kosmatopoulos, E.B.: DARP: divide areas algorithm for optimal multi-robot coverage path planning. J. Intell. Robot. Syst. 86(3–4), 663–680 (2017)
Keller, J.F.: Path planning for persistent surveillance applications using fixed-wing unmanned aerial vehicles. Comput. Oper. Res. (2016)
Leahy, K., Zhou, D., Vasile, C.I., Oikonomopoulos, K., Schwager, M., Belta, C.: Persistent surveillance for unmanned aerial vehicles subject to charging and temporal logic constraints. Auton. Robots 40(8), 1363–1378 (2016)
Likhachev, M., Ferguson, D.: Planning long dynamically feasible maneuvers for autonomous vehicles. IJRR 28(8), 933–945 (2009)
Mellone, A., Franzini, G., Pollini, L., Innocenti, M.: Persistent coverage control for teams of heterogeneous agents. In: Proceedings of CDC, pp. 2114–2119 (2018)
Nedjati, A., Izbirak, G., Vizvari, B., Arkat, J.: Complete coverage path planning for a multi-UAV response system in post-earthquake assessment. Robotics 5(4), 26 (2016)
Pivtoraiko, M., Kelly, A.: Generating near minimal spanning control sets for constrained motion planning in discrete state spaces. In: Proceedings of IROS, pp. 3231–3237 (2005)
Pohl, I.: Heuristic search viewed as path finding in a graph. Artif. Intell. 1(3–4), 193–204 (1970)
Schwager, M., Rus, D., Slotine, J.J.: Decentralized, adaptive coverage control for networked robots. IJRR 28(3), 357–375 (2009)
Smith, R.N., Schwager, M., Smith, S.L., Jones, B.H., Rus, D., Sukhatme, G.S.: Persistent ocean monitoring with underwater gliders: adapting sampling resolution. JFR 28(5), 714–741 (2011)
Smith, S.L., Schwager, M., Rus, D.: Persistent robotic tasks: monitoring and sweeping in changing environments (2011). arXiv:1102.0603
Srinivasan, S., Latchman, H., Shea, J., Wong, T., McNair, J.: Airborne traffic surveillance systems: video surveillance of highway traffic. In: Proceedings of the ACM 2nd International Workshop on Video Surveillance & Sensor Networks, pp. 131–135 (2004)
Stump, E., Michael, N.: Multi-robot persistent surveillance planning as a vehicle routing problem. In: IEEE International Conference on Automation Science and Engineering, pp. 569–575 (2011)
Sun, X., Koenig, S., Yeoh, W.: Generalized adaptive A*. In: Proceedings of AAMAS, pp. 469–476. International Foundation for Autonomous Agents and Multiagent Systems (2008)
Teixeira, L., Alzugaray, I., Chli, M.: Autonomous aerial inspection using visual-inertial robust localization and mapping. In: Proceedings of FSR, pp. 191–204. Springer (2018)
Thakur, D., Likhachev, M., Keller, J., Kumar, V., Dobrokhodov, V., Jones, K., Wurz, J., Kaminer, I.: Planning for opportunistic surveillance with multiple robots. In: Proceedings of IROS, pp. 5750–5757 (2013)
Toth, P., Vigo, D.: The vehicle routing problem. SIAM (2002)
Vansteenwegen, P., Souffriau, W., Van Oudheusden, D.: The orienteering problem: a survey. Eur. J. Oper. Res. 209(1), 1–10 (2011)
Yamauchi, B., et al.: Frontier-based exploration using multiple robots. Agents 98, 47–53 (1998)
Zhu, C., Ding, R., Lin, M., Wu, Y.: A 3D frontier-based exploration tool for MAVs. In: Proceedings of ICTAI, pp. 348–352 (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Kusnur, T. et al. (2021). A Planning Framework for Persistent, Multi-UAV Coverage with Global Deconfliction. In: Ishigami, G., Yoshida, K. (eds) Field and Service Robotics. Springer Proceedings in Advanced Robotics, vol 16. Springer, Singapore. https://doi.org/10.1007/978-981-15-9460-1_32
Download citation
DOI: https://doi.org/10.1007/978-981-15-9460-1_32
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-15-9459-5
Online ISBN: 978-981-15-9460-1
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)