«Штучний інтелект» 4’2010

535

6П

УДК 004.896

В.А. Плотников

Государственный университет информатики и искусственного интеллекта,

г. Донецк, Украина

1karies1@mail.ru

Анализ эффективности существующих

методов уклонения от столкновения

для мобильного робота

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

Проводится анализ эффективности существующих методов избежания столкновения и обхода препятствий

для мобильного робота.

Введение

В робототехнике принято представление о роботе как механизме, управляемом

центральным контроллером (мозгом), который постоянно обновляет свое представле-

ние об окружающем мире и вырабатывает план поведения, исходя из этого представ-

ления. Новая информация о мире поступает от сенсоров, например: осязания, света,

ультразвука и т.д. Мозг анализирует всю информацию, обновляет представление об

окружающей среде, а затем принимает решение о том или ином действии. Данный под-

ход сопряжен с определенными трудностями. Во-первых, он требует большого объема

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

очень сложная, т.к. мир меняется постоянно. Все действия выполняются с помощью

приводов и эффекторов. Первые обычно представляют собой некие двигатели, под-

соединенные к устройствам, непосредственно взаимодействующим с окружающим

миром – эффекторам. Примерами последних могут служить колеса или руки. При этом

иногда под приводами понимаются как сами приводы, так и эффекторы.

Целью данной работы является анализ эффективности существующих методов

уклонения мобильных роботов от столкновений для последующего использования

их в разработке систем предотвращения столкновения объектов.

Классификация существующих методов уклонения

роботов от столкновений

Наиболее общими движениями робота являются движения, связанные с обходом

объектов, для которых единственное ограничение состоит в том, чтобы робот не столк-

нулся с объектами в рабочем пространстве. Поэтому при разработке различных задач

важно планировать движения мобильного робота с учетом обхода препятствий. В раз-

ных областях были предложены различные алгоритмы обхода препятствий. Ниже кратко

изложим эти алгоритмы, предназначенные для обхода роботом препятствий в трех-

мерном пространстве.

Алгоритмы можно разделить на несколько классов:

Плотников В.А.

«Искусственный интеллект» 4’2010

536

6П

– гипотеза – тест;

– штрафная функция;

– метод скелетирования;

– нечеткая логика.

1. Раньше других был предложен метод гипотезы и теста, состоящий из трех ос-

новных шагов:

а) предлагается гипотеза относительно пути-кандидата между начальной и конеч-

ной конфигурациями мобильного робота при движении;

б) набор конфигураций вдоль этого пути тестируется на возможность столкно-

вений;

в) если столкновение оказывается возможным, с целью определения пути обхо-

да исследуется препятствие, которое может вызвать это столкновение.

Весь процесс повторяется для модифицированного движения.

Главное преимущество метода «гипотеза – тест» заключается в его простоте. Ос-

новными вычислительными операциями метода являются определение возможных стол-

кновений и модификация путей для предотвращения столкновений. Первая операция

равнозначна способности определять ненулевое геометрическое пересечение между

моделями манипулятора и препятствий. Эта возможность, как правило, имеется в боль-

шинстве систем геометрического моделирования. Вторая операция-модифицирование

предложенного пути может быть очень трудной. Обычные предложения модифика-

ции пути основываются на аппроксимации препятствий в виде замкнутых сфер. Эти

методы хорошо работают, когда препятствия расположены редко. Когда же простран-

ство заполнено объектами, попытки избежать столкновения с одним препятствием

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

столкновений может быть осуществлено более точно, если применить систему техни-

ческого зрения и/или другие системы очувствления [1].

2. Второй класс алгоритмов обхода препятствий основывается на определении

штрафной функции для конфигурации мобильного робота, с помощью которой коди-

руется наличие объектов.

Метод штрафных функций относится к численным методам решения задач ус-

ловной оптимизации. В данном случае исходная задача условной оптимизации преоб-

разуется в последовательность задач безусловной оптимизации путем введения штраф-

ных функций. Рассмотрим задачу условной минимизации вида

min,

)

(

>

x

f

}

,

1

,

0

)

(

:

{

r

i

x

g

R

x

X

x

i

n

=

?

?

=

?

.

На ее основе строится задача безусловной минимизации

min,

))

(

,

(

)

(

)

,

(

>

?

+

=

x

g

R

x

f

R

x

P

n

R

x

?

,

где

)

,

( R

x

P

? расширенная функция,

))

