Способы оценки и снижения вычислительной сложности алгоритмов принятия решений в задачах одновременной локализации и картографирования

Способы оценки и снижения вычислительной сложности алгоритмов принятия решений в задачах одновременной локализации и

картографирования

В. В. Дергачев, О. О. Карташов ФГБОУ ВО «Ростовский государственный университет путей сообщения»

Аннотация: Целью исследования является перспективная, быстро развивающаяся и востребованная область одновременная локализация и картографирование (Simultaneous Localization and Mapping далее SLAM). Одновременная локация и построение карты -является практической проблемой автономной робототехники. Основной принцип заключается в размещении мобильного робота в неизвестной среде, где он сможет постепенно выстроить последовательную карту этой местности при одновременном определении своего местоположения в пределах карты. На сегодняшний день работы в данной области направлены на улучшение эффективности вычислений и решения проблем в объединении данных. В процессе построения мобильным роботом карты окружающей среды и одновременного ее использования, для определения своего местоположение, в режиме онлайн, одновременно оцениваются траектория платформы и расположение всех ориентиров без необходимости априорно заданных знаний о их расположении. Статья посвящена обзору решений проблем алгоритмической сложности, объединения данных и практической реализации рассматриваемых методов. Представлена краткая историческая справка ранних разработок и становления основных задач современных исследований SLAM. Сформулирована структура проблемы в стандартной форме Байеса, дано описание эволюция процесса SLAM. Разработаны два ключевых вычислительных решения проблемы SLAM с использованием расширенного фильтра Кальмана (EKF-SLAM) и фильтра Rао-Blackwellized (FastSLAM).

Ключевые слова: одновременная локализация и картографирование, расширенный фильтр Кальмана, фильтр частиц, мобильный робот, рекурсивный метод, гауссианы, модель наблюдения, модель движения.

Введение. За последнее десятилетие заметны существенные продвижения в решении проблемы одновременной локализации и картографирования (Simultaneous Localization and Mapping далее SLAM), которая была сформулирована и решена как теоретическая проблема в ряде формулировок. На теоретическом и концептуальном уровне, SLAM можно считать решенной проблемой. Существенные проблемы остаются в практической реализации обобщенных решений, в частности, в области

перцептивно проработанных высоко детализированных карт и алгоритмов их построения.

Впервые обсуждение вероятностной задачи SLAM произошло в 1986 на конференции "Robotics and Automation Conference", состоявшейся в Сан-Франциско, штат Калифорния. Ряд исследователей, таких как Питер Чизмен, Джим Кроули и Хью Даррент-Вайт рассматривали возможность применения теории статистического оценивания для составления карт и проблем локализации на них. Результатом обсуждения стало признание факта, что последовательное вероятностное картографирование - это фундаментальная проблема в области робототехники на ряду с другими основными концептуальными и вычислительными проблемами. В течение следующих нескольких лет был проведен ряд ключевых исследований. Работы П. Смита, П. Чизмена [1] и Х. Даррент-Уайта [2] установили статистический базис для описания отношений между ориентирами и манипулированием геометрической неопределенностью. Ключевым аспектом этих работ является иллюстрация высокой степени корреляции между оценками местоположения различных ориентиров на карте, а также их ростом с возрастанием количества последовательных наблюдений.

Параллельно велись работы в визуальной навигации для мобильных роботов, Д. Кроули [3], Р. Шантила и Ламонд [4], в гидроакустической навигации, основанных на использовании алгоритмов фильтра Кальмана. Все работы имели много общего и наглядно показывали, что при движении робота по неизвестной среде и оценивании предполагаемого местоположения относительно ориентиров, последние всегда коррелирует друг с другом из-за распространенной ошибки в предполагаемом нахождении объекта [5]. Следовательно последовательное и полное решение комбинированной задачи локации и картографирования требует решения задачи нахождения связей между местоположениями каждого ориентира и мобильного робота,

