Масштабируемые алгоритмы одновременного построения карты и локализации стаи мобильных роботов
Введение …………………………………………………………………………………………………………………. 5
1 Постановка задачи slam и обзор ее решений ………………………………………………………… 10
1.1 Классификация алгоритмов решения задачи SLAM ……………………………………….. 11
1.2 SLAM, основанные на выделении особых точек ……………………………………………. 15
1.2.1 Общий подход к решению задачи SLAM на основе выделения особых точек. 15
1.2.2 EKF SLAM …………………………………………………………………………………………………. 16
1.2.3 FastSLAM …………………………………………………………………………………………………… 18
1.3 Байесовская теория ……………………………………………………………………………………….. 19
1.4 Фильтр частиц. Gmapping……………………………………………………………………………… 23
1.5 Графовый SLAM. Cartographer ……………………………………………………………………… 25
1.6 Выводы по первой главе ……………………………………………………………………………….. 28
2 Многоагентные алгоритмы решения задачи slam, их структура и архитеткура ……. 29
2.1 Классические методы решения задачи многоагентного SLAM ………………………. 30
2.2 Роли в многоагентном SLAM алгоритме ……………………………………………………….. 33
2.3 Способы вычисления взаимного расположения агентов и слияние карт …………. 34
2.4 Модель многоагентных алгоритмов решения задачи SLAM ………………………….. 37
2.5 Графовый многоагентный SLAM ………………………………………………………………….. 38
2.6 Неграфовый многоагентный SLAM ………………………………………………………………. 40
2.7 Выводы по второй главе ……………………………………………………………………………….. 41
3 Многоагентный масштабируемый алгоритм решения задачи slam для стаи
мобильных роботов ……………………………………………………………………………………………….. 43
3.1 Физические и технические ограничения применения алгоритма …………………….. 43
3.1.1 Ограничения, накладываемые на окружающую среду и агентов ………………….. 43
3.1.2 Используемые технологии …………………………………………………………………………. 45
3.2 Компоненты многоагентного алгоритма SLAM ……………………………………………… 45
3.2.1 Описание особенностей ядра многоагентного алгоритма …………………………….. 47
3.2.2 Применение теории Демпстера-Шафера для увеличения точности работы
алгоритма …………………………………………………………………………………………………………… 50
3.2.3 Обоснование увеличения точности работы алгоритма SLAM при
использовании теории Демпстера-Шафера ………………………………………………………….. 53
3.3 Описание многоагентного алгоритма SLAM …………………………………………………. 58
3.3.1 Алгоритм определения взаимного расположения агентов …………………………… 61
3.3.2 Алгоритм объединения карт ………………………………………………………………………. 63
3.4 Выводы по третьей главе ……………………………………………………………………………….. 65
4 Масштабируемый алгоритм фильтрации двумерных лазерных сканов ………………… 66
4.1 Методы уменьшения размерности лазерного скана ………………………………………… 67
4.2 Критерии корреляции …………………………………………………………………………………… 68
4.3 Параметры и константы в алгоритме фильтрации сканов ………………………………. 71
4.4 Детектор коридоров ……………………………………………………………………………………… 73
4.5 Оценка качества и точности работы фильтра лазерных сканов ……………………….. 77
4.5.1 Оценка алгоритмической сложности фильтра ……………………………………………… 78
4.5.2 Количественная оценка точности работы алгоритма SLAM с фильтром ……… 79
4.6 Выводы по четвертой главе ………………………………………………………………………. 80
5 Качественные и количественные показатели могоагентного алгоритма ……………….. 82
5.1 Программная реализация разработанного алгоритма ……………………………………… 82
5.2 Архитектура ПО общего назначения ……………………………………………………………… 84
5.3 Методика тестирования точности разработанного алгоритма …………………………. 87
5.3.1 Выбор характеристики измерения точности алгоритма ……………………………….. 88
5.3.2 Применение набора данных MIT для тестирования многоагентного алгоритма
SLAM …………………………………………………………………………………………………………………. 89
5.4 Оценка точности разработанного многоагентного SLAM алгоритма ………………. 93
5.5 Оценка производительности и потребляемых ресурсов ………………………………….. 97
5.6 Выводы по пятой главе ……………………………………………………………………………….. 101
Заключение ………………………………………………………………………………………………………….. 102
Словарь терминов ………………………………………………………………………………………………… 104
Список использованной литературы …………………………………………………………………….. 105
В первой главе проведен обзор литературы по методам решения задачи одновременной локализации и построения карты. На основе рассмотренных алгоритмов проведена классификация существующих подходов к решению этой задачи.
По размерности наблюдений алгоритмы можно разделить на двумерные и трехмерные.
По типу используемых сенсоров можно выделить лазерные и визуальные алгоритмы.
По способу обработки входных измерений алгоритмы можно разделить на класс алгоритмов, основанных на выделении особых точек, а также класс алгоритмов, использующих «сырые» измерения.
По способу представления карты можно выделить алгоритмы, использующие сетку занятости или графовые алгоритмы.
По характеру изменения окружающей среды алгоритмы разделяются на статические и динамические.
Вне зависимости от принадлежности алгоритма к тому или иному классу, можно выделить высокоуровневую структуру алгоритма решения задачи одновременной локализации и построения карты. Основные компоненты алгоритма представлены на рисунке 1.
Рисунок 1 – Основные компоненты алгоритма решения задачи одновременной локализации и построения карты
Во второй главе формулируются дополнительные задачи, которые возникают при описании многоагентного алгоритма, решающего задачу одновременной локализации и построения карты.
1. Определить роли мобильных агентов.
2. Определить способ вычисления взаимного расположения агентов.
3. Определить способ объединения карт.
4. Определить, что является выходными данными.
Среди многоагентных алгоритмов большой популярностью пользуются
алгоритмы, роли агентов в которых распределяются неравномерно. Обычно в стае агентов присутствует «ведущий агент», который корректирует поведение всех остальных. Ключевой недостаток таких алгоритмов заключается в том, что выход из строя «ведущего» приводит либо к потере работоспособности системы, либо к необходимости выбора нового «ведущего».
Кроме того, многоагентные алгоритмы разделяются по количеству информации о первоначальном положении роботов в системе. На практике часто невозможно определить начальную позицию робота с погрешностью менее нескольких сантиметров, поэтому алгоритмы, вычисляющие взаимное расположение агентов без использования априорных знаний, имеют более широкую область применения.
К требованиям о принадлежности разрабатываемого алгоритма к классу двумерных неграфовых одноагентных алгоритмов, описанным в главе 1, добавляются требования о структуре агентов. Для обеспечения масштабируемости системы необходимо, чтобы все агенты выполняли одинаковые функции: и наблюдение за окружающей средой, и обработку полученных данных, и выбор времени для синхронизации. Помимо этого, вместо использования априорного знания о начальном расположении агентов необходимо вычислять взаимное расположение агентов во время их синхронизации.
Третья глава содержит описание архитектуры разработанного многоагентного алгоритма одновременной локализации и построения карты. Схема компонентов, участвующих в выполнении этого алгоритма показана на рисунке 2.
Рисунок 2 – Схема компонентов, участвующих в выполнении разработанного многоагентного алгоритма
Определение того, что один агент находится в прямой зоне видимости другого, осуществляется посредством некоторого отдельного сенсора. Выбор такого сенсора не лежит в рамках данной работы, однако для примера можно использовать технологию передачи данных bluetooth, которая предполагает дальность действия сигнала не более нескольких метров.
Когда агенты находятся близко друг к другу, они могут начинать процесс обмена построенными картами. Карта – это структура данных, которая содержит ячейки, включающие в себя информацию о собственных координатах в карте, а также вероятность ячейки быть занятой. Когда агенты встречаются, построенные ими карты обязательно будут иметь общую часть, поскольку они оба наблюдают и добавляют в карту одну и ту же часть окружения в момент встречи. Кроме карт агенты передают друг другу текущий лазерный скан. Это нужно для того, чтобы применить алгоритм скан матчера, аналогичный тому, который работает в ядре каждого агента при решении обычной задачи SLAM.
При помощи скан матчера по карте одного агента, а также лазерному скану другого агента определяется взаимное расположение агентов. После этого начинается процесс объединения карт. Второй агент передает первому построенную карту. В простом случае слияние карт состоит из перебора всех ячеек обеих карт и выбора или наибольшего, или наименьшего, или среднего значения занятости соответствующих клеток. В этой главе описано применение теории Демпстера-Шафера в задаче слияния карт. Эта теория применяется при вычислении вероятности каждой ячейки результирующей карты быть занятой.
Следуя теории Демпстера-Шафера, клетка карты имеет четыре состояния, каждое из которых имеет вероятность: состояние быть занятой с вероятностью p, быть свободной с вероятностью q, быть неисследованной с вероятностью u, а также быть в невозможном, конфликтующем состоянии с вероятностью v. Эти четыре вероятности связаны между собой тождеством p + q + u + v = 1. Согласно теории Демпстера-Шафера, неисследованное состояние – это состояние, когда ячейка может быть и занята, и свободна, об этом пока просто нет информации. Конфликтующее состояние – это состояние, при котором ячейка ни занята, ни
свободна. Это математическая абстракция, которая не встречается в реальном мире, однако, введение состояния конфликта позволяет усилить формулы классической Байесовской вероятности.
Во время объединения вероятностей ячеек, составляющих карту, применяется правило объединения вероятностей, описываемое формулой
, (1) где А, B, C – это различные состояния, такие как ячейка является свободной,
занятой или неизвестно (свободной или занятой), m – э то вероятность состояния, K – вычисляется по формуле
(2) Более детально объяснить величину занятости ячейки кары m12(p) можно, если в формулу (1) подставить конкретные вероятности занятости, свободы и
неизвестности ячейки:
, (3)
где m , m , m – это вероятности состояния клетки, p – занятое состояние, q – 1 2 12
свободное состояние, u – неизвестное состояние, то есть состояние, когда клетка одновременно и занята, и свободна.
Применение теории Демпстера-Шафера позволяет сделать карту более устойчивой к погрешности лидара, а также некоторым промахам скан матчера.
В четвертой главе описан горизонтально масштабируемый алгоритм фильтрации лазерных сканов, выполняющий предобработку входных данных для описанного в главе 3 многоагентного масштабируемого алгоритма решения задачи SLAM. Идея фильтра основана на сохранении нескольких последовательных сканов в скользящем окне и сравнении каждого нового скана со сканами из этого окна. Если новый скан сильно коррелирует с каждым сканом из окна, его следует отбросить.
Горизонтальное масштабирование алгоритма достигается за счет распределения вычислений самого трудоемкого этапа фильтрации – предобработки входных данных. Входными данными является лазерный скан, который может содержать от десятков тысяч до десятков миллионов точек, которые возможно обрабатывать параллельно.
В качестве коэффициента корреляции был выбран коэффициент Пирсона, рассчитываемый по формуле:
P cov(X,Y)
X,Y
составляющих два лазерных скана,
cov – ковариация этих случайных величин,
X, Y – дисперсия случайных величин Х и Y.
Схема предложенного алгоритма фильтрации представлена на рисунке 3.
XY , (4) где X, Y – случайные величины, представляющие собой значения расстояний,
Рисунок 3 – Схема алгоритма фильтрации
Результат применения алгоритма фильтрации можно увидеть в таблице 1. В
таблице 2 указано соответствие номера последовательности данных с ее названием в наборе данных.
В качестве набора данных, на котором проводилось тестирование, был выбран набор данных от Массачусетского Технологического университета, поскольку в этом наборе данных присутствуют как данные лидаров, так и истинная траектория движения роботов, благодаря которой можно количественно оценивать результаты работы алгоритмов.
Таблица 1. Среднеквадратичное отклонение траектории (в метрах), построенное алгоритмами SLAM с фильтром и без, от истинной траекторией движения робота.
No
СКО vinySLAM
СКО vinySLAM с фильтром
СКО cartographer
СКО сartographer с фильтром
% отброшено
1 0.062 ± 0.004
2 0.080 ± 0.018
3 0.096 ± 0.007
4 0.094 ± 0.006
5 0.170 ± 0.019
6 0.534 ± 0.085
7 0.090 ± 0.020
8 0.183 ± 0.014
9 0.305 ± 0.174
10 0.361 ± 0.175
0.078 ± 0.004 0.089 ± 0.013 0.111 ± 0.013 0.100 ± 0.002 0.121 ± 0.006 0.543 ± 0.034 0.090 ± 0.003 0.213 ± 0.027 0.289 ± 0.181 0.348 ± 0.152
0.131 ± 0.058 0.153 ± 0.072 0.183 ± 0.015 0.176 ± 0.010 0.248 ± 0.014 0.586 ± 0.174 0.130 ± 0.025 0.188 ± 0.011 0.188 ± 0.004 0.378 ± 0.025
0.119 ± 0.041 59 0.163 ± 0.094 56 0.181 ± 0.014 59 0.179 ± 0.012 63 0.251 ± 0.007 52 0.642 ± 0.191 58 0.119 ± 0.017 52 0.185 ± 0.011 51 0.189 ± 0.005 50 0.399 ± 0.030 47
Таблица 2. Соответствие номера последовательности данных с ее названием в наборе данных MIT.
No Последовательность данных
1 2011-01-20-07-18-45 4 2011-01-25-06-29-26 7 2011-03-18-06-22-35
10 2011-01-28-06-37-23
No Последовательность данных
2 2011-01-21-09-01-36 5 2011-01-27-07-49-54 8 2011-04-06-07-04-17
No Последовательность данных
3 2011-01-24-06-18-27 6 2011-03-11-06-48-23 9 2011-01-19-07-49-38
В таблице 1 показаны значения средних отклонений выходных траекторий от истинных на различных последовательностях данных из набора данных MIT. Рассматривались такие SLAM алгоритмы, как vinySLAM и Google Cartographer. Из таблицы следует, что точность алгоритма при использовании фильтрации в среднем не изменяется, но обработано менее половины лазерных сканов. Таким образом удалось сохранить точность работы алгоритма, потратив значительно меньше времени на обработку входных данных
В пятой главе рассмотрено тестирование характеристик точности и производительности разработанного программного обеспечения на основе многоагентного алгоритма, представленного в главе 3.
Программная реализация основана на фреймворках ROS1 и slam- constructor2. Результаты тестирования показали, что среднеквадратичная ошибка многоагентного алгоритма на дистанции 100 метров, пройденной одним агентом, при условии однократной синхронизации с другим агентом, составила 9,4 см. Исследование производительности показало, что разработанный алгоритм может обрабатывать до 24 лазерных сканов в секунду на платах модели Raspbery Pi 3 Model B+, обладающими ограниченными вычислительными ресурсами. Таким образом, при помощи разработанного ПО можно обрабатывать данные со скоростью, сопоставимой со скоростью предоставления данных от лидара.
Точность алгоритма – это величина среднеквадратичного отклонения точек построенной алгоритмом траектории движения робота от истинной траектории, записанной в предложенном наборе данных. Сравнение точности разработанного алгоритма проведено отдельно с одноагентным алгоритмом, а также с распространенным на данный момент графовым алгоритмом Google Cartorgapher. Результаты сравнения точности представлены на графике на рис. 4.
СКО, м 0,6000
0,5000 0,4000 0,3000 0,2000 0,1000 0,0000
многоагентный алгоритм
cartographer
одноагентный алгоритм
Рисунок 4 – В изуализация СКО многоагентного алгоритма, одноагентного алгоритма и алгоритма cartographer. Номера наборов данных соответствуют таблице 1.
1 Robot Operating System https://www.ros.org
2 Slam-constructor наплатформе github https://github.com/OSLL/slam-constructor
2011-01-20-07-18-45
2011-01-21-09-01-36
2011-01-24-06-18-27
2011-01-25-06-29-26
2011-01-28-06-37-23
2011-01-27-07-49-54
набор данных
Оценка границ применимости на малопроизводительных вычислительных устройствах производилась среди устройств Raspberry Pi. Тестирование проводилась на устаревших маломощных моделях и на новейших, обладающих значительными ресурсами. Приведем характеристики моделей вычислительных устройств.
1. Raspberry Pi 3 Model B (Процессор Broadcom BCM2837, оперативная память LPDDR2 1GB, операционная система Ubuntu Xenial x64).
2. Raspberry Pi 3 Model B+ (Процессор Quad Core 1.2GHz Broadcom BCM2837B0, оперативная память LPDDR2 1GB, операционная система UbuntuXenial x64).
3. Raspberry Pi 4 Model B (Процессор Quad Core 1.5GHz Broadcom BCM2711, оперативная память LPDDR4 2GB, операционная система Ubuntu Xenial x64).
4. Персональный компьютер (Процессор: Intel Core i7-860 4×2.8GHz, оперативная память DDR3 8GB, операционная система Ubuntu Xenial x64).
Количество лазерных сканов, обрабатываемых за секунду времени продемонстрировано на рисунке 5.
80
60
40
20
10 17
Скорость работы алгоритма на разных вычислительных платформах (сканов/с)
49
24
Raspberry Pi 3 Model B Raspberry Pi 3 Model B+ Raspberry Pi 4 Model B ПК
количество сканов в секунду средняя скорость работы лидара
Рисунок 5 – График, демонстрирующий количество обрабатываемых сканов в секунду на различных вычислительных конфигурациях.
Основные результаты.
1) Проведен сравнительный анализ и классификация существующих одноагентных и многоагентных алгоритмов, решающих задачу SLAM. Была построена классификация одноагентных алгоритмов по различным характеристикам.
2) Разработан масштабируемый алгоритм многоагентного решения задачи SLAM. Разработанный алгоритм имеет низкую вычислительную сложность за счет применения метода Монте-Карло в задаче скан-матчинга, а также отказа от графовой структуры алгоритма и применения теории Демпстера-Шафера. Горизонтальная масштабируемость алгоритма достигается отсутствием разделения ролей агентов, выполняющих его.
3) Разработан горизонтально масштабируемый алгоритм фильтрации двумерных лазерных сканов. Применение этого алгоритма позволяет уменьшить среднее время обработки лазерного скана более чем на 40% из-за быстрого определения корреляции скана с предыдущими.
4) Реализовано программное обеспечение, демонстрирующее работу разработанного алгоритма и позволяющее практически оценить качество алгоритма.
5) Определены характеристики точности, а также границы применимости на вычислительных устройствах, обладающих ограниченными ресурсами. Используемый в рамках проделанной работы алгоритм оказался точнее, чем популярное решение от Google – графовый алгоритм cartographer. Среднеквадратичная ошибка многоагентного алгоритма на дистанции 100 метров, пройденной одним агентом, при условии однократной синхронизации с другим агентом, составила 9,4 см. Погрешность определения позиции робота сопоставима с его габаритами, что свидетельствует о высокой точности разработанного алгоритма.
Исходя из полученных результатов можно сделать вывод о том, что достигнута цель работы – разработаны масштабируемые алгоритмы для многоагентного решения задачи SLAM, применимых для низкопроизводительных роботов. В дальнейшем возможно применение теории Демпстера-Шафера к алгоритму фильтрации данных, а также применение графовых алгоритмов определения лидера для увеличений точности объединения карт (в случаях, когда в синхронизации одновременно участвует более двух агентов).
По данным исследовательской компании Gartner [52] в 2019 году
произведено и введено в эксплуатацию более 300 тыс. беспилотных автомобилей.
По прогнозам аналитиков Gartner к 2023 году это число возрастёт до 745 тыс.
единиц. Такая статистика говорит о безоговорочном росте индустрии
автопилотируемых транспортных средств. Выручка одного из гигантов этой
области – компании TeslaMotors – в 2019 году составила $24.58 млрд [53]. Таким
образом, можно уверенно говорить о коммерческом интересе к области
производства беспилотных автомобилей. Следовательно, любое научное или
инженерное изобретение в данной области является интересным и
востребованным.
Одна из задач, которые ставятся перед беспилотным автомобилем –
ориентация на местности. От того, насколько точна карта местности, построенная
в памяти бортового компьютера и согласно которой движется транспортное
средство, зависит, насколько аккуратно и точно будет двигаться автомобиль.
Немаловажную роль играет определение его собственного положения на этой
карте. Определять собственное положение необходимо с точностью до
сантиметров, ни одна спутниковая система локализации на это не способна.
Для обеспечения точной локализации применяются алгоритмы, решающие
задачу SLAM (англ. Simultaneous Localization And Mapping) – одновременного
определения собственного положения и построения карты. Строить карту
согласно работы алгоритма вместо использования заготовленной заранее имеет
смысл в том случае, если известно, что местность может изменяться по
сравнению с тем, что было запечатлено заранее. Например, автомобиль, который
движется по дорогам общего пользования, должен избегать ям на дорогах или
объезжать временно перекрытые участка дороги. Снабдить беспилотный
автомобиль такой информацией заранее является сложной задачей. Поэтому
использовать заготовленную карту, безусловно, полезно, но необходимо также
обновлять эту карту по мере движения.
В качестве другого примера использования алгоритма, решающего задачу
SLAM, приведем задачу построения плана местности на Луне или на Марсе.
Марсоход не может определить собственное положение, используя спутниковую
локализацию, поэтому задача локализации на неизвестной карте стоит наиболее
остро. Такая же задача может возникнуть в более «приземленных» условиях.
Например, автономный робот-спасатель, который должен проникнуть в
разрушающееся здание в поисках нуждающихся в спасении людей, не может
рассчитывать на использование только плана здания – ему нужно получать
информацию о проходимости коридоров и комнат прямо по ходу его движения.
Использование нескольких агентов, работающих сообща и вместе строящих
карту местности, позволяет ускорить построение карты и увеличить точность
локализации каждого робота в отдельности. Ускорение работы достигается за
счет того, что исследуемая область может быть поделена на участки, каждый из
которых исследует только один или несколько агентов, а затем все изученные
участки карты объединяются. Увеличение точности по сравнению с
одноагентным алгоритмом достигается за счет того, что каждый агент не только
дополняет, но и верифицирует карту других агентов. Это позволяет вовремя
исправлять возможные ошибки, которые возникают по ходу вычисления
собственного положения и построения карты.
Целью данной работы является разработка масштабируемых алгоритмов
для многоагентного решения задачи SLAM, применимых для роботов с
ограниченными вычислительными ресурсами. В контексте данной работы
роботом является передвижная платформа, оснащенная вычислительным
устройством, а также лидаром – датчиком, который может измерять расстояние
до препятствий, окружающих робота. Ограничение ресурсов распространяется в
первую очередь на вычислительное устройство, анализ применимости различных
лидаров в данной работе не проводится. Робот с ограниченными
вычислительными ресурсами – это робот, имеющий ограниченные
вычислительную мощность и объём оперативной памяти, небольшие размеры и
питание от портативной батареи. На текущий момент типичными
представителями таких устройств являются продукты Raspberry Pi или Jetson
Nano.
В рамках поставленной цели, мобильный робот, решающий задачу SLAM,
является автономным; единственным источником данных об окружающей среде
является лидар.
Во время выполнения данной работы были поставлены и решены
следующие задачи:
1 Классификация и сравнительный анализ существующих одноагентных и
многоагентных алгоритмов, решающих задачу SLAM.
2 Разработка масштабируемого многоагентного алгоритма SLAM на базе
теории Демпстера-Шафера.
3 Разработка алгоритма фильтрации двумерных лазерных сканов для
освобождения вычислительных ресурсов.
4 Программная реализация масштабируемого многоагентного алгоритма
решения задачи SLAM.
5 Оценка точности карты и траектории, построенных в результате работы
многоагентного алгоритма, а также оценка производительности на
вычислительных устройствах с ограниченными ресурсами.
Объектом исследования является взаимодействие стаи мобильных роботов
при решении задачи одновременного построения карты и локализации.
Предметом исследования является архитектура, точность и
быстродействие многоагентного алгоритма, решающего задачу одновременного
определения положения и построения каты.
Методы исследования. Для решения поставленных задач использовались
методы математической статистики, теории вероятностей, теории графов.
На защиту диссертационной работы выносятся следующие положения:
1 Масштабируемые метод и алгоритм решения многоагентной задачи
SLAM на базе теории Демпстера-Шафера, которые позволяют снизить требования
к вычислительным ресурсам.
2 Масштабируемый корреляционный фильтр двумерных лазерных сканов
для многоагентного алгоритма SLAM, обеспечивающий снижение размерности
входных данных.
3 Архитектура программного обеспечения, реализующего
масштабируемый многоагентный алгоритм, решающий задачу SLAM.
Научная новизна работы заключается в следующем:
1 Предложен многоагентный горизонтально масштабируемый алгоритм
решения задачи SLAM для стаи мобильных роботов на базе теории Демпстера-
Шафера, строящий карту окружения. Применение этой теории позволяет
увеличить точность построенной карты, а также уменьшить влияние шумов по
сравнению с классической Байесовской теорией.
2 Разработан алгоритм фильтрации двумерных лазерных сканов на базе
построения гистограмм и вычисления коэффициента корреляции Пирсона,
позволяющий обрабатывать только часть входных данных без ущерба для
точности.
3 Разработана масштабируемая архитектура компонентов многоагентного
алгоритма SLAM, допускающая выход из строя любого числа агентов, кроме
одного последнего.
Теоретическая значимость работы заключается в применении теории
Демпстера-Шафера к модели карты занятости, которая строится в процессе
работы алгоритма, решающего задачу SLAM. В работе получены закономерности,
связывающие параметры алгоритма и характеристики мобильного робота и
увеличивающие за счет этого точность построения карты и локализации.
Практическая значимость. Разработанные алгоритмы и программное
обеспечение могут быть применены для решения задачи одновременной
локализации и построения карты при одновременной работе нескольких
подвижных роботов. В частности, они могут быть использованы для роботов-
курьеров, сервисных и складских роботов. Поскольку разработанные методы и
алгоритмы нацелены на сокращение требований к вычислительным ресурсам, то
их применение позволит понизить стоимость производства таких роботов и более
эффективно использовать вычислительные ресурсы.
Апробация результатов. Результатом выполнения диссертационной
работы является разработанный многоагентный алгоритм решения задачи SLAM
и реализующее его программное обеспечение. Промежуточные результаты были
представлены на конференциях FRUCT, проходивших с 2016 по 2019 год. Во
время выполнения работы было получено 1 свидетельство о регистрации
программного обеспечения (ПО) для ЭВМ [3], а также 9 публикаций в научных
изданиях, среди которых 2 публикации в изданиях, входящих в перечень ВАК
[1], [2], 7 публикаций в изданиях, индексируемых в базе данных Scopus [18], [19],
[20], [31], [32], [33], [34], среди которых одна работа в журнале Q2 и одна – в
журнале Q1.
Достоверность и обоснованность представленных в диссертационной
работе научных выводов подтверждается согласованностью теоретических и
практических результатов, корректностью доказательств, а также апробацией
основных теоретических положений в научных статьях и выступлениях на
научных конференциях. Достоверность результатов диссертационной работы
также подтверждается проведенными экспериментами с использованием
программной реализации многоагентного масштабируемого алгоритма
одновременной локализации и построения карты стаи роботов.
Внедрение результатов работы. Научные результаты, полученные в
результате работы над диссертацией были внедрены в учебный процесс
СПБГЭТУ «ЛЭТИ» им. В. И. Ульянова (Ленина).
Личный вклад автора. Все результаты, изложенные в диссертации и
сформулированные в положениях, выносимых на защиту, получены автором
лично или при его непосредственном участии.
Структура и объём диссертационной работы. Диссертационная работа
состоит из введения, пяти глав, заключения и списка литературы из 55
наименований. Объём работы 111 машинописных страниц, она содержит 39
рисунков, 3 таблицы.
Итогом проведенных теоретических и экспериментальных исследований
является решение актуальной задачи одновременной локализации и построения
карты стаей мобильных роботов. Поставленные задачи решены, и можно
сделать следующие выводы:
1 После проведения сравнительного анализа и классификации
существующих одноагентных и многоагентных алгоритмов, решающих задачу
SLAM, была построена классификация одноагентных алгоритмов по различным
характеристикам.
2 Разработан масштабируемый алгоритм многоагентного решения задачи
SLAM. Он имеет низкую вычислительную сложность за счет применения метода
Монте-Карло к задаче скан-матчинга, а также отказа от графовой структуры
алгоритма и применения теории Демпстера-Шафера. Горизонтальная
масштабируемость алгоритма достигается за счет отсутствия разделения ролей
выполняющих его агентов.
3 Разработан горизонтально масштабируемый алгоритм фильтрации
двумерных лазерных сканов. Применение этого алгоритма позволяет уменьшить
среднее время обработки лазерного скана более чем на 40% за счет быстрого
определения корреляции скана с предыдущими.
4 Реализовано программное обеспечение, демонстрирующее работу
разработанного алгоритма и позволяющее оценить качество алгоритма на
практике. Получено свидетельство о регистрации программного обеспечения для
ЭВМ.
5 Определены характеристики точности, а также границы применимости
на вычислительных устройствах, обладающих ограниченными ресурсами.
Используемый в рамках проделанной работы алгоритм оказался точнее, чем
популярное решение от Google – графовый алгоритм cartographer.
Среднеквадратичная ошибка многоагентного алгоритма на дистанции 100 метров,
пройденной одним агентом, при условии однократной синхронизации с другим
агентом, составила 9,4 см. Погрешность определения позиции робота сопоставима
с его габаритами, что свидетельствует о высокой точности разработанного
алгоритма.
Исходя из полученных результатов можно сделать вывод о том, что цель
работы достигнута: разработаны масштабируемые алгоритмы для многоагентного
решения задачи SLAM, применимые для низко производительных роботов. В
дальнейшем возможно применение как теории Демпстра-Шафера к алгоритму
фильтрации данных, так и графовых алгоритмов определения лидера для
увеличения точности объединения карт (в случаях, когда в синхронизации
одновременно участвует более двух агентов).
Словарь терминов
SLAM: англ. Simultaneous Localization And Mapping – задача
одновременного определения собственного положения и построения карты.
Лидар: сенсор, вычисляющий расстояния до окружающих объектов при
помощи лазеров и оптических систем.
Мобильный робот: передвижная платформа, оснащенная вычислительным
устройством, а также лидаром – датчиком, который может измерять расстояние
до препятствий, окружающих робота
Одометрия: сведения о перемещении мобильного робота, напрямую
измеренные датчиками перемещения, установленными на роботе
Скан: набор точек, представленный массивом расстояний от лидара до
препятствий на пути лазера, пущенными под углами, отличающимися на
одинаковую величину.
Скан матчинг: процесс сопоставления сканов друг с другом или сканов с
построенной картой для определения точной позиции робота, с которой снимался
скан.
Скан матчер: алгоритм, реализующий скан матчинг.
Слияние карт: алгоритм построения глобальной карты, включающей в себя
все, участвующие в слиянии, карты
Стая: набор автономных роботов, имеющих сопоставимое техническое
оснащение для наблюдения окружающей среды в ограниченной окрестности, не
имеющих иерархии и обменивающихся информацией друг с другом для
совместной разметки окружающей среды.
Фильтр частиц: алгоритм численного решения задачи фильтрации путём
создания нескольких гипотез о фильтруемой величине и оценки
правдоподобности каждой гипотезы при получении новых наблюдений.
Фреймворк: программа, обеспечивающая и облегчающая разработку и
объединение разных компонентов большого программного проекта.
1.Филатов А. Ю. Сравнение современных лазерных алгоритмов SLAM.
Филатов А. Ю., Филатов А.Ю., Гулецкий А.Т, Карташов Д. А., Кринкин К. В. //
Известия ЛЭТИ. – 2018. – № 7. – С. 66-73.
2.Филатов А. Ю. Методы сравнения качества 2D-SLAM-алгоритмов.
Филатов А. Ю., Филатов А. Ю., Кринкин К. В., Чен Б., Молодан Д. // Известия
ЛЭТИ. – 2018. – № 7. – С. 87-95.
3.Филатов А. Ю., Кринкин К. В. Программа для вычисления взаимного
расположения агентов, выполняющих алгоритм решения задачи SLAM. Санкт-
Петербургский Государственный Электротехнический университет (ЛЭТИ). –
ПрЭВМ в Роспатенте, 15.01.2020г. № 2020610524.
4.Akaike H. Likelihood and the Bayes procedure //Selected papers of
Hirotugu Akaike. – Springer, New York, NY, 1998. – С. 309-332.
5.Andersson L. A. A., Nygards J. C-SAM: Multi-robot SLAM using square
root information smoothing //2008 IEEE International Conference on Robotics and
Automation. – IEEE, 2008. – С. 2798-2805.
6.Bailey T. Consistency of the EKF-SLAM algorithm //2006 IEEE/RSJ
International Conference on Intelligent Robots and Systems. – IEEE, 2006. – С. 3562-
3568.
7.Bay H., Tuytelaars T., Van Gool L. Surf: Speeded up robust features
//European conference on computer vision. – Springer, Berlin, Heidelberg, 2006. – С.
404-417.
8.Birk A., Carpin S. Merging occupancy grid maps from multiple robots
//Proceedings of the IEEE. – 2006. – Т. 94. – №. 7. – С. 1384-1397.
9.Carpin S. Fast and accurate map merging for multi-robot systems
//Autonomous Robots. – 2008. – Т. 25. – №. 3. – С. 305-316.
10.Castellanos J. A. Robocentric map joining: Improving the consistency of
EKF-SLAM //Robotics and autonomous systems. – 2007. – Т. 55. – №. 1. – С. 21-29.
11.Castro D. A., Morales C. F., De la Rosa R. F. Multi-robot slam on client-
server architecture //2012 Brazilian Robotics Symposium and Latin American Robotics
Symposium. – IEEE, 2012. – С. 196-201.
12.Cieslewski T., Choudhary S., Scaramuzza D. Data-efficient decentralized
visual SLAM //2018 IEEE International Conference on Robotics and Automation
(ICRA). – IEEE, 2018. – С. 2466-2473.
13.Cole D. M., Newman P. M. Using laser range data for 3D SLAM in
outdoor environments //Proceedings 2006 IEEE International Conference on Robotics
and Automation, 2006. ICRA 2006. – IEEE, 2006. – С. 1556-1563.
14.Dempster A. P.The Dempster–Shafer calculusfor statisticians
//International Journal of approximate reasoning. – 2008. – Т. 48. – №. 2. – С. 365-377.
15.Doucet A. Rao-Blackwellised particle filtering for dynamic Bayesian
networks //arXiv preprint arXiv:1301.3853. – 2013.
16.Duckietown: сайт. – URL: https://www.duckietown.org/ (дата обращения
11.05.2020). – Текст: электронный
17.Fallon M. The mit stata center dataset //The International Journal of
Robotics Research. – 2013. – Т. 32. – №. 14. – С. 1695-1699.
18.Filatov A., Krinkin K. A Simplistic Approach for Lightweight Multi-Agent
SLAM Algorithm. // International Journal of Embedded and Real-Time Communication
Systems (IJERTCS). – 2020. – Т. 11. – №. 3. – С. 67-83.
19.Filatov A., Krinkin K. Multi-Agent SLAM Approaches for Low-Cost
Platforms //2019 24th Conference of Open Innovations Association (FRUCT). – IEEE,
2019. – С. 89-95.
20.Forster C. Collaborative monocular slam with multiple micro aerial
vehicles //2013 IEEE/RSJ International Conference on Intelligent Robots and Systems.
– IEEE, 2013. – С. 3962-3970.
21.Fox D. Monte carlo localization: Efficient position estimation for mobile
robots //AAAI/IAAI. – 1999. – Т. 1999. – №. 343-349. – С. 2-22.
22.Grisettiyz G., Stachniss C., Burgard W. Improving grid-based slam with
rao-blackwellized particle filters by adaptive proposals and selective resampling
//Proceedings of the 2005 IEEE international conference on robotics and automation. –
IEEE, 2005. – С. 2432-2437.
23.Grisetti G. A tutorial on graph-based SLAM //IEEE Intelligent
Transportation Systems Magazine. – 2010. – Т. 2. – №. 4. – С. 31-43.
24.Hess W. Real-time loop closure in 2D LIDAR SLAM //2016 IEEE
International Conference on Robotics and Automation (ICRA). – IEEE, 2016. – С.
1271-1278.
25.Hol J. D., Schon T. B., Gustafsson F. On resampling algorithms for particle
filters //2006 IEEE nonlinear statistical signal processing workshop. – IEEE, 2006. – С.
79-82.
26.Huletski A., Kartashov D. A slam research framework for ros //Proceedings
of the 12th Central and Eastern European Software Engineering Conference in Russia. –
2016. – С. 1-6.
27.Huletski A., Kartashov D., Krinkin K. Vinyslam: an indoor slam method
for low-cost platforms based on the transferable belief model //2017 IEEE/RSJ
International Conference on Intelligent Robots and Systems (IROS). – IEEE, 2017. – С.
6770-6776.
28.Karrer M., Schmuck P., Chli M. CVI-SLAM—collaborative visual-inertial
SLAM //IEEE Robotics and Automation Letters. – 2018. – Т. 3. – №. 4. – С. 2762-
2769.
29.Kerl C., Sturm J., Cremers D. Dense visual SLAM for RGB-D cameras
//2013 IEEE/RSJ International Conference on Intelligent Robots and Systems. – IEEE,
2013. – С. 2100-2106.
30.Kim B. Multiple relative pose graphs for robust cooperative mapping
//2010 IEEE International Conference on Robotics and Automation. – IEEE, 2010. – С.
3185-3192.
31.Krinkin K., Filatov A. Correlation Filter of 2D Laser Scans for Indoor
Environment. // Robotics and Autonomous Systems. – 2021. – Т. 142 – С. 91-99.
32.Krinkin K. Data distribution services performance evaluation framework
//2018 22nd Conference of Open Innovations Association (FRUCT). – IEEE, 2018. – С.
94-100.
33.Krinkin K. Evaluation of modern laser based indoor slam algorithms //2018
22nd Conference of Open Innovations Association (FRUCT). – IEEE, 2018. – С. 101-
106.
34.Krinkin K. The scan matchers research and comparison: Monte-carlo, olson
and hough //2016 19th Conference of Open Innovations Association (FRUCT). – IEEE,
2016. – С. 99-105.
35.Konolige K. Map merging for distributed robot navigation //Proceedings
2003 IEEE/RSJ international conference on intelligent robots and systems (IROS
2003)(Cat. No. 03CH37453). – IEEE, 2003. – Т. 1. – С. 212-217.
36.Lazaro M. T. Multi-robot SLAM using condensed measurements //2013
IEEE/RSJ International Conference on Intelligent Robots and Systems. – IEEE, 2013. –
С. 1069-1076.
37.Leonard J. J., Durrant-Whyte H. F. Simultaneous map building and
localization for an autonomous mobile robot //IROS. – 1991. – Т. 3. – С. 1442-1447.
38.Mason J., Marthi B. An object-based semantic world model for long-term
change detection and semantic querying //2012 IEEE/RSJ International Conference on
Intelligent Robots and Systems. – IEEE, 2012. – С. 3851-3858.
39.Montemerlo M. FastSLAM: A factored solution to the simultaneous
localization and mapping problem //Aaai/iaai. – 2002. – Т. 593598.
40.Montemerlo M. FastSLAM 2.0: An improved particle filtering algorithm
for simultaneous localization and mapping that provably converges //IJCAI. – 2003. –
С. 1151-1156.
41.Moras J., Cherfaoui V., Bonnifait P. Credibilist occupancy grids for vehicle
perception in dynamic environments //2011 IEEE International Conference on Robotics
and Automation. – IEEE, 2011. – С. 84-89.
42.Mur-Artal R., Montiel J. M. M., Tardos J. D. ORB-SLAM: a versatile and
accurate monocular SLAM system //IEEE transactions on robotics. – 2015. – Т. 31. –
№. 5. – С. 1147-1163.
43.Nettleton E. Decentralised SLAM with low-bandwidth communication for
teams of vehicles //Field and Service Robotics. – Springer, Berlin, Heidelberg, 2003. –
С. 179-188.
44.O’Kane J. M. A gentle introduction to ROS. – 2014.
45.Özkucur N. E., Akın H. L. Cooperative multi-robot map merging using
fast-SLAM //Robot Soccer World Cup. – Springer, Berlin, Heidelberg, 2009. – С. 449-
460.
46.Pfingsthorn M., Slamet B., Visser A. A scalable hybrid multi-robot SLAM
method for highly detailed maps //Robot Soccer World Cup. – Springer, Berlin,
Heidelberg, 2007. – С. 457-464.
47.Richardson M., Wallace S. Getting started with raspberry PI. – ” O’Reilly
Media, Inc.”, 2012.
48.Rublee E. ORB: An efficient alternative to SIFT or SURF //2011
International conference on computer vision. – Ieee, 2011. – С. 2564-2571.
49.Schmuck P., Chli M. Multi-uav collaborative monocular slam //2017 IEEE
International Conference on Robotics and Automation (ICRA). – IEEE, 2017. – С.
3863-3870.
50.Scovanner P., Ali S., Shah M. A 3-dimensional sift descriptor and its
application to action recognition //Proceedings of the 15th ACM international
conference on Multimedia. – 2007. – С. 357-360.
51.Smith R., Self M., Cheeseman P. Estimating uncertain spatial relationships
in robotics //Autonomous robot vehicles. – Springer, New York, NY, 1990. – С. 167-
193.
52.Statistics.Gartner.Autonomousvehicles:сайт.–URL:
https://www.gartner.com/en/information-technology/glossary/autonomous-vehicles
(дата обращения 11.05.2020). – Текст: электронный
53.TrustedadvisorforenterprisesGartner:сайт.–
URL:https://www.gartner.com/en(датаобращения11.05.2020).–Текст:
электронный
54.Thrun S., Montemerlo M. The graph SLAM algorithm with applications to
large-scale mapping of urban structures //The International Journal of Robotics
Research. – 2006. – Т. 25. – №. 5-6. – С. 403-429.
55.Turtlebot: сайт. – URL: https://www.turtlebot.com/ (дата обращения
11.05.2020). – Текст: электронный
56.Willowgarage.Обзорроботаpr2-bot:сайт–URL:
http://www.willowgarage.com/pages/pr2/overview (дата обращения 11.05.2020). –
Текст: электронный
57.Yager R. R. On the Dempster-Shafer framework and new combination
rules //Information sciences. – 1987. – Т. 41. – №. 2. – С. 93-137.
58.Zhou X. S., Roumeliotis S. I. Multi-robot SLAM with unknown initial
correspondence: The robot rendezvous case //2006 IEEE/RSJ international conference
on intelligent robots and systems. – IEEE, 2006. – С. 1785-1792.
Читать «Масштабируемые алгоритмы одновременного построения карты и локализации стаи мобильных роботов»
Помогаем с подготовкой сопроводительных документов
Хочешь уникальную работу?
Больше 3 000 экспертов уже готовы начать работу над твоим проектом!
4.5 (9 отзывов)
5 (428 отзывов)
4.2 (25 отзывов)
5 (18 отзывов)
4.9 (20 отзывов)
5 (9 отзывов)
4.6 (71 отзыв)
5 (44 отзыва)
4.6 (522 отзыва)
