Отображение сетки занятости

Картирование сетки занятости относится к семейству компьютерных алгоритмов в вероятностной робототехнике для мобильных роботов , которые решают проблему создания карт на основе зашумленных и неопределенных данных измерений датчиков в предположении, что поза робота известна. Сетки занятости были впервые предложены Х. Моравецом и А. Эльфесом в 1985 году. ^[1]

Основная идея сетки занятости состоит в том, чтобы представить карту окружающей среды как равномерно расположенное поле двоичных случайных величин, каждая из которых представляет наличие препятствия в этом месте среды. Алгоритмы сетки занятости вычисляют приблизительные апостериорные оценки для этих случайных величин. ^[2]

Схема алгоритма

Существует четыре основных компонента подхода к картированию сетки занятости. Они есть:

Интерпретация
Интеграция
Оценка позиции
Разведка ^[3]

Алгоритм отображения сетки занятости

Целью алгоритма отображения занятости является оценка апостериорной вероятности по картам с учетом данных: $p(m\mid z_{1:t},x_{1:t})$ , где $m$ это карта, $z_{1:t}$ представляет собой набор измерений от времени 1 до t, а $x_{1:t}$ — набор поз робота от времени 1 до t. Данные управления и одометрии не играют никакой роли в алгоритме отображения сетки занятости, поскольку предполагается, что путь известен.

Алгоритмы сетки занятости представляют карту $m$ как мелкозернистая сетка на непрерывном пространстве мест в окружающей среде. Наиболее распространенным типом карт сетки занятости являются 2D-карты, которые описывают часть трехмерного мира.

Если мы позволим $m_{i}$ обозначают ячейку сетки с индексом i (часто в 2d-картах два индекса используются для представления двух измерений), затем обозначение $p(m_{i})$ представляет вероятность того, что ячейка i занята. Вычислительная задача с оценкой апостериорного $p(m\mid z_{1:t},x_{1:t})$ является размерность задачи: если карта содержит 10 000 ячеек сетки (относительно небольшая карта), то количество возможных карт, которые могут быть представлены с помощью этой сетки, равно $2^{10,000}$ . Таким образом, вычисление апостериорной вероятности для всех таких карт невозможно.

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

p(m_{i}\mid z_{1:t},x_{1:t})

для всех ячеек сетки $m_{i}$ . Каждая из этих задач оценки тогда является бинарной задачей. Такая разбивка удобна, но при этом теряется часть структуры задачи, поскольку она не позволяет моделировать зависимости между соседними ячейками. Вместо этого задняя часть карты аппроксимируется путем ее разложения на

p(m\mid z_{1:t},x_{1:t})=\prod _{i}p(m_{i}\mid z_{1:t},x_{1:t})

.

Благодаря этой факторизации можно использовать двоичный фильтр Байеса для оценки вероятности заполнения каждой ячейки сетки. Обычно используется логарифмическое представление вероятности того, что каждая ячейка сетки занята.

См. также

Роботизированное картографирование

Ссылки

^ Х. Моравец; А.Э. Эльфес (1984). «Карты высокого разрешения с широкоугольного сонара» . Слушания. 1985 Международная конференция IEEE по робототехнике и автоматизации . Силвер-Спринг, Миссури: Издательство компьютерного общества IEEE. стр. 116–121. дои : 10.1109/РОБОТ.1985.1087316 . S2CID 41852334 .
^ Трун, С. ; Бургард, В .; Фокс, Д. (2005). Вероятностная робототехника . Кембридж, Массачусетс: MIT Press. ISBN 0-262-20162-3 . ОЛ 3422030М .
^ Трун С. и Бюкен А. (1996). «Интеграция сеточных и топологических карт для навигации мобильных роботов» (PDF) . Материалы тринадцатой национальной конференции по искусственному интеллекту : 944–950. ISBN 0-262-51091-Х .

Внешние ссылки

Конспект лекций 16-831: Статистические методы в робототехнике НИИ КМУ

[1] Х. Моравец; А.Э. Эльфес (1984). «Карты высокого разрешения с широкоугольного сонара» . Слушания. 1985 Международная конференция IEEE по робототехнике и автоматизации . Силвер-Спринг, Миссури: Издательство компьютерного общества IEEE. стр. 116–121. дои : 10.1109/РОБОТ.1985.1087316 . S2CID 41852334 .

[2] Трун, С. ; Бургард, В .; Фокс, Д. (2005). Вероятностная робототехника . Кембридж, Массачусетс: MIT Press. ISBN 0-262-20162-3 . ОЛ 3422030М .

[3] Трун С. и Бюкен А. (1996). «Интеграция сеточных и топологических карт для навигации мобильных роботов» (PDF) . Материалы тринадцатой национальной конференции по искусственному интеллекту : 944–950. ISBN 0-262-51091-Х .

[1]

[2]

[3]