On the use of fuzzy preorders and asymmetric distances for multi-robot communication

Jose Guerrero; Javier Antich; Oscar Valero; Jose Guerrero; Javier Antich; Oscar Valero

doi:10.3934/math.2024565

AIMS Mathematics

2024, Volume 9, Issue 5: 11511-11536. doi: 10.3934/math.2024565

Previous Article Next Article

Research article

On the use of fuzzy preorders and asymmetric distances for multi-robot communication

1.
Mathematics and Computer Science Department, Universitat de les Illes Balears, Carr. Valldemossa km. 7.5, Palma, 07122, Spain
2.
Health Research Institute of the Balearic Islands (IdISBa), Hospital Universitari Son Espases, Palma, 07120, Spain

Received: 03 December 2023 Revised: 16 January 2024 Accepted: 19 March 2024 Published: 25 March 2024
MSC : 54E35, 54H30, 68T37, 93A16

One of the main problems to be addressed in a multi-robot system is the selection of the best robot, or group of them, to carry out a specific task. Among the large number of solutions provided to allocate tasks to a group of robots, this work focuses on swarm-like approaches, and more specifically on response-threshold algorithms, where each robot selects the next task to perform by following a Markov process. To the best of our knowledge, the current response-threshold algorithms do not provide any formal method to generate new transition functions between tasks. Thus, this paper provides, for the first time, a mathematical model, as based on the so-called fuzzy preorders, for the allocation of tasks to a collective of robots with communication capabilities. In our previous work, we proved that transitions in the aforementioned process can be modeled as fuzzy preorders, constructed through the aggregation of asymmetric distances, in such a way that each robot makes its decision without taking into account the decisions of its teammates. Now, we extend this model in such a way that each robot will take into account the number of robots previously allocated for each task. To implement this method, a very simple communication mechanism has been considered. Several simulations have been carried out in order to validate our approach. The results confirm that fuzzy preorders are able to model the evolution of the system when this type of communication is considered and show when and how the communication process improves the system's performance. Experimental results show the existence of a set of good values for the maximum communication distance between robots and that these values depend on the distribution of the tasks in the environment. Thus, in some cases, a better communication mechanism does not imply better results.
- multi-robot communication,
- fuzzy preorders,
- asymmetric distances,
- task allocation,
- possibility theory,
- aggregation
Citation: Jose Guerrero, Javier Antich, Oscar Valero. On the use of fuzzy preorders and asymmetric distances for multi-robot communication[J]. AIMS Mathematics, 2024, 9(5): 11511-11536. doi: 10.3934/math.2024565

Related Papers:

Abstract

One of the main problems to be addressed in a multi-robot system is the selection of the best robot, or group of them, to carry out a specific task. Among the large number of solutions provided to allocate tasks to a group of robots, this work focuses on swarm-like approaches, and more specifically on response-threshold algorithms, where each robot selects the next task to perform by following a Markov process. To the best of our knowledge, the current response-threshold algorithms do not provide any formal method to generate new transition functions between tasks. Thus, this paper provides, for the first time, a mathematical model, as based on the so-called fuzzy preorders, for the allocation of tasks to a collective of robots with communication capabilities. In our previous work, we proved that transitions in the aforementioned process can be modeled as fuzzy preorders, constructed through the aggregation of asymmetric distances, in such a way that each robot makes its decision without taking into account the decisions of its teammates. Now, we extend this model in such a way that each robot will take into account the number of robots previously allocated for each task. To implement this method, a very simple communication mechanism has been considered. Several simulations have been carried out in order to validate our approach. The results confirm that fuzzy preorders are able to model the evolution of the system when this type of communication is considered and show when and how the communication process improves the system's performance. Experimental results show the existence of a set of good values for the maximum communication distance between robots and that these values depend on the distribution of the tasks in the environment. Thus, in some cases, a better communication mechanism does not imply better results.

References

