Вероятностные методы локализации и навигации

Для решения задач локализации мобильных роботов при наличии неопреде­ленности в информации о рабочем пространстве и сенсорных данных (шум, погрешности, неоднозначная интерпретация) успешно используются вероят­ностные методы [217, 219, 250, 343, 352, 374].

При использовании вероятностных методов информация о текущем место­положении робота представлена функцией распределения плотности вероятно­сти, которая задана во всех доступных роботу участках рабочего пространства (карте) и обновляется по итеративной методике прогнозирования и согласова­ния с использованием формулы Байеса. В качестве «действительного» место­положения робота принимается, либо местоположение с большей степенью ве­роятности [217, 352], либо центр тяжести распределения [374]. Методы вероят­ностной локализации являются частным случаем метода оценки состояния сис­темы в рамках теории Марковских процессов принятия решений, где искомым состоянием является местоположение MP.

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

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

• Все показания сенсоров для данного местоположения робота предпола­гаются условно независимыми. Это означает что, сенсорные данные первого типа зависят только от текущего местоположения робота. Если местоположе­ние робота известно, для предсказания текущих сенсорных данных не нужны предыдущие показания сенсоров. Это условие нарушается в динамически из­меняющемся рабочем пространстве, когда, например, в поле зрения сенсоров попадают проходящие мимо люди.

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

Использование вероятностных методов требует наличия (построения) двух вероятностных моделей (условных распределений плотности вероятности): сенсорной модели окружающего пространства и модели движения мобильного робота. Вероятностная сенсорная модель связывает показания сенсоров с кон­кретным местоположением робота. Эта модель может быть задана изначально, вычислена по данным карты или построена опытным путем при исследовании роботом неизвестной территории. Вероятностная модель движения мобильного робота связывает возможные результаты изменения местоположения робота с его программно заданным перемещением, учитывая при этом все возможные погрешности. При определении этой модели основная проблема связана с не­определенностью результатов передвижений робота, которая возникает из-за ошибок в управляющих и исполнительных подсистемах и других обстоятельств (возможное буксование колес, неровности пола, и т.д.).

воздействие внешних факторов невозможно или очень сложно, поэтому на практике часто используются приближенные оценки сверху [217, 372, 374]. Часто подразумевается, что величина погрешности из-за воздействия внешних факторов линейно зависит от пройденной роботом дистанции. Такой подход хорошо описывает результаты для простых перемещений (движение по прямой, вращение на месте), но для более сложных перемещений из-за нелинейности уравнений движения может давать неудовлетворительные результаты. Итера­тивные методы вычисления неопределенности местоположения на основе одо- метрических данных опубликованы в работах [220, 286, 353].

Рис. 1.9. Аппроксимация распределения вероятности с помощью трехмерных дискретных сеток

Для аппроксимации функции распределения плотности вероятности для ме­стоположения мобильного робота хорошо зарекомендовали себя трехмерные дискретные сетки (рис. 1.9). Однако их хранение требует значительного объема памяти, особенно при увеличении площади РП и точности аппроксима­ции [220]. Поэтому применение дискретных сеток требует значительных вы­числительных ресурсов, что делает их неэффективными и ограничивает их ис­пользование в приложениях реального времени. Для повышения эффективно­сти Марковских методов локализации предлагают производить выборочные вычисления [220,372], динамически изменять точность получения решения за счет адаптивного изменения точности аппроксимации [218], применять эффек­тивные модели для специфических РП [370]. Тем не менее, вычислительные за­траты при таком виде аппроксимации все равно остаются высокими.

В последнее время интенсивно развивается класс вероятностных алгорит­мов локализации Монте-Карло [296,373,375]. Согласно этим алгоритмам рас­пределение плотности вероятности аппроксимируется плотностью множества взвешенных «пробных» точек, соответствующих местоположениям робота. При таком подходе снимаются ограничения на точность аппроксимации, а из­меняя размер множества пробных точек можно варьировать объем вычислений.

достатков. Во-первых, их устойчивость и эффективность сложным образом за­висят от размера множества пробных точек, а также от используемых алгорит­мов повторной выборки, применяемых для обновления множества пробных то­чек на этапах прогнозирования и согласования. Отношение между площадью окружающей среды и требуемым количеством пробных точек в методах Монте- Карло далеко не так очевидно и обычно должно быть определено в ходе экспе­риментов. Существует вероятность того, что метод повторной выборки может не сгенерировать пробные точки или удалить пробные точки в правильном ме­стоположении, что приведет к тому, что робот «потеряется». Также отмечается, что методы локализации Монте-Карло медленнее восстанавливают корректное местоположение после сбоев в системе. Поэтому Марковская локализация с ап- проксимацей на дискретных сетках все еще остается одним из самых надежных и эффективных методов определения местоположения роботов.

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

1.6.