Составление карты

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

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

В литературе задачу составления карты роботом часто называют задачейодновременной локализации и составления карты, сокращенно обозначая ее какSLAM (Simultaneous Localization And Mapping). Робот не только обязан составить карту, но и должен сделать это, изначально не зная, где он находится. SLAM — одна из наиболее важных задач в робототехнике. Мы рассмотрим ту версию этой задачи, в которой среда является фиксированной. Даже этот более простой вариант задачи с большим трудом поддается решению; но положение становится значительно сложнее, когда в среде допускается возникновение изменений в ходе перемещения по ней робота.

С точки зрения статистического подхода задача составления карты сводится к задаче байесовского алгоритмического вывода, так же как и локализация. Если, как и прежде, карта будет обозначаться через м, а поза робота во время t — через x_t, то можно включить данные обо всей карте в выражение для апостериорной вероятности:

P(X_{t + l}, M | z_{l:t + l}, a_1:t) = aP(z_t+1 | x_t+1, M) ∫ P(x_t+1 | x_t, a_t) P(x_t, M | z_1:t, a_1:t-1) dx_t

Ha основании этого уравнения фактически можно сделать некоторые благоприятные для нас выводы: распределения условных вероятностей, необходимые для включения данных о действиях и измерениях, по существу являются такими же, как и в задаче локализации робота. Единственная предосторожность связана с тем, что новое пространство состояний (пространство всех поз робота и всех карт) имеет гораздо больше измерений. Достаточно представить себе, что принято решение изобразить конфигурацию всего здания с фотографической точностью. Для этого, по-видимому, потребуются сотни миллионов чисел. Каждое число будет представлять собой случайную переменную и вносить свой вклад в формирование чрезвычайно высокой размерности пространства состояний. Эта задача еще в большей степени усложняется в связи с тем фактом, что робот может даже не знать заранее о том, насколько велика его среда. Это означает, что ему придется динамически корректировать размерность Mв процессе составления карты.

По-видимому, одним из наиболее широко применяемых методов решения задачи SLAM является EKF. Об этом говорит сайт https://intellect.icu . Обычно этот метод используется в сочетании с моделью восприятия данных об отметках и требует, чтобы все отметки были различимыми. апостериорная оценка была представлена с помощью гауссова распределения со средним µ_t и ковариацией ∑_t. При использовании для решения задачи SLAM подхода, основанного на методе EKF, это распределение апостериорных вероятностей снова становится гауссовым, но теперь среднее µ_t. выражается в виде вектора с гораздо большим количеством измерений. В нем представлена не только поза робота, но и местонахождение всех характеристик (или отметок) на карте. Если количество таких характеристик равно л, то вектор будет иметь размерность 2n+3 (два значения требуются для указания местонахождения отметки и три — для указания позы робота). Следовательно, матрица ∑_t имеет размерность (2n+3) х (2n+3) и следующую структуру:

В этом уравнении ∑_хх — ковариация данных о позе робота, которая уже рассматривалась в контексте локализации; ∑_хх — матрица с размерами 3x2n, которая выражает корреляцию между характеристиками на карте и координатами робота. Наконец, ∑_хх — это матрица с размерами 2nх2n, которая задает ковариацию характеристик на карте, включая все парные корреляции. Поэтому потребность в памяти для алгоритмов, основанных на методе EKF, измеряется квадратичной зависимостью от n (количества характеристик на карте), а время обновления также определяется квадратичной зависимостью от n.

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

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

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

Алгоритм EKF составления карты напоминает алгоритм локализации EKF, описанный в предыдущем разделе. Основное различие между ними определяется тем, что в распределении апостериорных вероятностей учитываются дополнительные переменные отметок. Модель движения для отметок является тривиальной, поскольку они не движутся. Таким образом, для этих переменных функция f представляет собой единичную функцию, а функция измерения по существу остается такой же, как и прежде. Единственное различие состоит в том, что якобиан H_t в уравнении обновленияEKF берется не только по отношению к позе робота, но также и по отношению к местонахождению отметки, которая наблюдалась во время t. Результирующие уравнения EKF являются еще более устрашающими по своей сложности, чем те, которые были сформулированы перед этим; именно по этой причине мы их здесь опускаем. Однако существует еще одна сложность, которая до сих пор нами  игнорировалась, — тот факт, что размер карты M заранее не известен. Поэтому не известно также количество элементов в окончательной оценке µ_t и ∑_t. Эти данные приходится переопределять динамически, по мере обнаружения роботом все новых и новых отметок. Но эту проблему можно решить чрезвычайно просто — как только робот обнаруживает новую отметку, он добавляет новый элемент к распределению апостериорных вероятностей. Если же значение дисперсии этого нового элемента инициализируется очень большим числом, то результирующее распределение апостериорных вероятностей становится таким же, как если бы робот заранее знал о существовании этой отметки.

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