За рубежом основные ссылки делаются на работы Брукса и Хатиба, которые вышли в свет в 1985 году [6, 7]. Следует отметить, что в Японии подобные разработки были выполнены сотрудниками фирмы Hitachi, Ltd. в 1984 году [9]. Подобные же алгоритмы использовались и при трассировке печатных плат в 1967 году (см. [8], в которой дана ссылка на более раннюю работу 1948 года). Для того, чтобы проследить эволюцию архетипа основной идеи метода, ниже приводится историческая справка о разработках, имеющих отношение к методу потенциалов в задачи выбора пути.

В данной работе исследованы модификации алгоритма, изложенного в [1]. При этом рассмотрены следующие направления модификации исходного алгоритма:

1) Исследованы степенная и показательная функции отталкивания от препятствий и влияние их на результирующий путь мобильного робота (МР). Для оценки эффективности пути использовалась функция отклонения вектора направления движения от вектора направления на цель.

2) Проанализированы возможности использования метода потенциалов для управления распределенной мобильной системой (РМС). Исследовано пять способов организации такого движения:

движение по схеме «цепь». В этом случае сила притяжения цели действует на «лидера», и каждый МР «притягивается» к впереди идущему;

движение типа «гонка за лидером». В этом случае все элементы РМС «притягиваются» к «лидеру», который, в свою очередь, «притягивается» к целевой точке;

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

движение типа «схождение». В этом случае «лидер» собирает все элементы РМС в компактную группу;

организация движения типа «свободный поиск». В этом случае сила притяжения к цели отсутствует, и каждый элемент РМС движется в свободном от препятствий направлении.

Первые два режима используются для организации передвижения РМС, последние три - для информационного исследования среды.

Основное отличие нового алгоритма от изложенного в [1] состоит в том, что в [1] непосредственно вычислялось расстояние до каждого из препятствий i непосредственно, а в новом алгоритме используется имитатор дальномерной системы. Полученный массив дальностей в некотором секторе в дальнейшем подвергается логической фильтрации для построения оценок величин i.

Наряду с указанным названием - метод потенциалов (Potential Field Approach), он имеет следующие названия: способа «искусственных потенциальных полей» (artificial potential fields), «полей виртуальных сил» (virtual force field - VFF), «гистограммы векторных сил» (vector field histogram-VFH) и др. Суть этого метода, напомним, заключается в том, что путь строится на основе решения специального «уравнения движения», в которое входят «сила притяжения к цели», «силы отталкивания от препятствий» и, возможно, некоторые другие «силы». При ссылке на этот метод в качестве пионерских упоминаются работы 1985-1986 гг. [6,7]. Вместе с тем работа фирмы Хитачи по управлению МР, в которой использованы идеи «силового поля», выпущена в 1984 г. [9]. В [1] опубликовали результаты подобного исследования в ИПМ АН СССР в 1974 г. Вместе с тем использование подобных физических аналогий при трассировке электронных плат уходит корнями вглубь 50_х годов [8]. Правда, вычислительные аспекты при этом имеют свою специфику.

Сам архетип идеи движения в поле «информационных» (виртуальных) сил восходит к работам 30-40-х годов одного из виднейших представителей гештальтпсихологии Курта Левина. Он выступил с идеей применения в психологии концепции физического поля для описания поведения и конфликтных ситуаций при взаимодействии индивида с окружающим миром [3]. Современные психологи критикуют К. Левина за физикализм концепции, акцент на динамический аспект в ущерб содержательному и многое другое. Вместе с тем в указанных работах К. Левина можно почерпнуть немало интересного. Экспериментальный материал, подтверждающий разработанную концепцию, был получен в основном при наблюдении за детьми разного возраста и документирован посредством киносъемок.

Все они имеют аналоги при использовании метода потенциалов для управления МР.

