Abstract
In perimeter defense, a team of defenders seeks to intercept a team of intruders before they reach the perimeter. Though the single defender case is relatively well studied, with multiple defenders significant complexity is introduced because coordination must also be considered. In this work, we present a formulation of the perimeter defense problem as an instance of the min-cost-max-flow problem for flow networks, and leverage existing efficient algorithms for network flows to solve both the task assignment and routing problems for perimeter defense concurrently. When considering homogeneous defender robots, the computed solution is optimal for any individual timestep. Additionally, we detail a deconflict-based strategy for dealing with heterogeneous defenders, and show in simulation that the proposed solutions match or outperform a naive greedy baseline.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agmon, N., Kraus, S., Kaminka, G.A.: Multi-robot perimeter patrol in adversarial settings. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 2339–2345 (2008)
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows (1993)
Bajaj, S., Bopardikar, S.D.: Dynamic boundary guarding against radially incoming targets. In: IEEE International Conference on Decision and Control (CDC), pp. 642–649 (2019)
Bays, M.J., Shende, A., Stilwell, D.J.: An approach to multi-agent area protection using Bayes risk. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 642–649 (2012)
Fu, J.G.M., Bandyopadhyay, T., Ang, M.H.: Local Voronoi decomposition for multi-agent task allocation. In: IEEE International Conference on Robotics and Automation, pp. 1935–1940 (2009)
Ma, H., Koenig, S.: Optimal target assignment and path finding for teams of agents. In: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems (AAMAS), pp. 1144–1152. International Foundation for Autonomous Agents and Multiagent Systems, Richland (2016)
Macharet, D.G., Chen, A.K., Shishika, D., Pappas, G.J., Kumar, V.: Adaptive partitioning for coordinated multi-agent perimeter defense. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (2020)
Shishika, D., Kumar, V.: Local-game decomposition for multiplayer perimeter-defense problem. In: IEEE Conference on Decision and Control (CDC), pp. 2093–2100 (2018)
Shishika, D., Macharet, D.G., Sadler, B.M., Kumar, V.: Game theoretic formation design for probabilistic barrier coverage. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 11,703–11,709 (2020)
Shishika, D., Paulos, J., Hsieh, M.A., Kumar, V.: Team composition for perimeter defense with patrollers and defenders. In: IEEE Conference on Decision and Control (CDC), pp. 7325–7332 (2019)
Shishika, D., Paulos, J., Kumar, V.: Cooperative team strategies for multi-player perimeter-defense games. IEEE Robot. Autom. Lett. 5(2), 2738–2745 (2020)
Smith, S.L., Bopardikar, S.D., Bullo, F.: A dynamic boundary guarding problem with translating targets. In: Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pp. 8543–8548 (2009)
Tarjan, R.E.: Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Math. Program. 78(2), 169–177 (1997)
Yu, J., LaValle, S.M.: Multi-agent path planning and network flow. In: Frazzoli, E., Lozano-Perez, T., Roy, N., Rus, D. (eds.) Algorithmic Foundations of Robotics X. STAR, vol. 86, pp. 157–173. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36279-8_10
Yu, J., LaValle, S.M.: Optimal multirobot path planning on graphs: complete algorithms and effective heuristics. IEEE Trans. Rob. 32(5), 1163–1177 (2016)
Zhang, Y., Meng, Y.: A decentralized multi-robot system for intruder detection in security defense. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 5563–5568 (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Chen, A.K., Macharet, D.G., Shishika, D., Pappas, G.J., Kumar, V. (2022). Optimal Multi-robot Perimeter Defense Using Flow Networks. In: Matsuno, F., Azuma, Si., Yamamoto, M. (eds) Distributed Autonomous Robotic Systems. DARS 2021. Springer Proceedings in Advanced Robotics, vol 22. Springer, Cham. https://doi.org/10.1007/978-3-030-92790-5_22
Download citation
DOI: https://doi.org/10.1007/978-3-030-92790-5_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-92789-9
Online ISBN: 978-3-030-92790-5
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)