Нейронные сети при планировании маршрута движения мобильного робота

Планирование поведения одно из направлений исследований по искусственному интеллекту. Основная задача этого направления поиск процедур, которые могли бы автоматически предлагать наикратчайший путь к достижению поставленной цели исходя из данной ситуации. Задачи такого типа оказались наиболее актуальными для роботов, действующих автономно. Сегодня ученые многих стран работают над проблемой расширения функциональных возможностей мобильных транспортных роботов. Типичным примером интеллектуальной задачи можно считать планирование поведения робота при транспортировке грузов. Процесс решения задачи сводится к выбору плана действий робота, направленных на достижение цели и поиск путей обхода препятствий, преодоления возникающих трудностей. Существует множество работ в области построения маршрута движения мобильного робота [1, 2, 3]. Это построение рабочего коридора, метод диафрагм, аппроксимация набора точек, com-объекты Excel (построение трендов), открытые методы Autocad (построение сплайна) и нейронные сети. Обзор показывает, что в настоящее время данное направление исследований развивается достаточно интенсивно. Но хотелось бы отметить, что у существующих методов, кроме нейронных сетей, очень низкое быстродействие.

Рассмотрим алгоритм использования нейронных сетей при планировании прохождения маршрута движения мобильного робота. Задача построения траектории на основе некоторого числа точек сводится к задаче классификации объектов. В данном случае входным вектором нейронных сетей будет служить множество точек, преобразованное в смешанное множество координат:

{ (x, y)| x, y є R}→{x’ | x’є R}.                            (1)

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

Рассмотрим общий алгоритм с фиксированным количеством ядер классов М . Классами в рамках данной работы будем считать названия моделируемых кривых. Ядром класса назовем наиболее общий набор описаний для всех представителей данного класса. Имеется в виду, что некоторый объект, который похож на все остальные, больше, чем каждый из них.

Количество ядер, в отличие от предложений авторов источников [4, 5, 6], может изменяться в процессе эксплуатации нейронной сети. При обучении число ядер остается постоянным.

Начальные значения ядер с¹,…, с^m могут выбираться случайными, одинаковыми или по другим эвристическим правилам.

Каждая итерация алгоритма состоит из двух этапов:

• 1.    Ищем такое разбиение т{р) объектов {х^р} на классы, чтобы минимизировать суммарную меру близости между объектами и ядрами их классов:

• 2.    При неизменном разбиении т (p) настраиваем ядра {с^m} так, чтобы в пределах каждого класса m 0 суммарная мера близости ядра этого класса и объектов, принадлежащих ему, была минимальной:

  для всех m 0 =1…М.

  
  

min{D = ^dx^p , c^mp }.                                (2)

p

Результат этапа создание функции т (р) , разбивающей объекты на классы.

minAD =  d^c P ( x^p , c m ^{( p} ))>

p:m(p) m0

Результат этого этапа – новый набор ядер {с^m}.

Формализация задачи. Выберем в качестве входных данных вектор параметров единственного объекта. Результатом работы сети будет код класса, к которому принадлежит предъявленный на входе объект. В нейросетях принято кодирование номером канала. Поэтому сеть будет иметь М выходов, по числу классов, и, чем большее значение принимает выход номер m 0 , тем больше «уверенность» сети в том, что входной объект принадлежит к классу m 0 . Полезно применить функцию активации

μ:

OUT =

e NET

NET eⁱ

i

тогда сумма выходов всегда будет равна единице при любых значениях сигналов NET i . Каждый выход можно будет трактовать как вероятность того, что объект принадлежит данному классу. Все выходы образуют полную группу, так как сумма выходов равна единице и объект заведомо относится к одному из классов.

Выберем евклидову меру близости. В этом случае ядро класса, минимизирующее сумму мер близости для объектов этого класса, совпадает с центром тяжести объектов:

с m °₌    ¹       X^x^p ,                                  (4)

N ⁽ m o ) p : m ( p )= m ₀

где N(m 0 )  число объектов x^p в классе m 0 .

При разбиении на классы должна быть минимизирована суммарная мера близости для всего множества {x^p} входных объектов:

