Локализация
Локализация — это универсальный пример робототехнического восприятия. Она представляет собой задачу определения того, где что находится. Локализация — одна из наиболее распространенных задач восприятия в робототехнике, поскольку знания о местонахождении объектов и самого действующего субъекта являются основой любого успешного физического взаимодействия. Например, роботы, относящиеся к типу манипуляторов, должны иметь информацию о местонахождении объектов, которыми они манипулируют. А роботы, передвигающиеся в пространстве, должны определять, где находятся они сами, чтобы прокладывать путь к целевым местонахождениям.
Существуют три разновидности задачи локализации с возрастающей сложностью. Если первоначальная поза локализуемого объекта известна, то локализация сводится к задаче отслеживания траектории. Задачи отслеживания траектории характеризуются ограниченной неопределенностью. Более сложной является задача глобальной локализации, в которой первоначальное местонахождение объекта полностью неизвестно. Задачи глобальной локализации преобразуются в задачи отслеживания траектории сразу после локализации искомого объекта, но в процессе их решения возникают также такие этапы, когда роботу приходится учитывать очень широкий перечень неопределенных состояний. Наконец, обстоятельства могут сыграть с роботом злую шутку и произойдет "похищение" (т.е. внезапное исчезновение) объекта, который он пытался локализовать. Задача локализации в таких неопределенных обстоятельствах называется задачей похищения. Ситуация похищения часто используется для проверки надежности метода локализации в крайне неблагоприятных условиях.
В целях упрощения предположим, что робот медленно движется на плоскости и что ему дана точная карта среды (пример подобной карты показан на рис. 25.7). Поза такого мобильного робота определяется двумя декартовыми координатами со значениями х и у, а также его угловым направлением со значением 0, как показано на рис. 25.6, а. (Обратите внимание на то, что исключены соответствующие скорости, поэтому рассматриваемая модель скорее является кинематической, а не динамической.) Если эти три значения будут упорядочены в виде вектора, то любое конкретное состояние определится с помощью соотношения xt= (xt, yt, 0t) т.
В этой кинематической аппроксимации каждое действие состоит из "мгновенной" спецификации двух скоростей — скорости переноса vt и скорости вращения cot. Для небольших временнь/х интервалов At грубая детерминированная модель движения таких роботов задается следующим образом:
Обозначение X относится к детерминированному предсказанию состояния. Безусловно, поведение физических роботов является довольно непредсказуемым. Такая ситуация обычно моделируется гауссовым распределением со средним f (xt/ vt, cot) и ковариацией Zx (математическое определение приведено в приложении А).
P(Xt+i|Xt/ Vt,CDt) = iV(Xt+1,Sx)
Затем необходимо разработать модель восприятия. Рассмотрим модели восприятия двух типов. В первой из них предполагается, что датчики обнаруживают стабильные, различимые характеристики среды, называемые С отметками. Для каждой отметки они сообщают дальность и азимут. Предположим, что состояние робота определяется выражением xt= (xt,yt, 6t) т и он принимает информацию об отметке, местонахождение которой, как известно, определяется координатами (Xi,yi) т. При отсутствии шума дальность и азимут можно вычислить с помощью простого геометрического соотношения (см. рис. 25.6, а). Точное предсказание наблюдаемых значений дальности и азимута может быть выполнено с помощью следующей формулы:
Еще раз отметим, что полученные результаты измерений искажены шумом. Для упрощения можно предположить наличие гауссова шума с ковариацией Zz:
P(zt|xt) = iV(zt,Iz)
Для дальномеров такого типа, как показаны на рис. 25.2, часто более приемлемой является немного другая модель восприятия. Такие датчики вырабатывают вектор значений дальности zt= (z1#..., zM) т, в каждом из которых азимуты являются фиксированными по отношению к роботу. При условии, что дана поза xt, допустим, что z-j — точное расстояние вдоль направления j-ro луча от xt до ближайшего препятствия. Как и в описанном раньше случае, эти результаты могут быть искажены гауссовым шумом. Как правило, предполагается, что погрешности для различных направлений лучей независимы и заданы в виде идентичных распределений, поэтому имеет место следующая формула:
На рис. 25.6,6 показан пример четырехлучевого дальномера и двух возможных поз робота, одну из которых на полном основании можно рассматривать как позу, в которой были получены рассматриваемые результаты измерения дальностей, а другую — нет. Сравнивая модель измерения дальностей с моделью отметок, можно убедиться в том, что модель измерения дальностей обладает преимуществом в том, что не требует идентификации отметки для получения возможности интерпретировать результаты измерения дальностей; и действительно, как показано на рис. 25.6, б, робот направлен в сторону стены, не имеющей характерных особенностей. С другой стороны, если бы перед ним была видимая, четко идентифицируемая отметка, то робот мог бы обеспечить немедленную локализацию.
В главе 15 описаны фильтр Калмана, позволяющий представить доверительное состояние в виде одного многомерного гауссова распределения, и фильтр частиц, который представляет доверительное состояние в виде коллекций частиц, соответствующих состоянию. В большинстве современных алгоритмов локализации используется одно из этих двух представлений доверительного состояния робота, P(Xt|z1:t,al!t-i).
Локализация с использованием фильтрации частиц называется локализацией Монте-Карло, или сокращенно MCL (Monte Carlo Localization). Алгоритм MCL идентичен алгоритму фильтрации частиц, приведенному в листинге 15.3; достаточно лишь предоставить подходящую модель движения и модель восприятия. Одна из версий алгоритма, в которой используется модель измерения дальностей, приведена в листинге 25.1. Работа этого алгоритма продемонстрирована на рис. 25.7, где показано, как робот определяет свое местонахождение в офисном здании. На первом изображении частицы распределены равномерно согласно распределению априорных вероятностей, показывающему наличие глобальной неопределенности в отношении положения робота. На втором изображении показано, как поступает первый ряд результатов измерений и частицы формируют кластеры в областях с высоким распределением апостериорных доверительных состояний. А на третьем изображении показано, что поступило достаточное количество результатов измерений, чтобы переместить все частицы в одно место.
Листинг 25.1. Алгоритм локализации Монте-Карло, в котором используется модель восприятия результатов измерения дальностей с учетом наличия независимого шума
function Monte-Carlo-Localization(a, z, N, model, map) returns множество выборок S
inputs: а, предыдущая команда приведения робота в движение
z, результаты измерения дальностей с М отсчетами zi,...,zM N, количество сопровождаемых выборок
model, вероятностная модель среды с данными о предыдущей позе Р(Хо), моделью движения P(Xi|Xo,Ao) и моделью шума для датчика расстояний P(Z\Z) тар, двухмерная карта среды static: S, вектор выборок с размером N, первоначально вырабатываемый из Р(Хо)
local variables: W, вектор весов с размером N
for i = 1 to N do
S[i] <— выборка из P(X1\X0=S[i] ,A0=a) W[i] <- 1
for j = 1 to M do
z <— Exact-Range (j, S[i] ,map)
W[i]
На рис. 25.8 показано применение понятия линеаризации для (одномерной) модели движения робота. В левой части показана нелинейная модель движения f(xt,at) (параметр at на этом графике не показан, поскольку он не играет никакой роли в этой линеаризации). В правой части эта функция аппроксимируется линейной функцией f(xt,at). График этой линейной функции проходит по касательной к кривой f в точке |nt, которая определяет среднюю оценки состояния во время t. Такая линеаризация называется разложением в ряд Тейлора (первой степени). Фильтр Калмана, линеаризующий функции f и h с помощью разложения в ряд Тейлора, называется расширенным фильтром Калмана (или Extended Kalman Filter — EKF). На рис. 25.9 показана последовательность оценок, полученных роботом, который действует под управлением алгоритма локализации на основе расширенного фильтра Калмана. По мере передвижения робота неопределенность в оценке его местонахождения возрастает, как показано с помощью эллипсов погрешностей. Но как только робот начинает получать данные о дальности и азимуте до отметки с известным местонахождением, его погрешность уменьшается. Наконец, погрешность снова возрастает, как только робот теряет отметку из виду. Алгоритмы EKF действуют успешно, если отметки являются легко идентифицируемыми. Еще один вариант состоит в том, что распределение апостериорных вероятностей может быть мультимодальным, как показано на рис. 25.7, б. Задача, для решения которой требуется знать идентификацию отметок, представляет собой пример задачи ассоциации данных, которая обсуждалась в конце главы 15.