На начальном этапе исследований в ИПМ рассматривались препятствия в виде окружностей. Подобное представление после результатов работ Koditschek с соавторами [4, 5] можно считать основным. Сила притяжения к цели полагалась постоянной по модулю и направленной к точке цели. Сила отталкивания от i_ого препятствия fi зависела от аргумента Ri /ri, где Ri - радиус i_ой окружности, ri -расстояние от центра i_ой окружности до движущейся точки. fi считалась направленной от центра окружности. Траектория («локомоция») получалась в результате интегрирования уравнений движения второго порядка, так как ускорение, действующее на движущуюся точку, определялось суммой указанных сил. В ходе исследований выяснилось, что инерционность, заложенная в указанную модель, приводит к тому, что траектория движения становится малоприемлемой (препятствие «отбрасывает» движущуюся точку очень сильно и траектория получается чересчур «изрезанной». Для того, чтобы избавиться от этого недостатка и сделать метод годным для случая аппроксимации контуров препятствий другими способами, было предпринято следующее. Во-первых, стали использоваться уравнения движения первого порядка (т.е. действующие силы определяют скорость, по сути дела речь идет об аналоге простого градиентного спуска). Во-вторых, сила отталкивания стала определяться аргументом, равным расстоянию до препятствия. При этом форма контура препятствия произвольна, а для приведенного выше примера это разность ri - Ri. Направлена эта сила в сторону от ближайшей точки препятствия. В ходе исследований было признано рациональным в случае наличия нескольких препятствий использовать функции от указанного аргумента x типа x-k или e-cx, которые быстро убывают с расстоянием. При этом коэффициенты k и c могут быть варьируемыми параметрами.

Следует особо подчеркнуть, что, варьируя параметры k и c при определении сил отталкивания, можно получать траектории для движения нескольких МР. Если ввести в этом процессе запаздывание, то можно получить режим «следования друг за другом».

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

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

Анализируя разнообразие зарубежных работ по методу потенциалов, можно выделить два интересных направления.

Первое является попыткой ответить на вопрос: можно ли эффективно задавать силовое поле так, чтобы отсутствовали устойчивые точки равновесия в принципе. Достаточно очевидно, что в общем случае ответ на этот вопрос положительный. Действительно, функция потенциала в точке x, равная минимальной длине допустимого пути от x к g - точке цели, задает такое поле. Однако эту функцию в общем случае считать весьма непросто. Koditschek с соавторами в серии работ [4,5] и др. предложили свой подход к этой проблеме, который хотя и отличается оригинальностью, в итоге, оказывается, вряд ли намного проще способа, указанного выше. Вначале рассматривается «Сферический мир». Для плоскости это окружности-препятствия, окруженные окружностью-рамкой. В этом мире результирующая сила определяется не как сумма сил, действующих от различных препятствий, а как произведение таких сил. Эти два положения позволяют избежать наличия точек равновесия силового поля, что зафиксировано теоретически.

Далее строится последовательность диффеоморфизмов. Поначалу между «сферическим миром» и «звездным миром» - в котором препятствия представляют многоугольники особого вида. Затем происходит переход от «звездного мира» ко все более и более» общим мирам». При этом диффеоморфизм сохраняет «безособость» получающихся при поэтапных переходах от «сферического мира» силовых полей. Однако необходимо отметить, что демонстрируемые иллюстрации подобных полей для более общих постановок, чем «сферический мир», позволяют утверждать, что для них весьма характерны «овражные эффекты». Следовательно, при фиксированном значении шага возможны в лучшем случае эффекты типа «информационного дребезга», а также зацикливание в ложном экстремуме. Возможно, что именно поэтому авторы не демонстрируют построение траекторий движения, а только картинки линий уровня.

Второе направление, берущее начало от работ исследователей Оксфордского университета, заключается в следующем. Сам МР представляется не точкой, а отрезком или прямоугольником. Это позволяет рассчитывать не только результирующую силу, действующую на МР, но и момент сил, т.е. управлять ориентацией.

Ниже приводятся некоторые ранее не публиковавшиеся результаты исследования алгоритмов, основанных на методе потенциалов, полученные в ИПМ в 70 - 80 х гг. прошлого века.

Критическое отношение шага к радиусу обходимой окружности для появления информационного дребезга 0.1 для степенной функции и 0.3 для экспоненты.

Подобным образом исследовалось влияние информационного дребезга для плавного контура (окружность радиуса 1) при обходе методом потенциалов.

В статье [9] описывается мобильный робот (МР), разработанный фирмой Hitachi, Ltd. (Япония) в 1984 г., в котором, в частности, для реализации управления автономным перемещением, был использован так называемый «метод потенциального наведения». Он предусматривает оснащение робота дальномерами, измеряющими расстояние до объектов в рабочей зоне. Принцип этого метода схематически представлен на рис. 3, где обозначено: Xk - точка нахождения робота в текущий момент времени; tk - направление передвижения робота до текущего момента времени; tk+1 - направление передвижения робота в текущий момент времени; XG - целевая точка; g - вектор, направленный к целевой точке; rmax - максимальный радиус; ri* - вектор, проведенный до объекта, находящегося в рабочей зоне робота.

Страницы: 1, 2, 3, 4, 5