(

,

( x

g

R

?

? штрафная функция,

R

? штрафной параметр.

Задача условной минимизации

)

(x

f

заменяется последовательностью задач без-

условной минимизации

)

,

(

1

?

t

R

x

P

при t = 1, 2... При этом, исходя из заданной началь-

ной точки

]

0

[

x

, находится последовательность точек

...

,

]

2

[

]

1

[

x

x

, сходящаяся при опре-

деленных условиях к решению

*

x

исходной задачи. При минимизации расширенной

Анализ эффективности существующих методов уклонения...

«Штучний інтелект» 4’2010

537

6П

функции

)

,

(

1

?

t

R

x

P

, t = 1, 2..., исходной (начальной) точкой является

]

1

[

?

t

x

, а реше-

ние задачи безусловной минимизации

)

,

(

1

?

t

R

x

P

определяет точку

]

[t

x

.

Обычно для конфигурации, которая приводит к столкновениям, значение штрафа

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

Полная штрафная функция представляет собой сумму штрафов отдельных препят-

ствий, к которой иногда добавляется штрафной член отклонения от кратчайшего пу-

ти. Для каждой конфигурации мы можем вычислить значение штрафной функции и

оценить ее частные производные по отношению к параметрам конфигурации. На ос-

нове этой локальной информации с помощью функции поиска пути необходимо выб-

рать последовательность конфигураций. Решение должно соответствовать локально-

му минимуму штрафной функции, т.е. компромиссу между увеличением длины пути

и максимальным приближением к препятствиям.

Интерес к методам штрафных функций основан на том, что они обеспечивают

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

нако это справедливо лишь для робота с вращательной степенью свободы; в этом слу-

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

шинства реальных роботов, таких, как двухзвенный манипулятор, штрафную функцию

можно было бы определить через преобразование конфигурации препятствия в про-

странстве. В противном случае движения робота, уменьшающие значения штрафной

функции, не были бы безопасными. Различие между этими двумя типами штрафных

функций характеризуется тем, что движение вдоль уменьшающихся значений штраф-

ной функции является безопасным, в то же время подобное движение мобильного ро-

бота приводит к столкновению.

Иногда промежуточные методы используют штрафную функцию, которая удов-

летворяет определению потенциального поля. Градиент поля в точке робота интерпре-

тируется как сила отталкивания в этой точке, которая суммируется с силой притяжения,

действующей из конечного положения робота. Движение робота является результа-

том взаимодействия этих двух сил при наличии кинематических ограничений. Исполь-

зуя несколько точек робота, можно избежать столкновения.

Основным недостатком использования штрафных функций для планирования без-

опасных путей является точная локальная информация, которую они дают для поиска

пути. Попытки определения пути по локальным минимумам штрафной функции могут

привести к тупиковым ситуациям, когда дальнейший поиск пути становится невозмож-

ным. В этом случае алгоритм должен выбрать предыдущую конфигурацию и продол-

жить поиск в другом направлении. Такие точки возврата трудны для идентификации

на основе локальной информации. Поэтому полезно комбинировать метод штрафных

функций с более общим методом «гипотеза – тест». Штрафные функции более удобны

в тех случаях, когда требуются только небольшие модификации известного пути [2].

3. Алгоритмы скелетирования сводят свободное пространство робота к одномер-

ному представлению, для которого задача планирования пути становится проще. Та-

кое представление с меньшим количеством измерений называется скелетом простран-

ства конфигураций.

Пример применения метода скелетирования приведен на рис. 1: это – линия Во-

роного для свободного пространства, которая представляет собой геометрическое мес-

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

осуществить планирование пути с помощью линии Вороного, мобильный робот вна-

чале переходит из текущей конфигурации в точку на линии Вороного. Можно легко

Плотников В.А.

«Искусственный интеллект» 4’2010

538

6П

показать, что такую операцию всегда можно выполнить с помощью передвижения по

прямой в пространстве конфигураций. Затем мобильный робот следует по линии Во-

роного до тех пор, пока не достигнет точки, ближайшей к целевой конфигурации. На-

конец, робот покидает линию Вороного и движется к цели. И на этом последнем этапе

снова выполняется движение по прямой в пространстве конфигураций.

Рисунок 1 – Линия Вороного для свободного пространства

Один из примеров метода скелетирования: линия Вороного – это геометричес-

кое место точек, равноудаленных от двух или нескольких препятствий в пространстве

конфигураций.

Таким образом, первоначальная задача планирования пути сводится к поиску

пути на линии Вороного, которая обычно является одномерной (за исключением не-

которых частных случаев) и имеет конечное количество таких точек, в которых пе-

ресекаются три или большее количество одномерных кривых. Движение по линии

Вороного может не обеспечить получение кратчайшего пути, но обнаруженные пути

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

тода, основанного на использовании линии Вороного, состоят в том, что их сложно

применять в пространствах конфигураций с большими размерностями, кроме того,

при их использовании приходится совершать слишком большие обходные маневры, ес-

ли пространство конфигураций характеризуется широким размахом. К тому же может

оказаться сложным вычисление линии Вороного, особенно в пространстве конфигу-

раций, характеризующемся сложной формой препятствий [3].

4. Нечеткая логическая система производит однозначное преобразование векто-

ра входных сигналов в вектор выходных сигналов. Для этого преобразования исполь-

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

Входным и выходным сигналам в нечеткой логической системе соответствуют ло-

гико-лингвистические переменные, значения которых определяется термами-множест-

вами. База знаний нечеткой логической системы состоит из продукционных правил,

определяющих зависимость между входными и выходными термами-множествами,

и функций принадлежности, показывающих степень соответствия реальных величин по-

нятиям, определяемых термами-множествами.

Например, пусть имеется входной сигнал скорости V. Определим для логико-линг-

вистической переменной V три значения: «МАЛАЯ», «СРЕДНЯЯ» и «БОЛЬШАЯ».

Соответствия между реальными значениями скорости и значениями переменной V оп-

ределяются по их функциям принадлежности (рис. 2). Таким образом, диапазон скорос-

тей от 0,3 до 0,6 м/с с достоверностью 1 относятся к понятию «СРЕДНЯЯ». Скорости

Анализ эффективности существующих методов уклонения...

«Штучний інтелект» 4’2010

539

6П

0,2 м/с и 0,7 м/с к понятию «СРЕДНЯЯ» относятся с достоверностью 0,5. Скорости

0,1 м/с и ниже, равно, как 0,8 м/с и выше, к понятию «СРЕДНЯЯ» не относятся

(т.е. достоверность равна 0).

Рисунок 2 – Функции принадлежности по входной переменной

Весь диапазон возможных значений выходной переменной функциями принад-

лежности разбивают на несколько частей (рис. 3). Удельный вес некоторых выходных

функций принадлежности может доминировать над удельным весом других функций

принадлежности. Такие функции принадлежности будут доминировать при принятии

совместных решений по нескольким правилам.

Рисунок 3 – Функции принадлежности по выходной переменной

Достоинством технологии нечеткой логики является:

– возможность плавного перехода от одной категории к другой за счет формиро-

вания средневзвешенного результата, что позволяет существенно сократить число про-

дукционных правил по сравнению с экспертной системой;

– возможность объяснения результата в процессе отладки системы [4].

Математическая модель движения мобильного робота

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

колесами, электродвигателями для ведущих колёс. Схема мобильного робота показа-

на на рис. 4.

Рисунок 4 – Схема мобильного робота

Плотников В.А.

«Искусственный интеллект» 4’2010

540

6П

Составим кинематическую модель для мобильного робота.

)

(

*

2

2

1

V

V

K

V

+

=

,

)

(

*

2

2

1

V

V

K

?

?

=

?

,

V

y

*

sin

1

?

=

&

,

V

y

*

cos

2

?

=

&

,

?

?

=

&

.

где y

1

, y

2

– координаты робота на плоскости;

V – скорость робота;

V

1

– скорость левого ведущего колеса;

V

2

– скорость правого ведущего колеса;

?

– угловая скорость робота при поворотах;

?

– угол поворота робота в плоскости;

К – коэффициент передачи привода.

Для определения препятствия на мобильном роботе необходимо разместить

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

обнаружения основан на излучении в окружающее пространство электромагнитного

поля СВЧ диапазона и регистрации его изменений, вызванных отражением от объек-

та, движущегося в зоне чувствительности сенсора. Микроволновые активные сенсоры,

реализующие этот метод, относятся к классу детекторов движения. Перемещение объекта

приводит к появлению изменяющегося во времени отраженного сигнала. Здесь разли-

чают два эффекта: изменение пространственной картины стоячих волн и частотный

сдвиг отраженной от движущегося объекта волны (эффект Доплера). Принцип разме-

щения массива микроволновых сенсоров на мобильном роботе показан на рис. 5.

Рисунок 5 – Размещение массива микроволновых датчиков на мобильном роботе

Данные, получаемые от массива микроволновых датчиков, формируют картину

окружающего мира для мобильного робота. Датчики расположены таким образом, что-

бы охватить как можно большую площадь слева, впереди и справа от направления дви-

жения мобильного робота.

На основе данных, полученных от массива микроволновых сенсоров о препятст-

виях, находящихся около робота, можно построить навигационную систему. Разделим

навигационную систему на два блока:

а) блок движения к цели;

б) блок обхода препятствий.

