Abstract
This paper solves the problem of herding countless evaders by means of a few robots. The objective is to steer all the evaders towards a desired tracking reference while avoiding escapes. The problem is very challenging due to the highly complex repulsive evaders’ dynamics and the underdetermined states to control. We propose a solution that is based on Implicit Control and a novel dynamic assignment strategy to select the evaders to be directly controlled. The former is a general technique that explicitly computes control inputs even in highly complex input-nonaffine dynamics. The latter is built upon a convex-hull dynamic clustering inspired by the Voronoi tessellation problem. The combination of both allows to choose the best evaders to directly control, while the others are indirectly controlled by exploiting the repulsive interactions among them. Simulations show that massive herds can be herd throughout complex patterns by means of a few herders.
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
References
Auletta, F., Fiore, D., Richardson, M.J., di Bernardo, M.: Herding stochastic autonomous agents via local control rules and online target selection strategies. Auton. Robots 46, 469–481 (2022). https://doi.org/10.1007/s10514-021-10033-6
Aurenhammer, F.: Voronoi diagrams-a survey of a fundamental geometric data structure. ACM Comput. Surv. 23(3), 345–405 (1991)
Barber, C.B., Dobkin, D.P., Huhdanpaa, H.: The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22(4), 469–483 (1996)
Casao, S., Naya, A., Murillo, A.C., Montijano, E.: Distributed multi-target tracking in camera networks. In: IEEE International Conference on Robotics and Automation, pp. 1903–1909. IEEE (2021)
Dempster, A.P., Laird, N.M., Rubin, D.B.: Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Stat. Soc.: Ser. B (Methodol.) 39(1), 1–22 (1977)
Franchi, A., Stegagno, P., Oriolo, G.: Decentralized multi-robot encirclement of a 3D target with guaranteed collision avoidance. Auton. Robot. 40(2), 245–265 (2016)
Gao, S., Song, R., Li, Y.: Cooperative control of multiple nonholonomic robots for escorting and patrolling mission based on vector field. IEEE Access 6, 41883–41891 (2018)
Licitra, R.A., Bell, Z.I., Dixon, W.E.: Single-agent indirect herding of multiple targets with uncertain dynamics. IEEE Trans. Rob. 35(4), 847–860 (2019)
Likas, A., Vlassis, N., Verbeek, J.J.: The global k-means clustering algorithm. Pattern Recogn. 36(2), 451–461 (2003)
Montijano, E., Priolo, A., Gasparri, A., Sagues, C.: Distributed entrapment for multi-robot systems with uncertainties. In: IEEE Conference on Decision and Control, pp. 403–408 (2013)
Olfati-Saber, R.: Flocking for multi-agent dynamic systems: algorithms and theory. IEEE Trans. Autom. Control 51(3), 401–420 (2006)
Pierson, A., Schwager, M.: Controlling noncooperative herds with robotic herders. IEEE Trans. Rob. 34(2), 517–525 (2018)
Schwarting, W., Pierson, A., Karaman, S., Rus, D.: Stochastic dynamic games in belief space. IEEE Trans. Rob. 37(6), 2157–2172 (2021)
Scott, W., Leonard, N.E.: Pursuit, herding and evasion: a three-agent model of caribou predation. In: American Control Conference, pp. 2978–2983 (2013)
Sebastián, E., Montijano, E.: Multi-robot implicit control of herds. In: IEEE International Conference on Robotics and Automation, pp. 1601–1607 (2021)
Sebastián, E., Montijano, E., Sagüés, C.: All-in-one: certifiable optimal distributed kalman filter under unknown correlations. In: IEEE Conference on Decision and Control, pp. 6578–6583. IEEE (2021)
Sebastián, E., Montijano, E., Sagüés, C.: Adaptive multi-robot implicit control of heterogeneous herds. IEEE Transactions on Robotics (2022)
Song, H., et al.: Herding by caging: a formation-based motion planning framework for guiding mobile agents. Auton. Robots 45(5), 613–631 (2021). https://doi.org/10.1007/s10514-021-09975-8
Tsatsanifos, T., Clark, A.H., Walton, C., Kaminer, I., Gong, Q.: Modeling and control of large-scale adversarial swarm engagements. arXiv preprint arXiv:2108.02311 (2021)
Zhang, S., Pan, J.: Collecting a flock with multiple sub-groups by using multi-robot system. IEEE Robot. Autom. Lett. 7(3), 6974–6981 (2022)
Zhi, J., Lien, J.M.: Learning to herd agents amongst obstacles: training robust shepherding behaviors using deep reinforcement learning. IEEE Robot. Autom. Lett. 6(2), 4163–4168 (2021)
Acknowledgments
This work has been supported by the ONR Global grant N62909–19–1-2027, the Spanish projects PID2021–125514NB–I00, PID2021–124137OB–I00 and PGC2018–098719–B–I00 (MCIU/AEI/FEDER, UE), DGA T45-20R, and Spanish grant FPU19 - 05700.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Sebastián, E., Montijano, E., Sagüés, C. (2023). Multi-robot Implicit Control of Massive Herds. In: Tardioli, D., Matellán, V., Heredia, G., Silva, M.F., Marques, L. (eds) ROBOT2022: Fifth Iberian Robotics Conference. ROBOT 2022. Lecture Notes in Networks and Systems, vol 589. Springer, Cham. https://doi.org/10.1007/978-3-031-21065-5_37
Download citation
DOI: https://doi.org/10.1007/978-3-031-21065-5_37
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-21064-8
Online ISBN: 978-3-031-21065-5
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)