Centralized Algorithms Based on Clustering with Self-tuning of Parameters for Cooperative Target Observation

João Pedro Bernardino Andrade; Jose Everardo B. Maia; Gustavo Augusto L. de Campos

doi:10.22456/2175-2745.107154

Authors

João Pedro Bernardino Andrade
Jose Everardo B. Maia
Gustavo Augusto L. de Campos

DOI:

https://doi.org/10.22456/2175-2745.107154

Keywords:

Multi-Agent Systems, Agent-Based Simulation, Clustering Methods, Intelligent Robots

Abstract

Clustering on target positions is a class of centralized algorithms used to calculate the surveillance robots' displacements in the Cooperative Target Observation (CTO) problem. This work proposes and evaluates Fuzzy C-means (FCM) and Density-Based Spatial Clustering of Applications with Noise (DBSCAN) with K-means (DBSk) based self-tuning clustering centralized algorithms for the CTO problem and compares its performances with that of K-means. Two random motion patterns are adopted for the targets: in free space or on a grid. As a contribution, the work allows identifying ranges of problem configuration parameters in which each algorithm shows the highest average performance. As a first conclusion, in the challenging situation in which the relative speed of the targets is high, and the relative sensor range of the surveillance is low, for which the existing algorithms present a substantial drop in performance, the FCM algorithm proposed outperforms the others. Finally, the DBSk algorithm adapts very well in low execution frequency, showing promising results in this challenging situation.

Downloads

Download data is not yet available.

References

KANISTRAS, K. et al. A survey of unmanned aerial vehicles (uavs) for traffic monitoring. In: IEEE. 2013 International Conference on Unmanned Aircraft Systems (ICUAS). Atlanta, 2013. p. 221–234. Dispon ́ıvel em: 〈https://doi.org/10.1109/ICUAS.2013.6564694〉.

BONADIES, S.; LEFCOURT, A.; GADSDEN, S. A. A survey of unmanned ground vehicles with applications to agricultural and environmental sensing. In: INTERNATIONAL SOCIETY FOR OPTICS AND PHOTONICS. Autonomous air and ground sensing systems for agricultural optimization and phenotyping. Baltimore, 2016. v. 9866, p. 98660Q. Dispon ́ıvel em: 〈https://doi.org/10.1117/12.2224248〉.

SULLIVAN, K. M.; LUKE, S. Autonomous uuv control via tunably decentralized algorithms. In: IEEE. 2004 IEEE/OES Autonomous Underwater Vehicles (IEEE Cat. No. 04CH37578). Sebasco, 2004. p. 47–53. Dispon ́ıvel em: 〈https://doi.org/10.1109/AUV.2004.1431192〉.

FIORANELLI, F. et al. Classification of loaded/unloaded micro-drones using multistatic radar. Electronics Letters, IET, Stevenage, v. 51, n. 22, p. 1813–1815, 2015. Dispon ́ıvel em: 〈https://doi.org/10.1049/el.2015.3038〉.

RODR ́IGUEZ, A. et al. The eye in the sky: Combined use of unmanned aerial systems and gps data loggers for ecological research and conservation of small birds. PLoS One, Public Library of Science, S ̃ao Francisco, v. 7, n. 12, p. e50336, 2012. Dispon ́ıvel em: 〈https://doi.org/10.1371/journal.pone.0050336〉.

KHALEGHI, A. M. et al. A DDDAMS-based planning and control framework for surveillance and crowd control via UAVs and UGVs. Expert Systems with Applications, Elsevier, Amsterd ̃a, v. 40, n. 18, p. 7168–7183, 2013. Dispon ́ıvel em:〈https://doi.org/10.1016/j.eswa.2013.07.039〉.

PARKER, L. E. Cooperative robotics for multi-target observation. Intelligent Automation & Soft Computing, Taylor & Francis, Abingdon-on-Thames, v. 5, n. 1, p. 5–19, 1999. Dispon ́ıvel em: 〈https://doi.org/10.1080/10798587.1999.10750747〉.

KHAN, A.; RINNER, B.; CAVALLARO, A. Cooperative robots to observe moving targets. IEEE transactions on cybernetics, IEEE, Piscataway, v. 48, n. 1, p. 187–198, 2016. Dispon ́ıvel em: 〈https://doi.org/10.1109/TCYB.2016.2628161〉.

LUKE, S. et al. Tunably decentralized algorithms for cooperative target observation. In: Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems. Nova Iorque: [s.n.], 2005. p. 911–917. Dispon ́ıvel em: 〈https://doi.org/10.1145/1082473.1082611〉.

ASWANI, R.; MUNNANGI, S. K.; PARUCHURI, P. Improving surveillance using cooperative target observation. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence. S ̃ao Francisco: AAAI Publications, 2017. Dispon ́ıvel em: 〈https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14882〉.

BEZDEK, J. C. Pattern recognition with fuzzy objective function algorithms. Berlim: Springer Science & Business Media, 2013.

ESTER, M. et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In: KDD’96: Proceedings of the Second International Conference on Knowledge Discovery and Data Mining. Menlo Park: AAAI Press, 1996. v. 96, n. 34, p. 226–231. Dispon ́ıvel em: 〈https://dl.acm.org/doi/10.5555/3001460.3001507〉.

BANFI, J. et al. An integer linear programming model for fair multitarget tracking in cooperative multirobot systems. Autonomous Robots, Springer, Berlim, v. 43, n. 3, p. 665–680, 2019. Dispon ́ıvel em: 〈https://doi.org/10.1007/s10514-018-9735-4〉.

PAKHIRA, M. K. A modified k-means algorithm to avoid empty clusters. International Journal of Recent Trends in Engineering, Academy Publisher, Barpeta, v. 1, n. 1, p. 220, 2009.

DUNN, J. C. A fuzzy relative of the isodata process and its use in detecting compact well-separated clusters. Journal of Cybernetics, Taylor & Francis, Abingdon-on-Thames, v. 3, n. 3, p. 32–57, 1973. Dispon ́ıvel em: 〈https://doi.org/10.1080/01969727308546046〉.

ANDRADE, J. P. B. et al. Organization/fuzzy approach to the cto problem. In: 2018 7th Brazilian Conference on Intelligent Systems (BRACIS). S ̃ao Paulo: [s.n.], 2018. p. 444–449. Dispon ́ıvel em: 〈https://ieeexplore.ieee.org/document/8575654/〉.

TORRA, V. On the selection of m for fuzzy c-means. In: ATLANTIS PRESS. 2015 Conference of the International Fuzzy Systems Association and the European Society for Fuzzy Logic and Technology (IFSA-EUSFLAT-15). Gij ́on, 2015. Dispon ́ıvel em: 〈https://doi.org/10.2991/ifsa-eusflat-15.2015.224〉