Диссертация (1090939), страница 11
Текст из файла (страница 11)
Их число также увеличивает итоговуювычислительную сложность. Количество частиц является параметром, спомощью которого достигается нужный баланс между сложностью ибыстродействием алгоритма (рис. 2.24).Рис. 2.24. Зависимость точности работы алгоритма FastSLAM от числачастиц [50]Также необходимо отметить, что алгоритм FastSLAM менее подверженвременным ошибкам при сопоставлении ориентиров вследствие того, чтокаждая из частиц представляет собой независимое состояние системы. Вслучае алгоритма EKF SLAM восстановление работы системы при этомзатруднено, так как последующие оценки стостояния системы будут зависет80от ошибочных данных полученных ранее. В таблице 2.6 приведны основныеразличия подходов с использованием фильтра частиц и расширенногофильтра Калмана.Таблица 2.6 Особенности алгоритмов FastSLAM и EKF SLAMEKF SLAMFastSLAMВектор состоянияВключает в себя как текущееПредставляет собой наборположение камеры, так и наблюдения независимых K состоянийориентиров:ориентиров, хранящихся в каждойчастице.
Состояние каждогоxt (stT ,0T ,1T ,..., KT )Tориентира характеризуетсяПри обновлении карты ориентиров,калмановским фильтром размерностиизменяется размерность вектора2×2. Обновление карты происходитсостояния:путем добавления новых наблюденийdim( xt ) 2 K 3.в вектор каждой из частиц.Апостериорная вероятностьВсе распределения, участвующие вЗадача раскладывается на K+1вычислениях апостериорнойподзадач: оценка положения камеры,вероятностии оценка положений K ориентиров:t 1p ( s t , | z t , n t ) p ( z t | x t ) p ( xt | z )tp ( xt | z ) p( zt | z t )p ( s t | z t , n t ) p ( k | s t , z t , n t )kмоделируются гауссовским шумом.Сопоставление наблюденийНаблюдения ориентировКаждая частица характеризуетсясопоставляются единственнымуникальным соответствиемобразом, что искажает итоговыйнаблюдений nt[m ] .результат в случае ошибкисопоставления.Модель наблюденийМодель наблюдений основывается на В дополнение к модели наблюденийнормальном распределении:алгоритма EKF SLAM, в FastSLAMнепосредственно учитываютсяp( xt | z t ) ~ N (h( xt ), Rt ) .Матрица ковариации R обновляется соответствия наблюдений nt :tp ( z t | s t , t , n t ) .в соответствии со значениямиякобиана.81Основным отличием в реализации алгоритмов FastSLAM 1.0 иFastSLAM 2.0 является то, что во второй версии алгоритма, предположение отекущем состоянии системы St основывается не только на предыдущихоценках St-1, но и на текущих измерениях zt:st[ m] ~ pst | st[m1] , zt , nt .Это распределение может быть представлено в следующем виде:ps t | st[m1] , z t , n t [ m] pzt | n , st , nt p n | st[m1] , zt 1 , nt 1 d n pst | st[m1] ,tttгде для множителей справедливо:pzt | n , st , nt ~ N h n , st , Rt ,ttp n | s , zt 1 , nt 1 ~ N n[ m ] , [nm,]t 1 ,tpst | sгде модели hn , st иt[ m]t 1[m]t 1 ~ N f s , P ,[m]t 1tttf st[m1] в общем виде характеризуют проблемуодновременной локализации и картирования как модели наблюдения идвижения:pzt | n , st , nt h n , st t ,pst | st[ m]t 1t f s .[ m]t 1tКроме этого, в алгоритме FastSLAM 2.0 применяется иной механизмвычисления весовых значений частиц, учитывающий нормирующий член [ m ] .
Аналогично тому, как это реализовано в версии 1.0 алгоритма,итоговое соответствие nt выбирается с учетом максимальной вероятностиизмерения zt для частицы m. Однако эта вероятность должна бытьмодифицирована с учетом перераспределения частиц. Линеаризация моделинаблюдения h n , st определяет шум измерения zt со математическимtожиданием h n[ m] , st[ m] и ковариацией Rt.t82В результате анализа знаковых публикаций в области исследованияSLAM алгоритмов на основе фильтра частиц, в частности [88], было приняторешение использовать в работе версию алгоритма FastSLAM 2.0.
Данныйметод более устойчив к ошибкам локализации ориентиров, что особенноактуально именно в случае использования возможностей прикладногообъемного телевидения, как менее точной системы в сравнении с лазернымидальномерами.2.4.2. Сравнение подходов FastSLAM и EKF SLAMДля тестирования FastSLAM и EKF SLAM версий алгоритмоводновременной локализации и картирования было решено взять за основупопулярныепрограммныепрограммированияMatlab.реализацииДанныеметодовреализации[24]напредставляютязыкесобойоригинальные версии алгоритмов EKF SLAM, FastSLAM 1.0 и FastSLAM 2.0.Для симуляции процесса движения камеры в пространстве используютсяпредопределенные наборы ориентиров и траектория движения, заданнаяпоследовательностьюкоординат.Ошибканаблюденияориентировмоделируется аддитивным белым гаусовским шумом.Как и в большинстве подобных алгоритмов, подразумевается, чтовизуальные либо механические одометрические данные поступают на входалгоритма в форме матрицы трансформации, включающей в себя матрицуповорота R и вектор смещения T.
Как правило, в случаях, когда данныепоступают в ином виде, они аналитическими методами приводятся к форме Rи T. Так, например, при использовании алгоритма SLAM для локализацииколесной роботизированной платформы, входные одометрические данныемогут представлять собой число оборотов колес. В этом случае необходимодополнительно учитавать специфическую ошибку измерения, связанную сформойодометрическихданных.Математическаямобильного робота приводится в первой главе работы.83модельдвиженияОбъективнаяоценкахарактеристикалгоритмовявляетсянетривиальной задачей, сложность которой заключается в том, чторезультаты работы программно реализованных методов кардинальнымобразом зависят от низкоуровневых деталей реализации, скрытых подматематическимиабстракциями.Различныеспособыоптимизацииразработанных методов, такие, как, например, параллельное выполнениепроцессов программы или обработка изображений с помощью графическогоадаптера, существенно влияют на производительность алгоритма.
В рамкахданного этапа работы тестирование алгоритмов одновременной локализациии картирования FastSLAM и EKF SLAM, производилось в однопоточномрежиме на персональном компьютере под управлением процессора Intel Corei5-4210 с частотой 1.7 ГГц.Рис. 2.25. Тестовое пространство для моделирования процесса SLAM, накарте присутствуют 17 ориентировДля оценки производительности алгоритмов была выбрана следующаясхема испытаний. Для оценки зависимости времени работы алгоритмов отколичества ориентиров в окружающем пространстве, использовались 8 карт сразличным суммарным количеством ориентиров на протяжении пути84камеры, от 17 до 232 точек.
Внешний вид карты пространства симулятораприведен на рисунке 2.3.4. Длительность выполнения алгоритма усредняласьпо 10 измерениям для каждого случая. Погрешность измерений при этом взначительной степени зависит от контекста выполнения программы иконкурирующих процессов операционной системы.На рисунке 2.26 приведены графики зависимости длительностиобработки алгоритмами EKF SLAM и FastSLAM данных о наблюденияхориентиров, полученных в процессе моделирования движения камеры впространстве.Рис.
2.26. Зависимость времени работы алгоритмов EKF SLAM и FastSLAMот количества отслеживаемых ориентировПолученныеданныеподтверждаюттеоретическиевыкладкиовычислительной сложности алгоритмов. Так, необходимость постоянногообновления ковариационной матрицы в алгоритме EKF SLAM приводит кквадратичной сложности алгоритма относительно количества наблюдений.МетодFastSLAMприэтомхарактеризуетсялинейнымхарактеромзависимости длительности вычислений от количества ориентиров, и с85определенного момента показывает лучшие относительно EKF SLAMрезультаты.
Оптимизация структуры данных алгоритма для достижениялогарифмической сложности рассматривается далее в данной главе.Рис. 2.27. Зависимость времени работы алгоритма FastSLAM от количествачастицРис. 2.28. Зависимость среднеквадратической ошибки определенияположения камеры от количества частиц86Определяющим параметром алгоримов, использующих фильтр частицпри наблюдении какой-либо величины, является количество различныхвекторовсостоянийсистемы.Этотпараметрвлияеткакнапроизводительность, так и на точность работы системы, и его изменение, какправило, является основным способом достижения баланса между временемработы алгоритма и минимальной величиной ошибки.
На рисунках 2.27 –2.28 приведены зависимости времени работы алгоритма FastSLAM ивеличины ошибки локализации камеры от количества частиц.Рис. 2.29. Различные оценки траектории движения камеры, обрабатываемыефильтром частиц в алгоритме FastSLAM при использовании 1 частицы (а) и100 частиц (б)Величинаошибкивычисляласькаксреднеезначениеpp отсреднеквадратического отклонения оценки координат камеры xоцен, yоценppдействительных данных xдейств на протяжении всего пути P движения, yдействкамеры в процессе симуляции.E xpPpоценppp yоцен xдейств yдейств22.NP87Полученные зависисмости позволяют принять решение о минимальнонеобходимом количетве частиц для достижения нужной точности припостроении траектории движения камеры и карты ориентиров окружающегопространства.