Исследование явления "интерференции" дальномерных измерений для мобильного робота

( The study of phenomena "interferences" of distance-measuring measurements for mobile robot
Preprint, Inst. Appl. Math., the Russian Academy of Science)

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

Априорная оценка надежности алгоритмов системы управления (СУ) мобильного робота (МР) определяется в основном составом предположений о характеристиках среды, эффективностью алго­ритмов в случае выполнения этих предположений и характером поведения СУ МР в случае нарушения этих предположений (последнее имеет большое значение для обеспечения живучести МР). Одним из важных обстоятельств, здесь является выполнение условий согласо­вания (УС) информационных и двигательных параметров МР [1-5].

Алгоритму информационного обеспечения движения МР при этом соответс­твует несколько неравенств, связывающих функции параметров, ха­рактеризующие измеритель (высота положения, частоты сканирова­ния, угловые скорости вращения блока обзора и т.п.), с парамет­рами, характеризующими движение робота (скорость движения, па­раметры участка пути и т.п.). При выполнении этих неравенств га­рантируется выполнение текущей информационно-двигательной задачи (обнаружение в движении препятствий заданных типов и размеров слежение в движении за ориентиром и т. п.). В случае нарушения какого-либо из неравенств необходимо либо менять алгоритм, либо соглашаться с ухудшением качества и надежности работы СУ МР.

Учет УС необходим как на этапе проектирования, так и для уже построенных МР. В обоих случаях основу методики составляют расчетные случаи движения.

В работе рассмотрен расчётный случай цилиндрической постановки осмотра зоны обзора при стоящем и движущемся МР и на основе численного моделирования получены оценки результирующих горизонтальной и вертикальной дискретностей осмотра. Введено понятие асимптотически оптимального осмотра.

Приведены основные УС для МР. В разработке четвёртого типа УС принимал активное участие Ахтёров А.В.

В работе рассматривается случай равномерной развёртки дальномерных систем по углу обзора (углу места).

1. ОСНОВНЫЕ ТИПЫ УСЛОВИЙ СОГЛАСОВАНИЯ

При движении МР или распределённой мобильной системы (РМС) необходима организация адекватного информационно-двигательного поведения для решения функциональной задачи. Это требует согласования информационно-двигательных параметров и синхронизации движения элементов РМС. Существуют четыре типа УС информационно-двигательной активностей (ИДА) МР и элементов РМС [5]:

1)       УС в ближней зоне осмотра;

2)       УС при осмотре дальнего плана;

3)       УС при планировании навигационных измерений в соответствии со структурной особенностью среды.

Содержание и последствия их нарушения отражены в таблице 1.

Четвёртый тип УС для синхронизации движения элементов РМС в общем виде выглядит следующим образом [6]:  P(x, y, x), где , Р – предикат. Пусть теперь V - носитель террайна, - видимая окрестность множества , а  - открытая граница множества, т.е. те участки границы множества , через которые МР может покинуть . Пусть - положение -го МР в момент времени . Тогда такт работы системы управления РМС заключается в выборе подцелей движения для элементов РМС из множества: .

Таблица 1. Таблица нарушений  УС.

Пусть ставятся следующие задачи:

1.        Достижимость целевой точки и аналог информационного обхода для конечного графа. Пусть  - множество вершин графа возможных перемещений. Время дискретно, - положения РМС.  - пройденные вершины графа возможных перемещений. Условие согласование выглядит следующим образом:

 (кванторная приставка - ).

2.        Информационный обход в общем случае. Пусть  - носитель террайна (графа с континуум рёбер вершин). В этом случае условие согласование выглядит следующим образом:

 (кванторная  приставка - ).

Следует особо отметить, что для этой задачи возможна запись УС в следующем виде: 

,

где  - время окончания ИО.

3.        Информационное блокирование – усиление УС информационного обхода

 (кванторная приставка-).

Это условие аналогично можно записать в виде:   

Следует особо подчеркнуть, что приведённые выше УС являются инвариантами для любого допустимого алгоритма данной функциональной задачи.

Примеры формул отражены в таблице 2.

Таблица 2. Формульное определение УС.

2. ЦИЛИНДРИЧЕСКИЙ ВАРИАНТ:

ГОРИЗОНТАЛЬНАЯ ДИСКРЕТНОСТЬ

Рассматривается движение робота по прямой со скоростью V и единственным углом обзора (углом развертки a, рис. 5). Пусть перед началом каждого из циклов осмотра система управления робота должна иметь информацию о расположенном перед ним участке местно­сти. Размер этого участка определяется конструктивными особеннос­тями робота.