Анализ эффективности существующих методов уклонения...

«Штучний інтелект» 4’2010

541

6П

а) Сформируем набор правил для блока движения к цели с помощью нечеткой

логики, используя правило «если, то».

ЕСЛИ необходимо двигаться к цели под углом – 45

0

, ТО движение «влево-вперед».

ЕСЛИ необходимо двигаться к цели под углом 0

0

, ТО движение «вперед».

ЕСЛИ необходимо двигаться к цели под углом +45

0

, ТО движение «вправо-вперед».

Выходом данного блока будет нечеткое множество направлений движения мо-

бильного робота.

б) База правил для блока обхода препятствий будет содержать пять правил, по

одному для каждого сенсора.

ЕСЛИ дистанция до сенсора –90

0

«близко», ТО движение запрещено

ЕСЛИ дистанция до сенсора –45

0

«близко», ТО движение запрещено

ЕСЛИ дистанция до сенсора 0

0

«близко», ТО движение запрещено

ЕСЛИ дистанция до сенсора +45

0

«близко», ТО движение запрещено

ЕСЛИ дистанция до сенсора +90

0

«близко», ТО движение запрещено.

Выходом блока обхода препятствий будет нечеткое множество запрещенных на-

правлений движения робота [5].

Выводы

После анализа методов уклонения роботов от столкновений становится понят-

