СОДЕРЖАНИЕ

Введение ……………………………………………………………………..….3
1. “Гермес” – прототип пакета прикладных программ для
исследования алгоритмов выбора пути, основанных на
использовании метода потенциалов………….....….........…………………4
2. Сопряженные  толерантные  пространства ….…………………………4
3. Конечное  покрытие  террайна  классами  видимости …..……………5
4. Логика   слежения  .....……………………………………………………….7
5. Гибридный алгоритм С₁+A_МП ………………………………………………8
6. Моделирование движения МР на уровне отрезка …………………...10
7. Режим движения в лабиринте …………………………………………...11
Заключение …………………………………………………………………….12
Литература ……………………………………………………………………..13
Иллюстрации …………………………………………………………………..15

Введение

Использование метода потенциалов в задаче выбора пути для мобильного робота  (МР) было предложено А.К. Платоновым в 1970 году.

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

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

Подробно эти вопросы рассмотрены в работах [1-16]. В данной работе описано развитие алгоритмов, использующих метод потенциалов, для задачи управления распределенной мобильной системой (РМС). В начале описаны возможности прототипа пакета программ «Гермес» для исследования алгоритмов, основанных на использовании метода потенциалов. Затем для реализации схемы «плавающего» потенциала рассмотрены возможности сопряженных толерантных пространств и конечных покрытий террайна (среды, в которой действует РМС) классами видимости. Далее рассмотрены основные положения логики слежения одним элементом РМС за другими элементами РМС. Организация подобного слежения необходима для реализации управления в игре информационного взаимодействия, когда «белые» собирают информацию о среде, а «черные» следят за ними. Затем рассмотрен гибридный алгоритм, объединяющий возможности метода потенциалов с одновременным гарантированием от зацикливания без исследования сложных схем формирования потенциала без локальных минимумов, подобно тому, как это делается в [4,5]. В заключение работы приводятся результаты моделирование движения МР на уровне отрезка.

1. «Гермес» – прототип пакета прикладных программ для исследования  алгоритмов выбора пути, основанных на использовании метода потенциалов.

«Гермес» позволяет разрабатывать алгоритмы, использующие все возможности, описанные в [1], в том числе осуществлять изменение сил отталкивания от препятствий и притяжения к цели как на уровне функций, так и на уровне их параметров. Существенным дополнением является то, что «Гермес» позволяет проводить исследование поля сил, используя 4 основных представления:

-         цифровая карта рельефа поля сил (рис.1);

-         линии токов к целевой точки (рис.2);

-         дискретные линии токов (рис. 3);

-         линии уровня (рис. 4).

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

2. Сопряженные толерантные пространства

В соответствии с общепринятыми определениями, класс толерант-ности является аналогом понятия клики на графе [18]. Здесь следует напомнить, что отношение толерантности симметрично, рефлексивно, но, в общем случае, не транзитивно [19].  Известно, что основное информационно-двигательное отношение – отношение видимости – является отношением толерантности [19]. Аналогом класса толерантности в этом случае выступает класс видимости [21]. В соответствии с построениями Ю.А. Шрейдера и С.М. Якубович, сопряженным толерантным пространством называется пространство, элементами которого являются классы толерантности исходного пространства, и два элемента сопряженного пространства толерантны между собой, если их пересечение не пусто в исходном пространстве. [18,19]. Ю.А. Шрейдером указано, что в сопряженном толерантном пространстве можно выделять базис классов толерантности (соответственно, базис классов видимости) B ={K_a} [19]. Его определение таково (здесь и ниже “~” обозначает отношение толерантности или отношение видимости):

Базисом видимости называется подмножество классов видимости {Ka}, обладающее следующими свойствами:

(1) " x,y : x ~ y  Þ $ K_a  : x,y Î K_a ;

(2) из {K_a} нельзя удалить ни одного класса без потери свойства (1).

Основные типы классов видимости указаны в [21].

Теорема 1. Базис классов видимости имеет мощность континуум для любого террайна.

Доказательство.

Пусть на (x_i, y_i) наблюдается ситуация типа «класп» («замόк») [21] с вершиной P (см. рис. 7). Очевидно, что x_i видимо из y_i, поэтому из определения базиса классов следует, что для любой такой пары существует K_i Î B, при этом x_i, y_i Î K_i. Но очевидно, что x_i, y_i Î ¶K_i. Варьируя положение отрезка (x_i, y_i) относительно начального на некоторый угол Dj, можно получить континуум таких пар. Поскольку граница класса видимости в конечном террайне расположена не более чем на конечном числе отрезков, то отсюда следует, что континуум таких пар будет расположен на континууме же классов видимости, входящих в базис.¨

         Возможные конфигурации сопряженного толерантного пространства иллюстрированы рис. 8 - 13. Следует отметить, что для рис. 8  не учтено влияние несвязных классов видимости [21].