D = Wfxp-cm(p) )2=Vp(x' хрЛ-Кхр cm(ph + (cm(p) cm(phlf51

D           (xi    ci   )        [(x , x ) 2(X , c )' (c     , c )] .

pip

Здесь расписано скалярное произведение. В этой сумме два слагаемых не зависят от способа разбиения и постоянны:

^ (cm(p),cm(P/l) = const,^ (xp ,xp ) = const.(6)

pp

Поэтому задача поиска минимума D эквивалентна поиску максимума выражения:

minD —» max^"^x-’c"m'p.

pi

Запишем вариант алгоритма классификации для поиска максимума этой функции:

• 1.    Цикл: для каждого вектора х^р {

• 2.    Цикл: для каждого m {

• 3.    Рассчитаем    x^pc^m = D^m,p

• 4.    Находим m₀ , для которого m₀: max { D m^p }.

• 5.    Относим объект к классу m 0 .

i

} // конец цикла.

^o    m

} // конец цикла.

Такой алгоритм легко реализуется в виде нейронной сети. Для этого требуется М сумматоров, находящих все D ^m,p , и интерпретатор, находящий сумматор с максимальным выходом.

Сумма     xpcm очень напоминает взвешенную сумму NET = w x , ii рассчитываемую формальным нейроном. Выберем xp в качестве входных сигналов (что мы, впрочем, уже сделали) и компоненты ядер cm в качестве весовых коэффициентов wijl. Тогда каждый формальный нейрон с числом входов, равным числу компонент во входном векторе, дает на выходе одну из сумм Dm,p.

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

Нейроны слоя Кохонена [7] генерируют сигналы D^m,p. Интерпретатор выбирает максимальный сигнал слоя Кохонена и выдает номер класса m , соответствующий номеру входа, по которому интерпретатором получен максимальный сигнал. Это соответствует номеру класса объекта, который был предъявлен на входе в виде вектора x^p.

Ядра с^m являются весовыми коэффициентами нейронов. Каждый нейрон Кохонена запоминает одно ядро класса и отвечает за определение объектов в своем классе, т.е. величина выхода нейрона тем больше, чем ближе объект к данному ядру класса.

Общее количество классов совпадает с количеством нейронов Кохонена. Меняя количество нейронов, можно динамически менять количество классов.

Нейроны Кохонена имеют линейную функцию активации. Если применить функцию μ, то выход слоя Кохонена можно трактовать как вероятность принадлежности объекта к каждому из классов. Но применение μ некорректно с точки зрения принципа локальности, так как вычисление этой функции активации требует знания всех выходов сети каждым из нейронов, а в реальной сети это не выполняется.

Входные векторы сети чаще всего нормируются: pp ^x      x^pили     ^x        x^p .                             (8)

|x^p |                         | x^p | ²

з

Возможны другие способы нормировки.

Задача обучения научить сеть активировать один и тот же нейрон для похожих векторов x^p на входе. Не важно, какой конкретно нейрон будет активирован.

Обычно начальные значения в нейронных сетях выбираются малыми случайными числами. Для слоя Кохонена такой выбор возможен, но имеет недостатки. Разумеется, если ядра классов нормированы, то и начальные значения нужно нормировать.

Если веса инициализируются случайными значениями с равномерным распределением, то возникает проблема. Когда ядра распределяются равномерно, то в областях пространства X, где мало входных векторов, ядра будут использоваться редко, так как мало будет похожих векторов. В тех областях, где входных векторов много, плотность ядер окажется недостаточной, и непохожие объекты будут активировать один и тот же нейрон, так как более похожего ядра не найдется. Для устранения проблемы можно выделять ядра в соответствии с плотностью входных векторов. Но распределение входных векторов часто бывает заранее неизвестно. В этом случае помогает метод выпуклой комбинации , рассмотренный ниже.

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

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

• 1.    Присваиваем начальные значения весовым коэффициентам.

• 2.    Подаем на вход один из векторов х^р .

• 3.    Рассчитываем выход слоя Кохонена D^m,p и определяем номер выигравшего нейрона т₀, выход которого максимален, m₀ :™^x { D m ^{, p} } .

• 4.    Корректируем веса только выигравшего нейрона m 0 :

w_m := w_m + a ( x^p ~ w - ) • m₀      m₀               m₀

Здесь коррекция записана в виде векторного выражения (вектор весов w нейрона m 0 имеет столько компонент, сколько их у входного вектора x^p ); v скорость обучения, малая положительная величина. Часто используют расписание с обучением, когда v = v(t) монотонно убывает. Требования к v(t) те же, что и в случае многослойного перцептрона. Веса корректируются так, что вектор весов приближается к текущему входному вектору. Скорость обучения управляет быстротой приближения.

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