Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 324
Текст из файла (страница 324)
Наконец, обстоятельства могут сыграть с роботом злую шутку и произойдет "похищение" (т.е. внезапное исчезновение) объекта, который он пытался локализовать. Задача локализации в таких неопределенных обстоятельствах называется Ъ. задачей похищения. Ситуация похищения часто используется для проверки надежности метода локализации в крайне неблагоприятных условиях.
В целях упрощения предположим, что робот медленно движется на плоскости и что ему дана точная карта среды (пример подобной карты показан на рис. 25.7). Поза такого мобильного робота определяется двумя декартовыми координатами со значениями х и у, а также его угловым направлением со значением О, как показано на рис. 25.6, а. (Обратите внимание на то, что исключены соответствующие скорости, поэтому рассматриваемая модель скорее является кинематической, а не динамической.) Если эти три значения будут упорядочены в виде вектора, то любое конкретное состояние определится с помощью соотношения х,= ( х„у„, 8, ) '.
1!Ф Ч;3 и, ~'1! 1)6юенн~ р ~-г~г~рч~иг и ~м Ъ~~ г 1199 Глава 25. Робототехника ( (х~-х') ч (у -у') в, = )з(хе) агсеап -0~ Х,-Хт Еше раз отметим, что полученные результаты измерений искажены шумом. Для упрощения можно предположить наличие гауссова шума с ковариацией Х,: Р(в~(х~) = эг(в~,ь,) Для дальномеров такого типа, как показаны на рис. 25.2, часто более приемлемой является немного другая модель восприятия. Такие датчики вырабатывают вектор значений дальности г,= ( г„..., я„) ', в каждом из которых азимуты являются фиксированными по отношению к роботу.
При условии, что дана поза х„допустим, что зз — точное расстояние вдоль направления )-го луча от ж, до ближайшего препятствия. Как и в описанном раньше случае, эти результаты могут быть искажены гауссовым шумом. Как правило, предполагается, что погрешности для различных направлений лучей независимы и заданы в виде идентичных распределений, поэтому имеет место следующая формула; На рис.
25.б, б показан пример четырехлучевого дальномера и двух возможных поз робота, одну из которых на полном основании можно рассматривать как позу, в которой были получены рассматриваемые результаты измерения дальностей, а другую — нет. Сравнивая модель измерения дальностей с моделью отметок, можно убедиться в том, что модель измерения дальностей обладает преимушеством в том, что не требует идентификации отметки для получения возможности интерпретировать результаты измерения дальностей; и действительно, как показано на рис. 25.6, б, робот направлен в сторону стены, не имеющей характерных особенностей. С другой стороны, если бы перед ним была видимая, четко идентифицируемая отметка, то робот мог бы обеспечить немедленную локализацию.
В главе 15 описаны фильтр Калмана, позволяюший представить доверительное состояние в виде одного многомерного гауссова распределения, и фильтр частиц, который представляет доверительное состояние в виде коллекций частиц„соответствующих состоянию. В большинстве современных алгоритмов локализации используется одно из этих двух представлений доверительного состояния робота, (х, ~ ~„„~...,). Локализация с использованием фильтрации частиц называется 'з.
локализапией Монте-Карло, или сокращенно МС1. (Моп(е Саг!о 1.оса1)ха(юп). Алгоритм МСЬ идентичен алгоритму фильтрации частиц, приведенному в листинге 15.3; достаточно лишь предоставить подходящую модель движения и модель восприятия. Одна из версий алгоритма, в которой используется модель измерения дальностей, приведена в листинге 25.1. Работа этого алгоритма продемонстрирована на рис. 25.7, где показано, как робот определяет свое местонахождение в офисном здании. На первом изображении частицы распределены равномерно согласно распределению априорных вероятностей, показываюшему наличие глобальной неопределенности в отношении положения робота.
На втором изображении показано, как поступает первый 1200 Часть ЪЧ]. Общение, восприятие и осуществление действий ряд результатов измерений и частицы формируют кластеры в областях с высоким распределением апостериорных доверительных состояний. А на третьем изображении показано, что поступило достаточное количество результатов измерений, чтобы переместить все частицы в одно место. Листинг 25.1. Алгоритм локализации Монте-Карло, в котором используется модель восприятия результатов измерения дальностей е учетом наличия независимого шума гипсезоп мопсе-сат1о-ьоса11гасьоп(а, г, )у, тес)е1, лир) кееигив множество выборок о ьпривн: а, предыдушая команда приведения робота в движение в, результаты измерения дальностей с м отсчетами гг,.,.,г„ Ы, количество сопровождаемых выборок тобе1, вероятностная модель среды с данньдчи о предыдушей позе Р(хо), моделью движения Р(к~[хо,ло) и моделью шума для датчика расстояний Р(я]Л) лар, двухмерная карта среды ввавьс: Я, вектор выборок с размером )Ч, первоначально вырабатываемый из Р(Уя) 1оса1 чаг1аЬ1ее: ы, вектор весов с размером и гог 1 = 1 Ео Ы Е(о Я[1] < — выборка из Р(Хь[Ха=5[1] Ль=а) М[1] ь — 1 яок у = 1 Ео М Е(о г ь- лхасс-ааппе(у,я[1],тар) м(1] ь- и[1] р(л=г,[я=г) Л < — Ие1д)зеес)-яашр1е-н1пй-яер1асешепе(Ь[, я, у) кевигп ь" Е)це один важный способ локализации основан на применении фильтра Калмана.
Фильтр Калмана представляет апостериорную вероятность Р(Х,!вюе а...,) с помощью гауссова распределения. Среднее этого гауссова распределения будет обозначено р, а его ковариация — Ею Основным недостатком использования гауссовых доверительных состояний является то, что они замкнуты только при использовании линейных моделей движения Е и линейных моделей измерения уь В случае нелинейных г или )з результат обновления фильтра обычно не является гауссовым. Таким образом, алгоритмы локализации, в которых используется фильтр Калмана, 'в. лииеаризуют модели движения и восприятия.
Линеаризацией называется локальная аппроксимация нелинейной функции с помо)цью линейной. !203 Глава 25. Робототехника Составление карты До сих пор в этой главе рассматривалась задача локализации одного объекта. Но в робототехнике поиск часто осуществляется в целях локализации сразу нескольких объектов. Классическим примером такой задачи является составление карты с помощью робота. Представьте себе робота, которому не дана карта его среды. Вместо этого он вынужден составлять такую карту самостоятельно. Безусловно, человечество добилось потрясающих успехов в искусстве составления карт, описывающих даже такие крупные объекты, как вся наша планета.
Поэтому одна из задач, присущих робототехнике, состоит в создании алгоритмов, позволяющих роботам решать аналогичную задачу. В литературе задачу составления карты роботом часто называют задачей Ъ.одновременной локализации и составления карты, сокра)ценно обозначая ее как Я.АМ (Б)пш1)апеоцз Еоса1(га()оп Ап() Марр)пя). Робот не только обязан составить карту, но и должен сделать это, изначально не зная, где он находится. Я.АМ вЂ” одна из наиболее важных задач в робототехнике.
Мы рассмотрим ту версию этой задачи, в которой среда является фиксированной. Даже этот более простой вариант задачи с большим трудом поддается решению; но положение становится значительно сложнее, когда в среде допускается возникновение изменений в ходе перемещения по ней робота. С точки зрения статистического подхода задача составления карты сводится к задаче байесовского алгоритмического вывода, так же как и локализация.
Если, как и прежде, карта будет обозначаться через ж, а поза робота во время с — через х„ то можно переформулировать уравнение 25.1, чтобы включить данные обо всей карте в выражение для апостериорной вероятности: в(к„,,л(~ а,,., а,,) и Р(а~+1(к~+1,и) Р(х, Пх„а,) Р(х„и~акт,а1:т 1) с)х, На основании этого уравнения фактически можно сделать некоторые благоприятные для нас выводы: распределения условных вероятностей, необходимые для включения данных о действиях и измерениях, по су)цеству являются такими же„как и в задаче локализации робота. Единственная предосторожность связана с тем, что новое пространство состояний )пространство всех поз робота и всех карт) имеет гораздо больше измерений.
Достаточно представить себе, что принято решение изобразить конфигурацию всего здания с фотографической точностью. Для этого, повидимому, потребуются сотни миллионов чисел. Каждое число будет представлять собой случайную переменную и вносить свой вклад в формирование чрезвычайно высокой размерности пространства состояний.
Эта задача еше в большей степени усложняется в связи с тем фактом, что робот может даже не знать заранее о том, насколько велика его среда. Это означает, что ему придется динамически корректировать размерность м в процессе составления карты. По-видимому, одним из наиболее широко применяемых методов решения задачи БЕАМ является ЕКР. Обычно этот метод используется в сочетании с моделью восприятия данных об отметках и требует, чтобы все отметки были различимыми. В предыдущем разделе апостериорная оценка была представлена с помощью гауссова распределения со средним )), и ковариацией Х,.
При использовании для решения 1204 Часть У)1. Общение, восприятие и осуществление действий задачи Я.АМ подхода, основанного на методе ЕКЕ, это распределение апостериорных вероятностей снова становится гауссовым, но теперь среднее р„выражается в виде вектора с гораздо большим количеством измерений. В нем представлена не только поза робота, но и местонахождение всех характеристик (или отметок) на карте.
Если количество таких характеристик равно п, то вектор будет иметь размерность 2 пь3 (два значения требуются для указания местонахождения отметки и три — для указания позы робота). Следовательно, матрицаХ, имеет размерность (2п+3 ) х (2п+3 ) и следующую структуру: (25.2) В этом уравнении Ххх — ковариация данных о позе робота, которая уже рассматривалась в контексте локализации; Ххя — матрица с размерами Зх2п, которая выражает корреляцию между характеристиками на карте и координатами робота. Наконец, Х~ — это матрица с размерами 2пх2п, которая задает ковариацию характеристик на карте, включая все парные корреляции. Поэтому потребность в памяти для алгоритмов, основанных на методе ЕКЕ, измеряется квадратичной зависимостью от п (количества характеристик на карте), а время обновления также определяется квадратичной зависимостью от п.
Прежде чем перейти к изучению математических выкладок, рассмотрим решение задачи по методу ЕКГ на графиках. На рис. 25.10 показано, как робот движется в среде с восемью отметками, расположенными в два ряда по четыре отметки каждый. Первоначально робот не имеет информации о том, где находятся отметки. Предполагается, что каждая отметка имеет другой цвет, и робот может надежно отличать их друг от друга. Робот начинает двигаться влево, в заранее заданном направлении, но постепенно теряет уверенность в том, есть ли у него достоверная информация о своем местонахождении. Эта ситуация показана на рис. 25.10, а с помощью эллипсов погрешности, ширина которых возрастает по мере дальнейшего передвижения робота. Движущийся робот получает данные о дальности и азимуте до ближайших отметок, а эти наблюдения используются для получения оценок местонахождения таких отметок.
Естественно, что неопределенность в оценке местонахождения этих отметок тесно связана с неопределенностью локализации робота. На рис. 25.10, б, в показано изменение доверительного состояния робота по мере того, как он продвигается в своей среде все дальше и дальше. Важной особенностью всех этих оценок (которую не так уж легко заметить, рассматривая приведенные графические изображения) является то, что в рассматриваемом алгоритме поддерживается единственное гауссово распределение по всем оценкам. Эллипсы погрешностей на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
