Метод переменных стратегий построения траекторий движения роботов в среде с препятствиями

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2008
1. Verfasser:	Макарычев, В.П.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2008
Schlagworte:	Управление и информационное обеспечение мехатронных и робототехнических систем
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/7045
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Метод переменных стратегий построения траекторий движения роботов в среде с препятствиями / В.П. Макарычев // Штучний інтелект. — 2008. — № 3. — С. 451-461. — Бібліогр.: 10 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-7045
record_format	dspace
spelling	irk-123456789-70452010-03-23T12:02:07Z Метод переменных стратегий построения траекторий движения роботов в среде с препятствиями Макарычев, В.П. Управление и информационное обеспечение мехатронных и робототехнических систем В работе предложен и исследован метод построения траекторий движения роботов в среде с препятствиями, основанный на смене стратегий поведения в зависимости от ситуации. Метод состоит из ряда шагов. Сначала делается попытка построения в целевую точку канонической траектории в свободном пространстве, оптимальной по быстродействию и с учётом динамических ограничений. Быстрый анализ наличия пересечений построенной траектории с препятствиями основан на их пирамидальной структуре. Описаны реализующая разработанный метод компьютерная программа на Matlab и результаты экспериментального исследования на примере макета космического технологического манипулятора. In this paper is proposed and investigated the method of constructing trajectories of the motion of robots in environments with obstacles based on the change of behavior strategies depending of situation. Method consists of a number of steps. First is made an attempt of the construction into the purposeful point of canonical trajectory in the free space, optimum for the time and taking into account dynamic limitations. The rapid analysis of the presence of intersections of the constructed trajectory with obstacles is based on their pyramidal structure. Are described the realizing the developed method computer program at Matlab and results of experimental studies based on the example of the space technological manipulator. 2008 Article Метод переменных стратегий построения траекторий движения роботов в среде с препятствиями / В.П. Макарычев // Штучний інтелект. — 2008. — № 3. — С. 451-461. — Бібліогр.: 10 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/7045 004.896:62-523.8 ru Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Управление и информационное обеспечение мехатронных и робототехнических систем Управление и информационное обеспечение мехатронных и робототехнических систем
spellingShingle	Управление и информационное обеспечение мехатронных и робототехнических систем Управление и информационное обеспечение мехатронных и робототехнических систем Макарычев, В.П. Метод переменных стратегий построения траекторий движения роботов в среде с препятствиями
description	В работе предложен и исследован метод построения траекторий движения роботов в среде с препятствиями, основанный на смене стратегий поведения в зависимости от ситуации. Метод состоит из ряда шагов. Сначала делается попытка построения в целевую точку канонической траектории в свободном пространстве, оптимальной по быстродействию и с учётом динамических ограничений. Быстрый анализ наличия пересечений построенной траектории с препятствиями основан на их пирамидальной структуре. Описаны реализующая разработанный метод компьютерная программа на Matlab и результаты экспериментального исследования на примере макета космического технологического манипулятора.
format	Article
author	Макарычев, В.П.
author_facet	Макарычев, В.П.
author_sort	Макарычев, В.П.
title	Метод переменных стратегий построения траекторий движения роботов в среде с препятствиями
title_short	Метод переменных стратегий построения траекторий движения роботов в среде с препятствиями
title_full	Метод переменных стратегий построения траекторий движения роботов в среде с препятствиями
title_fullStr	Метод переменных стратегий построения траекторий движения роботов в среде с препятствиями
title_full_unstemmed	Метод переменных стратегий построения траекторий движения роботов в среде с препятствиями
title_sort	метод переменных стратегий построения траекторий движения роботов в среде с препятствиями
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2008
topic_facet	Управление и информационное обеспечение мехатронных и робототехнических систем
url	http://dspace.nbuv.gov.ua/handle/123456789/7045
citation_txt	Метод переменных стратегий построения траекторий движения роботов в среде с препятствиями / В.П. Макарычев // Штучний інтелект. — 2008. — № 3. — С. 451-461. — Бібліогр.: 10 назв. — рос.
work_keys_str_mv	AT makaryčevvp metodperemennyhstrategijpostroeniâtraektorijdviženiârobotovvsredesprepâtstviâmi
first_indexed	2025-07-02T09:50:35Z
last_indexed	2025-07-02T09:50:35Z
_version_	1836528262830882816
fulltext	«Штучний інтелект» 3’2008 451 6М УДК 004.896:62-523.8 В.П. Макарычев Государственный научный центр Российской Федерации, Центральный научно-исследовательский институт робототехники и технической кибернетики, г. Санкт-Петербург, Россия makar@.rtc.ru Метод переменных стратегий построения траекторий движения роботов в среде с препятствиями В работе предложен и исследован метод построения траекторий движения роботов в среде с препятствиями, основанный на смене стратегий поведения в зависимости от ситуации. Метод состоит из ряда шагов. Сначала делается попытка построения в целевую точку канонической траектории в свободном пространстве, оптимальной по быстродействию и с учётом динамических ограничений. Быстрый анализ наличия пересечений построенной траектории с препятствиями основан на их пирамидальной структуре. Описаны реализующая разработанный метод компьютерная программа на Matlab и результаты экспериментального исследования на примере макета космического технологического манипулятора. Существует многообразие алгоритмов и методов построения траекторий движения для роботов: мобильных и манипуляторов [1], [2]. Однако до сих пор отсутствует единый универсальный подход к построению траекторий в среде с препятствиями. Можно выделить три группы методов планирования пути (траектории как геомет- рической кривой). 1. Методы потенциальных функций. 2. Клеточно-графовые методы. 3. Методы вероятностной дорожной карты. В методах потенциальных функций построение пути робота в заданную точку осуществляется за счет действующих на него потенциальных сил двух типов: силы притяжения к цели и сил отталкивания от границ препятствий. Для создания поля этих сил искусственно формируются потенциалы, и решается экстремальная задача без огра- ничений. Главным недостатком метода потенциальных функций является его громозд- кость в случае многомерных пространств и сложность потенциальной функции: наличие локальных экстремумов. Более гибкими логическими возможностями при обходе известных препятствий теоретически любой сложности обладают клеточно-графовые методы, использующие описания проблемной среды в виде клеток и соответствующих им графов. Далее ищется оптимальный путь на графе [3], что в случае большой размерности может быть трудным. Современный популярный метод вероятностной дорожной карты (PRM – Probabilistic Road Map) [4], [5] показал свою эффективность и преимущества по сравнению с рассмот- ренными выше классическими методами. Сначала на фазе планирования строится дорож- ная карта с помощью повторяемого алгоритма построения случайных конфигураций, и в качестве «узлов» дорожной карты выбираются свободные, т.е. не пересекающие пре- пятствия, конфигурации. Затем находятся траектории, соединяющие выбранные узлы с помощью простого и быстрого алгоритма, который лежит в основе процедуры планиро- Макарычев В.П. «Искусственный интеллект» 3’2008 452 6М вания пути PRM и называется локальным планировщиком. Таким образом, формируется граф, в котором конфигурации являются узлами графа, а вычисляемые локальным пла- нировщиком пути – дугами. На фазе исполнения решается задача нахождения пути между двумя свободными конфигурациями робота на карте аналогично клеточно-графовым методам. Итоговый путь получается дополнением траекторий из начальной и целевой точек в узлы графа. Заметим, что случай заранее неизвестных препятствий сводится к случаю стати- ческих препятствий, когда в каждый момент времени имеется квазистатическая карта этих препятствий. Конечно, для эффективного решения задачи требуется, чтобы и метод построения траекторий был эффективным, т.е. быстрым. Структура метода переменных стратегий В работах [6-8] был предложен новый подход, который назовём «методом перемен- ных стратегий», основанный на следующих компонентах: – канонической процедуре построения субоптимальной по времени траектории в конфигурационном C-пространстве робота, с учетом кинематических и динамичес- ких ограничений, но без учёта препятствий; – таблице известных безопасных (или свободных, т.е. не пересекающихся с препятст- виями) траекторий, ранее построенных системой при фиксированном множестве стати- ческих препятствий; – локальной коррекции траектории в случае пересечения канонической (п.1) траектории с препятствием и отсутствии траектории в таблице безопасных траекторий. На рис. 1 изображена структура метода. Формироание движений с обходом препятствий Формирование графа правильных траекторий с помощью пробных движений Поиск пути на графе правильных траекторий Локальный обход препятствий введением пробной точки Оператор Модель проблемной среды Математическая модель кинематики робота Ввод/вывод данных Рисунок 1 – Структура метода переменных стратегий Изначально строится субоптимальная по времени, с учетом динамических ограниче- ний, программная траектория в конфигурационном C-пространстве обобщенных коорди- нат nQ , где n – число координат. Используется процедура, использующая параметризацию Формирование движений с обходом препятствий Метод переменных стратегий построения траекторий движения роботов… «Штучний інтелект» 3’2008 453 6М траектории длиной дуги в этом римановом пространстве и подробно описанной в [7], [8]. Две точки nT Qqq ∈,0 соединяются прямой в евклидовой метрике nQ и получаются аналитические выражения для её координат как функций параметра длины дуги ( ) [ ] ( )∑ = −==∆∈ ∆ ∆ += ∆ − += n i i T i T qqSqSss q qqs q qqqsq 1 200 0 0 ,,0 , . (1) Разбивая траекторию на некоторое число узлов, например, равномерно по пара- метру времени t , ( ) ( ) ( ) ( ) STstntss p jjj ===== pp nn00 ss ,0s ,1,,0j , , получаем мно- жество узловых точек со значениями скоростей и ускорений в них ( ) ( ) ( ) . , ,0 jjjjj s q qsqs q qsqs q qqsq ∆ ∆ = ∆ ∆ = ∆ ∆ += (2) Представление препятствий Образующие препятствия и робот геометрические тела представляются в виде пирамидальной структуры совокупности вложенных друг в друга и содержащих препятствие и робот простых тел (параллелепипед, шар, цилиндр) разного уровня [5]. Так, области на 1-м уровне содержат все препятствия и робот, области 2-го уровня содержатся в областях 1-го уровня и имеют меньшие размеры – они детализируют области 1-го уровня, и т.д. При анализе пересечений, если отсутствуют пересечения с какой-либо областью i-го уровня, то дальнейшее разбиение этой области i-го уровня не производится. Если же имеется пересечение с областью i-го уровня, то производится анализ пересече- ний для всех содержащихся в нем областей (i+1)-го уровня и т.п. Разбиение препятствий на области разных уровней, начиная с 1-го уровня, производится либо программистом- разработчиком, программистом-оператором, либо автоматически модулем СУД автома- тической системы разбиения, имеющей черты искусственного интеллекта. Препятствия опишем в виде областей ,,1, W m i niRWG =⊂∈ в рабочей зоне W (также, области) евклидова пространства 3,2, =mRm для плоской или пространственной задачи, соответственно. Аналогичным образом опишем робот: ( ) ,m i iG G q W R= ∈ ⊂ 1, ,Ri n= выделяя в его конструкции отдельные элементы iG , рассматриваемые как абсо- лютно твердые тела (например, основание мобильного робота или звенья манипулятора). Тогда запретная зона совокупности препятствий имеет вид m ni i RWGG W ⊂∈= = ∪ ,1 , а робот – ( ) ( ) m ni i RWqGqGG R ⊂∈== = ∪ ,1 . Опишем разбиения областей на иерархические системы элементарных областей, являющихся покрытиями и вложениями областей (важный частный случай – описанные и вписанные окружности для достаточно симметричных областей, в особенности, если они близки). Области на уровне «k» будем обозначать с помощью k-индексов. Далее, 11 1 11 101 ,1, IiSSSSS I i ii =⊂==⊂ = ∪ – области 1-го уровня, содержащиеся в 0S ; 2211 2 12 2,10,112,1 ,1,,1, IiIiSSSS I i iiiiii ====⊂ = ∪ – области 2-го уровня, содержащиеся в 0,1iS ; 1, 2,..., 1, 2,..., ( 1) 1, 2,..., ( 1),0 1, 2,..., ( 1), 1 1 2 2 1 1 1 , 1, , 1, ,..., 1, Ik i i ik i i i k i i i k i i i k ik k k ik S S S S i I i I i I− − − − − = ⊂ = = = = =∪ – области Макарычев В.П. «Искусственный интеллект» 3’2008 454 6М k-го уровня, содержащиеся в )1(,...,2,1 −kiiiS . Здесь всюду индекс «0» обозначает все области следующего уровня, содержащиеся в проиндексированной до этого уровня области – как бы отсутствие дальнейшего разбиения. Кроме того, введем индексацию, при которой каж- дая область имеет k индексов, дополняя отсутствующие индексы нулями, а именно ijiiijiiijii SSS ,...,2,10,,...,2,10...0,,...,2,1 == и введем соглашение, что 1, 2,..., j0, if j: I i i ik jS i= ∃ > . Таким образом, получаем представление для препятствий 1, 2,..., 1, 2,..., ( 1)i i ik i i i kS S −⊂ ⊂ 1 1... i iS G⊂ ⊂ ⊂ и аналогичные представления для робота и эталонов. Представление структуры препятствий двумя уровнями вложения изображено на рис. 2. Структура S содержит шесть полей. Рисунок 2 – Блок-схема структуры препятствий 1. x_obj – 3-вектор центра координат препятствия; 2. d_obj – вектор параметров препятствий (радиус шара, длина ребра параллелепи- педа, радиус цилиндра); 3. l_obj – тип препятствия (1 – шар, 2 – параллелепипед, 3 – цилиндр); 4. cross – признак пересечения с элементом робота (1 – есть, 0 – нет); 5. x_cross_obj – 6-вектор координат начала и конца отрезка пересечения; 6. sublevel – вектор структур, размерность которого зависит от количества вложен- ных препятствий. Оператором заполняются поля x_obj, d_obj, l_obj, sublevel, остальные поля струк- туры заполняются в процессе работы алгоритма. Поиск на графе безопасных траекторий На основании результатов построения траекторий и определения пересечений в структуру S заносятся полученные данные. Результатом отработки алгоритма формиро- вания графа безопасных траекторий является симметричная матрица безопасных траекто- рий M размерности nn× , где n − количество вершин графа, т.е. безопасных конфи- Метод переменных стратегий построения траекторий движения роботов… «Штучний інтелект» 3’2008 455 6М гураций манипулятора. Матрица M строится на основе пробных траекторий, задаваемых оператором в виде начальных 0q и конечных Tq конфигураций, поэтому вершинами графа являются свободные конфигурации (не попадающие в препятствия) пробных траекторий, задаваемых оператором. Они же отвечают диагональным элементам матрицы M, которые поэтому равны 1. Итак, матрица [ ]ijmМ = , порядка n , в которой i j i j 1, если существует путь без пресечений из вершины q в вершину q , 1, если путь без пересечений из вершины q в вершину q не существует.ijm = − (3) Безопасные траектории, соответствующие всем 1=ijm , хранятся в массиве ячеек MT, то есть траектория из вершины i в вершину j, если 1=ijm , хранится в ячейке ),...,( ji ij qqMT = , где ),...,,( 21 n i qqqq = и ),...,,( 21 n j qqqq = , n − число обобщенных координат робота. Если построенная из начальной точки в конечную точку каноническая траектория пересекается с препятствиями, то осуществляется поиск пути на графе безопасных траек- торий методом сетевого графа. Траектория задается в виде двух точек (конфигураций): начала 0q и конца Tq траектории. Может оказаться, что данных конфигураций на графе нет, тогда находятся ближайшие к заданным конфигурациям 0q и Tq конфигурации на графе безопасных траекторий begq и endq . Затем проверяется, есть ли пути без пересе- чений из 0q в begq и из endq в Tq . Если данные пути существуют, то осуществляется поиск наикратчайшего пути на графе безопасных траекторий методом Дейкстры [9] из вершины begq в вершину begq . В том случае, если путь из вершины begq в вершину begq найден, то искомая траектория без пересечений выглядит так: ),...,,...,,...,( 0 Tendbegtrace qqqqQ = . Локальная коррекция траектории Для локальной коррекции траектории могут использоваться разные методы, связан- ные с методами поиска экстремумов: случайный поиск, градиентные, нейронные сети и т.п. Простейшим из них является случайный поиск промежуточной точки. Берём самые удалённые от начала и конца канонической траектории точки ( ), , , , 1 2, ,..., ,beg loc beg loc beg loc beg loc nq q q q= ( ), , , , 1 2, ,...,end loc end loc end loc end loc n nq q q q Q= ∉ , ещё не пересекающиеся с препятствиями, и середину отрезка, образуемого этими точками. Запускаем генератор случайных чисел для каждой присоединённой (обобщённой) координаты робота и умножаем его на d – расстояние (полуторное, удвоенное) между точками ( ), , , , 1 2, ,..., ,beg loc beg loc beg loc beg loc nq q q q= ( ), , , , 1 2, ,...,end loc end loc end loc end loc nq q q q= . Добавляем его к начальной точке ( ), , , , 1 2, ,...,beg loc beg loc beg loc beg loc nq q q q= . Проверяем, что эта новая точка ( ), ,1 , ,1 , ,1 , ,1 1 2, ,...,new loc new loc new loc new loc nq q q q= попала в свободную зону, и если так, то строим каноническую траекторию в неё из начальной точки. Проверяем отсутствие пересечений этой новой подтраектории. Если траектория свободная, то включаем новую точку 1,,locnewq в таблицу, заменяем начальную точку ,beg locq на новую точку , ,1newlocq и строим траекторию из , ,1newlocq в конечную точку ,end locq . И так, пока не найдём новую свободную точку. Если долго не находится, то увеличиваем параметр расстояния d и т.д. Макарычев В.П. «Искусственный интеллект» 3’2008 456 6М Для генетического алгоритма возможна следующая модификация. Вместо выбора случайного числа берём число в диапазоне между этими векторами ( ) ( ), , , , , , , , 1 2 1 2, ,..., , , ,...,beg loc beg loc beg loc beg loc end loc end loc end loc end loc n nq q q q q q q q= = и добавляем к начальному вектору добавки, кодируемые результатом работы функции генетического алгоритма. Например, весь диапазон отдельной конфигурационной координатой для ( ) ( )locend n locendlocendlocendlocbeg n locbeglocbeglocbeg qqqqqqqq ,, 2 , 1 ,,, 2 , 1 , ,...,,,,...,, == разбиваем на N2 частей, при этом каждый диапазон кодируется двоичным числом типа (1 0 1 0 0 0 …1 0 1) (N цифр). Кодировка для всего вектора присоединённых координат составит двоичное число размерности N x n. Это и будет числом, которое будет генерировать генетический алгоритм. Результатом работы будет некоторый код, который отвечает максимальному удалению от препятствий. Если это расстояние положительно, то эта промежуточная точка и выбирается. Если она соединяет без пересечений с препятствиями обе точки ,beg locq = ( ) ( ), , , , , , , 1 2 1 2, , ..., , , , ...,b eg lo c b eg lo c b eg lo c en d lo c en d lo c en d lo c en d lo c n nq q q q q q q= = , то всё хорошо. Иначе повторяем процедуру с заменой одной из точек ( ), , , , 1 2, ,..., ,beg loc beg loc beg loc beg loc nq q q q= ( ), , , , 1 2, ,...,end loc end loc end loc end loc nq q q q= на новую промежуточную. Градиентный метод имеет следующий вид. Пусть надо найти ncross Qq ∈ – первое (по s) пересечение препятствий с роботом, т.е. точку касания робота и препятствия, характеризующуюся фреймом crosscrossobjectlink x,NN ,,, r=Φ , где objectlink NN , – номер звена и номер препятствия этого пересечения, crosscross x,r – координаты точки пересечения в системах координат и базовой, соответственно. ( )pFq OKZ ~~ 1−= , ( ) pqpp ∆+=~ , (4) ne aaap ne ++=∆ ττ , где crossT ppe += – вектор, направленный из точки касания ncross Qq ∈ , в целевую (ко- нечную) точку Tq , τ – вектор, направленный вдоль поверхности препятствия, т.е. по касательной, n – вектор, направленный по нормали от этой поверхности, ne aaa ,, τ – параметры, задающие величину шага смещения по векторам ne ,,τ . Структура программы Рассмотрим работу алгоритма построения свободной траектории робота на уровне связи подпрограмм (рис. 3). Прежде всего, строится каноническая траектория и опреде- ляется её пересечение с препятствиями [5]. В случае наличия пересечений ищем траек- торию на графе ранее построенных безопасных траекторий. Если модуль поиска пути на этом графе не дал результатов, то осуществляется локальная коррекция траектории. Изображены следующие подпрограммы: − BASE – описание проблемной среды; − LINK – математическое описание кинематики робота; − IN_OUT_PATH – ввод/вывод данных траекторий; − TRACE_TRAP – построение канонической траектории; Метод переменных стратегий построения траекторий движения роботов… «Штучний інтелект» 3’2008 457 6М − INTERSECT_OBSTACLE_PATH – проверка пересечений робота с препятствиями; − GRAPH_PATH – построение траекторий на графе свободных траекторий; − LOCAL_CORRECT_PATH – локальная коррекция траектории. Оператор BASE LINK IN_OUT_PATH TRACE_TRAP INTERSECT_OBSTACLE_PATH GRAPH_PATH LOCAL_CORRECT_PATH Рисунок 3 – Блок-схема программы на уровне связи основных подпрограмм Подпрограмма TRACE_TRAP имеет следующие входные данные: – n − число обобщенных координат манипулятора; – kcurv_trap = 1 обычная трапеция, 2 сглаженная фильтром 1-го порядка; – q0 − начальная точка траектории; – qt − конечная точка траектории; – q2_accel − величина ускорения разгона; – q1_const − величина постоянной скорости; – t_filter − постоянная времени фильтра сглаживания; – t − текущее время. Её выходными данными являются: – qp − величина текущих обобщенных программных координат; – qp1 − величина текущих обобщенных программных скоростей; – qp2 − величина текущих обобщенных программных ускорений. Подпрограмма MONITIRING осуществляет поиск на графе безопасных траекторий. Её входными данными являются начальные 0q и конечные Tq точки пробных траекто- рий, такие, что nT Qqq ∈,0 . Выходом подпрограммы MONITIRING является матрица безопасных траекторий M графа дорожной карты. Матрица M эквивалентна графу, на котором далее можно искать путь. Другие параметры: – S – структура препятствий; – q0 – начальная конфигурация манипулятора; – qt – конечная конфигурация манипулятора; – t – текущее время; – q(s,j) – обобщенная координата как функция параметра длины дуги s; – np – количество конфигураций (узлов траектории); – cross – признак пересечения, cross = 1 – есть, cross = 0 – нет; – N1 – количество препятствий на первом уровне пирамидального представления струк- туры пространства; – N2 – количество препятствий второго уровня i-го препятствия первого уровня; Макарычев В.П. «Искусственный интеллект» 3’2008 458 6М – N3 – количество препятствий третьего уровня, принадлежащее i-му препятствию пер- вого уровня, j-му препятствию второго уровня; – N4 – препятствия четвертого уровня, принадлежащие i-му препятствию первого уровня, j-му препятствию второго уровня и k-му препятствию третьего уровня ; – N5 – препятствия пятого уровня, принадлежащие i-му препятствию первого уровня, j- му препятствию второго уровня, k-му препятствию третьего уровня, n-му препятствию четвертого уровня; – M – матрица безопасных траекторий графа дорожной карты. Алгоритм поиска на графе безопасных траекторий реализован в программе GRAPH_PATH. Входом программы GRAPH_PATH являются начальная 0q и конечная Tq конфигурации траектории и матрица безопасных траекторий M. Выходом программы GRAPH_PATH является искомая траектория ),( 0 Tqq без пересечений, если такая траек- тория существует. Если такую траекторию найти на графе не удалось, то согласно методу переменных стратегий переходим к локальной коррекции траектории в подпрограмме LOCAL_CORRECT_PATH. Алгоритм коррекции реализован введением случайной пробной точки. Входом для программы LOCAL_CORRECT_PATH являются начальная 0q и конечная Tq конфигу- рации траектории. Выходом программы является траектория ),( 0 Tqq без пересечений. Экспериментальное исследование и выводы Оператор задаёт препятствие, заполняя древовидную структуру данных S. В рас- сматриваемом примере уровень вложения препятствий равен трём (рис. 4). S S(1) .x_obj [0.5 0.7 0.5] .d_obj 0.3 .l_obj 2 .sublevel struct 1×1 .x_obj [0.5 0.7 0.5] .d_obj 0.2 .l_obj 2 .sublevel struct 1×3 (1) (1) (3) .x_obj [0.45 0.65 0.5] .d_obj 0.1 .l_obj 1 (2) S(2) .x_obj [0.3 -0.8 0.6] .d_obj 0.25 .l_obj 3 .sublevel struct 1×1 (1) .x_obj [0.3 -0.8 0.6] .d_obj 0.15 .l_obj 3 S(3) .x_obj [1.2 -1 1] .d_obj 0.3 .l_obj 1 .sublevel struct 1×1 .x_obj [1.2 -1 1] .d_obj 0.2 .l_obj 1 .sublevel struct 1×1 (1) (1) .x_obj [1.2 -1 1] .d_obj 0.05 .l_obj 2 .x_obj [0.48 0.8 0.5] .d_obj 0.05 .l_obj 3 .x_obj [0.6 0.65 0.5] .d_obj 0.06 .l_obj 1 Рисунок 4 – Представление древовидной структуры S Метод переменных стратегий построения траекторий движения роботов… «Штучний інтелект» 3’2008 459 6М Изображенное на рис. 4 представление структуры означает, что на первом уровне моделируемой проблемной среды находятся три препятствия. 1. Параллелепипед с центром x_obj = (0.5, 0.7, 0.5) и расстоянием от центра до граней, равным d_obj = 0.3, внутри которого находится препятствие второго уровня: 1.1. параллелепипед с центром x_obj = (0.5, 0.7, 0.5) и расстоянием от центра до граней, равным d_obj = 0.2, внутри которого расположены три препятствия на третьем уровне: 1.1.1. шар с центром x_obj = (0.45, 0.65, 0.5) и радиусом d_obj = 0.1м; 1.1.2. цилиндр с центром x_obj = (0.48, 0.8, 0.5) и радиусом d_obj = 0.05м; 1.1.3. шар с центром x_obj = (0.6, 0.65, 0.5) и радиусом d_obj = 0.06м. 2. Цилиндр с центром x_obj = (0.3, – 0.8, 0.6) и радиусом основания d_obj = 0.25м, внутри которого расположено препятствие на втором уровне: 2.1. цилиндр с центром x_obj = (0.3, – 0.8, 0.6) и радиусом основания d_obj = 0.15м. 3. Шар с центром x_obj = (1.2, – 1, 1) и радиусом d_obj = 0.3м, внутри которого расположено препятствие на втором уровне вложения: 3.1. шар с центром x_obj = (1.2, – 1, 1) и радиусом d_obj = 0.2м, внутри которого расположено препятствие на третьем уровне: 3.1.1. параллелепипед с центром x_obj = (1.2, – 1, 1) и расстоянием от центра до граней, равным d_obj = 0.05м. На рис. 5 схематично показано графическое представление смоделированной проб- лемной среды c помощью описания проблемной среды средствами Matlab. Рисунок 5 – Представление узловых конфигураций на траектории 00 ),( tqq Таблица 1 – Узловые конфигурации траектории 00 ),( tqq t, c Вектор обобщенных координат, q 0 0 0 0 0 0 0 5 0,1952 0,2362 -0,1952 0 0,1952 0 10 0,4392 0,5315 -0,4392 0 0,4392 0 15 0,6832 0,8268 -0,6832 0 0,6832 0 20 0,9272 1,1220 -0,9272 0 0,9272 0 25 1,1712 1,4173 -1,1712 0 1,1712 0 30 1,4151 1,7126 -1,4151 0 1,4151 0 35 1,5700 1,9000 -1,5700 0 1,5700 0 Макарычев В.П. «Искусственный интеллект» 3’2008 460 6М Рассмотрим макет шестистепенного космического манипулятора [8]. Рассмот- рим построенную каноническую траекторию с началом в точке )0,0,0,0,0,0(0 =q и концом в точке (1.57,1.9, 1.57, 0,1.57, 0)tq = − . На рис. 5 и в табл. 1 приведены на- чальная, конечная и промежуточные конфигурации, а также траектория схвата. Траек- тории пересекаются с препятствием № 1 в структуре S. В результате отработки алгоритма проверки пересечений робота с препятствиями выявлено, что следующие промежуточ- ные конфигурации пересекают препятствия: 10 (0.4392, 0.5315, 0.4392, 0, 0.4392, 0)q = − , 15 (0.6832, 0.8268, 0.6832, 0, 0.6832, 0)q = − , 20 (0.9272,1.1220, 0.9272, 0, 0.9272, 0)q = − . Так как траектория 0 0( , ) ((0,0,0,0,0,0),(1.57,1.9, 1.57, 0,1.57, 0))tq q = − пересекает пре- пятствия, то модифицируем её с помощью алгоритма локальной коррекции, что приведёт к траектории, отображённой в табл. 2 и на рис. 6 где изображена траектория схвата робота. Рисунок 6 – Представление движения схвата на траекториях 1010 ),(,),( tt qqqq Таблица 2 – Узловые конфигурации траектории 10 ),( tqq t, c Вектор обобщенных координат, q 0 0 0 0 0 0 0 5 0,0456 0,0570 -0,0471 0,3986 0,0471 0 10 0,1026 0,1282 -0,1059 0,8968 0,1059 0 15 0,1595 0,1994 -0,1648 1,3950 0,1648 0 20 0,2165 0,2706 -0,2236 1,8933 0,2236 0 25 0,2735 0,3419 -0,2825 2,3915 0,2825 0 30 0,3305 0,4131 -0,3413 2,8897 0,3413 0 35 0,3874 0,4843 -0,4002 3,3880 0,4002 0 40 0,4283 0,5354 -0,4424 3,7453 0,4424 0 45 0,5351 0,6689 -0,4943 3,3789 0,5527 0 50 0,6686 0,8358 -0,5593 2,9209 0,6906 0 55 0,8021 1,0026 -0,6242 2,4630 0,8285 0 60 0,9074 1,1342 -0,6754 2,1018 0,9372 0 65 1,0068 1,2585 -0,8206 1,7608 1,0399 0 70 1,1311 1,4138 -1,0020 1,3345 1,1682 0 75 1,2553 1,5691 -1,1835 0,9082 1,2966 0 80 1,3796 1,7244 -1,3649 0,4819 1,4249 0 85 1,5023 1,8779 -1,5442 0,0606 1,5518 0 Метод переменных стратегий построения траекторий движения роботов… «Штучний інтелект» 3’2008 461 6М По результатам эксперимента можно сделать вывод, что траектория, построенная с помощью алгоритма локальной коррекции, может получиться не вполне гладкой и чаще всего не оптимальной. Для получения лучших результатов нужно использовать другие алгоритмы локальной коррекции. Однако следует отметить, что реализованный метод локальной коррекции логически прозрачен, математически прост и не требует больших вычислительных затрат. Кроме рассмотренного простейшего примера был построен ещё ряд траекторий, в том числе, с использованием графа безопасных траекторий. Таким образом, метод показал свою работоспособность и эффективность. Литература 1. Latombe J. Robot Motion Planning. – Kluwer, Boston, MA,1991. 2. LaValle S.M. Planning Algorithms [Электронный ресурс]: 2004. – 859 с. – Режим доступа: http://msl.cs.uiuc.edu/planning/ 3. Вирт Н. Алгоритмы и структуры данных. – М.: Невский Диалект, 2006. – С. 352. 4. Kavraki L. and Latombe J.-C. Randomized preprocessing of configuration space for fast path planning // In Proc. IEEE Int. Conf. Robotics and Automation. – San Diego, CA. – 1994. – P. 2138-2145. 5. Kavraki L. E., Latombe J.C. Probabilistic Roadmaps for Robot Path Planning, Robotics Laboratory, Department of Computer Science Stanford University. – Stanford, California CA 94305. – 1998. – 21 p. 6. Макарычев В.П. Методы управления космическими роботами // «Искусственный Интеллект». – 2003. – № 4. – С. 140-147. 7. Макарычев В.П. Использование интеллектуальных технологий при построении траекторий роботов в среде с препятствиями // Материалы Международной научной конференции Искусственный интеллект. Интеллектуальные и многопроцессорные системы-2004. – Т. 2. Таганрог: Изд-во ТРТУ. – 2004. – С. 401-405. 8. Макарычев В.П., Юревич Е.И. Супервизорное управление космическими манипуляторами. – СПб.: Астерион, 2005. – 108 с. 9. Dijkstra E.W. A note on two problems in connection with graphs // Numerische Mathematik. – 1959. – V. 1. – P. 269-271. 10. Динамика управления роботами / В.В. Козлов, В.П. Макарычев, А.В. Тимофеев, Е.И. Юревич / Под ред. Е.И. Юревича. – М.: Наука. Главная редакция физико-математической литературы, 1984. – 336 с. V.P. Makarychev The Variable Strategy Method of Constructing Trajectories of the Motion of Robot in the Environment with Obstacles In this paper is proposed and investigated the method of constructing trajectories of the motion of robots in environments with obstacles based on the change of behavior strategies depending of situation. Method consists of a number of steps. First is made an attempt of the construction into the purposeful point of canonical trajectory in the free space, optimum for the time and taking into account dynamic limitations. The rapid analysis of the presence of intersections of the constructed trajectory with obstacles is based on their pyramidal structure. Are described the realizing the developed method computer program at Matlab and results of experimental studies based on the example of the space technological manipulator. Статья поступила в редакцию 22.07.2008.

Метод переменных стратегий построения траекторий движения роботов в среде с препятствиями

Institution

Ähnliche Einträge