Порівняльна оцінка алгоритмів розподілу завдань у багатороботних системах
DOI:
https://doi.org/10.20535/1560-8956.48.2026.351925Ключові слова:
багатороботні системи, розподіл завдань, алгоритми, продуктивність, оптимізація, координація роботів, система, архітектура, моделювання, автоматичне управління, робототехнічні системи, architecture, modeling, automatic control, robotic systemsАнотація
У статті представлено порівняльну оцінку шести алгоритмів розподілу завдань у багатороботних системах: Least Connections, Load Balancing, Random, Ant Colony Optimization, Simulated Annealing та Linear Optimization. Дослідження проведено на основі симуляції із використанням набору з 20 роботів та випадково згенерованого набору завдань з різними пріоритетами, тривалістю та вимогами. Для аналізу роботи алгоритмів розподілу було використано окремий модуль аналітики, який дозволив легко та інтерактивно переглядати графіки по всім параметрам, за якими проводилась оцінка якості призначення задач. Оцінка продуктивності кожного з алгоритмів здійснювалася за такими показниками: середній ETA (очікуваний час завершення), кількість завдань у черзі та середній час призначення. Результати показали, що алгоритми Least Connections та Load Balancing демонструють найкращу рівномірність розподілу навантаження, забезпечуючи стабільний розподіл черг і час призначення. Випадковий алгоритм показав найгірші результати. Це пояснюється тим, що даний алгоритм абсолютно не враховує поточний стан системи, агентів та їх властивостей. Лінійна оптимізація дозволяє досягти найточніших відповідностей між завданнями і роботами, однак при цьому супроводжується суттєвим дисбалансом. Отримані результати досліджень підкреслюють важливість узгодження алгоритмічного дизайну з операційними цілями.
Бібл. 13. іл. 12, табл. 6
Посилання
Fang Z., Ma T., Huang J., Niu Z., Yang F. Efficient Task Allocation in Multi-Agent Systems Using Reinforcement Learning and Genetic Algorithm. MDPI. URL: https://www.mdpi.com/2076-3417/15/4/1905 (date of access: 25.05.2025).
Liu H., Zhang Y., Tang Y., Wang X. A Novel Multi-Robot Task Allocation Model in Marine Plastics Cleaning Based on Replicated Dynamics. MDPI. URL: https://www.mdpi.com/2071-1050/15/6/5074 (date of access: 25.05.2025).
Bronsdon C. Multi-Agent Coordination Strategies: From Theory to Practice. Galileo. URL: https://www.galileo.ai/blog/multi-agent-coordination-strategies (date of access: 25.05.2025).
Braquet M., Bakolas E. Greedy Decentralized Auction-based Task Allocation for Multi-Agent Systems. URL: https://martinbraquet.com/wp-content/uploads/Greedy-Decentralized-Auction-based-Task-Allocation-for-Multi-Agent-Systems.pdf (date of access: 25.05.2025).
Purwar A. Automated Planning Tool Makes Work Order Allocation More Efficient. Amazon Science. URL: https://www.amazon.science/blog/automated-planning-tool-makes-work-order-allocation-more-efficient (date of access: 25.05.2025).
Petzoldt C., Niermann D., Maack E., Sontopski M., Vur B., Freitag M. Digital Twin-Based Task Allocation for Multi-Agent Systems in Production Logistics. MDPI. URL: https://www.mdpi.com/2076-3417/12/24/12645 (date of access: 25.05.2025).
Amazon's Robot Army Is Watching: New Tools Boost Fulfillment Vigilance. Tomorrow Desk. URL: https://tomorrowdesk.com/vigilance/amazon-robot-arm (date of access: 25.05.2025).
Elmogy A. M. Multi-Robot Task Allocation: A Review of the State-of-the-Art. URL: https://www.researchgate.net/publication/277075091_Multirobot_Task_Allocation_A_Review_of_the_State-of-the-Art (date of access: 25.05.2025).
Multi-Agent Coordination across Diverse Applications: A Survey. arXiv. URL: https://arxiv.org/html/2502.14743v1 (date of access: 25.05.2025).
Consensus-Based Fast and Energy-Efficient Multi-Robot Task Allocation. ScienceDirect.URL:https://www.sciencedirect.com/science/article/abs/pii/S0921889022001592 (date of access: 25.05.2025).
Task Allocation in Multi-Robot System Using Resource Sharing. PLOS ONE. URL: https://journals.plos.org/plosone/article?id=10.1371%2Fjournal.pone.0267982 (date of access: 25.05.2025).
Yuan Y., Yang P., Jiang H., Shi T. A Multi-Robot Task Allocation Method Based on the Synergy of the K-Means++ Algorithm and the Particle Swarm Algorithm. MDPI. URL: https://www.mdpi.com/2313-7673/9/11/694 (date of access: 25.05.2025).
Patel R., Rudnick-Cohen E., Azarm S., Otte M., Xu H., Herrmann J. W. A Comparative Study of Task Allocation Algorithms for Multi-Robot Systems. URL: https://user.eng.umd.edu/~jwh2/papers/Patel-ICRA-2020.pdf (date of access: 25.05.2025).
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
1.Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у нашому журналі.
2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована нашим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у нашому журналі.
3. Політика журналу дозволяє і заохочує розміщення рукопису роботи авторами в мережі Інтернет (наприклад, на arXiv.org або на особистих веб-сайтах). Причому рукописи статей можуть бути розміщенні у відкритих архівах як до подання рукопису до редакції, так і під час його редакційного опрацювання. Це сприяє виникненню продуктивної наукової дискусії, позитивно позначається на оперативності ознайомлення наукової спільноти з результатами Ваших досліджень і як наслідок на динаміці цитування вже опублікованої у журналі роботи. Детальніше про це: The Effect of Open Access.
