Составление карты
До сих пор в этой главе рассматривалась задача локализации одного объекта. Но в робототехнике поиск часто осуществляется в целях локализации сразу нескольких объектов. Классическим примером такой задачи является составление карты с помощью робота. Представьте себе робота, которому не дана карта его среды. Вместо этого он вынужден составлять такую карту самостоятельно. Безусловно, человечество добилось потрясающих успехов в искусстве составления карт, описывающих даже такие крупные объекты, как вся наша планета. Поэтому одна из задач, присущих робототехнике, состоит в создании алгоритмов, позволяющих роботам решать аналогичную задачу.
В литературе задачу составления карты роботом часто называют задачей одновременной локализации и составления карты, сокращенно обозначая ее как SLAM (Simultaneous Localization And Mapping). Робот не только обязан составить карту, но и должен сделать это, изначально не зная, где он находится. SLAM — одна из наиболее важных задач в робототехнике. Мы рассмотрим ту версию этой задачи, в которой среда является фиксированной. Даже этот более простой вариант задачи с большим трудом поддается решению; но положение становится значительно сложнее, когда в среде допускается возникновение изменений в ходе перемещения по ней робота.
С точки зрения статистического подхода задача составления карты сводится к задаче байесовского алгоритмического вывода, так же как и локализация. Если, как и прежде, карта будет обозначаться через м, а поза робота во время t — через xt, то можно переформулировать уравнение 25.1, чтобы включить данные обо всей карте в выражение для апостериорной вероятности:
На основании этого уравнения фактически можно сделать некоторые благоприятные для нас выводы: распределения условных вероятностей, необходимые для включения данных о действиях и измерениях, по существу являются такими же, как и в задаче локализации робота. Единственная предосторожность связана с тем, что новое пространство состояний (пространство всех поз робота и всех карт) имеет гораздо больше измерений. Достаточно представить себе, что принято решение изобразить конфигурацию всего здания с фотографической точностью. Для этого, по-видимому, потребуются сотни миллионов чисел. Каждое число будет представлять собой случайную переменную и вносить свой вклад в формирование чрезвычайно высокой размерности пространства состояний. Эта задача еще в большей степени усложняется в связи с тем фактом, что робот может даже не знать заранее о том, насколько велика его среда. Это означает, что ему придется динамически корректировать размерность м в процессе составления карты.
По-видимому, одним из наиболее широко применяемых методов решения задачи SLAM является EKF. Обычно этот метод используется в сочетании с моделью восприятия данных об отметках и требует, чтобы все отметки были различимыми. В предыдущем разделе апостериорная оценка была представлена с помощью гауссова распределения со средним jut и ковариацией Et. При использовании для решения задачи SLAM подхода, основанного на методе EKF, это распределение апостериорных вероятностей снова становится гауссовым, но теперь среднее щ. выражается в виде вектора с гораздо большим количеством измерений. В нем представлена не только поза робота, но и местонахождение всех характеристик (или отметок) на карте. Если количество таких характеристик равно л, то вектор будет иметь размерность 2 л+3 (два значения требуются для указания местонахождения отметки и три — для указания позы робота). Следовательно, матрица 2t имеет размерность (2 л+3) х (2 л+3) и следующую структуру:
В этом уравнении Ехх — ковариация данных о позе робота, которая уже рассматривалась в контексте локализации; Ехм— матрица с размерами 3x2л, которая выражает корреляцию между характеристиками на карте и координатами робота. Наконец, Емм— это матрица с размерами 2лх2л, которая задает ковариацию характеристик на карте, включая все парные корреляции. Поэтому потребность в памяти для алгоритмов, основанных на методе EKF, измеряется квадратичной зависимостью от л (количества характеристик на карте), а время обновления также определяется квадратичной зависимостью от л.
Прежде чем перейти к изучению математических выкладок, рассмотрим решение задачи по методу EKF на графиках. На рис. 25.10 показано, как робот движется в среде с восемью отметками, расположенными в два ряда по четыре отметки каждый. Первоначально робот не имеет информации о том, где находятся отметки. Предполагается, что каждая отметка имеет другой цвет, и робот может надежно отличать их друг от друга. Робот начинает двигаться влево, в заранее заданном направлении, но постепенно теряет уверенность в том, есть ли у него достоверная информация о своем местонахождении. Эта ситуация показана на рис. 25.10, а с помощью эллипсов погрешности, ширина которых возрастает по мере дальнейшего передвижения робота. Движущийся робот получает данные о дальности и азимуте до ближайших отметок, а эти наблюдения используются для получения оценок местонахождения таких отметок. Естественно, что неопределенность в оценке местонахождения этих отметок тесно связана с неопределенностью локализации робота. На рис. 25.10, б, в показано изменение доверительного состояния робота по мере того, как он продвигается в своей среде все дальше и дальше.
Важной особенностью всех этих оценок (которую не так уж легко заметить, рассматривая приведенные графические изображения) является то, что в рассматриваемом алгоритме поддерживается единственное гауссово распределение по всем оценкам. Эллипсы погрешностей на рис. 25.10 представляют собой проекции этого гауссова распределения на подпространство координат робота и отметки. Эта многомерное гауссово распределение апостериорных вероятностей поддерживает корреляции между всеми оценками. Данное замечание приобретает важное значение при попытке понять, что происходит на рис. 25.10, г. На этом рисунке показано, что робот обнаруживает отметку, ранее нанесенную на карту. В результате его собственная неопределенность резко уменьшается. Такое же явление происходит и с неопределенностью всех других отметок. Указанное событие является следствием того факта, что оценка местонахождения робота и оценки местонахождений отметок имеют высокую степень корреляции в гауссовом распределении апостериорных вероятностей.
Алгоритм EKF составления карты напоминает алгоритм локализации EKF, описанный в предыдущем разделе. Основное различие между ними определяется тем, что в распределении апостериорных вероятностей учитываются дополнительные переменные отметок. Модель движения для отметок является тривиальной, поскольку они не движутся. Таким образом, для этих переменных функция f представляет собой единичную функцию, а функция измерения по существу остается такой же, как и прежде. Единственное различие состоит в том, что якобиан Ht в уравнении обновления EKF берется не только по отношению к позе робота, но также и по отношению к местонахождению отметки, которая наблюдалась во время t. Результирующие уравнения EKF являются еще более устрашающими по своей сложности, чем те, которые были сформулированы перед этим; именно по этой причине мы их здесь опускаем.
Однако существует еще одна сложность, которая до сих пор нами игнорировалась, — тот факт, что размер карты м заранее не известен. Поэтому не известно также количество элементов в окончательной оценке jut и Et. Эти данные приходится переопределять динамически, по мере обнаружения роботом все новых и новых отметок. Но эту проблему можно решить чрезвычайно просто — как только робот обнаруживает новую отметку, он добавляет новый элемент к распределению апостериорных вероятностей. Если же значение дисперсии этого нового элемента инициализируется очень большим числом, то результирующее распределение апостериорных вероятностей становится таким же, как если бы робот заранее знал о существовании этой отметки.