Обзор существующих решений

Наиболее передовые алгоритмы используют изображение с веб-камер и дальномеров для определения положения робота. Эти методы являются более точными и универсальными. Разработками подобных алгоритмов занимаются ведущие мировые университеты. В иностранной литературе [1] алгоритмы определения положения робота на карте одновременно с построением карты называют аббревиатурой SLAM (Simultaneous Location and Mapping). Большинство реализованных алгоритмов основаны на применении фильтров частиц. Для определения положения они используют «особые точки» в имеющихся данных, которых обычно не так уж много, особенно в привычных прямоугольных помещениях, где ими являются только углы. Поэтому при длительной работе возникают ошибки — полученный образ пространства искажается, хотя возможность навигации по карте сохраняется [2]. Значит, необходим алгоритм вычисления положения робота, адекватно работающий при малом числе особых точек и не искажающий пространство при длительной работе.. Обобщенный алгоритм работы системы определения положения робота приведен на рисунке (Рисунок 1).

Рисунок 1. Обобщенный алгоритм работы системы определения положения робота.

Сложность технического процесса определения текущего местоположения и построения карты обусловлена низкой точностью приборов, участвующих в процессе вычисления текущего местоположения. Метод одновременной навигации и построения карты (SLAM) — это концепция, которая связывает два независимых процесса в непрерывный цикл последовательных вычислений. При этом результаты одного процесса участвуют в вычислениях другого процесса [3].

Однако даже при наличии качественного лазерного дальномера задача составления карты нетривиальна: для этого необходимо с высокой точностью определить текущее положение робота, а для того, чтобы определить положение по показаниям дальномера, нужно составить карту. Прямолинейные подходы к решению задачи, в которых сначала производится локализация по существующей частично составленной карте, а затем на основе наиболее вероятного текущего положения достраивается недостающая ее часть, имеют тенденцию к составлению карт с ошибками. Более того, эти ошибки накапливаются с течением времени. Движение робота по замкнутому кругу при таком подходе может привести к серьезным проблемам с выравниванием в месте замыкания цикла.

Одним из первых алгоритмов, способных решать данную задачу в один проход и без дополнительных эвристик для разрешения циклов, был FastSLAM. Этот алгоритм основывался на идее Мерфи. Он использовал фильтр частиц Рао-Блэквелла для построения гипотез о текущем положении робота и фильтр Калмана для отслеживания положений наперед заданных меток [4]. Данный метод решал проблему составления карты ценою введения меток. Проблема же их распознавания была достаточно сложна, хотя существовали наработки и по этой тематике.