ным, что использование лишь одного метода не является эффективным. Существующие

методы уклонения от столкновений роботов являются узконаправленными и зачастую

зависят от конфигурации робота либо от окружающей среды, в которой использует-

ся робот. В результате выполнения работы была предложена математическая модель

движения мобильного робота. Составлена схема размещения массива микроволно-

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

движения и обхода препятствий мобильным роботом.

Литература

1.

Аттетков А.В. Методы оптимизации : [учеб. для студ. втузов] / Аттетков А.В., Галкин С.В., Зару -

бин В.С. ? М. : Изд-во МГТУ, 2001. – 175 с.

2.

Харчистов Б .Ф. Методы оптимизации : [учебное пособие] / Б .Ф. Харчистов. – Таганрог : Изд-во

ТРТУ , 2004. ? 140 с.

3.

Карманов В.Г. Математическое программирование / В.Г. Карманов. – М. : Физматлит, 2000. – 250 с.

4.

Круглов В.В. Нечеткая логика и искусственные нейронные сети / Круглов В.В., Дли М.И., Голунов Р.Ю. –

М. : Физматлит, 2001. – 224 с.

5.

Плотников В.А. Стенд для исследования проблем построения и испытания системы предотвращения

столкновения объектов на основе использования массива микроволновых сенсоров / В.А. Плотников,

В.А. Санжаревский // Искусственный интеллект. – 2009. – № 4. – С. 283-287.

В.О. Плотніков

Аналіз ефективності існуючих методів у хилення від зіткнення для мобільного робота

У статті розглядається проблема планування руху мобільного робота з урахуванням обходу перешкод.

Проводиться аналіз ефективності існуючих методів запобігання зіткнення й обходу перешкод для

мобільного робота.

V.A. Plotnikov

Analysis of Efficiency of the Collision Avoidance Methods the Mobile Robot

In the article the problem of planning of movement of the mobile robot taking into account detour of obstacles

is

considered. The analysis of efficiency of existing methods of the collision avoidance and detour of obstacles for

the mobile robot is carried out.

Статья поступила в редакцию 14.06.2010.