[1]	G. Theraulaz, E. Bonabeau, J. N. Denuebourg, Response threshold reinforcements and division of labour in insect societies, Proc. Roy. Soc. Lond. B: Biol. Sci., 265 (1998), 327–332. https://doi.org/10.1098/rspb.1998.0299 doi: 10.1098/rspb.1998.0299
[2]	W. Agassounon, A. Martinoli, Efficiency and robustness of threshold-based distributed allocation algorithms in multi-agent systems, In AAMAS'12, Bolonia, Italy, 2002, 1090–1097.
[3]	B. Heap, M. Pagnucco, Repeated sequential single-cluster auctions with dynamic tasks for multi-robot task allocation with pickup and delivery, Lect. Notes Comput. Sci., 8076 (2013), 87–100. https://doi.org/10.1007/978-3-642-40776-5_10 doi: 10.1007/978-3-642-40776-5_10
[4]	M. Otte, M. J. Kuhlman, D. Sofge, Auctions for multi-robot task allocation in communication limited environments, Auton. Robot., 44 (2020), 547–584. https://doi.org/10.1007/s10514-019-09828-5 doi: 10.1007/s10514-019-09828-5
[5]	R. J. Marcotte, X. P. Wang, D. Mehta, E. Olson, Optimizing multi-robot communication under bandwidth constraints, Auton. Robot., 44 (2020), 43–55. https://doi.org/10.1007/s10514-019-09849-0 doi: 10.1007/s10514-019-09849-0
[6]	A. Contini, A. Farinelli, Coordination approaches for multi-item pickup and delivery in logistic scenarios, Robot. Auton. Syst., 146 (2021), 103871.
[7]	S. Chowdhury, E. Sklar, Investigating the impact of communication quality on evolving populations of artificial life agents, In: the 13th European Conference on Artificial Life, 2015. https://doi.org/10.7551/978-0-262-33027-5-ch096
[8]	A. M. Deshpande, R. Kumar, M. Radmanesh, N. Veerabhadrappa, M. Kumar, A. A. Minai, Self-organized circle formation around an unknown target by a multi-robot swarm using a local communication strategy, In 2018 Annual American Control Conference (ACC), 2018, 4409–4413.
[9]	M. Dorigo, Swarm-bot: An experiment in swarm robotics, In Proceedings 2005 IEEE Swarm Intelligence Symposium, 2005,192–200.
[10]	D. A. Patil, M. Y. Upadhye, F. S. Kazi, N. M. Singh, Multi robot communication and target tracking system with controller design and implementation of swarm robot using arduino, In 2015 International Conference on Industrial Instrumentation and Control (ICIC), 2015,412–416.
[11]	M. S. Talamali, A. Saha, J. A. R. Marshall, A. Reina, When less is more: Robot swarms adapt better to changes with constrained communication, Sci. Robot., 6 (2021), 1–14. https://doi.org/10.1126/scirobotics.abf1416 doi: 10.1126/scirobotics.abf1416
[12]	J. Gielis, A. Shankar, A. Prorok, A critical review of communications in multi-robot systems, Curr. Robot. Rep., 3 (2022), 213–225. https://doi.org/10.1007/s43154-022-00090-9 doi: 10.1007/s43154-022-00090-9
[13]	J. Guerrero, O. Valero, G. Oliver, Toward a possibilistic swarm multi-robot task allocation: Theoretical and experimental results, Neural Process. Lett., 46 (2017), 881–897. https://doi.org/10.1007/s11063-017-9647-x doi: 10.1007/s11063-017-9647-x
[14]	L. A. Zadeh, Fuzzy sets as a basis for a theory of possibility, Fuzzy Set. Syst., 3 (1971), 177–200. https://doi.org/10.1016/S0165-0114(99)80004-9 doi: 10.1016/S0165-0114(99)80004-9
[15]	H. Prade, D. Dubois, Fuzzy sets and systems: Theory and applications, Academic Press, 1980.
[16]	K. Avrachenkov, E. Sanchez, Fuzzy markov chains and decision making, Fuzzy Optim.Decis. Ma., 1 (2002), 143–159.
[17]	J. Recasens, Indistinguishability operators: Modelling fuzzy equalities and fuzzy equivalence relations, Springer, 2010.
[18]	J. Guerrero, J. Miñana, O. Valero, On the use of fuzzy preorders in multi-robot task allocation problem, In Cham Springer, editor, International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, 2018,195–206.
[19]	G. Mayor, O. Valero, Aggregation of asymmetric distances in computer science, Inform. Sci., 180 (2010), 803–812. https://doi.org/10.1016/j.ins.2009.06.020 doi: 10.1016/j.ins.2009.06.020
[20]	E. Castello, T. Yamamoto, F. D. Libera, W. G. Liu, A. F. T. Winfield, Y. Nakamura, et al., Adaptive foraging for simulated and real robotic swarms: The dynamical response threshold approach, Swarm Intell., 10 (2016), 1–31. https://doi.org/10.1007/s11721-015-0117-7 doi: 10.1007/s11721-015-0117-7
[21]	Y. M. Yang, C. J. Zhou, Y. T. Tin, Swarm robots task allocation based on response threshold model, In ICARA'09, Willengton, New Zeland, 2009,171–176.
[22]	L. A. Zadeh, Similarity relations and fuzzy orderings, Inform. Sci., 1 (1971), 177–200. https://doi.org/10.1016/S0020-0255(71)80005-1 doi: 10.1016/S0020-0255(71)80005-1
[23]	R. P. Klement, R. Mesiar, E. Pap, Triangular norms, Kluwer Academic Publishers, 2000.
[24]	M. M. Deza, E. Deza, Encyclopedia of distances, Springer, 2009.
[25]	D. Dubois, H. Prade, S. Sandri, On possibility/probability transformations, Fuzzy logic, 12 (1993). https://doi.org/10.1007/978-94-011-2014-2_10 doi: 10.1007/978-94-011-2014-2_10
[26]	J. Harwell, M. Gini, Swarm engineering through quantitative measurement of swarm robotic principles in a 10,000 robot swarm, In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19), 2019.
[27]	J. Guerrero, J. J. Miñana, O. Valero, G. Oliver, Indistinguishability operators applied to task allocation problems in multi-agent systems, Appl. Sci., 7 (2017), 963. https://doi.org/10.3390/app7100963 doi: 10.3390/app7100963
[28]	M. D. M. Bibiloni-Femenias, J. Guerrero, J. J. Miñana, O. Valero, Indistinguishability operators via yager t-norms and their applications to swarm multi-agent task allocation, Mathematics, 2 (2021), 190. https://doi.org/10.3390/math9020190 doi: 10.3390/math9020190
[29]	S. Chanas, M. Nowakowski, Single value simulation of fuzzy variable, Fuzzy Set. Syst., 25 (1988), 43–57. https://doi.org/10.1016/0165-0114(88)90098-X doi: 10.1016/0165-0114(88)90098-X
[30]	M. Aggarwal, S. Kumar, The use of nanorobotics in the treatment therapy of cancer and its future aspects: A review, Cureus, 14 (2022), 1–8. https://doi.org/10.7759/cureus.29366 doi: 10.7759/cureus.29366

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)