Abstract
This paper compares different distributed control approaches which enable a team of robots search for and track an unknown number of targets. The robots are equipped with sensors which have a limited field of view (FoV) and they are required to explore the environment. The team uses a distributed formulation of the Probability Hypothesis Density (PHD) filter to estimate the number and the position of the targets. The resulting target estimate is used to select the subsequent search locations for each robot. This paper compares Lloyd’s algorithm, a traditional method for distributed search, with two typical stochastic optimization methods: Particle Swarm Optimization (PSO) and Simulated Annealing (SA). This paper presents novel formulations of PSO and SA to solve the multi-target tracking problem, which more effectively trade off between exploration and exploitation. Simulations demonstrate that the use of these stochastic optimization techniques improves coverage of the search space and reduces the error in the target estimates compared to the baseline approach.
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 assumes that, per the note in Algorithm 1, line 2, the Voronoi computations are combined with the distributed PHD filter step.
References
Blackman, S.: Multiple hypothesis tracking for multiple target tracking. IEEE Aerosp. Electron. Syst. Mag. 19(1), 5–18 (2004). https://doi.org/10.1109/MAES.2004.1263228
Chen, J., Xie, Z., Dames, P.: The semantic PHD filter for multi-class target tracking: From theory to practice. Robot. Autonomous Syst. 149 (2022). https://doi.org/10.1016/j.robot.2021.103947
Cortes, J., Martinez, S., Karatas, T., Bullo, F.: Coverage control for mobile sensing networks. IEEE Trans. Robot. Autom. 20(2), 243–255 (2004). https://doi.org/10.1109/TRA.2004.824698
Dames, P., Kumar, V.: Autonomous localization of an unknown number of targets without data association using teams of mobile sensors. IEEE Trans. Autom. Sci. Eng. 12(3), 850–864 (2015). https://doi.org/10.1109/tase.2015.2425212
Dames, P., Kumar, V.: Experimental characterization of a bearing-only sensor for use with the phd filter (2015). https://doi.org/10.48550/arXiv.1502.04661
Dames, P.M.: Distributed multi-target search and tracking using the PHD filter. Auton. Robot. 44, 673–689 (2020). https://doi.org/10.1007/s10514-019-09840-9
Davis, L.: Bit-climbing, representational bias, and test suit design. In: Proc. Intl. Conf. Genetic Algorithm, 1991, pp. 18–23 (1991)
Derr, K., Manic, M.: Multi-robot, multi-target particle swarm optimization search in noisy wireless environments. In: 2009 2nd Conference on Human System Interactions, pp. 81–86 (2009). https://doi.org/10.1109/HSI.2009.5090958
Deutsch, I., Liu, M., Siegwart, R.: A framework for multi-robot pose graph slam. In: 2016 IEEE International Conference on Real-time Computing and Robotics (RCAR), pp. 567–572 (2016). https://doi.org/10.1109/RCAR.2016.7784092
Doitsidis, L., et al.: Optimal surveillance coverage for teams of micro aerial vehicles in gps-denied environments using onboard vision. Auton. Robot. 33(1), 173–188 (2012). https://doi.org/10.1007/s10514-012-9292-1
Du, Q., Faber, V., Gunzburger, M.: Centroidal voronoi tessellations: applications and algorithms. SIAM Rev. 41(4), 637–676 (1999). https://doi.org/10.1137/S0036144599352836
Fortmann, T., Bar-Shalom, Y., Scheffe, M.: Sonar tracking of multiple targets using joint probabilistic data association. IEEE J. Oceanic Eng. 8(3), 173–184 (1983). https://doi.org/10.1109/JOE.1983.1145560
Glover, F.: Tabu search-part i. ORSA J. Comput. 1(3), 190–206 (1989)
Goldhoorn, A., Garrell, A., Alquézar, R., Sanfeliu, A.: Searching and tracking people with cooperative mobile robots. Auton. Robot. 42(4), 739–759 (2018). https://doi.org/10.1007/s10514-017-9681-6
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of ICNN’95 - International Conference on Neural Networks, vol. 4, pp. 1942–1948 vol 4 (1995). https://doi.org/10.1109/ICNN.1995.488968
Kirkpatrick, S., Gelatt, C.D., Jr., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Mahler, R.: Multitarget bayes filtering via first-order multitarget moments. IEEE Trans. Aerosp. Electron. Syst. 39(4), 1152–1178 (2003). https://doi.org/10.1109/TAES.2003.1261119
Mirjalili, S.: Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm. Knowl.-Based Syst. 89, 228–249 (2015). https://doi.org/10.1016/j.knosys.2015.07.006
Murphy, R.: Human-robot interaction in rescue robotics. IEEE Trans. Syst. Man Cybern. Part C (Applications and Reviews) 34(2), 138–153 (2004). https://doi.org/10.1109/TSMCC.2004.826267
Qie, H., Shi, D., Shen, T., Xu, X., Li, Y., Wang, L.: Joint optimization of multi-uav target assignment and path planning based on multi-agent reinforcement learning. IEEE Access 7, 146264–146272 (2019). https://doi.org/10.1109/ACCESS.2019.2943253
Rizk, Y., Awad, M., Tunstel, E.W.: Decision making in multiagent systems: a survey. IEEE Trans. Cognitive Developmental Syst. 10(3), 514–529 (2018). https://doi.org/10.1109/TCDS.2018.2840971
Robin, C., Lacroix, S.: Multi-robot target detection and tracking: taxonomy and survey. Auton. Robot. 40(4), 729–760 (2016)
Schuhmacher, D., Vo, B.T., Vo, B.N.: A consistent metric for performance evaluation of multi-object filters. IEEE Trans. Signal Process. 56(8), 3447–3457 (2008). https://doi.org/10.1109/TSP.2008.920469
Shi, W., He, Z., Tang, W., Liu, W., Ma, Z.: Path planning of multi-robot systems with boolean specifications based on simulated annealing. IEEE Robot. Autom. Lett. 7, 6091–6098 (2022). https://doi.org/10.1109/LRA.2022.3165184
Stone, L.D., Streit, R.L., Corwin, T.L., Bell, K.L.: Bayesian multiple target tracking. Artech House (2013)
Tang, Q., Yu, F., Xu, Z., Eberhard, P.: Swarm robots search for multiple targets. IEEE Access 8, 92814–92826 (2020). https://doi.org/10.1109/ACCESS.2020.2994151
Vo, B.N., Ma, W.K.: The Gaussian mixture probability hypothesis density filter. IEEE Trans. Signal Process. 54(11), 4091–4104 (2006)
Vo, B.N., Singh, S., Doucet, A.: Sequential Monte Carlo methods for multitarget filtering with random finite sets. IEEE Trans. Aerosp. Electron. Syst. 41(4), 1224–1245 (2005)
Wang, B.: Coverage problems in sensor networks: A survey. ACM Comput. Surv. 43(4) (2011). https://doi.org/10.1145/1978802.1978811
Zhang, C., Lesser, V.: Coordinating multi-agent reinforcement learning with limited communication. In: Proceedings of the 2013 International Conference on Autonomous Agents and Multi-Agent Systems, AAMAS ’13, pp. 1101–1108. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC (2013)
Acknowledgement
This work was funded by NSF grants IIS-1830419 and CNS-2143312.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Xin, P., Dames, P. (2024). Comparing Stochastic Optimization Methods for Multi-robot, Multi-target Tracking. In: Bourgeois, J., et al. Distributed Autonomous Robotic Systems. DARS 2022. Springer Proceedings in Advanced Robotics, vol 28. Springer, Cham. https://doi.org/10.1007/978-3-031-51497-5_27
Download citation
DOI: https://doi.org/10.1007/978-3-031-51497-5_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-51496-8
Online ISBN: 978-3-031-51497-5
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)