Российская Академия Наук
ОРДЕНА ЛЕНИНА ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ
им. М.В. Келдыша
А.К. Платонов, А.А. Кирильченко, М.А. Колганов
МЕТОД ПОТЕНЦИАЛОВ В ЗАДАЧЕ ВЫБОРА ПУТИ: ИСТОРИЯ И ПЕРСПЕКТИВЫ
Москва, 2001 г.
Платонов А.К., Кирильченко А.А., Колганов М.А., Метод потенциалов в задаче выбора пути: история и перспективы.
Аннотация
Метод потенциалов основывается на реализации движения мобильного робота в поле «информационных сил» («притяжение» к целевой точке, «отталкивание» от препятствий и т.п.). Рассмотрена история представлений подобного рода, начиная с «теории поля» К. Левина. Представлены результаты использования метода потенциалов для управления распределенной мобильной системой.
СОДЕРЖАНИЕ
1. Введение........................................................................................................ 3
2. Историческая справка................................................................................... 4
3. Современное состояние................................................................................. 8
4. Описание метода и его реализаций............................................................ 16
5. Использование метода для управления движением распределенной мобильной системы............................................................................................................ 19
6. Заключение.................................................................................................. 20
Литература...................................................................................................... 22
Иллюстрации................................................................................................... 24
Platonov A.K., Kiril’chenko A.A., Kolganov M.A. The potential field approach in the path finding problem: history and perspectives.
ABSTRACT
The potential field approach is based on the mobile robot motion in the field of “information forces” (“attraction” to goal point, “repulsion” from obstacles, etc.). The history of such representations beginning from the “field theory” of K. Levin is presented. The results of the potential field approach use for the distributed mobile system control are also presented.
Метод потенциалов в задаче выбора пути для мобильного робота (МР) был предложен А.К. Платоновым в 1970 году.
При этом рассматривается случай, когда робот снабжен достаточно точной навигационной системой, чтобы ее ошибками можно было пренебречь, и системе управления известны как координаты робота и измерительного устройства, так и ориентация сектора обзора и направление производящихся измерений в некоторой абсолютной системе координат (АСК). Робот во всех случаях представляет собой точку с предписанным вектором ориентации.
Суть метода заключается в следующем. Предположим, что цель имеет некоторый положительный заряд, препятствия заряжены отрицательно; местоположения цели и препятствий фиксированы. Пусть также имеется некоторая отрицательно заряженная точка, способная перемещаться. Поместим ее в исходную точку. Под действием сил подвижная точка будет притягиваться к цели и отталкиваться от препятствий, причем законы движения могут задаваться, в принципе, различными способами. Логично предположить, что при некоторых ограничениях на структуру местности и законы движения подвижной точки эта точка достигнет цели.
В зависимости от способа задания функций, можно получить трассы с обходом препятствий с той или иной степенью «риска» (величины приближения к препятствиям). Рассматриваемые ниже алгоритмы гарантируют от зацикливания в случае, когда контуры препятствий выпуклы. Метод может также использоваться для случая, когда препятствия разбиваются на группы, выпуклые оболочки которых не пересекаются.
За рубежом основные ссылки делаются на работы Брукса и Хатиба, которые вышли в свет в 1985 году [6,7]. Следует отметить, что в Японии подобные разработки были выполнены сотрудниками фирмы Hitachi, Ltd. в 1984 году [9]. Подобные же алгоритмы использовались и при трассировке печатных плат в 1967 году (см. [8], в которой дана ссылка на более раннюю работу 1948 года). Для того, чтобы проследить эволюцию архетипа основной идеи метода, ниже приводится историческая справка о разработках, имеющих отношение к методу потенциалов в задачи выбора пути.
В данной работе исследованы модификации алгоритма, изложенного в [1]. При этом рассмотрены следующие направления модификации исходного алгоритма:
1) Исследованы степенная и показательная функции отталкивания от препятствий и влияние их на результирующий путь мобильного робота (МР). Для оценки эффективности пути использовалась функция отклонения вектора направления движения от вектора направления на цель.
2) Проанализированы возможности использования метода потенциалов для управления распределенной мобильной системой (РМС). Исследовано пять способов организации такого движения:
a) Движение по схеме «цепь». В этом случае сила притяжения цели действует на «лидера», и каждый МР «притягивается» к впереди идущему.
b) Движение типа «гонка за лидером». В этом случае все элементы РМС «притягиваются» к «лидеру», который, в свою очередь, «притягивается» к целевой точке.
c) Движение типа «расхождения». В этом случае на МР, расположенные компактной группой или цепью, начинает действовать сила отталкивания от «лидера». МР «разбегаются», исследуя каждый свой участок.
d) Движение типа «схождение». В этом случае «лидер» собирает все элементы РМС в компактную группу.
e) Организация движения типа «свободный поиск». В этом случае сила притяжения к цели отсутствует, и каждый элемент РМС движется в свободном от препятствий направлении.
Первые два режима используются для организации передвижения РМС, последние три – для информационного исследования среды.
Основное отличие нового алгоритма от изложенного в [1] состоит в том, что в [1] непосредственно вычислялось расстояние до каждого из препятствий ri непосредственно, а в новом алгоритме используется имитатор дальномерной системы. Полученный массив дальностей в некотором секторе в дальнейшем подвергается логической фильтрации для построения оценок величин ri.
Наряду с указанным названием – метод потенциалов (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]. Современные психологи критикуют К. Левина за физикализм концепции, акцент на динамический аспект в ущерб содержательному и многое другое. Вместе с тем в указанных работах К. Левина можно почерпнуть немало интересного. Экспериментальный материал, подтверждающий разработанную концепцию, был получен в основном при наблюдении за детьми разного возраста и документирован посредством киносъемок. Имеет смысл привести четыре особенности поведения сил «психологического поля», выделенного К. Левиным [3]:
(1). "...сила поля исчезает (или по крайней мере сильно ослабевает) как только объект попадает в сферу "владений индивида".
(2). "... в некоторых случаях величина валентности [заряда] увеличивается с ее явной близостью. Это выражается как в продолжительности,
так и в интенсивности попыток к достижению цели".
(3). "... величина сил поля, которые соответствуют отрицательной валентности, уменьшаются намного быстрее с увеличением физического расстояния, чем это происходит с силами поля, соответствующими положительной валентности".
(4). Возможны колебания локомоций вблизи точек равновесия сил, которые называются также "годологическим конфликтом".
Все они имеют аналоги при использовании метода потенциалов для управления МР.
На начальном этапе исследований в ИПМ рассматривались препятствия в виде окружностей. Подобное представление после результатов работ Koditschek с соавторами [4,5] можно считать основным. Сила притяжения к цели полагалась постоянной по модулю и направленной к точке цели. Сила отталкивания от i-ого препятствия fi зависела от аргумента Ri /ri , где Ri -радиус i-ой окружности, ri -расстояние от центра i-ой окружности до движущейся точки. fi считалась направленной от центра окружности. Траектория ("локомоция") получалась в результате интегрирования уравнений движения второго порядка, так как ускорение, действующее на движущуюся точку, определялось суммой указанных сил. В ходе исследований выяснилось, что инерционность, заложенная в указанную модель, приводит к тому, что траектория движения становится малоприемлемой (препятствие "отбрасывает" движущуюся точку очень сильно и траектория получается чересчур "изрезанной". Для того, чтобы избавиться от этого недостатка и сделать метод годным для случая аппроксимации контуров препятствий другими способами, было предпринято следующее. Во-первых, стали использоваться уравнения движения первого порядка (т.е. действующие силы определяют скорость, по сути дела речь идет об аналоге простого градиентного спуска). Во-вторых, сила отталкивания стала определяться аргументом, равным расстоянию до препятствия. При этом форма контура препятствия произвольна, а для приведенного выше примера это разность ri – Ri. Направлена эта сила в сторону от ближайшей точки препятствия. В ходе исследований было признано рациональным в случае наличия нескольких препятствий использовать функции от указанного аргумента x типа x-k или e-cx, которые быстро убывают с расстоянием. При этом коэффициенты k и c могут быть варьируемыми параметрами.