Децентралізоване вирішення конфліктів у багатоагентному плануванні шляхів (MAPF) за допомогою динамічних локальних аукціонів

Скорочена інформація про документ
dc.contributor.advisorКуєвда, Юлія Валеріївна
dc.contributor.authorХроколов, Ярослав Юрійович
dc.date.accessioned2026-09-10T12:46:09Z
dc.date.available2026-09-10T12:46:09Z
dc.date.issued2026
dc.description.abstractДипломна робота: 103 с., 10 рис., 7 табл., 2 додатки, 15 джерел. Об'єкт дослідження – процес безконфліктного управління рухом у багатоагентних робототехнічних системах складської логістики. Предмет дослідження – децентралізовані ринкові алгоритми вирішення просторово-часових конфліктів у задачі MAPF. Мета роботи – підвищення обчислювальної масштабованості та відмовостійкості систем MAPF шляхом розробки децентралізованого методу динамічних локальних аукціонів (DLA). Методи дослідження – системний аналіз, теорія графів, просторовочасовий пошук A*, теорія ігор (аукціон Вікрі), симуляційне моделювання мовою Python. Актуальність – обчислювальний колапс централізованих підходів при масштабуванні системи та потреба в конфіденційності маршрутів некооперативних агентів. Результати – математично формалізовано середовище й економічну поведінку раціональних агентів. Реалізовано точкові торги за правилом другої ціни та механізм ухилення від дедлоків. Здійснено порівняльний аналіз ключових метрик ефективності, який експериментально підтвердив високу обчислювальну масштабованість, відмовостійкість та точність запропонованого підходу. Подальший розвиток – інтеграція динамічних обмежень фізичних шасі роботів та розробка стратегій безперервного онлайн-надходження завдань.
dc.description.abstractotherDiploma thesis: 103 p.,10 fig., 7 tables, 2 appendices, 15 sources. Object of Research –the process of collision-free motion control in warehouse multi-agent robotic systems. Subject of Research – decentralized market-based strategies for space-time conflict resolution in the MAPF problem. Objective – to improve computational scalability and fault tolerance in MAPF systems by developing a decentralized dynamic local auctions (DLA) method. Research Methods – systems analysis, graph theory, space-time A* search, game theory (Vickrey auction), Python-based simulation modeling. Relevance – computational collapse of centralized approaches during scaling and the need for route privacy of non-cooperative agents. Results – a mathematical model of the environment and economic behavior of rational agents has been formalized. Local biddings based on the second-price rule and a deadlock evasion mechanism were implemented. A comparative analysis of key performance metrics was performed, experimentally confirming the high computational scalability, fault tolerance, and accuracy of the proposed approach. Future Development – integration of physical robot chassis dynamic constraints and development of strategies for continuous online task arrival.
dc.format.extent103 с.
dc.identifier.citationХроколов, Я. Ю. Децентралізоване вирішення конфліктів у багатоагентному плануванні шляхів (MAPF) за допомогою динамічних локальних аукціонів : дипломна робота … бакалавра : 124 Системний аналіз / Хроколов Ярослав Юрійович. – Київ, 2026. – 103 с.
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/82970
dc.language.isouk
dc.publisherКПІ ім. Ігоря Сікорського
dc.publisher.placeКиїв
dc.subjectбагатоагентне планування шляхів (mapf)
dc.subjectдецентралізоване вирішення конфліктів
dc.subjectдинамічні локальні аукціони
dc.subjectаукціон вікрі
dc.subjectсистемний аналіз
dc.subjectmulti-agent path finding (mapf)
dc.subjectdecentralized conflict resolution
dc.subjectdynamic local auctions
dc.subjectvickrey auction
dc.subjectsystems analysis
dc.titleДецентралізоване вирішення конфліктів у багатоагентному плануванні шляхів (MAPF) за допомогою динамічних локальних аукціонів
dc.typeBachelor Thesis

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Khrokolov_bakalavr.pdf
Розмір:
2.78 MB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
8.98 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Бакалаврські роботи (ММСА)
Бакалаврські роботи