меняющихся при фиксации каждого наблюдения при движении. В свою очередь, это потребовало бы осуществить расчет огромного вектора состояний (порядка числа ориентиров, определенных на карте) со сложностью вычисления, как квадрат количества ориентиров. Важно отметить, что в данных работах в расчет не брались свойства сходимости карт и признаки устойчивого поведения. Следовательно, в момент возникновения предполагаемой ошибки, предполагалось отсутствие сходимости карты, что порождало поведение случайного блуждания мобильной платформы с неограниченным ростом ошибок. Учитывая высокую вычислительную сложность этих задач, исследования были сосредоточены на аппроксимации последовательного картографирования в условиях принудительной корреляции ориентиров, с применением полной фильтрации ориентиров, несвязанных с фильтрами мобильной платформы. В результате теоретические работы по решению комбинированной задачи локализации и картографирования на какое-то время были приостановлены.

Значительный сдвиг в этой области произошел с осознанием того, что проблемы картографии и локации на самом деле конвергентны и необходимо сформулировать единую комбинационную задачу. Одним из ключевых моментов является определение корреляции между ориентирами, что ранее большинство исследователей пробовали свести к минимуму. Это было критической частью проблемы, чем больше возрастают эти корреляции, тем лучше результаты решения. Структура задачи и аббревиатура SLAM были впервые представлены в статье «Localisation of automatic» в 1995 году на Международном симпозиуме по исследованиям робототехники [6]. В настоящее время ряд исследовательских групп работают над задачей картографирования и локализации, в частности, в Массачусетском технологическом институте, а также в ACFR в Сиднее. Также SLAM имеет название Concurrent Mapping and Localization (CML) и на текущий момент

существуют разработки для применения в помещении, на улице, подводных условиях. На сегодняшний день работы направлены на улучшение эффективности вычислений и решения проблем в объединении данных.

Состав и структура задачи SLAM. Основная проблема SLAM заключается в одновременной оценки местоположения робота и ориентиров. Истинное нахождение никогда не известно и измеряется относительно друг друга. Замеры проводятся между истинным местоположением робота и местом ориентира.

Рассмотрим робота, движущегося в окружающей среде. Примем во внимание относительные наблюдения ряда неизвестных ориентиров, используя датчик, расположенный на мобильной платформе, как показано на рис.1.

Робот Ориентир

Планируемый *

Истинный "О О

Рис. 1 - Схема передвижения робота и нахождения ориентиров В момент времени к, определены следующие величины: Хк - вектор состояния, описывающий расположение и ориентацию транспортного средства;

ик -вектор управления, применяемый во время к-1, чтобы переместить транспортное средство в состояние Хк в момент времени к; Ш1 - вектор, описывающий расположение 1-го ориентира, где истинное местоположение предполагается в инвариантное время;

zik - наблюдения полученные от транспортного средства по месту нахождения i-го ориентира в момент времени k.

При наличии нескольких наблюдений наземного ориентира в любой момент времени, или, когда конкретный ориентир не имеет веса для принятия решения, то такое наблюдение будет описано как zk.

Кроме того, определены следующие множества: Хо:к=(хо, xj, ..., xk}={x0:k-i, xk}: история местоположения транспортного средства;

U0:k={uj, u2, ..., uk}={U0:k-J, uk}: история входных сигналов управления;

m={mj, m2, ..., mn}: множество всех ориентиров;

Z0:k={zj, z2, ..., zk}={Z0:k-J, zk}: множество всех этапных наблюдений.

Вероятностный SLAM. В вероятностном виде, одновременная локализация и построение карты (SLAM) требует, вычисления вероятностного распределения для всех k случаев.

Данное распределение описывает совместную плотность местоположений ориентиров и состояние транспортного средства (в момент k), зарегистрированные наблюдения и входы контроля «до» и «включая» время k в совокупности с начальным состоянием. В общем случае, предпочтителен рекурсивный метод решения проблемы SLAM. Начиная с оценки распределения Щ-k-i) в момент времени к-1, с