Суть явления «интерференции» при повторных осмотрах заключается в том, что при достаточно медленном движении МР и соответствующей развёртке возможен такой повторный осмотр, при котором положение точек повторной измерительной сети не совпадает с измерительной сетью, полученной при предыдущем цикле осмотра, что ведёт к уменьшению величины разброса результирующей измерительной сети.

Ниже приведены необходимые формулы для исследования горизонтальной и вертикальной дискретности осмотра [2].

Рассмотрим условия согласования для гарантированного обнаружения препятствия типа ямы и выступа в двухмерном случае.

Пусть робот движется со скоростью V = const вдоль горизонтальной базовой линии ОXA, а измеритель дальности расположен на высоте H = const над этой линией. Согласованная периодическая развертка с периодом T₀ заключается в проведении измерений при изменении угла развертки a в пределах , . Зона обзора задается тремя параметрами:

R - начальное расстояние до зоны обзора от робота при ;

L - длина зоны обзора;

1 - длина перекрытия двух соседних зон обзора.

Если в момент t = 0 измеритель наведен в точку x_a = R, , робот находится в точке х_a = 0, то по завершении периода развертки в момент t = T₀  наведение осуществляется в точку x_a = R + L – l, , робот находится в точке VT₀. Отсюда следует, что период развертки определится как .

Могут существовать различные программы изменения угла развертки . В собственной системе координат (ССК) расстояние до точки измерения х_с по горизонтали меняется в пределах , где , . Время подъёма измерительного луча принимается равным cT₀. Если с = 0.5, то число измерений при подъеме луча равно числу измерений при его опускании.

Пусть измерения проводятся с частотой ,  - расстояния между измеряемыми на базовой линии точками в ССК робота, а  - то же расстояние в абсолютной системе координат (АCK). Тогда . При подъеме луча  > 0, при опускании  < 0.

Ниже развертка предполагается монотонной, т.е. за весь период развертки переключение знака производной угла развертки происходит только один раз. Положим , где t - целое число в диапазоне от 1 до . Измерения производятся в моменты t. Нетрудно получить, что

,

где

Пусть L_x,  - координата в зоне обзора текущего периода. Если , то вся зона обзора разбивается на три участка:

А.   ;

Б.    ;

В.    .

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

Пусть . Тогда нетрудно видеть, что число периодов, в течение которых осматривается данная точка в АCК, равно , где [.] - целая часть.

Перейдем теперь к рассмотрению наиболее часто встречающегося и наиболее простого в реализации типа развертки - развертки с постоянной скоростью по углу обзора. В этом случае , с = 0. 5. Отсюда следует, что

.

При других типах разверток w₀ сохраняет смысл средней скорости вращения угла обзора.

Ясно, что заведомо .

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

Предположим, что возможны два типа препятствий: ямы шириной не менее e₀ и вертикальные выступы высотой не менее h₀ , ширина которых может быть сколь угодно малой. Чтобы гарантированно обнаружить яму, достаточно выполнения условия

,

или в линеаризованном виде достаточна оценка:

.

При нарушении условия возможна ситуация, когда яма обнаружена, не будет.

Для того, чтобы обнаружить вертикальный выступ высотой h₀  (независимо от ширины), достаточно выполнения условия

,

где  - смещение  за счет изменения угла  между измерениями, при этом при подъеме луча  > 0, а при опускании < 0. Отсюда следует грубая оценка

.

Адекватность данной формулы требует дополнительных исследований методами математического моделирования.

При подъеме луча  справедлива формула

.

Положив , получим соответственно

или

.

Во время обратного хода луча  уменьшается от  до R. Наложим при этом требование, чтобы измерения производились только в зоне обзора. Это приводит к условию

,

или в линеаризованной достаточной форме

.

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

и заведомо будет меньше, чем в случае подъема луча. Аналогичный вывод можно сделать и об .

При определении качества «интерференции» использовались пороги, описание которых приведено в таблице 3.

Таблица 3. Основные пороги горизонтальной дискретности.

        Ниже приведены результаты экспериментов по исследованию явления «интерференции» в случае горизонтальной дискретности.

3. ЦИЛИНДРИЧЕСКИЙ ВАРИАНТ:

ВЕРТИКАЛЬНАЯ ДИСКРЕТНОСТЬ

Суть алгоритма, рассчитывающего вертикальную дискретность, заключается в следующем. В каждой точке сканирования а) производится пост-роение «столбика» (вертикаль нулевой ширины), высота которого вычисляется по формуле h =e ctg a; б) по возможности, производится усечение ранее построенных «столбиков»; в) по окончании эксперимента находится «столбик» наибольшей длины, который и определяет вертикальную дискретность.

