Разработка и анализ методов восстановления карты проходимости на основе показаний датчиков измерения расстояния (1187419)
Текст из файла
Федеральное государственное автономное образовательное учреждениевысшего профессионального образования«Московский физико-технический институт(государственный университет)»Факультет управления и прикладной математикиКафедра информатикиДиссертация допущена к защитезав. кафедройПетров И.Б.«»2016 г.ДИССЕРТАЦИЯна соискание ученой степениМАГИСТРАТема: Разработка и анализ методов восстановления картыпроходимости на основе показаний датчиков измерениярасстоянияНаправление:03.04.01 – Прикладные математика и физикаМагистерская программа: 010956 – Математические и информационныетехнологииВыполнил студент гр.
073(а)Шепелев Д.А.Научный руководитель,к. ф.-м. н.Николаев Д.П.Рецензент,к. ф.-м. н.Гладилин С.А.Москва – 20162ОглавлениеВведение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Глава 1.4Обратная и прямая модель сонара. Методы восстановления карты проходимости. . . . . . . . . . . . . . . .
. . . . . . .71.1. Обратная модель сенсора. Восстановление карты проходимостина основе обратной модели. . . . . . . . . . . . . . . . . . . . . . .71.1.1.Обратная модель сенсора. . . . . . . . . . . . . . . . . . .71.1.2.Описание традиционного метода картирования, основанного на обратной модели сенсора. . . . . . . . .
. . . . . .1.1.3.8Недостатки традиционного метода картирования с обратной моделью. . . . . . . . . . . . . . . . . . . . . . . . . .101.2. Прямая модель сенсора. Восстановление карты проходимости наоснове прямой модели. . . . . . . . . . . . . . . . . . . . . . . . .121.2.1.Прямая модель сонара . . . . . . . . . . . . . . .
. . . . .121.2.2.Прямая модель сонара Труна . . . . . . . . . . . . . . . .121.2.3.Картирование с прямой моделью . . . . . . . . . . . . . .15Картирование методом стохастического градиента . . .162.1. Функция правдоподобия карты проходимости . . . . . . . . . . .162.2. Алгоритм картирования стохастическим градиента . . . . . . . .182.3. Работа в режиме реального времени . . .
. . . . . . . . . . . . . .19Глава 2.Глава 3.Картирование методом градиентного спуска . . . . . . .213.1. Модель сонара . . . . . . . . . . . . . . . . . . . . . . . . . . . . .213.1.1.Функция правдоподобия . . . . . . . . . . . . . . . . . . .213.1.2.Весовые коэффициенты . . . . . . . . . . . . . . . . . . .243.2. Алгоритм картирования методом градиентного спуска . . . . . .273Глава 4.Эксперименты и результаты . . . . .
. . . . . . . . . . . .294.1. Генерация синтетических данных с помощью прямой модели . .294.2. Детали реализации . . . . . . . . . . . . . . . . . . . . . . . . . .304.2.1.Расположене сонаров во время экспериментов . . . . . . .304.2.2.Диаграмма направленности сонара . . . . . . . . . . . . .314.2.3.Диаграмма чувствительности сонара . . .
. . . . . . . . .324.2.4.Обратная модель сонара . . . . . . . . . . . . . . . . . . .334.3. Результаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .334.3.1.Картирование методом градиентного спуска . . . . . . . .344.3.2.Картирование методом стохастического градиента . . . .37Заключение . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .40Список литературы. . . . . . . . . . . . . . . . . . . . . . . . . . . . .42Восстановленные карты проходимости . . . . .44Приложение А.4ВведениеКарта проходимости является одним из основных способов описания окружения робота. Чаще всего такая карта задается в виде сетки, состоящей из квадратных ячеек одинакового размера, каждая из которых содержит информациюо проходимости соответствующего участка территории. Например, территорияможет быть занята или свободна, или каждая клетка может содержать вероятность того, что она содержит препятствие. Подобные карты проходимости,построенные на основе данных с сонаров, уже использовались в 1989 году [1, 2].В основном карты проходимости используются для задач навигации.
Дляпостроения этих карт могут использоваться различные датчики: стереопары(с использованием плотных алгоритмов стереосопоставления) [3, 4], лазерныедальномеры (лидары) [5], сонары [1, 6, 7]. Лидары обеспечивают высокое качество измерений, однако являются дорогостоящими. Используя стереопару можно восстановить информацию о проходимости, однако её использование предполагает подходящие условия освещения. Сонары значительно дешевле и доступнее лидаров, и могут использоваться при любом освещении. Их недостатком является низкая точность, зашумленность и большой угловой разброс измерений.Также существуют поверхности, которые рассеивают ультразвук или отражаютсигналы сонаров только под углами, близкими к прямому.
Всё вышеуказанноезначительно затрудняет процесс восстановления карты с использованием сонаров, однако существует множество методов, которые различными способамикомпенсируют эти недостатки.Ставший на сегодняшний день уже традиционным подход картирования наоснове обратной модели сенсора представляет карту проходимости в виде сетки, каждая ячейка которой содержит вероятность занятости соответствующейтерритории. Вероятность занятости каждой клетки оценивается независимо отдругих клеток-соседей, что позволяет строить карту проходимости на лету. Наиболее известным представителем этого семейства алгоритмов является [1], его5простота и возможность работы в режиме реального времени обеспечили емуширокое приложение в робототехнике.
Однако предположение о независимостиячеек, которое используется в определении обратной модели, может приводитьк артефактам на результирующей карте проходимости при некоторых сценариях работы.Альтернативой упомянутому выше методу является нахождение полнойкарты проходимости, которая максимально правдоподобно объясняет сразу всепоказания сонаров. Похожие подходы используется, например, в работах [7–9].Карта проходимости в работе [7] находится путем ЕМ-оптимизации [10], в статье[9] перебираются все возможные локальные конфигурации карты для нахождения максимально правдоподобной. Подобные методы опираются на так называемую прямую модель сонара.
Проблема большинства алгоритмов, основанныхна прямой модели, заключается в невозможности их имплементации для работыв режиме реального времени, а также необходимости больших вычислительныхресурсов для поиска оптимальной конфигурации карты. Требование работы врежиме реального времени к эффективному алгоритму построения карты проходимости является достаточно важным, так как часто такие модули являютсянеотъемлемой частью систем навигации робота.Хотя и карты проходимости в виде сетки до сих пор остаются достаточнонаглядным и популярным способом представления окружения, но из-за строгой дискретизации пространства неизбежна потеря точности и информации оформе поверхностей препятствий.
Подобными недостатками не обладают карты, представляющие препятствия в виде геометрических фигур [11, 12]. Однакоподобные подходы имеет два существенных недостатка: они находят только границы между занятыми и незанятыми областями, но не указывают явно проходимость той или иной клетки. В работе [13] предлагается метод, позволяющийобъединить достоинства обоих подходов, однако он является вычислительносложным и вряд ли возможна real-time реализация.Целью данной работы является разработка алгоритмов картирования с6прямой моделью сонара, которые лишены недостатков методов, основанных наобратных моделях [1, 6], и при этом возможна имплементация разработанныхметодов для работы в режиме реального времени, в отличии от [7–9, 13]. Врезультате этой работы созданы два метода, восстанавливающие карту проходимости с помощью сонаров.
Результаты картирования сравниваются с традиционным методом, описанным в [1].7Глава 1Обратная и прямая модель сонара. Методывосстановления карты проходимости.В этой главе описываются два подхода, используемых в большинстве известных на сегодняшний день алгоритмов для восстановления карты проходимости.
Первый подход базируется на обратной модели сенсора. Основанный наэтой модели алгоритм из [1] будет рассмотрен подробно, так как построенныеим карты проходимости будут использованы для сравнения с предложеннымив следующих главах алгоритмами. Далее дается определение прямой моделии описывается суть методов картирования, основанных на ней. Предложеннаяв [7] прямая модель описывается подробно, так как в дальнейшем она будетиспользована в главе 2.Введем необходимые в дальнейшем обозначения.
Пусть - клетка картыпроходимости . Будем считать, что каждая клетка - бинарная случайная величина, принимающая два значения: {свободная, занятая}. Наблюдением сенсора будем называть измерение и позу датчика в момент времени ,где это измерение было получено.1.1. Обратная модель сенсора. Восстановление картыпроходимости на основе обратной модели.1.1.1. Обратная модель сенсора.Величину ( | ) называют обратной моделью сенсора (inverse sensormodel), она выражает вероятность занятости клетки при известном наблюдении .
По определению считается, что клетки карты являются независимымислучайными величинами. Эта модель называется обратной, так как она обратна8процессу измерения – расстояние до объекта в такой модели определяется показанием сонара, хотя в реальности наблюдение сонара определяется расстояниемдо препятствия.Из такого определения обратной модели следует, что совместное распределение (1 , ..., |) ≡ (|) раскладывается следующим образом (|) =∏︀ ( |). Также заметим, что вероятность занятости клетки оценивается только из наблюдения и не зависит от состояния клеток-соседей.Вместо того, чтобы напрямую решать задачу картирования, методы основанные обратной модели ищут оценивают следующую вероятность (|1 , ..., ) ≡(|1, ).
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