3. Конечное покрытие террайна классами видимости

Для построения конечного покрытия террайна, препятствия на котором -  выпуклые многоугольники с углами 90° и 270°,  классами видимости, авторами был разработан следующий алгоритм:

1)          Выбирается отрезок - произвольная сторона любого препятствия на террайне и максимально распространяется в обе стороны до пересечения с другими препятствиями. Полученный отрезок назовем фронтом видимости.

2)          Фронт видимости распространяем в перпендикулярном к выбранной стороне препятствия направлении до прерывания его каким-либо препятствием. Полученная прямоугольная область очевидно будет классом видимости.

3)          Повторяем шаги 1,2 для каждой стороны каждого препятствия. Получим совокупность пересекающихся классов видимости.

Поскольку работа первых трех шагов не алгоритма не гарантирует покрытия всего террайна (например, на террайне типа «мельница», представленном на рис. 14), то проводим следующую процедуру

4)                Выявляем непокрытую прямоугольную область террайна.

5)                Для каждой стороны этой области строим фронт видимости и максимально распространяем его в соответствующем направлении. Полученная прямоугольная область также будет классом видимости

6)                Повторяем шаги 4,5 для всех непокрытых областей террайна.

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

Результат работы алгоритма представлен на рис. 14. На рис. 15 изображен граф связей классов, полученный на основе результатов работы алгоритма. Вершинам графа соответствуют классы видимости, а ребрам – пересечения классов.

Теорема 2. Результат применения алгоритма построения покрытия классами видимости единственен (то есть не зависит от последовательности опорных отрезков).

Доказательство.

Пусть в алгоритме в качестве опорного отрезка взят отрезок a (рис. 14) и фронт видимости распространяется в направлении w до прерывания его препятствием, скажем, отрезком или частью отрезка b. Пусть при этом весь отрезок b входит в фронт распространения l. l_b – распространение отрезка b до фронта. Очевидно, что по построению l_b ³ l_a. Если l_b = l_a, то классы построенные на этих двух отрезках совпадают; если l_b > l_a, то будет построен класс на отрезке b, который будет иметь непустое пересечение с классом, построенным на l_a. Подобное рассуждение справедливо для любых отрезков. ¨

4. Логика слежения

Задача слежения за движущимися объектами одной из основных  функций  МР - разведчиков.

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

     (1) Список, содержащий:

           - 8 предикатов (EQV, PLC, CNT, UVS, OUT, SHD, NTH и ЕXV),

           - 1 функцию (RNT),

           - 1 параметр (VMAX),

           - 3 понятия (STR,STRCTR, PATH) и

           - 1 оператор (MVNEWP),

который является минимально необходимым для адекватной интерпретации на верхнем уровне СУ ситуации  слежения  за  движущимися  объектами, наблюдаемыми  с  помощью  используемой информационной системы.  Этот список приведен на рис. 17.  Истинность предикатов  устанавливается на основе обработки данных,  получаемых от информационной системы, и фактов,  хранящихся в базе знаний о  возможных  объектах  наблюдения (предикат CNT).

     (2) Пять основных типов правил слежения (рис. 18). Рассмотрим их более подробно.

А) Квазинепрерывность.

Правила этого типа позволяют утверждать, что сместившийся  в  поле  зрения объект - это тот же объект,  что и наблюдаемый ранее  в достаточно близкой позиции.  Здесь следует сделать замечание о предикате EQV. В предлагаемой методике принимается  принцип  не двойного именования (переменные и константы),  как это принято в языках логического программирования, а тройного именования (переменные,  константы и недопределенные объекты). Иными словами,  именуются классы объектов, конкретные объекты и вводятся специальные  "псевдоимена",  используемые  для  именования объектов без полного их отнесения к какому-либо из известных классов (без полного их распознавания). Дело в том, что полное распознавание может потребовать значительных временных и информационных  затрат.  Поэтому  на промежуточной стадии слежения, в условиях ожидания окончания процесса обработки данных или подсказки оператора, такие объекты именуются специальным  образом.  После появления уточняющей информации правила квазинепрерывности позволяют выделить  реальный  объект  из  перечня псевдоименованных.

 Б) Затенения.

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

В) Встреча.

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