Так же был использован ещё один алгоритм. Отличие этого алгоритма от первого заключается в шаге а). В данном случае он заменяется наложением сетки на зону движения мобильного робота. Сетка состоит из «столбиков» высоты равной высоте мобильного робота и имеет шаг q.  Тогда в каждой точке сканирования необходимо проводить только лишь усечение столбиков сетки (возможно неоднократное). Положительной чертой данного алгоритма является надёжность, отрицательной – погрешность, зависящая от шага q.

Была проведена оценка полученных результатов для горизонтальной дискретности по параметру e₀ = VDt+e (дискретность осмотра после 0.5 периода осмотра, т.е. без «интерференции), для вертикальной - по аналогичному параметру h₀.

Особо следует отметить,  что пороги горизонтальной дискретности переводятся в соответствующие пороги вертикальной дискретности в соответствии с приближённой формулой приведённой в предыдущем пункте.

4. ПОНЯТИЕ АСИМПТОТИЧЕСКИ-ОПТИМАЛЬНОГО ОСМОТРА

Асимптотически-оптимальный осмотр характеризуется эффектом стремления дискретности осмотра к нулю при увеличении количества периодов осмотра. Этот эффект наблюдается при стоящем МР лишь в случае использования в дальномерной обзорно-информационной системе сканирующего зеркала, а не матрицы или линейки лазеров. Ниже приведены графики, иллюстрирующие вышесказанное, а на таблице 4 приведены данные о лазерных дальномерах для шагающих роботов [7].

Таблица 4. Характеристики лазерных измерительных систем.

На рис. 9 дискретность осмотра достигла оптимального значения на третьем периоде осмотра. Это объясняется наложением точек сканирования после третьего периода, на измерительную сеть полученную на первых трёх периодах осмотра.

Для того, чтобы не допустить подобного эффекта следует установить значение угловой скорости, к примеру, на 31,4 ˚/c.

На рис. 10 на двадцатом периоде дискретность осмотра равна 0,05224 м., при этом на сотом периоде она достигла значения 0,01107 м., что свидетельствует о стремлении дискретности к нулю при неограниченном увеличении количества периодов осмотра.

Проведём аналогичные исследования для лабораторного макета шагающего робота.

Получен аналогичный результат. На двадцатом периоде дискретность осмотра равна 0,02272 м., на сотом - 0,00298 м.

5. ТЕОРЕМА ОБ ОПРЕДЕЛЕНИИ ДИСКРЕТНОСТИ ОСМОТРА

НА ПЛОСКОСТИ

Горизонтальная дискретность осмотра на плоскости может определяться различными способами, например с помощью диаграмм Вороного [2]. В данном пункте доказана теорема (анонсированная в [2]), позволяющая рассчитывать эту дискретность альтернативным способом.

Пусть Ω - замкнутый прямоугольник,  характеризующий зону обзора на плоскости, Q - конечная измерительная сеть,

размер ε - сети (ε = ε₀) Q в области Q.

Положим . Точки множества B будем называть экстремальными. Через  обозначается число элементов конечного множества М, или его длина, или площадь в случае, если они существуют.

Лемма 1. Пусть . Тогда

Доказательство. 1. Очевидно, что  в силу определения B. Пусть, ,  . Тогда . Пусть - точка измерительной сети, для которой

Далее положим

,

где  выбирается так, чтобы , а все точки трактуются как векторы в некоторой декартовой системе координат.

Тогда .

С другой стороны, . Последнее неравенство справедливо, если вместо  взять любой другой элемент из  в силу выбора . Таким образом, расстояние от точки  до множества Q (в общепринятом смысле) будет больше, чем , что противоречит определению последней величины. Полученное противоречие доказывает, что .

2. Пусть теперь ,   и - величина, аналогичная определенной выше, при этом минимум берётся по множеству . Проведем через середину отрезка  перпендикуляр; он, очевидно, пройдет через  и построим точку  на этом перпендикуляре, находящуюся  на расстоянии  от  в таком направлении, чтобы выполнялось неравенство  ( определяется аналогично п. 1). Нетрудно видеть, что при таком выборе расстояние от  до  также будет больше чем . Полученное противоречие доказывает, что .

Следствие. Из второй части доказательства следует, что любая экстремальная точка из  является центром окружности, описанной вокруг остроугольного треугольника, вершины которого суть точки из Q. Действительно, если это утверждение не выполняется, то в окружности радиуса  с центром в  можно провести диаметр, обладающий тем свойством, что на интервале одной из полуокружностей, на которые он делит исходную окружность, не будет точек из Q и рассуждение п.2 доказательства, проведенное для перпендикуляра к этому  диаметру останется в силе.

Лемма 2. Пусть и  . Пусть   - полуплоскость без точки z, границей которой является перпендикуляр к отрезку , проходящий через точку z. Если выполняется условие , то , где , .

