Разработка и анализ методов восстановления карты проходимости на основе показаний датчиков измерения расстояния (1187419), страница 2
Текст из файла (страница 2)
Проблема в том, что карта проходимости принадлежит пространству большой размерности, но из определения обратной модели можно получить следующее:(|1, ) =∏︁( |1, )(1.1)Таким образом задача сводится к оценке вероятностей занятости каждойклетки карты при известных наблюдениях.1.1.2. Описание традиционного метода картирования, основанногона обратной модели сенсора.Разложим ( | ) по правилу Байеса( |1, ) =( | , 1,−1 )( |1,−1 )( |1,−1 )(1.2)В предположении статичности окружения, ясно, что наблюдение не зависит от предыдущих наблюдений, при условии известной карты проходимости( |, 1,−1 ) = ( |)(1.3)9Выражение (1.3) действительно верное при предположении о статичностиокружения. Однако это утверждение усиливается, так как по определению обратной модели клетки считаются независимыми случайными величинами: наблюдение не зависит от предыдущих измерений при заданном состоянии клетки , в независимости от состояний соседних клеток.( | , 1,−1 ) = ( | )(1.4)Подставив (1.4) в (1.2), снова воспользуемся правилом Байеса( |1, ) =( | )( |1,−1 ) ( | )( )( |1,−1 )=( |1,−1 )( )( |1,−1 )(1.5)Формула (1.5) выписана для оценки вероятности занятости клетки .
Аналогичное выражение можно получить для оценки вероятности того, что ячейка является свободной( |1, ) =( | )( )( |1,−1 )( )( |1,−1 )(1.6)Поделив (1.5) на (1.6) получим( |1, ) ( | ) ( ) ( |1,−1 )=( |1, ) ( | ) ( ) ( |1,−1 )(1.7)Заметим, что ( ) = 1 − ( ).
Поэтому, переписав (1.7) в виде log-odds( )( ) = log 1−(, окончательно получаем выражение итеративной оценки для)( |1, )( |1, ) = ( | ) + ( |1,−1 ) − ( )(1.8)10Алгоритм 1: Картирование с обратной моделью сенсора/* Инициализация*/for all in do( ) = log 1−()end/* Рекурсивное обновление log-odds*/for all dofor all in do( | )( ) += log 1−(− log 1−( | ))endend/* Получение вероятностей из log-odds*/for all in do( |1, ) = 1 − −endВ (1.7) вероятность ( ) выражает наши априорные представления о карте, обычно её полагают равной 0.5, считая что какой-либо информации о занятости каждой клетки карты нам неизвестно ничего определенного.1.1.3. Недостатки традиционного метода картирования с обратноймоделью.Выполнение предположения (1.4) является в некоторых случаях существенным, и его невыполнение влечет к артефактам на карте проходимости.
Рассмотрим в качестве примера ситуацию, когда для картирования используется идеальные сонары (без ошибки измерений). Сонар имеет достаточно широкий луч(область видимости, диаграмма направленности), который часто представляется в виде конуса, пересекающий множество клеток (рисунок 1.1). Измерениесонара говорит о следующем - на конце конуса должно находится препятствие,11которое должно хорошо объяснять полученное измерение, при этом вероятностьсуществования других препятствий внутри этого конуса невелико.На рисунке 1.1 изображены два сонара (A, B ), области видимости которых пересекаются в нескольких клетках.
Для сонара А эти клетки принадлежат области препятствий, а для B - свободной от препятствий территории. Врезультате работы алгоритма мы получим, противоречивую информацию о занятости этих клеток: одно измерение говорит о том, что эти ячейки должныбыть заняты, другое - что свободны. В этом примере легко понять, что для того чтобы хорошо объяснить наблюдения сонаров A и B, клетки на пересеченииконусов видимости должны быть свободны, так как есть другие клетки хорошообъясняющие эти измерения (Рис 1.1 (в)). Однако эта важная дополнительнаяинформация не используется методом, в силу предположения о независимостиклеток.(а)(б)(в)Рис. 1.1.
Сонары A и B, области видимости которых пересекаются в нескольких клетках(a). Карта проходимости для этого случая, которая будет построена алгоритмом с обратноймоделью сонара (б). Верная карта проходимости для этого случая (в).На самом деле, эта проблема может коснуться не только традиционного метода, но и любого другого метода, который использует предположение онезависимости клеток тогда, когда оно может не выполняться. Таким образом,можно сделать вывод, что использование подобных методов может приводить к12восстановлению такой карты проходимости, которая в некоторых случаях ошибочно объясняет наблюдения сонаров.
В работе [7] предложен другой подход ккартированию, лишенный описанных выше проблем.1.2. Прямая модель сенсора. Восстановление картыпроходимости на основе прямой модели.1.2.1. Прямая модель сонараВеличина (|) представляет собой вероятностное распределение наблюдений сенсора при некоторой известной карте проходимости . По аналогиис обратной моделью ( |), будем называть (|) прямой моделью сенсора(forward model). Прямая модель показывает на сколько правдоподобно наблюдение объяснено картой проходимости .
Эта модель в отличии от обратнойнапрямую не опирается на предположение о независимости клеток. Идея методов картирования, основанных на прямой модели, сводится к следующему:найти такую карту * которая наилучшим образом согласуется с показаниямисенсоров, максимизируя значение вероятности (1, |).Далее приводится подробное описание прямой модели сонара из [7], таккак в дальнейшем она будет использована одним из методов, предлагаемых вэтой работе.1.2.2. Прямая модель сонара ТрунаПредполагается, что сонар выдаёт измерения из отрезка [ , ].Измерение может быть получено в результате двух сценариев:1. Случайный выброс.
С вероятностью сонар выдаёт случайное значение дальности, распределенное равномерно на [ , ]. Этот случайописывает возможные ошибочные измерения сенсора, которые могут получится в результате переотражений, зашумлений другими сонарами и13т.д.2. Обычный случай. С вероятностью ℎ некоторое ближайшее препятствие, которое находится в области видимости сонара, может отразитьволну, и таким образом сенсор с некоторой ошибкой вернёт расстояниедо него. С вероятностью 1 − ℎ это препятствие может остаться незамеченным датчиком, но волна в конце концов может отразиться от какого-нибудь следующего препятствия.
Если же все препятствия внутриобласти видимости останутся незамеченными сонаром, то в качестве измерения вернётся максимальное .В качестве пояснения рассмотрим пример, изображенный на рисунке 1.1.На этом рисунке видно, что самое близкое препятствие не лежит в конусе видимости сонара, поэтому в обычном случае оно не влияет на (|). С вероятностью сонар выдаст ошибочное измерение. Пусть 1 и 2 расстояниядо первого и второго препятствия в области видимости сонара соответственно.С вероятностью (1 − )ℎ сонар обнаружит первое препятствие и вернёт1 + , где - некоторая ошибка. Однако с вероятностью (1 − )(1 − ℎ )первое препятствие не будет замечено сенсором.
Аналогично с вероятностью(1 − )(1 − ℎ )ℎ будет обнаружено второе препятствие. С вероятностью(1 − )(1 − ℎ )2 сенсор вернет максимально возможное измерение .Рис. 1.1. Пример сонара и возможных положений препятствий.14Теперь опишем эту модель формально. Пусть внутри области видимостисонара находятся препятствий, отсортированных в порядке возрастания дистанции . Через {* , 0 , 1, } будем обозначать множество различных сценариев работы сонара, через * - случайный выброс, 0 - измерение .1. Пусть реализовался случай, когда измерение было порождено событием , ∈ {0, .., }(|, ) = √12 2− 12(− )22(1.9)2.
Если реализовался случай * , то(|, * ) =1(1.10)Таким образом, распределение (|) является смесью распределений∑︁(|) =(|, )( )(1.11) ∈{* ,0, }Из рассуждений выше запишем априорную вероятность ( )⎧⎪⎪⎪ ,=*⎪⎪⎨( ) = (1 − )(1 − ℎ ) ,=0⎪⎪⎪⎪⎪⎩(1 − )(1 − ℎ )−1 ℎ , > 0(1.12)Окончательно получаем(|) =+1∑︁√∈{1,...,}+√12 212 221 (− )2− 221 (− )2− 2(1 − )(1 − ℎ )−1 ℎ(1 − )(1 − ℎ )(1.13)15(а)(б)Рис.
1.2. Результаты картирования двери из работы [7]. (а) - результаты алгоритма на основеобратной модели, (б) - на основе EM-алгоритма с прямой моделью.1.2.3. Картирование с прямой модельюВ работе [7] описанная прямая модель сонара в 1.2.2 используется дляпостроения карты проходимости при помощи EM-алгоритма [10]. В отличииот картирования на основе обратной модели, алгоритмы с прямой модельюсохраняют зависимости между клетками карты, что позволяет лучше восстанавливать карту проходимости.
На рисунке 1.2 видно, что метод из работы [7]восстановил дверной проем, когда как традиционный метод [1] - нет.Как уже отмечалось раньше основной недостаток метода [7] заключаетсяв том, что он не может быть имплементирован для работы в режиме реальноговремени и требуют больших вычислительных ресурсов для поиска оптимальнойкарты. Поэтому в этой работе предлагается иной метод на основе рассмотреннойздесь прямой модели сонара, который допускает real-time реализацию.16Глава 2Картирование методом стохастическогоградиентаИспользуя прямую модель, описанную в 1.2.2, мы предлагаем метод картирования, который использует преимущества прямой модели, и при этом допускает real-time реализацию.
Как и раньше, через будем обозначать картупроходимости. Через = {1 , ..., } - множество наблюдений сонаров . Через ( ) будем обозначать занятость клетки : ( ) = 0 - клетка проходима,( ) = 1 - клетка непроходима.Вначале введем функцию правдоподобия, состоящую из прямой моделисенсора и априорных представлений об окружении. Затем случайным перебором будем максимизировать значение этой функции.2.1. Функция правдоподобия карты проходимостиВведем следующий функцию от при заданных наблюдениях :Φ(, ) = (, ) + () + (),(2.1)Рассмотрим составляющие части функции (2.1)1. - распределение наблюдений сонаров при заданной карте проходимости . (, ) = (1 , ..., |) =∏︁( |)(2.2)Эта часть (2.1) показывает на сколько хорошо карта объясняет показания сонаров .
В работе в качестве модели сонара ( |) используется17прямая модель, описанная в 1.2.2. Вместо (2.2) в окончательной формулеиспользуется логарифм от этой функции: (, ) = log (1 , ..., |) =∑︁log ( |)(2.3)2. () отвечает за априорные знания о проходимости карты () =∑︁ ( )(2.4)В зависимости от значения весового коэффициента можно регулировать наше первоначальное представление о карте, без учета наблюденийсонаров.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