Г) Выводы о структуре.

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

Д) Смена положения.

Правила для активации процедуры смены точки наблюдения в СУ МР.

5.  Гибридный алгоритм С₁+A_МП

Для реализации гибридного алгоритма, позволяющего выходить из точек равновесия потенциальной функции, были разработаны алгоритмы обхода по контуру С₁+A_МП. Нетрудно видеть, что алгоритм, основанный на использовании метода потенциалов «вырождается» в подобие алгоритмов контурного обхода при приближении функции отталкивания от препятствия к функции «барьерного» вида.

         Суть алгоритма С₁+A_МП заключается в следующем. МР управляется алгоритмом, основанном на методе потенциалов. При попадании в окрестность особой точки, называемой точкой захода на препятствие, МР начинает контурный обход препятствия. На каждом шаге обхода МР вычисляет расстояние между точкой  нахождения и целевой точкой и запоминает минимум этой величины для текущей процедуры обхода. Совершив полный контурный обход препятствия, МР получает координаты точки минимума расстояния, называемой точкой схода, и из этой точки продолжает движение к цели методом потенциалов.

Теорема 3. Алгоритм С₁+A_МП сходится на конечном террайне к целевой точке за конечное число шагов (под шагом понимается обход одного препятствия).

Доказательство.

Пусть r(x,y) – расстояние между точкам x и y, g – целевая точка.

Если МР, управляемый алгоритмом С₁+A_МП, обходил препятствие Х и продолжил движение с него в точке схода х, то он попадет на следующее препятствие Y в точке захода y. При этом

r(y,g) < r(x,g),

поэтому МР продолжит движение с точки у₁, расположенной на Y и ближайшей  к точке цели. Тогда

r(y₁,g) < r(y,g)

и заведомо

r(y₁,g) < r(x,g).

 Поэтому на уже пройденное препятствие МР никогда не попадет. Поскольку число препятствий конечно, то за конечное число шагов МР достигнет целевой точки. ¨

Алгоритм С₁+A_МП требует локальную память на одну точку. Он представляет собой алгоритм построения пути по максимуму силы притяжения к целевой точке на контуре препятствия (в случае, если притяжение к цели увеличивается с уменьшением расстояния до цели). Примеры работы алгоритма приведены на рис. 19, 20

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

         Схема построения путевого графа в этом случае будет следующая: фиксируется первое препятствие p₁, на которое попадает МР и все точки схода с него (вершины препятствий). Если с какой-нибудь точки схода мы попадаем на другое препятствие p₂, фиксируем аналогичным образом точки схода с него. Если число препятствий в террайне n, то не более чем за n подобных обобщенных шагов мы получим путевой граф, включающий в себя исходную и целевую точки и узловые точки пути.                     

6.  Моделирование движения МР на уровне отрезка

Авторами была разработана модификация алгоритма выбора пути мобильным роботом (МР) на основе метода потенциалов в случае, когда МР представляется отрезком (с учетом вращения отрезка в поле «информационных» сил вокруг центра масс). МР представлялся как совокупность нормально распределенных вдоль отрезка элементов (точек), а расчет производился по формулам:

где

m            - масса МР,

m_i           - масса i-го элемента МР,

( x _c , y _c )   - координаты центра масс,

( x_i , y_i )     - координаты i-го элемента МР,

r_i                    - расстояние от центра масс до i-го элемента,

F_ix , F_iy     - проекции результирующей силы, действующей на i-ый  элемент на оси координат,

p                - момент вращения.

Рис. 21 демонстрирует работоспособность указанного метода.

7. Режимы движения в лабиринте

В [16] проанализированы возможности использования метода потенциалов для управления РМС. Исследовано пять способов организации такого движения:

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

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

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

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

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

Первые два режима используются для организации передвижения РМС, последние три – для информационного исследования среды.  Последние три режима не были проиллюстрированы в [16]. Здесь даются иллюстрации движения РМС в данных режимах на рис. 22 («схождение»), 23 («расхождение»), 24 («свободный поиск»).

Заключение

В работе получены следующие результаты:

1.      Приведены примеры работы прототипа пакета прикладных программ "Гермес" для исследования алгоритмов выбора пути, основанных на методе потенциалов.

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

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

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

5.      Приведен пример гибридного алгоритма, объединяющего алгоритм, основанный на методе потенциалов и алгоритм контурного обхода. Этот гибридный алгоритм гарантирует достижение целевой точки в случае наличия локальных особых точек потенциального поля для "информационных сил".

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

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

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