Доказательство проводится аналогично доказательству предыдущей леммы, поскольку выполнение указанного условия в случае  позволяет построить точку , расстояние от которой до Q превосходит .

Следствие. Если зона обзора Ω есть многоугольник, то условие леммы выполняется для всех точек границы многоугольника, кроме его вершин. Кроме того, если экстремальная точка находится на границе зоны и не является вершиной многоугольника, то она расположена на перпендикуляре, проведенном через середину отрезка, конечные точки которого входят в . 

Результаты лемм резюмируем в виде теоремы о  типах экстремальных точек в зоне обзора (теорема «ТЭТ 3D»).

Теорема «ТЭТ 3D».  Для экстремальной точки реализуем только один из трёх вариантов:

1.     Если экстремальная точка находится внутри Ω, то она является центром окружности, описанной вокруг остроугольного треугольника, точки которого входят в измерительную сеть Q (Рис. 13 а).

2.     Если экстремальная точка расположена на границе Q и не является вершиной многоугольника, то она расположена на перпендикуляре, проведенном через середину отрезка, конечные точки которого входят в измерительную сеть Q (Рис. 13 б).

3.     Кроме того, экстремальная точка может быть расположена в вершине многоугольника Q (Рис. 13 в).

Приведенная теорема позволяет строить конечное   множество точек, которые являются   кандидатами   в   экстремальные   точки. Обозначим это множество через М.  Поскольку теорема исчерпывает все возможные типы экстремальных точек, то .  Из определений следует формула

.

Таким образом, данная теорема вместе с указанной формулой продуцируют конструктивный алгоритм нахождения величины ε - сети, образуемой конечной измерительной сетью Q в зоне обзора Ω на базовой плоскости. Этот алгоритм заключается в построении конечного множества  и определении  на основе этого множества. Нетрудно видеть, что вычислительная сложность алгоритма есть , где .

Схема алгоритма расчёта дискретности осмотра на плоскости на основе данной теоремы, представлена на рис 14.

	Рис 14. Алгоритм расчёта дискретности осмотра на плоскости

 

ЗАКЛЮЧЕНИЕ

Как показали численные эксперименты при «интерференции» возможно уменьшение дискретности измерений в несколько раз (по сравнению с максимальной дискретностью при одноразовом осмотре). При этом на стоящем МР возможно построение ассимтотически оптимального осмотра.

Приведены способы определения горизонтальной и вертикальной дискретности осмотра.

Для случая 3D приведена теорема об определении горизонтальной дискретности.

По результатам исследований может быть сделан вывод о необходимости учёта явления «интерференции» при планировании осмотра.

ЛИТЕРАТУРА

1.        Барбашова Т.Ф., Кирильченко А.А., Ярошевский В.С., Яшкичев И.В. Условия согласования информационно-двигательных параметров мобильного робота при осмотре среды. //Препринт ИПМ им. М.В. Келдыша АН СССР, 1988, №190

2.        Каргашин А.Ю., Кирильченко А.А., Ярошевский В.С. Определение характеристик дискретного осмотра среды мобильным роботом с использованием дальномерной информационной системы. // «Программирование прикладных систем», М.: Наука, 1992, с. 155-163

3.        Брагин В.Б., Камынин С.С., Кирильченко А.А., Охоцимский Д.Е. и др. Системы очувствления и адаптивные роботы. // М.: Машиностроение, 1985.

4.        Bezbogov S.A., Kirilchenko A.A., Platonov A.K., Pryanichnikov V.E., Yaroshevsky V.S. Path finding problem and information support of mobile robots in uncertainty. // “2nd IFAC conf. of IAV-95, Proc.”, Helsinki, 1995, pp 74-80

5.        Ionova J.N., Kiril’chenko A.A., Pavlovsky V.E., Platonov A.K., Pryanichnikov V.E. Conditions for coordination the information and motion activities of mobile robots //Preprints pf the 3rd IFAC symbon Intelligent Autonomous Vehicles, Madrid, Spain, March 25-27, 1988, v.1, pp 67-52

6.        А.В. Ахтёров, А.И. Белоусов, Ф.Р. Джегутанов, А.А. Кирильченко, Групповой поиск в лабиринте (Атлас расчётных случаев для задачи информационного блокирования) //М.: Препринт Ин-та прикл. матем. им. М.В. Келдыша РАН, 2002, №32.

7.        Okhotsimsky D.E., Platonov A.K., Kiril’chenko A.A., Lapshin V.V.,     Tolstousova V.G., Walking Machines. //”Advances in mechanics”, 1992, v.15, №1-2, pp. 39-70.