Abstract
We address a decentralized control problem for a multi-agent network whose goal is to track a moving multi-target system over a cluttered environment. Our problem is comprised of two interconnected problems. In the first problem, we aim to find a reference density path for the multi-target system that the multi-agent network must track as a whole. In our proposed solution approach, the probability density of the multi-target system is represented as a Gaussian mixture density which is estimated by an adaptive Gaussian sum filter. The second problem seeks for the individual inputs that will make the agents follow the moving targets while avoiding collisions. To address the latter problem, we propose a control algorithm which is based on a variation of Lloyd’s algorithm that utilizes the Gaussian mixture density computed as part of the solution to the first problem and a modified Voronoi tessellation which is composed of the so-called Obstacle-Aware Voronoi Cells. Because the two sub-problems are interconnected, an iterative approach is proposed which combines their solutions to solve the multi-target tracking problem in a comprehensive and safe way. Finally, we provide simulation results to showcase the effectiveness of our proposed approach.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Data Availability
Available upon request
Code Availability
Available upon request
References
Bakhshipour, M., Jabbari Ghadi, M., Namdari, F.: Swarm robotics search and rescue: a novel artificial intelligence-inspired optimization approach. Appl. Soft Comput. 57, 708–726 (2017)
Hu, J., Xie, L., Xu, J., Xu, Z.: Multi-agent cooperative target search. Sensors 14(6), 9408–9428 (2014)
Anderson, B.D.O., Sun, Z., Sugie, T., Azuma, S.-I., Sakurama, K.: Formation shape control with distance and area constraints. IFAC J. Syst. Control 1, 2–12 (2017)
Tran, V.P., Garratt, M.A., Petersen, I.R.: Multi-vehicle formation control and obstacle avoidance using negative-imaginary systems theory. IFAC J. Syst. Control 15, 100117 (2021)
Wu, Z., Guan, Z., Wu, X., Li, T.: Consensus based formation control and trajectory tracing of multi-agent robot systems. J. Intell. Robot. Syst. 48(3), 397–410 (2007)
Dong, X., Xiang, J., Han, L., Li, Q., Ren, Z.: Distributed time-varying formation tracking analysis and design for second-order multi-agent systems. J. Intell. Robot. Syst. 86(2), 277–289 (2016)
Pierson, A., Rus, D.: Distributed target tracking in cluttered environments with guaranteed collision avoidance. In: 2017 International Symposium on Multi-Robot and Multi-Agent Systems (MRS), pp. 83–89 (2017)
Ogren, P., Leonard, N.E.: A convergent dynamic window approach to obstacle avoidance. IEEE Trans. Robot. 21(2), 188–195 (2005)
Zhang, H., Zhou, X., Wang, Z., Yan, H., Sun, J.: Adaptive consensus-based distributed target tracking with dynamic cluster in sensor networks. IEEE Trans. Cybern. 49(5), 1580–1591 (2019)
Shinde, C., Das, K., Lima, R., Vankadari, M.B., Kumar, S.: Adaptive gaussian mixture-probability hypothesis density based multi sensor multi-target tracking. In: 2019 18th ECC, pp. 862–868 (2019)
Gao, L., Zhang, H., Wang, Y.: An efficient multi-target tracking algorithm using gaussian mixture probability hypothesis density filter. In: 2018 IEEE CSAA, pp. 1–5 (2018)
Yu, Y.: Consensus-based distributed mixture Kalman filter for maneuvering target tracking in wireless sensor networks. IEEE Trans. Veh. Technol. 65(10), 8669–8681 (2016)
Granström, K., Orguner, U., Mahler, R., Lundquist, C.: Corrections on: “extended target tracking using a Gaussian-mixture PHD filter”. IEEE Trans. Aerosp. Electron. Syst. 53(2), 1055–1058 (2017)
Sharma, P., Saucan, A., Bucci, D.J., Varshney, P.K.: Decentralized Gaussian filters for cooperative self-localization and multi-target tracking. IEEE Trans. Signal Process. 67(22), 5896–5911 (2019)
Zhang, H., Zhou, X., Wang, Z., Yan, H.: Maneuvering target tracking with event-based mixture Kalman filter in mobile sensor networks. IEEE Trans. Cybern. 50(10), 4346–4357 (2020)
Hu, J., Bhowmick, P., Lanzon, A.: Distributed adaptive time-varying group formation tracking for multiagent systems with multiple leaders on directed graphs. IEEE Trans. Control Netw. Syst. 7(1), 140–150 (2020)
Baradaran Khalkhali, M., Vahedian, A., Sadoghi Yazdi, H.: Multi-target state estimation using interactive Kalman filter for multi-vehicle tracking. IEEE Trans. Intell. Transp. Syst. 21(3), 1131–1144 (2020)
Yuan, W., Ganganath, N., Cheng, C. -T., Qing, G., Lau, F.C.M.: Semi-flocking-controlled mobile sensor networks for dynamic area coverage and multiple target tracking. IEEE Sensors J. 18(21), 8883–8892 (2018)
Wu, Y., Liu, L.: Distributed average tracking for linear heterogeneous multi-agent systems with external disturbances. IEEE Trans. Netw. Sci. Eng. 1–1 (2021)
Ma, J., Lu, H., Xiao, J., Zeng, Z., Zheng, Z.: Multi-robot target encirclement control with collision avoidance via deep reinforcement learning. J. Intell. Robot. Syst. 99(2), 371–386 (2019)
Cortes, J., Martinez, S., Karatas, T., Bullo, F.: Coverage control for mobile sensing networks. IEEE Trans. Robot. Autom. 20(2), 243–255 (2004)
Lee, S.G., Diaz-Mercado, Y., Egerstedt, M.: Multirobot control using time-varying density functions. IEEE Trans. Robot. 31(2), 489–493 (2015)
Cortes, J., Martinez, S., Karatas, T., Bullo, F.: Coverage control for mobile sensing networks: variations on a theme. 10th MCCA 1 (2002)
Miah, S., Fallah, M.M.H., Spinello, D.: Non-autonomous coverage control with diffusive evolving density. IEEE Trans. Autom. Control 62(10), 5262–5268 (2017)
Miah, S., Panah, A.Y., Fallah, M.M.H., Spinello, D.: Generalized non-autonomous metric optimization for area coverage problems with mobile autonomous agents. Automatica 80, 295–299 (2017)
Zuo, L., Shi, Y., Yan, W.: Dynamic coverage control in a time-varying environment using Bayesian prediction. IEEE Trans. Cybern. 49(1), 354–362 (2019)
Chung, Y.-F., Kia, S.S.: A distributed service-matching coverage via heterogeneous agents. IEEE Robot. Autom. Lett. 7(2), 4400–4407 (2022)
Inoue, D., Ito, Y., Yoshida, H.: Optimal transport-based coverage control for swarm robot systems: generalization of the Voronoi tessellation-based method. IEEE Control Syst. Lett. 5(4), 1483–1488 (2021)
Li, Z., Tang, Y., Huang, T., Kurths, J.: Formation control with mismatched orientation in multi-agent systems. IEEE Trans. Netw. Sci. Eng. 6(3), 314–325 (2019)
Bakolas, E.: Distributed partitioning algorithms for locational optimization of multiagent networks in se (2). IEEE Trans. Autom. Control 63(1), 101–116 (2017)
Bakolas, E.: Workspace partitioning and topology discovery algorithms for heterogeneous multiagent networks. IEEE Trans. Control Netw. Syst. 8(1), 354–366 (2020)
Jafari, M., Xu, H., Carrillo, L.R.G.: A biologically-inspired reinforcement learning based intelligent distributed flocking control for multi-agent systems in presence of uncertain system and dynamic environment. IFAC J. Syst. Control 13, 100096 (2020)
Ma, A., Cortés, J.: Distributed multi-agent deployment for full visibility of 1.5d and 2.5d polyhedral terrains. J. Intell. Robot. Syst. 100(3-4), 1111–1127 (2020)
Stergiopoulos, Y.J., Tzes, A.: Decentralized swarm coordination: a combined coverage/connectivity approach. J. Intell. Robot. Syst. 64(3-4), 603–623 (2011)
Abdulghafoor, A.Z., Bakolas, E.: Two-level control of multiagent networks for dynamic coverage problems. IEEE Trans. Cybernet. PP 1–12 (2021)
Abdulghafoor, A., Bakolas, E.: Distributed coverage control of multi-agent networks with guaranteed collision avoidance in cluttered environments. IFAC-PapersOnLine 54(20), 771–776 (2021). Modeling, Estimation and Control Conference MECC 2021
Acevedo, J., Arrue, B., Maza, I., Ollero, A.: Cooperative large area surveillance with a team of aerial mobile robots for long endurance missions. J. Intell. Rob. Syst. 70(1-4), 329–345 (2013)
Zhang, G., Fricke, G.K., Garg, D.P.: Spill detection and perimeter surveillance via distributed swarming agents. IEEE/ASME Trans. Mechatron. 18(1), 121–129 (2013)
Asad, M., Khan, S., Arif, M., Mehmood, Z., Durrani, S., Khan, U.: Ballistic missile tracking in the presence of clutter using multi-target tracking algorithm. In: 2017 14th International Bhurban Conference on Applied Sciences and Technology (IBCAST), pp. 357–360. https://doi.org/10.1109/IBCAST.2017.7868079 (2017)
Hwang, I., Balakrishnan, H., Roy, K., Tomlin, C.: Multiple-target tracking and identity management in clutter for air traffic control. In: Proceedings of the AACC American Control Conference (2004)
Koga, T., Lu, X.: Autonomous decentralized surveillance system and continuous target tracking technology for air traffic control applications.. In: 2013 IEEE Eleventh International Symposium on Autonomous Decentralized Systems (ISADS), pp. 1–8. https://doi.org/10.1109/ISADS.2013.6513406 (2013)
Benfold, B., Reid, I.: Stable multi-target tracking in real-time surveillance video. In: CVPR 2011, pp. 3457–3464. https://doi.org/10.1109/CVPR.2011.5995667 (2011)
Granström, K., Lundquist, C., Orguner, U.: A gaussian mixture PHD filter for extended target tracking. In: 2010 13th International Conference on Information Fusion, pp. 1–8 (2010)
Granstrom, K., Lundquist, C., Orguner, O.: Extended target tracking using a Gaussian-mixture PHD filter. IEEE Trans. Aerosp. Electron. Syst. 48(4), 3268–3286 (2012)
Yazdian-Dehkordi, M., Azimifar, Z., Masnadi-Shirazi, M.A.: Penalized Gaussian mixture probability hypothesis density filter for multiple target tracking. Signal Process. 92(5), 1230–1242 (2012)
Zhao, L., Ma, P., Su, X., Zhang, H.: A new multi-target state estimation algorithm for PHD particle filter. In: 2010 13th International Conference on Information Fusion, pp. 1–8 (2010)
Vo, B. -N., Singh, S., Doucet, A., et al.: Sequential monte carlo implementation of the PHD filter for multi-target tracking. In: Proc. Int’L Conf. on Information Fusion, pp. 792–799 (2003)
Leonard, M.R., Zoubir, A.M.: Multi-target tracking in distributed sensor networks using particle PHD filters. Signal Process. 159, 130–146 (2019)
Kalman, R.E.: A new approach to linear filtering and prediction problems. J. Basic Eng. 82(1), 35–45 (1960)
Maskell, S., Gordon, N.: A tutorial on particle filters for on-line nonlinear/non-Gaussian Bayesian tracking. In: Target Tracking: Algorithms and Applications, IEE Workshop On, pp. 2–1. IET (2001)
Daum, F., Huang, J.: Curse of dimensionality and particle filters. In: 2003 IEEE Aerospace Conference Proceedings, vol. 4, pp. 1979–1993 (2003)
Çağlar, A, Aksoy, S, Arıkan, O.: Maximum likelihood estimation of Gaussian mixture models using stochastic search. Pattern Recogn. 45(7), 2804–2816 (2012)
Xu, Y., Fang, Y., Peng, W., Wu, Y.: An efficient Gaussian sum filter based on prune-cluster-merge scheme. IEEE Access 7, 150992–151005 (2019)
Alspach, D., Sorenson, H.: Nonlinear Bayesian estimation using Gaussian sum approximations. IEEE Trans. Autom. Control 17(4), 439–448 (1972)
Ito, K., Xiong, K.: Gaussian filters for nonlinear filtering problems. IEEE Trans. Autom. Control 45(5), 910–927 (2000)
Pal, S., Coates, M.: Gaussian sum particle flow filter. In: 2017 IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), pp. 1–5 (2017)
Kotecha, J.H., Djuric, P.M.: Gaussian sum particle filtering. IEEE Trans. Signal Process. 51 (10), 2602–2612 (2003)
Raihan, D., Chakravorty, S.: Particle Gaussian mixture filters-i. Automatica 98, 331–340 (2018)
Raihan, D., Chakravorty, S.: Particle Gaussian mixture filters-ii. Automatica 98, 341–349 (2018)
Musicki, D., La Scala, B.F., Evans, R.J.: Integrated track splitting filter - efficient multi-scan single target tracking in clutter. IEEE Trans. Aerosp. Electron. Syst. 43(4), 1409–1425 (2007)
Terejanu, G., Singla, P., Singh, T., Scott, P.D.: Adaptive Gaussian sum filter for nonlinear Bayesian estimation. IEEE Trans. Autom. Control 56(9), 2151–2156 (2011)
Tabasso, C., Cichella, V., Mehdi, S.B., Marinho, T., Hovakimyan, N.: Time coordination and collision avoidance using leader-follower strategies in multi-vehicle missions. Robotics (Basel) 10(1), 34 (2021)
Ji, J., Khajepour, A., Melek, W.W., Huang, Y.: Path planning and tracking for vehicle collision avoidance based on model predictive control with multiconstraints. IEEE Trans. Veh. Technol. 66(2), 952–964 (2017)
Boardman, B., Harden, T., Martínez, S.: Multi-agent motion planning with sporadic communications for collision avoidance. IFAC J. Syst. Control 15, 100126 (2021)
Sun, J., Tang, J., Lao, S.: Collision avoidance for cooperative uavs with optimized artificial potential field algorithm. IEEE Access 5, 18382–18390 (2017)
Chen, Y.F., Liu, M., Everett, M., How, J.P.: Decentralized non-communicating multiagent collision avoidance with deep reinforcement learning. In: 2017 IEEE ICRA, pp. 285–292 (2017)
Hu, Y., Yu, H., Zhong, Y., Lv, Y.: Distributed collision-avoidance formation control: a velocity obstacle-based approach. In: 2019 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 1994–2000 (2019)
Mylvaganam, T., Sassano, M.: Autonomous collision avoidance for wheeled mobile robots using a differential game approach. Eur. J. Control. 40, 53–61 (2018)
Cappello, D., Garcin, S., Mao, Z., Sassano, M., Paranjape, A., Mylvaganam, T.: A hybrid controller for multi-agent collision avoidance via a differential game formulation. IEEE Trans. Control Syst. Technol. 29(4), 1750–1757 (2021)
Minguez, J., Montano, L.: Nearness diagram (nd) navigation: collision avoidance in troublesome scenarios. IEEE Trans. Robot. Autom. 20(1), 45–59 (2004)
Sutton, R., Singh, Y., Bibuli, M., Zereik, E., Sharma, S., Khan, A., Sutton, R.: A novel double layered hybrid multi-robot framework for guidance and navigation of unmanned surface vehicles in a practical maritime environment. J. Marine Sci. Eng. 8, 624 (2020)
Sun, J., Tang, J., Lao, S.: Collision avoidance for cooperative uavs with optimized artificial potential field algorithm. IEEE Access 5, 18382–18390 (2017)
Zhou, Z., Zhang, W., Ding, J., Huang, H., Stipanović, D.M., Tomlin, C.J.: Cooperative pursuit with Voronoi partitions. Automatica (Oxford) 72, 64–72 (2016)
Pierson, A., Ataei, A., Paschalidis, I.C., Schwager, M.: Cooperative multi-quadrotor pursuit of an evader in an environment with no-fly zones. In: 2016 IEEE ICRA, pp. 320–326 (2016)
Zhou, D., Wang, Z., Bandyopadhyay, S., Schwager, M.: Fast, on-line collision avoidance for dynamic vehicles using buffered Voronoi cells. IEEE Robot. Autom. Lett. 2(2), 1047–1054 (2017)
Risken, H.: The Fokker-Planck Equation : Methods of Solution and Applications., 2nd ed. edn. Springer Series in Synergetics Ser. ; vol. 18. Springer (1992)
Terejanu, G., Singla, P., Singh, T., Scott, P.D.: A novel gaussian sum filter method for accurate solution to the nonlinear filtering problem. In: 2008 11th International Conference on Information Fusion, pp. 1–8 (2008)
Calafiore, G.C., El Ghaoui, L.: Optimization Models. Cambridge University Press, Cambridge (2014)
Terejanu, G., Singla, P., Singh, T., Scott, P.D.: Uncertainty propagation for nonlinear dynamic systems using Gaussian mixture models. J. Guid. Control Dyn. 31(6), 1623–1633 (2008)
Bakolas, E.: Decentralized spatial partitioning algorithms for multi-vehicle systems based on the minimum control effort metric. Syst. Control Lett. 73(C), 81–87 (2014)
Bakolas, E.: Distributed partitioning algorithms for locational optimization of multiagent networks in se(2). IEEE Trans. Autom. Control 63(1), 101–116 (2018)
Pierson, A., Schwarting, W., Karaman, S., Rus, D.: Weighted buffered voronoi cells for distributed semi-cooperative behavior. In: 2020 IEEE ICRA 2020, Paris, France, May 31 - August 31, 2020, pp. 5611–5617 (2020)
Du, Q., Faber, V., Gunzburger, M.: Centroidal Voronoi tessellations: Applications and algorithms. SIAM Rev. 41(4), 637–676 (1999)
Du, Q., Emelianenko, M., Ju, L.: Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations. SIAM J. Numer. Anal. 44(1), 102–119 (2006)
Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations : Concepts and Applications of Voronoi Diagrams. Wiley, Hoboken (2000)
de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry : Algorithms and Applications, 3rd edn. Springer, Berlin (2008)
Bakolas, E.: Workspace partitioning and topology discovery algorithms for heterogeneous multiagent networks. IEEE Trans. Control Netw. Syst. 8(1), 354–366 (2021). https://doi.org/10.1109/TCNS.2020.3002984
Kennedy, J., Chapman, A., Dower, P.M.: Generalized coverage control for time-varying density functions.. In: 2019 18th ECC, pp. 71–76 (2019)
Sastry, S.: Nonlinear Systems : analysis, Stability, and Control. Interdisciplinary applied mathematics, vol. 10. Springer, New York (1999)
Lee, S.-J., Park, S.-S., Choi, H.-L.: Potential game-based non-myopic sensor network planning for multi-target tracking. IEEE Access 6, 79245–79257 (2018)
Funding
The authors declare that no funds, grants, or other support were received during the preparation of this manuscript
Author information
Authors and Affiliations
Contributions
All authors contributed to the study conception and design. Alaa Z. Abdulghafoor contributed to the following tasks: conceptualization, methodology, software, writing-original draft preparation, validation, visualization, investigation, and formal analysis. Efstathios Bakolas contributed to the following tasks: supervision, methodology, writing-reviewing and editing, and formal analysis. All authors read and approved the final manuscript.
Corresponding author
Ethics declarations
All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript.
Ethics approval
Not applicable. Our research does not involve any human or animal subjects.
Consent to participate
Not applicable. Our research does not involve any human subjects.
Consent for Publication
Not applicable.
Conflict of Interests
The authors have no relevant financial or non-financial interests to disclose
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Abdulghafoor, A.Z., Bakolas, E. Motion Coordination of Multi-Agent Networks for Multiple Target Tracking with Guaranteed Collision Avoidance. J Intell Robot Syst 107, 5 (2023). https://doi.org/10.1007/s10846-022-01786-y
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10846-022-01786-y