Благодарности

     Авторы выражают глубокую признательность А.К.Платонову за поддержку исследований и С.Б.Ткачеву за полезные обсуждения.

Литература

1. Платонов А.К., Карпов И.И., Кирильченко А.А. Метод потенциалов в задаче прокладки трассы // М.: Препринт Ин-та прикладной математики АН СССР, 1974, # 124, 27 с.

2. Wang Y., Lane D.N., Falconet G.S. Two novel approaches for unmanned underwater vehicle path planning: constrained optimization and semi-infinite constrained optimization.  "Robotica", 2000, v.18, pp 123-142.

3. Левин  К.  Топология и теория поля.  // "Хрестоматия по истории психологии", М.: Издательство МГУ, 1980, с.122-131.

4. Rimon E.,  Koditschek D.E. The construction of analytic diffeomorphisms for star worlds.  // "IEEE Int.  Conf.  Rob. and Autom., 1989: Proc. vol.1", - Waschington etc., 1989, pp. 21-26.

5. Koditschek D.E. Task encoding: toward a scientific paradigm  for robot planning and control // "Robotics and Automation systems", 1992, v.9, # 1-2, pp. 5-39.

6. Khatib O. Real-time obstacle avoidance for manipulators and mobile robots// “IEEE Int. Conf. Robotics and Automation”, 1985, pp. 500-505.

7. Brooks R.A. Self calibration of motion and stereo vision for mobile robots // “IEEE Int. Robotics and Automation”, 1986, 2:14.

8. Фиск К., Кэски Д., Уэст Л. Автоматическое проектирование печатных плат // ТИЭЭР, 1967, # 11, т. 55, стр. 217-228.

 9. Ichikawa Y., Fujie M., Ozaki N. On mobility and autonomous properties of mobile robots // Robot, 1984, # 44,  pp. 31-36.

10. Adams M.D., Hu Huosheng, Probert P.J. Towards a real-time architecture for obstacle avoidance and path palnning in mobile robots // “IEEE Int. Conf. Robotics and Automation”, 1990, pp. 584-589.

11. Hauge T., Brady M., Cameron S. Using moments to plan paths for the Oxford AGV // “IEEE Int. Conf. Robotics and Automation”, 1990, pp. 210-215.

12. Borenstein J., Koren Y.,Real-time Obstacle Avoidance for Fast Mobile Robots In Cluttered Enviroments // “IEEE Int. Conf. Robotics and Automation”, 1990, pp. 572-577.

13. Louste C., Liegeois A. Near optimal robust path planning for mobile robots: the viscous fluid method with friction // “Journal of Intelligent and Robotic Systems”, 2000, # 27, pp. 99-112.

14. Arkin R.C. Motor schema – based mobile robot navigation // “IEEE Int. Conf. Robotics and Automation”, 1987 pp. 92 – 112.

15. Takahashi O., Schilling R.J. Motor planning in a plane using generalized Voronoi diagram // “IEEE Transactions on Robotic and Automation”, 1989, pp. 143 – 150

16. Платонов А.К., Кирильченко А.А., Колганов М.А. Метод потенциалов в задаче выбора пути: история и перспективы. //М.: Ин-т прикл. матем. им. М.В.Келдыша РАН, 2001, N 40, 32 с.

17. Sossinski A.B. Tolerance Space Theory and Some Applications.//"Acta Applicandae Mathematicae", 1986, v.5, pp. 137-167.

18. Якубович С.М. О свойствах сопряженных пространств толерантности. //"Информ. вопросы семиотики, лингвистики и автоматического перевода", 1971, вып.1, с. 116-123.

19. Шрейдер Ю.А. Равенство, сходство, порядок. //М.: Наука, 1970, 255 с.

20. Кирильченко А.А. О представлении информационно-двигательного взаимодействия мобильного робота со средой на основе отношения видимости. //М.: Ин-т прикл. матем. им. М.В.Келдыша АН СССР, 1987, N 235, 28 с.

21. Кирильченко А.А. Ядра и классы видимости в задачах информационного обеспечения мобильных роботов //М.: Ин-т прикл. матем. им. М.В.Келдыша АН СССР, 1988, N 181, 24 с.

Иллюстрации

Рис.1

Рис.2

Рис. 3

Рис. 4

Рис. 5

Рис. 6

Рис. 9

Рис. 10

Рис.11

Рис. 12

Рис. 13

Рис. 14

Рис. 15

Рис. 16

Рис. 17        

Рис. 18

Рис. 19

Рис. 20

Рис. 21

Рис. 22

Рис. 23

Рис. 24