АЛГОРИТМИ РОЗПІЗНАВАННЯ ГРАФІВ КОЛЕКТИВОМ АГЕНТІВ
ІНФОРМАТИКА ТА МЕТОДИКА ЇЇ НАВЧАННЯ
DOI:
https://doi.org/10.31865/2413-26672415-3079132023295362Ключові слова:
розпізнавання графів, алгоритми обходу графа, колектив агентівАнотація
В роботі проведено огляд та проаналізовано сучасний стан наукових досліджень, пов'язаних з розпізнаванням графів колективом агентів. Також проаналізовано можливість та необхідність ознайомлення учнів старших класів закладів загальної середньої освіти з задачею розпізнавання графів та поглиблення її вивчення до колективного розпізнавання.
Посилання
Albers S., Henzinger M.R. Exploring unknown environments // SIAM Journal on Computing. – 2000. – №29(4). – P. 1164-1188.
R. Fleischer, G. Trippen Exploring an unknown graph efficiently G.S. Brodal, S. Leonardi (Eds.), Proceedings of the 13th Annual European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 3669, ESA 2005, Palma de Mallorca, Spain, October 3–6, 2005, Springer (2005), pp. 11-22
Thrun S., et al., Robotic mapping: a survey. – 2003. – pp. 1–35.
Zhang C. Parallelizing Depth-First Search for Robotic Graph Exploration // Harvard College, Cambridge, Massachusetts. – 2010.
Nagavarapu S.C., Vachhani L., Sinha A. et al. Generalizing Multi-agent Graph Exploration Techniques // International Journal of Control, Automation and Systems (2020). https://doi.org/10.1007/s12555-019-0067-8
Stepkin A. Using a Collective of Agents for Exploration of Undirected Graphs / A. Stepkin // Cybernetics and Systems Analysis. – 2015. – V.51, №2. – PP. 223-233.
Banfi J., Quattrini Li.A., Rekleitis I. et al. Strategies for coordinated multirobot exploration with recurrent connectivity constraints. // Autonomous Robots 42, 875-894 (2018). https://doi.org/10.1007/s10514- 017-9652-y
Стёпкин А.В. Возможность и сложность распознавания графов тремя агентами / А.В. Стёпкин // Таврический вестник информатики и математики. – 2012. – №1 (20). – C. 88-98.
Стёпкин А.В. Распознавание конечных графов тремя агентами / А.В. Стёпкин // Искусственный интеллект. – 2011. – №2. – С. 84-93.
Shannon C.E. Presentation of a maze-solving machine // Cybernetics Trans, of the 8 th Conf. of the JosiahMacy Jr. Found / Editor: H. Foerster. – 1951. – P. 173-180.
Wang H., Jenkin M., Dymond P. It can be beneficial to be 'lazy' when exploring graph-like worlds with multiple robots // In Proceedings of the IASTED International Conference on Advances in Computer Science and Engineering (ACSE). – 2009. – P. 55-60.
Zhang C. Parallelizing Depth-First Search for Robotic Graph Exploration // Harvard College, Cambridge, Massachusetts. – 2010.
Стёпкин А.В., Стёпкина А.С. Алгоритм распознавания простых графов коллективом агентов. Компьютерные исследования и моделирование. 2021. Т.13, №1. С. 33-45.
Jiayu Chen, Jingdi Chen, Tian Lan, Vaneet Aggarwal. Scalable Multi-agent Covering Option Discovery based on Kronecker Graphs / Jiayu Chen, Jingdi Chen, Tian Lan, Vaneet Aggarwal // Advances in Neural Information Processing Systems, 2022.
Ainur Zhaikhan, Ali H. Sayed. Graph Exploration for Effective Multi-agent Q-Learning. arXiv:2304.09547, 2023.