учетом управления uk и наблюдений zk, вычисляется с помощью теоремы Байеса. Для этого требуется, определить модели изменений состояний и наблюдений, описание влияния входного управления.

Модель наблюдения описывает вероятность фиксации наблюдений zk, когда местоположение транспортного средства и новое нахождение ориентиров известны, и в общем виде описывается в форме

rXOv

POfc|arfc,m).

Можно предположить, что при определении местоположения транспортного средства и карты, наблюдения условно независимы от них.

Модель движения для транспортного средства может быть описана в терминах распределения вероятностей переходов между состояниями в виде:

Таким образом, состояние перехода считается Марковским процессом, в котором следующее состояние xk зависит только от непосредственно предыдущего состояния xk-1 и приложенного управления uk, при этом оно независимо, как от наблюдений, так и от карты.

Алгоритм SLAM теперь реализован в стандартной двухступенчатой рекурсивной (последовательной) с прогнозированием (обновление по времени) и коррекцией (измерение-обновлений) форме:

Обновление по времени:

Р{Хь, 1, UQlA"o) = | Р(хк Mfe}

X P fek-it v UQ.lf г

Измерение-обновлений:

Уравнения (4) и (5) предоставляют рекурсивную процедуру вычисления следующего состояния Р(%%) робота хк и карты т за один к

раз, основанный на всех наблюдениях 20:к и всех входящих управлений и0:к, до момента к. Рекурсивная функция модели транспортного средства обозначеная /Ч^ь "ь! и модели наблюдения обозначена

даже при неопределенном абсолютном расположении ориентира mi. В вероятностной форме, это означает, что обобщенная плотность вероятности для пары ориентиров P(nttl»tf) максимальна, даже когда предельные

плотности вероятностей достаточно распределены.

Наиболее важным в понимании SLAM было осознание, что корреляция при определении ориентиров линейно возрастает, с ростом количества произведённых наблюдений. Эти результаты доказаны на линейной Гауссовской вероятностной модели. Следовательно, достоверность относительного расположения ориентиров всегда будет повышаться, и никогда не будет расходиться, независимо от направлений движения робота. В вероятностных терминах, это означает, что обобщенная плотность вероятности для всех ориентиров Р (m) будет линейно стремиться к максимуму с ростом количества произведенных наблюдений. Такая конвергенция происходит потому, что наблюдения, сделанные роботом можно рассматривать как "почти независимые" измерения относительного месторасположения ориентиров.

Обратимся снова к рис.1, и рассмотрим робота на месте xk наблюдая за двумя ориентирами mi и mj. Относительное расположение наблюдаемых ориентиров явно не зависит от координат транспортного средства, и последовательные наблюдения из этого фиксированного положения дают в дальнейшем независимые измерения относительного расстояния между ориентирами [7].

После перемещения робота к месту расположения xk+1, он снова фиксирует ориентир mj, что дает возможность оценить местоположение объекта и ориентира, а также обновить информацию относительно предыдущего места xk. Использование одних и тех же данных для обновления информации о других ориентирах делает их более

коррелированными. Ошибки наблюдений будут коррелироваться путем проведения последовательных движений робота, следовательно уместен термин «почти независимое» измерение. Далее пусть робот перемещен в позицию Хк+1, и он наблюдает за двумя новыми ориентирами относительно позиции 1пг Они непосредственно связаны или коррелируют с остальной частью карты. Все их последующие измерения будут обновлять данные об ориентире ту и через него т, и так далее. Все ориентиры в конечном итоге сформируют сеть, со связями относительного месторасположения или корреляциями, при этом точность значений будет возрастать с ростом количества произведенных наблюдений. Данный процесс можно визуализировать (см. рис.2) в виде полносвязного графа, на котором соединены все ориентиры.

Узлы (ориентиры) соединены связями, описывающими корреляции между ними. По мере того как транспортное средство движется назад или вперед через окружающую среду, жесткость связей и корреляций увеличивается (связи становятся толще). По мере наблюдения ориентиров расположения корректируются, а измеренные данные распространяются через всю сеть. Робот, также коррелируется с картой. Поэтому наблюдение в некоторой окрестности подобно перемещению источника системы, а эффект возрастает с ростом корреляционных свойств и уменьшается с увеличением

Рис. 2 - Граф корреляции ориентиров

расстояния до соседних ориентиров. Когда робот перемещается по окружающей его среде и фиксирует ориентиры, связи становятся (линейно) более прочными. В итоге будет построена строгая карта ориентиров (относительная карта окружающей среды), где будет определено местоположение объекта относительно карты, и оно ограничено только ее качеством и точностью датчика измерения робота. Теоретически, относительная точность определения местоположения робота равна точности локации достигаемой на данной карте.

Решения проблемы SLAM. Решения вероятностной задачи включает в себя поиск соответствующих представлений для моделей наблюдения (2) и движения (3), что обеспечивает возможность эффективного и последовательного вычисления предшествующих и последующий распределений в (4) и (5). Обычно представление находится в форме пространства состояний с совокупным Гауссовским шумом, что приводит к использованию расширенного фильтра Кальмана (EKF, Extended Kaiman Filter) для решения проблемы SLAM. Одним из важных альтернативных представлений для описания модели движения транспортного средства в (3) используется обобщенный набор выборок в виде негауссовских распределенных вероятностей. Это позволяет применять фильтр частиц Rao-Blackwellized (R-B) или алгоритм FastSLAM.

EKF-SLAM. Основой для EKF-SLAM метода является описание движения транспортного средства в виде

где А() кинематическая модель транспортного средства, при условии, что ^^ является аддитивным, нулевым средним некоррелированным Гауссовским возмущением движения с ковариацией Qk.

Л'^-. X-._-.ii-.) = Х-. = .Ii-.)" V,-;.,

Модель наблюдения описывается в виде где Ь(-) описывает геометрию наблюдения и где vk являются аддитивными, нулевыми средними не коррелируемыми Гауссовкими ошибками наблюдений с ковариацией Rk.

Используя эти определения, стандартный метод БМБ, может быть применен для вычисления среднего значения

и ковариационная матрица определяется как

Г Р Р П

1РГ Р = Е

'mír,-1 к к

Wt-íñJbt-wW | 0:

=

из следующего совместного распределения Обновление по времени

где это якобиан Г определенный, как оценка

Как правило, нет необходимости выполнять обновление времени для стационарных ориентиров, его применение необходимо для ориентиров, которые могут перемещаться.

Обновление наблюдения

а к

= [4|fc- A- J + Щ - К^щк-хМк-1)]

