Разработка и анализ методов восстановления карты проходимости на основе показаний датчиков измерения расстояния (1187419), страница 3
Текст из файла (страница 3)
Например, при < 0 и (, ) = пустая карта будетмаксимизировать Φ(, ).3. () представляет собой следующую сумму () =∑︁ 2 ( )(2.5)где ( ) - число таких соседей клетки , состояние которых не совпадает с состоянием . Функция (2.5), как и (2.4), отвечает за нашиаприорные знания об окружении и имеет простую интерпретацию.
Естественно считать что, если большинство соседей заняты, то и рассматриваемая клетка скорее всего занята. Аналогичную гипотезу можно сформулировать и для незанятых клеток. Поэтому если < 0, то клеткабудет штрафоваться за каждого соседа, состояние которого не совпадаетсо состоянием клетки. Абсолютная величина коэффициента позволяетрегулировать его относительный вклад в (2.1).Таким образом задача картирования сводится к задаче максимизации (2.1)по всем возможным картам проходимости18(︃)︃* () = argmax (, ) + () + ()(2.6)2.2. Алгоритм картирования стохастическим градиентаОптимизационная задача (2.6) решается методом стохастического градиента.
Каждый оптимизационный шаг состоит из следующих действий:1. Случайным образом выбирается клетка и значение проходимости ( )инвертируется* ( ) = 1 − ( )2. Для нового состояния клетки пересчитываются (, ), ()∑︀и (). В (, ) = log ( |) меняются только части суммы, для которых клетка лежит в области видимости сонара. Поэтомуможно достаточно быстро пересчитать новое значение * (, ).
Также ясно, что при инвертировании одной клетки возможно быстро получить новые значения * () и * (), так как () и () являются суммами функций от каждой клетки карты , и ихзначения зависят только состояния клетки и её соседей.3. Если Φ* (, ) = * (, ) + * () + * () > Φ(, ), тосохраняем новое значение * ( ) и Φ* (, ), * (, ), * (),* (); иначе возвращаемся в предыдущее состояние.
Для того чтобыизбежать застревания в локальных минимумах, добавляется рандомизация сохранения нового состояния: инвертирование сохраняется с вероятностью _ , вне зависимости от величины Φ* (, ).В этой работе имплементирована оффлайн версия алгоритма 2, котораяна вход получает сразу все наблюдения сонаров, и затем оптимизирует картупроходимости.19Алгоритм 2: Оффлайн версия картирования методом стохастического градиентаData: 0 - начальное состояние карты, - множество наблюденийсонаров, - число оптимизационных шаговResult: - карта проходимости/* инициализация*/begin = 0 ; (, ), (), ();Φ(, ) = (, ) + () + ();endfor = 0; < ; = + 1 doслучайным образом выбирается клетка карты ;* ( ) = 1 − ( );пересчитать * (, ), * (), * ();Φ*( , ) = * (, ) + * () + * () > Φ(, );if Φ*( , ) > Φ( , ) или (0, 1) < then = * (, ) = * (, ); () = * (); () = * ();Φ(, ) = Φ* (, );endend2.3.
Работа в режиме реального времениНа основе предложенного метода можно реализовать алгоритм, которыйработает в режиме реального времени. В этом режиме оптимизация ведетсяодновременно с получением новых данных. Ясно, что при долгом и непрерыв20ном сборе данных, в определенный момент времени количество наблюденийпревысит тот их объем, который возможно обрабатывать на лету.
Поэтому дляобработки необходимо выбирать лишь некоторую часть данных, чтобы не выйти за рамки отведенного оптимизации времени. Здесь предлагаются следующиеспособы составления выборки наблюдений для оптимизации:∙ Использовать скользящее окно и рассматривать последние наблюдений - таким образом мы гарантируем, что каждый пересчет (, )не превысит = Δ , где Δ - время пересчета одного слагаемогоиз (, ) соответствующего наблюдения.∙ Для каждой клетки хранить номера наблюдений сонаров, которыесодержат её в поле зрения. Ограничение числа наблюдений привязанныхк каждой ячейке значением гарантирует, что для каждой ячейкипересчет (, ) будет занимать времени не более = Δ .Предлагается выбирать последних наблюдений.∙ В каждом узле трехмерной сетки ( , , ) хранится список наблюдений = ( , , , ), которые принадлежат соответствующей части пространства: ∈ [ −Δ , +Δ ], ∈ [ −Δ , +Δ ] и ∈ [ −Δ , +Δ ].
Тогда в каждом узле можно хранить последних измерений илинекоторым образом фильтрованные наблюдения. При этом масштаб этойсетки, может не совпадать с масштабом карты проходимости.21Глава 3Картирование методом градиентного спускаВ этой главе предлагается другой подход к построению карты проходимости. В отличии от рассмотренных ранее методов на основе прямой модели, вкоторых картирование сводится к задаче оптимизации на конечномерных пространствах большой размерности, предлагаемый в этой главе метод решает задачу восстановления карты с помощью поиска минимума некоторого непрерывного штрафа. Чтобы прийти к этому методу нужно переформулировать задачувосстановления карты проходимости.Представим клетки карты проходимости как переменные , которыепринимают значения от 0 до 1 и характеризуют степень занятости ячеек. Каки раньше будем искать такую карту * , которая наилучшим образом объясняет наблюдения сонаров, и для этого введем функцию, которая показывает,насколько хорошо карта объясняет наблюдения .
В этом методе используется прямая модель сонара, отличная от модели 1.2.2. Далее следует описаниеиспользуемой модели.3.1. Модель сонара3.1.1. Функция правдоподобияИзмерение сонара несёт в себе не только информацию о том, что нарасстоянии скорее всего находится препятствие, но и о том, что на расстояниименьше препятствия маловероятны. Поэтому каждое наблюдения сонара можно интерпретировать следующим образом:∙ В некоторой области, расположенной на расстоянии примерно от сонара,располагается препятствие такого размера, что датчик смог его детектировать на таком расстоянии.22∙ В области видимости сонара на расстоянии меньше , препятствия определенных размеров, которые могли стать причиной измерения сонара сменьшим , отсутствуют.Через Ω (, ) будем обозначать множество переменных , которые соответствуют клеткам карты, находящимся внутри области видимости сонара,где не должно быть препятствий в соответствии с наблюдением = (, , , ).Множество переменных , которые соответствуют ячейкам карты, располагающимся в луче сонара там, где должно находиться препятствие, будем обозначатькак Ω (, ).В работе предполагается, что показание сонара определяется только суммарной (как будет показано ниже, взвешенной) площадью препятствий внутриобластей Ω и Ω , и не зависит от взаимного расположения занятых клетокв них, несмотря на то, что на самом деле на измерение сонара сильно влияетнаправление нормали поверхности препятствия.
Действительно, легче всего обнаружить то препятствие, поверхность которого перпендикулярна лучу сонара.Кроме того, сонары легче детектируют одно препятствие, расположенное в егополе зрения, чем несколько препятствий аналогичной формы и суммарной площади, которые рассредоточены в области луча. Данные эффекты в работе нерассматриваются.Далее рассмотрим функцию правдоподобия (, ), которая показывает, насколько хорошо карта объясняет показание сонара . (, ) состоитиз двух слагаемых: (, ) отвечает за отсутствие препятствий в областиΩ (, ), за наличие препятствий в области Ω (, ) – (, ). Далее длянаблюдения сонара и карты будем коротко записывать = + (3.1)Пусть = {1 , ..., } - множество всех наблюдений сонаров.
Тогда Ψ(, )- функция правдоподобия всех наблюдений сонаров. Будем считать, что Ψ(, )23является аддитивной относительно каждого наблюдения , все показания датчиков имеют одинаковую достоверность и входят в Ψ(, ) с равным весом.Поэтому значение функции правдоподобия должно принимать одинаковыемаксимальные и минимальные значения для различных сонаров. Постулируетпринимают значения от 0 дося, что для всех ∈ {1, ..., } значения и 1. Таким образомΨ(, ) =∑︁ + (3.2): ∈Теперь рассмотрим, каким образом должно формироваться значение для области Ω .
Ясно, что занятые клетки внутри Ω противоречат наблюдению сонара. Однако, если чувствительность датчика низкая, то одна занятаяячейка не является достаточным основанием полагать, что показание сенсора необъяснено картой . Таким образом внутри Ω может быть некоторое количество занятых клеток, которое зависит от чувствительности сонара. При этом невсе ячейки в Ω являются равнозначными: состояние тех клеток, которые лежат ближе к сонару, должно вносить больший вклад в , так как отражениеимпульса от них более вероятно, чем от более удаленных занятых клеток.
Поэтому, чтобы получить оценку эффективного количества препятствий в Ω ,рассмотрим взвешенную сумму=∑︁ (3.3) ∈Ω где - вес, определяющий, насколько важной является ячейка . Есливзвешенная сумма меньше некоторого порогового значения , то наблюдение считается хорошо объясненным. Если же сумма превышает , тоначисляется штраф, увеличивающийся с возрастанием .
Будем считать, что является кусочно линейной функцией вида24 =⎧⎪⎨ , < (3.4)⎪⎩ + ( − ), ≥ Учитывая ограничение (1) = 1, получаем 1 − =1 − (3.5)Параметр > 0 должен быть достаточно малым, но отличным от нуля.Это нужно для того, чтобы был ненулевой штраф при значениях ≤ ,когда измерение сонара хорошо объяснено в области Ω , и, таким образом,метод градиентного спуска мог бы сойтись.(1) = 0 иАналогичным образом, будем считать, что, при ограничении является кусочно линейной функцией видамалом > 0, =⎧⎪⎨1 − , < (3.6)⎪⎩1 − − ( − ), ≥ 1 − + =(3.7)3.1.2. Весовые коэффициентыДалее через ℎℎ будем обозначать и . Для расчета пороговℎℎ и весов необходимо знать информацию о чувствительности сонара.Обычно она предоставляется производителем и получается следующим образом: используется набор столбов различного диаметра, каждый из столбов помещается в разные точки диаграммы направленности датчика.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
