Details

В данной работе объектом исследования являются распределённые си­стемы управления роботами в условиях ограниченной коммуникации. Предмет исследования — алгоритмы назначения целей, учитывающие топологические ограничения сети связи. Основная цель работы — повышение эффективности распределения целей в системах роботов с ограниченными областями связи путём разработки и применения модифицированного аукционного алгоритма.Решаемые задачи в ходе исследования: – Изучение существующих алгоритмов назначения, включая аукционный и венгерский методы. – Анализ влияния ограниченной коммуникации на эффективность алго­ритмов. – Разработка модификации аукционного алгоритма, учитывающей топо­логические ограничения. – Реализация предложенного алгоритма и венгерского алгоритма в про­граммной среде. – Проведение сравнительного тестирования алгоритмов на модельных задачах с различными характеристиками коммуникационных ограниче­ний. По результатам экспериментов сделаны выводы о высокой эффектив­ности модифицированного аукционного алгоритма в условиях ограниченной коммуникации, особенно при высоких скоростях обмена данными. Установле­но, что аукционный алгоритм, в отличие от венгерского, позволяет учитывать погрешности в измерениях матрицы выгод путём выбора параметра точности ε соразмерно этим погрешностям, что обеспечивает высокую точность при меньших вычислительных затратах. Венгерский алгоритм, не учитывающий погрешности и лишённый параметра ε, стремится к точному решению, которое в условиях реальных погрешностей и ограниченного радиуса связи недостижимо, что делает аукционный алгоритм более эффективным. Выявлена зависимость числа итераций и точности от параметров радиуса связи, размера задачи и параметра ε. Алгоритм применим в военных робототехнических системах, поис­ково-спасательных операциях и промышленной автоматизации.

This work focuses on distributed robot control systems under conditions of restricted communication. The subject of the study is target assignment algorithms that account for topological constraints of the communication network. The primary goal is to enhance the efficiency of target allocation in robotic systems with restricted communication ranges by developing and applying a modified auction algorithm. The tasks addressed in the study include: – Analysis of existing assignment algorithms, including the auction and Hungarian methods. – Evaluation of the impact of restricted communication on algorithm performance. – Development of a modified auction algorithm that accounts for topological constraints. – Implementation of the proposed algorithm and the Hungarian algorithm in a software environment. – Comparative testing of the algorithms on model problems with varying communication constraints. Experimental results confirm the high efficiency of the modified auction algorithm under restricted communication conditions, particularly with high data exchange rates. It was established that, unlike the Hungarian algorithm, the auction algorithm accounts for measurement errors in the utility matrix by selecting the accuracy parameter ε proportional to these errors, achieving high accuracy with lower computational costs. The Hungarian algorithm, which does not account for errors and lacks the ε parameter, aims for an exact solution that is unattainable under real-world measurement errors and restricted communication range, making the auction algorithm more effective. The dependence of iteration count and accuracy on communication range, problem size, and the ε parameter was identified. The algorithm is applicable to military robotic systems, search and rescue operations, and industrial automation.

• Тема выпускной квалификационной работы
  • Введение
  • 1. Анализ существующих алгоритмов назначения
  • 2. Разработка модифицированного аукционного алгоритма
  • 3. Реализация и программное обеспечение
  • 4. Экспериментальное исследование и анализ результатов
  • 5. Перспективы дальнейшего развития и исследования
  • Заключение
  • Список использованных источников