где Sf¿. = j4tlT + üfc,

Чк это якобиан Ь от ^ а ъ 1 и

Такое решение ЕКБ-БЬЛМ очень хорошо известно и наследует многие преимущества и недостатки, стандартных решений ЕКБ для навигации или трекинга. Рассмотрим четыре ключевые особенности алгоритма.

Сходимость

В задаче ЕКБ-БЬЛМ, сходимость карты проявляется в монотонной сходимости детерминанта ковариационной матрицы и всех пар

ориентиров подматриц к нулю. Отдельные отклонения ориентиров сходятся к нижней границе и определяются начальными неопределенностями в положении робота и наблюдений. Типичное поведение сходимости мест расположения ориентиров в отклонениях показано на рис.3.

Вычислительные затраты

Каждый шаг обновления наблюдения требует, чтобы все ориентиры и совместная ковариационная матрица также соответственно обновлялась. Практически это означает, что вычисление квадратично растет с ростом количества наземных ориентиров. Была проделана большая работа, в развитии эффективных вариантов решения ЕКБ-БЬЛМ, и возможности вычисления в режиме реального времени со многими тысячами ориентиров, результаты которой продемонстрированы в работах [8,9].

Ассоциация данных

Стандартная формулировка решения ЕКБ-БЬЛМ особенно чувствительна к неправильной ассоциации наблюдений с наземными ориентирами. Так же существенной проблемой является закрытие петли, возникающая, при возвращении объекта, порождающая сделать повторные замеры ориентиров после большого пройдённого пути.

