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

---

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

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

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

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

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

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

---