^ 2

ш

х

X

ш

g 1.5

ш о

X

1

и 0

40 50 60 70 80 90 100 110 Время

Рис. 3 - Конвергенция неопределенности ориентиров

Нелинейность

Алгоритм EKF-SLAM использует линеаризованные модели нелинейного движения и модели наблюдений и соответственно наследует множество ограничений для этих моделей. Нелинейность может быть серьезной проблемой EKF-SLAM и может приводить к неизбежным, алогичностям в прикладных задачах. Конвергенция и последовательность может быть гарантирована только в линейном случае.

Фильтр Рао-Блэквеллизеда. Алгоритм FastSLAM произвел фундаментальный и концептуальный сдвиг в разработке рекурсивного вероятностного SLAM. Предыдущие усилия сосредоточивались на улучшении исполнения EKF-SLAM, сохраняя его существенные линейные Гауссовские характеристики. Алгоритм FastSLAM основан на рекурсивной выборке, формируемой с помощью метода Монте-Карло или фильтрации частиц, и он был первым алгоритмом, который непосредственно реализовывал нелинейный процесс, основанный на негауссовом распределении. FastSLAM все еще линеаризует модель наблюдения, однако, это как правило, разумное приближение измерений, имеющих диапазон, при установленном местоположении робота. Из-за высокой размерности пространство-состояний задачи SLAM прямое применение фильтров частиц

становиться вычислительно сложной задачей. Тем не менее, можно уменьшить в выборках пространство путем применения RAO-Blackwellization фильтра, посредством чего объединенное состояние разделено согласно правилу ¥{хь^г) = l^iVC*!.} и, если

можно представить аналитически, только FQfil должны быть выбранными W * л(л: ), Совместное распределение, таким образом, представлено

множеством ' l^'')}' и статистически, как маргинал

F\.\-j —I]. ? ' ,V - Л.1' !, который может быть получен с большей точностью,

чем с помощью выборки по совмещенному пространству.

Соответственно совмещенное состояние SLAM может быть разложено на компоненты транспортного средства и условного компонента карты:

Здесь распределение вероятности находится на траектории а не в единственной позиции что обусловлено траекторией, поскольку

ориентиры на карты становятся независимыми (см. рис.4).

Рис. 4 - Графическая модель алгоритма Га818ЬАМ Это является ключевой особенностью ГаБ18ЬЛМ и причиной его скорости вычисления, т.к. карта представляется в виде набора независимых

Гауссианов, с линейной сложностью, вместо совмещенной карты ковариации с квадратичной сложностью. Таким образом, совместное распределение, по

времени к, представлено множеством ',, Л^-,, Р у 2Г0: ^ ^, в

котором карта сопровождающих каждую частицу состоит из независимых Гауссовских распределений р(т\Х = П? Р

Рекурсивная оценка осуществляется фильтрацией частицы по состоянию позиции и ЕКБ для состояний карты.

Обновление карты, для каждой заданной частицы траектории

выполняется достаточно просто. Каждый наблюдаемый ориентир обрабатывается индивидуально, как обновление измерения от известной позиции ЕКБ.

Ненаблюдаемые ориентиры остаются неизменными. Эллипсами отмечены возможные расположения для каждой стадии обновления, из которых местоположения робота отобраны исходя из того, что эта позиция является наилучшей, опираясь на обновленные наблюдаемые ориентиры. Таким образом, отображение для каждого шага определяется точностью траектории. Множество таких траекторий обеспечивают вероятностную модель расположения робота. Мы не будем принимать во внимание шумовой фон, создаваемый фильтром частиц, за исключением, того который является производной от рекурсивной формы выборки и который в действительности показывает актуальную совмещенную историю состояний.

На каждом временном шаге к, частицы взяты из распределения

которое аппроксимирует распределение |1 ^ог.),

а выборки приведены в соответствие весовыми коэффициентами важности для компенсации любых расхождений. Соответственно ошибка

аппроксимации растет со временем, увеличивая изменение веса выборки, ухудшая статистическую точность. Шаг пересчёта восстанавливает равномерность весового коэффициента, но приводит к потере исторической информации частиц. Поэтому передискретизация возможна только для системы, которая "по экспоненте забывает" свои прошлые состояния.

В общем виде фильтр частиц R-B для SLAM выглядит следующим образом. Мы предполагаем, что в момент 4—1, совместное состояние

представлено 4L v Р г

1. Для каждой частицы, вычисляется распределение, исходя из истории конкретной частицы, и делается выборка из нее

-

Эта новая выборка (неявно) присоединяется к истории частиц

Вес выборки определяется в соответствии с функцией

(f}_ (fj f(в &I

Члены числителя этого уравнения - это модель наблюдения и модель движения, соответственно.

3. В случае необходимости, выполняется повторная выборка значений. Момент, когда лучше всего производить выборку является открытой темой для обсуждения. Некоторые реализации выполняют каждый раз, шаг за шагом, другие после фиксированного числа шагов, третьи после того, как дисперсия превышает пороговое значение. Повторная выборка осуществляется путем отбора частиц, с заменой, из множества включая

связанные с ними карты и вероятностью выбора, пропорциональной и^1. Отобранным частицам задается однородный вес, = 1/Лт.

4. Для каждой частицы выполняется обновление БКБ для наблюдаемых ориентиров как простая операция отображения с известным местоположением транспортного средства.

На сегодняшний день в литературе наибольшее распространение получили две версии Бав18ЬЛМ, Бав18ЬЛМ 1.0 и Бав18ЬЛМ 2.0, они отличаются только с точки зрения формы их распределения (шаг 1) и, следовательно, важности веса (Шаг 2), Бав18ЬЛМ 2.0 на сегодняшний день является более эффективным решением.

Для Бав18ЬЛМ 1.0, модель движения описывается

Следовательно, из (14), выборки взвешиваются в соответствии с маргинальной моделью наблюдения.

Для Бав18ЬЛМ 2.0, модель движения описывается

V; 2; ,.и,).

где = и С -

нормализующая константа. Значение веса в соответствии с (14) будет .. = С. Преимущество БаБ18ЬЛМ 2.0 заключается в том, что это

распределение является локально оптимальным. То есть, для каждой частицы, определяется значение с наименьшим возможным отклонение в

весе на основе имеющейся информации, и

Статистически, FastSLAM (1,0 и 2,0) страдает вырождением из-за своей неспособности "забыть" прошлое. Тем не менее, эмпирические результаты FastSLAM 2.0 в реальных условиях окружающей среды показывают, что алгоритм способен генерировать точную карту.

Реализация SLAM. В последние годы практические реализации вероятностного SLAM становятся все более впечатляющими и охватывают большие площади в более сложных условиях. Рассмотрим два примера реализации в известных приложениях.

Рис. 5 - Визуализация SLAM в режиме реального времени "Исследование и возвращение '' - этот эксперимент, проведенный Ньюманом [10] был достаточно масштабным и производился в помещении, в результате было подтверждено выполнение свойства не расхождения EKF-SLAM, на практике же робот вернулся к точно отмеченной точки старта. Эксперимент замечателен тем, что его обратная поездка к отмеченной точке была полностью автономна.

Заключение. SLAM приложения в настоящее время существуют в большом разнообразии. Авторы провели вычислительные эксперименты со SLAM моделями и установили, что снизить вычислительную сложность алгоритмов реализации можно за счет алгоритмов с использованием расширенного фильтра Кальмана (EKF-SLAM) и фильтра Rао-Blackwellized (FastSLAM).

Работа выполнена при финансовой поддержке РФФИ, проекты 16-01-00597-а, 17-07-00620-a.

Литература

1. R. Smith P.C. On the representation of spatial uncertainty // Int. J. Robot. Res., Vol. vol. 5, 1987. pp. 56-68.

2. Durrant-Whyte. Uncertain geometry in robotics // IEEE Trans. Robot. Automat., Vol. vol 5, 1988. pp. 24 - 32.

3. J.Crowley. World modeling and position estimation for a mobile // Proc. IEEE Int. Conf. Robot., Automat., 1989. pp. 674 - 681.

4. R. Chatila J.P.L. Position referencing and consistent // Proc. IEEE Int. Conf. Ro-bot., 1985,. pp. 138-143.

5. Гуренко Б.В., Шаповалов И.О., Соловьев В.В., Береснев М.А. Построение и исследование подсистемы планирования траектории перемещения для системы управления автономным подводным аппаратом // Инженерный вестник Дона, 2015, №4. URL:

ivdon.ru/ru/magazine/archive/n4y2015/3383.

6. H. Durrant-Whyte D.R.A.E.N. Robotics Research: The 7th International Sympo-sium // Localisation of automatic. New York: Springer Verlag. 1996. pp. 283 - 293.

7. Туан Зунг Нгуен Алгоритмы ускоренной обработки изображений препятствий в системе технического зрения робота // Инженерный вестник Дона, 2015, №1, ч.2 URL: ivdon.ru/ru/magazine/archive/n1p2y2015/2855.

8. Nebot J.E. G.A.E.M. Optimization of the simultaneous localization and map-building algorithm for real-time implementation // IEEE Trans. Robot. Automat. 2001. Vol. 17. No. 3. pp. 242-257.

9. Feder J.J.L.A.H.J.S. The Ninth International Symposium // A computational effi-cient method for. 2000. pp. 169-176.

10. P.M. Newman J.J.L.J.N.A.J.T. Int. Conf. Robot. Automat. // Explore and return: Experimental validation of real time concurrent mapping and localization. Conf. Robot. Automat.. 2002. pp. 1802-1809.

References

1. R. Smith P.C. On the representation of spatial uncertainty Int. J. Robot. Res., Vol. vol. 5, 1987. pp. 56-68.

2. Durrant-Whyte. Uncertain geometry in robotics IEEE Trans. Robot. Automat, Vol. vol 5, 1988. pp. 24 - 32.

3. J.Crowley. World modeling and position estimation for a mobile Proc. IEEE Int. Conf. Robot., Automat, 1989. pp. 674 - 681.

4. R. Chatila J.P.L. Position referencing and consistent Proc. IEEE Int. Conf. Ro-bot., 1985. pp. 138-143.

5. Gurenko B.V., Shapovalov I.O., Solov'ev V.V., Beresnev M.A. Inzenernyj vestnik Dona (Rus), 2015, №4. URL: ivdon.ru/ru/magazine/archive/n4y2015/3383.

6. H. Durrant-Whyte D.R.A.E.N. Robotics Research: The 7th International Sympo-sium Localisation of automatic. New York: Springer Verlag. 1996. pp. 283 - 293.

7. Tuan Zung Nguen Inzenernyj vestnik Dona (Rus), 2015, №1, part 2. URL: ivdon.ru/ru/magazine/archive/n1p2y2015/2855.

8. Nebot J.E. G.A.E.M. Optimization of the simultaneous localization and map-building algorithm for real-time implementation IEEE Trans. Robot. Automat. 2001. Vol. 17. No. 3. pp. 242-257.

9. Feder J.J.L.A.H.J.S. The Ninth International Symposium A computational effi-cient method for. 2000. pp. 169-176.

10. P.M. Newman J.J.L.J.N.A.J.T. Int. Conf. Robot. Automat. Explore and return: Experimental validation of real time concurrent mapping and localization. Conf. Robot. Automat.. 2002. pp. 1802-1809.