авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 9 |

«М.С. Корытов АВТОМАТИЗАЦИЯ СИНТЕЗА ОПТИМАЛЬНЫХ ТРАЕКТОРИЙ ПЕРЕМЕЩЕНИЯ ГРУЗОВ МОБИЛЬНЫМИ ГРУЗОПОДЪЕМНЫМИ КРАНАМИ В НЕОДНОРОДНОМ ОРГАНИЗОВАННОМ ...»

-- [ Страница 4 ] --

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

4.1. Переменная break, определяющая наличие (break=1) либо от сутствие (break=0) пересечения груза с препятствиями при движении по прямой в пространстве конфигураций между двумя точками si1 и sj1, принимается равной нулю:

break=0. (3.104) 4.2. В цикле с идентификатором i2 происходит изменение значе ния индекса i2 от 1 до некоторого максимального значения i2max, оп ределяемого условием LLmin, (3.105) где Lmin – постоянная величина, (x2)2 + (y 2)2 + (z 2)2 + c ( 2)2 + ( 2)2, L = (3.106) здесь x2=(xi1–xj1)/i2;

y2=(yi1–yj1)/i2;

z2=(zi1–zj1)/i2;

2=(i1–j1)/i2;

2=(i1–j1)/i2. (3.107) L sj si i2=1;

j2 [1;

2] i2=2;

j2 [1;

4] i2=4;

j2 [1;

8] ………………………………………… Рис. 3.23. Графическая интерпретация модифи кации рекурсивного алгоритма деления отрезка пополам (пример на плоскости, дерево рекурсии) Изменение индекса i2 на каждой итерации цикла i2 происходит по закону геометрической прогрессии (увеличение в 2 раза):

i2=i2 2. (3.108) Значение i2 определяет количество равноотстоящих друг от друга точек на прямой между точками si1 и sj1, в которых на текущей итера ции цикла i2 происходит проверка пересечения груза с препятствиями (рис. 3.23).

4.3. Кроме того, на каждой итерации цикла i2 во вложенном цик ле j2 с интервалом в 1 варьируется вспомогательный индекс j2:

j2[1;

i22]. (3.109) Максимальное значение j2=i22 определяет суммарное количест во точек, проверенных на пересечение с препятствиями с начала цик ла i2. Причем на каждой итерации цикла i2 во вложенном цикле j проверяются новые точки, не совпадающие с проверенными на пре дыдущей итерации i2 (см. рис. 3.23). Для этого на каждой итерации алгоритма i2 определяются собственные значения координат точки, с которой начинается проверка:

x2нач=xi1+(xi1–xj1)/(i22);

y2нач=yi1+(yi1–yj1)/(i22);

z2нач=zi1+(zi1–zj1)/(i22);

2нач=i1+(i1–j1)/(i22);

2нач=i1+(i1–j1)/(i22). (3.110) Затем во вложенном цикле j2 вычисляются координаты текущей проверяемой точки:

x2= x2нач+ x2(j2–1);

y2= y2нач+ y2(j2–1);

z2= z2нач+ z2(j2–1);

2= 2нач+ 2(j2–1);

2= 2нач+ 2(j2–1). (3.111) Соответствующие индексы координат на равномерной дискрет ной сетке определяются следующим образом:

i= x2/l ;

j= y2/l ;

k= z2/l ;

l= (2–min)/u ;

m= (2– min)/u. (3.112) 4.4. Далее во вложенном цикле j2 для текущей проверяемой точ ки с индексами координат (3.112) выполняется собственно проверка условия непересечения груза с препятствиями (3.102). В случае, если данное условие не выполняется, т.е. имеет место пересечение груза с препятствиями, переменная break принимается равной 1 и одновре менно циклы j2 и i2 прерываются:

break=1. (3.113) 4.5. Данный пункт выполняется после завершения либо прерыва ния вложенных циклов j2 и i2. Выполняется проверка условия (3.104).

Если данное условие не выполняется, т.е. имеет место пересечение груза с препятствиями при движении из точки si1 в sj1, вес соответст вующей дуги (ребра) графа принимается равным бесконечно большо му значению по (3.97). В случае выполнения условия (3.104) вес дуги рассчитывается как значение целевой функции СВД по (3.18).

5. Осуществляется поиск кратчайшего пути между двумя верши нами графа (sнач и sкон) при помощи алгоритма Дейкстры [216]. Ре зультатом поиска является оптимальная траектория S* с минималь ным значением целевой функции L*, представляющая собой последо вательность из нескольких вершин графа дорожной карты Gr:

S*={sp} sn=1.

p 6. Осуществляется линейная интерполяция найденной траектории на равномерной сетке обобщенной координаты xi (i[1;

imax]) для вы числения обобщенных координат yi, zi, i, i. Под интерполяцией под разумевается вычисление значений каждой из обобщенных координат груза в промежутках между узловыми точками найденной траекто рии, которое выполняется по известному алгоритму [65, 191].

Пуск Ввод исходных данных: sнач=(xн0, yн0, zн0, н0, н0);

sкон=(xк0, yк0, zк0, к0, к0);

v { Rig };

imax;

jmax;

kmax;

lmax;

mmax;

[YПР];

ng;

c;

u;

opt;

lзап_г;

lзап_в Построение массива гиперповерхности [Ymin] по методике раздела 3. s1=sнач=(xн0, yн0, zн0, н0, н0) p= ip= Randimax ;

jp= Randjmax ;

kp= Randkmax ;

lp= Randlmax ;

mp= Randmmax ;

xp=ipl;

yp= jpl;

zp=kpl;

p=(lp–0,5lmax)u;

p=(mp–0,5mmax)u Нет ypYmin(ip,kp,lp,mp) Да p=p+ 10 Да Нет sng=sкон=(xк0, yк0, zк0, к0, к0) 1 p(ng–1) Рис. 3.24. Блок-схема модифицированного алгоритма ВДК для пяти учитывае мых обобщенных координат груза (начало) i i1=1;

i1ng;

i1=i1+ j j1=1;

j1ng;

i j1=j1+ i2=2;

LLmin;

13 Да Нет i2=i xj1 xi1 break= x2нач=xi1+(xi1–xj1)/(i22);

y2нач=yi1+(yi1–yj1)/(i22);

z2нач=zi1+(zi1–zj1)/(i22);

2нач=i1+(i1–j1)/(i22);

2нач=i1+(i1–j1)/(i22) x2=(xi1–xj1)/i2;

y2=(yi1–yj1)/i2;

z2=(zi1–zj1)/i2;

2=(i1–j1)/i2;

2=(i1–j1)/i (x2)2 + (y 2)2 + (z 2)2 + c ( 2)2 + ( 2) L = j j2=1;

j2 i22;

j2=j2+ x2= x2нач+ x2(j2–1);

y2= y2нач+ y2(j2–1);

z2= z2нач+ z2(j2–1);

2= 2нач+ 2(j2–1);

2= 2нач+ 2(j2–1) i= x2/l ;

j= y2/l ;

k= z2/l ;

l= (2–min)/u ;

m= (2– min)/u Да Нет Нет y2Ymin(i,k,l,m) break= break= Да Li1,j1= 28 j ( ) x x 2+ i1 j ( ) = + y i1 y j1 + + Li1 j ( ) i + z i1 z j1 ( ) + ( ) + c j1 j 2 i1 i Поиск кратчайшего пути между двумя вершинами графа (sнач и sкон) при помощи алгоритма Дейкстры j Интерполяция и дискретная локальная оптимизация найденной траектории по методике раздела 3. 33 i1 Вывод резуль Останов татов: S*, L* Рис. 3.24. Блок-схема модифицированного алгоритма ВДК для пяти учитывае мых обобщенных координат груза (окончание) В результате интерполяции получается траектория, представ ляющая собой последовательность из смежных вершин, заданных на равномерной решетке S*={sp} ip=1.

max 7. Выполняется локальная оптимизация интерполированной тра ектории S* по методике, изложенной в разделе 3.5.

8. Определяется уточненное значение целевой функции L* опти мизированной лучшей траектории S* по (3.19).

9. Вывод результатов: L*, S*. Окончание работы алгоритма.

Блок-схема модифицированного алгоритма ВДК перемещения груза, положение которого определяют 3 линейные и 2 угловые обобщенные координаты, приведена на рис. 3.24. Вычислительные реализации модифицированного алгоритма и описанной методики на его основе в средах Microsoft Visual C++ и MATLAB показали рабо тоспособность и эффективность алгоритма для решения поставленной задачи.

3.9. Методика планирования траектории на основе алгоритма декомпозиции линейных и угловых координат Для решения задачи, сформулированной в разделе 3.1, предлага ется применить метод декомпозиции, разбивающий исходную задачу на несколько более мелких подзадач. Данный подход использует ос новную идею метода динамического программирования, которая за ключается в уменьшении размерности задачи за счет ее декомпозиции на подзадачи, каждая из которых имеет меньшую размерность по сравнению с основной. Оптимальное решение подзадач меньшего размера используется для решения исходной задачи [27, 74, 204, 209].

Предлагается разделить на две отдельные подзадачи оптимиза цию линейных координат груза и его угловых координат. Все преоб разования в трехмерном пространстве могут быть сведены к компо зиции двух преобразований: вращения и переноса вдоль координат ных осей. Это позволяет разделить и выполнять по отдельности: 1) нахождение траектории определенной точки груза в трехмерном про странстве с препятствиями;

2) оптимизацию траекторий трех угловых обобщенных координат груза. Необходимо разработать методику планирования траектории на основе алгоритма декомпозиции линей ных и угловых координат.

Общее 5-мерное пространство конфигураций груза разбивается на два частично перекрывающихся 3-мерных пространства. Предла гаемая методика на основе алгоритма декомпозиции линейных и уг ловых координат заключается в выполнении следующей последова тельности шагов [64, 82, 89, 101, 121]:

1. Задание численных значений исходных данных: sнач=(xн0, yн0, v zн0, н0, н0);

sкон=(xк0, yк0, zк0, к0, к0);

{ Rig };

imax;

jmax;

kmax;

lmax;

mmax;

[YПР];

nдек, c, u, opt;

lзап_г;

lзап_в.

2. С использованием методики построения полидистантных по верхностей вокруг препятствий в трехмерном пространстве, изложен ной в разделе 3.3, строим nдек полидистантных поверхностей вокруг реальной поверхности препятствий с различными значениями гори зонтальной Rг и вертикальной Rв полуосей эллипса удалений. Значе ния Rг варьировались в пределах (Rг)in=lзап_г+gmin+inRг, (3.114) где in[1;

nдек];

lзап_г – минимальный допустимый запас расстояния между произвольной точкой на поверхности груза и поверхностью препятствий в горизонтальном направлении;

Rг – шаг приращения v величины Rг;

gmin=min{| Rig |}– расстояние от начала системы коорди нат груза до ближайшей точки на поверхности груза.

Значения Rв варьировались в пределах (Rв)in=lзап_в+gmin+inRв, (3.115) где lзап_в – минимальный допустимый запас расстояния между произ вольной точкой на поверхности груза и поверхностью препятствий в вертикальном направлении;

Rв – шаг приращения величины Rв.

Отличие при построении полидистантных поверхностей в том, что Rг и Rв определяются не по (3.33), а по (3.114) и (3.115).

n Полидистантные поверхности обозначаются как {[YЭ]in} inдек. Ша = ги приращений Rг и Rв подбираются таким образом, чтобы поверх ность [YЭ] nдек соответствовала удалению от реальной поверхности препятствий в горизонтальном направлении на вылет максимально удаленной от начала системы координат груза точки его поверхности с запасом lзап_г.

3. С использованием известных алгоритмов поиска кратчайшего n пути на графе [216, 246], находим траектории {(SL*)in} inдек перемеще = ния точки начала системы координат груза из начального положения slнач=(xн0, yн0, zн0) в конечное slкон=(xк0, yк0, zк0) в трехмерном простран n стве с поверхностями препятствий {[YЭ]in} inдек соответственно (рис.

= 3.25), оптимальные по выражению целевой функции для линейных координат (длины прямой):

).

( (x x imax )2 + ( yi yi 1 )2 + (zi zi 1 ) L лин = (3.116) i i i = Y Конечная SL*nдек точка SL* SL* SL*2 Начальная точка Z X0 Y0 Z X Рис. 3.25. Примеры найденных оптимальных траекторий точки при различных значениях Rг и Rв При этом матрица смежности графа формируется по точкам ви димости по методике, изложенной ниже [64, 122].

Имеется граф Gr с конечным количеством вершин: Gr=(Sr, Er), где Sr={s1, s2,…, sng} – множество вершин графа;

Er = {(si1, s j1 )} ing, j1=1 – множество ребер. Общее количество вершин графа Gr определяется количеством рассматриваемых точек равномерной сетки линейных координат: ng=imaxjmaxkmax.

Алгоритмы поиска путей на графе работают с 2-мерным масси вом чисел, описывающим пространство с препятствиями как граф.

Пространство может быть двухмерным (карта), трехмерным (про странство) или многомерным. Недостатком графовых алгоритмов яв ляется резкое снижение производительности при увеличении размер ности пространства. Чтобы использовать алгоритмы поиска кратчай шего пути на графе, необходимо подготовить исходные данные, опи сывающие граф, в виде матрицы весов графа DG=[(Lлин)i1,j1] ing j1=1 1, [246]. Матрица весов DG – Y таблица, где как столбцы, так и j=1,2,…, строки соответствуют верши jmax нам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие i=1,2,…, imax X Z связи от вершины-строки к k=1,2,…,k max Рис. 3.26. Пространственная равномерная вершине-столбцу (либо наобо решетка (пример): o – свободные узлы;

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

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

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

3.26). При этом для каждого узла описываются его связи только с ближайшими узлами-соседями в решетке.

j+ j+ j+ j j+1 j– j j– j– i+1 i+ i i+ k–1 k k+ а) i+ k–2 k–1 k k+1 k+ б) i k–3 k–2 k–1 k k+1 k+2 k+ в) Рис. 3.27. Направления перемещения от узла к соседям:

а – в пределах одного ряда;

б – в пределах двух рядов;

в – в пределах трех рядов Для каждого узла возможно рассмотрение соседних узлов в пре делах одного ряда, в пределах двух или нескольких рядов (рис. 3.27).

Если для какого-либо узла пространственной решетки вертикаль ная координата y будет меньше высоты полидистантной поверхности в точке с текущими координатами x и z (т.е. узел будет находиться внутри препятствия), то расстояние между данным узлом и всеми его рассматриваемыми узлами-соседями принимается на графе равным бесконечности: Lлин= [64, 216, 246].

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

Улучшить эффективность поиска кратчайшего пути в среде с препятствиями можно за счет изменения алгоритма подготовки мат рицы весов графа. Предлагается, во-первых, уменьшить количество вершин графа, сформировав из него подграф, принимая в рассмотре ние только точки, расположенные на поверхности препятствий выше определенного уровня, например уровня нижней из двух точек нача ла/окончания пути (рис. 3.28). Свободные узлы (вне препятствий), равно как и узлы, находящиеся внутри препятствий, при этом способе исключаются из рассмотрения, что значительно уменьшает размеры матрицы смежности и ускоряет поиск пути. Исключение составляют две точки: начальная и конечная, которые учитываются, хотя нахо дятся вне препятствий. Начальная точка будет первой в списке вер шин подграфа, конечная – последней. Рассматриваемые точки будут располагаться на равномерной сетке относительно координат x и z.

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

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

Рис. 3.28. Точки поверхности (пример):

o – не учитываемые в подграфе;

– учитываемые в подграфе Последовательность предлагаемой методики создания матрицы весов по «точкам видимости» [83]:

3.1. Формирование последовательного списка точек поверхности, учитываемых в подграфе PGr (вершин полного графа Gr, располо женных на поверхности препятствий выше определенного уровня) в виде одномерного вектора.

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

Выполнение п. 3.1 алгоритма, если расположение осей координат соответствует условиям задачи и рис. 3.28, происходит в следующем порядке. Рабочая область с препятствиями задана в виде двухмерного массива чисел – высот точек поверхности YЭ(i,k), где i[1;

imax];

k[1;

kmax];

imax – число точек рассматриваемой области вдоль оси X0;

kmax – число точек вдоль оси Z0. При помощи циклов, меняющих i и k в за данной последовательности (i, затем k), осуществляется перебор каж дой точки сетки с высотой YЭ(i,k) и проверка выполнения условия YЭ(i,k)min[yн0, yк0]. (3.117) При выполнении данного условия текущий узел графа Gr зано сится в список узлов подграфа PGr. Первой в списке предварительно ставится начальная точка (1 на рис. 3.28), последней – конечная (89 на рис. 3.28). Последняя точка имеет номер i2кон [83].

Выполнение п. 3.1 алгоритма предлагается осуществлять сле дующим способом. Выполняется последовательный перебор всех вершин подграфа из списка i2[2;

i2кон], и для каждой текущей вер шины осуществляется построение прямой в пространстве между те кущей вершиной и всеми вершинами с большими номерами:

j2[i2+1;

i2кон]. Прямая разбивается на k2кон отрезков в соответствии с заданным шагом дискретности l, и на данной прямой на равном рас стоянии друг от друга расстанавливаются k2кон промежуточных точек, каждая со своими координатами в пространстве. Каждая из промежу точных точек прямой имеет координаты xk2=xi2+(xi2–xj2)k2/k2кон;

yk2=yi2+(yi2–yj2)k2/k2кон;

zk2=zi2+(zi2–zj2)k2/k2кон, (3.118) где k2[ 1;

k2кон];

k2кон=(Lлин)i2,j2/l.

Для каждой точки проверяется условие превышения ее верти кальной координаты над соответствующей вертикальной координатой поверхности:

yk2YЭ(i3,k3), (3.119) где i3= xk2/l ;

k3= zk2/l.

Если для всех k2кон точек отдельной прямой, соединяющей узел i с узлом j2, данное условие выполняется, делается вывод о том, что узлы i2 и j2 «видимы» между собой, информация об этом сохраняется в бинарной (булевой) переменной (Vid=1), и длина прямой (Lлин)i2,j между двумя точками в трехмерном пространстве вычисляется по вы ражению (xi 2 x j 2 )2 + ( yi 2 y j 2 )2 + (zi 2 z j 2 )2.

(L лин )i 2, j 2 = (3.120) Пуск Задание поверхности препятствий YЭ и начальной и конечной точек положения груза:

(xн0, yн0, zн0) и (xк0, yк0, zк0) i2=1;

[xi2 zi2 yi2]=[xн0 yн0 zн0] i=1:imax k=1:kmax 6 Да Нет YЭ(i,k)min[yн0, yк0] i2=i2+1;

[xi2 zi2 yi2]=[xi YПР(i,k) zk] i2кон=i2+1;

[xi2кон zi2 кон yi2 кон]=[xк0 yк0 zк0] i2=2:i2кон j2=(i2+1):i2кон (Lлин )i 2, j 2 = (xi 2 x j 2 ) + (yi 2 y j 2 ) + (zi 2 z j 2 ) 2 2 k2кон=(Lлин)i2,j2/l;

Vid= k2=1:k2кон xk2=xi2+(xi2–xj2)k2/k2кон;

yk2=yi2+(yi2–yj2)k2/k2кон;

zk2=zi2+(zi2–zj2)k2/k2кон;

i3= xk2/l ;

k3= zk2/l 16 Да Нет yk2YЭ(i3,k3) Vid= Нет Да Vid=0 (Lлин)i2,j2= Вывод результатов:

Останов PDG=[(Lлин)i2,j2] ii 2кон= 2,j Рис. 3.29. Блок-схема алгоритма формирования матрицы весов PDG подграфа PGr В противном случае длина принимается равной бесконечно большому значению (Vid=0):

(Lлин)i2,j2=. (3.121) Информация о «видимости» заносится в виде длины прямой (Lлин)i2,j2 в матрицу смежности подграфа. Матрица весов PDG подгра фа PGr, список вершин которого состоит из i2кон элементов, будет иметь размеры (i2конi2кон). Элементы матрицы заполняются соответ ствующими значениями:

PDG=[(Lлин)i2,j2] ii 2 кон=1. (3.122) 2,j Блок-схема алгоритма создания матрицы весов подграфа по опи санной методике приведена на рис. 3.29.

Из найденных любым алгоритмом поиска кратчайшего пути на n графе траекторий {(SL*)in} inдек каждая представляет собой последова = тельность из нескольких вершин sl подграфа PGr: SL*={slp} sn=1.

p 4. Осуществляется линейная интерполяция каждой найденной n траектории из множества {(SL*)in} inдек на равномерной сетке обоб = щенной координаты xi (i[1;

imax]) по известному алгоритму [65, 191] для вычисления обобщенных координат yi, zi. В результате интерпо ляции формируются траектории точки в трехмерном пространстве, представляющие собой последовательности из смежных вершин, за данных на равномерной решетке SL*={slp} ip=1.

max Линейные траектории состоят каждая из последовательно распо лагающихся вдоль оси X0 точек вида slp=(xp, yp, zp), p[1;

imax], (3.123) где xp[0l;

imaxl].

Т.е. каждая из найденных траекторий представлена в виде набора точек с равномерно возрастающими значениями вдоль одной из осей координат X0 через равные интервалы.

n 5. Для каждой из найденных траекторий {(SL*)in} inдек создается = n 3-мерное пространство с препятствиями {Puin} inдек соответственно, = состоящее из одной линейной x и из двух угловых координат объекта:

и. Для создания пространства Puin груз перемещается из начально го положения в конечное по траектории (SL*)in с шагом квантования l точки начала системы координат груза вдоль оси X0. В каждом из промежуточных положений груза на траектории (SL*)in (рис. 3.30, а) рассматриваются с шагом квантования u все возможные сочетания его варьируемых угловых координат и в заданных (3.40) гранич ных пределах.

Запрещенное Разрешенное состояние состояние Область Область разрешенных запрещенных Zg x состояний состояний Zg Yg * (SL )in Xg Z Y X а) б) X в) Рис. 3.30. К определению разрешенных и запрещенных состояний груза для за данной траектории точки его начала системы координат (примеры): а – траекто рия (SL*)in точки начала системы координат и одно из промежуточных положе ний груза на ней;

б – области разрешенных и запрещенных состояний груза в от дельной точке;

в – пространство Puin из одной линейной и двух угловых координат C использованием гиперповерхности минимальных значений вертикальных координат условного центра груза [Ymin]in, сформиро ванной по методике, описанной в разделе 3.4, формируется простран n ство с препятствиями {Puin} inдек. При рассмотрении двух угловых ко = ординат в качестве иллюстрации могут быть построены двухмерные графики, на каждом их которых будут присутствовать в общем случае две области: запрещенных и разрешенных состояний (рис. 3.30, б). В результате дискретного рассмотрения сочетаний углов на траектории движения (SL*)in формируется пространство Puin, в котором задана об ласть препятствий, т.е. запрещенных состояний груза (рис. 3.30, в).

Пространство Pu представлено в виде трехмерного массива бито вых элементов:

0 при yi Ymin (i,k,l,m );

Pu (i, l, m ) = (3.124) 1 при yi Ymin (i,k,l,m ), где i[1;

imax];

k= zi/l ;

l[1;

lmax];

m[1;

mmax];

yi, zi – соответствую щие координаты точки i траектории SL*.

6. Учитывая, что начальное и конечное положения груза заданы при постановке задачи, включая угловую ориентацию (н0, к0, н0, к0), это определит положение начальной и конечной точек груза в пространстве Puin и позволит найти кратчайшую траекторию с учетом угловых координат. В результате для каждой траектории точки ус ловного центра груза (SL*)in находится соответствующая «угловая траектория» У*in, минимизированная по угловым перемещениям груза с учетом заданных ограничений на значения угловых координат.

n Множество «угловых траекторий» {(У*)in} inдек формируется аналогич = n но траекториям {(SL*)in} inдек с формированием матрицы весов PDGin = пространства Puin на дискретной равномерной сетке координат с ша гами дискретизации l (для x), u (для и ) и поиском кратчайшего пути на графе (п. 3 настоящего алгоритма). Для пространств Puin ис пользуется собственное выражение целевой функции, учитывающее только угловые координаты:

).

( ( imax )2 + (i i 1 ) L угл = (3.125) i i i = 7. При совмещении линейной (SL*)in и угловой (У*)in траекторий формируется общая траектория груза SLУin вида (3.50), которая может быть оценена по значению целевой функции L*in, вычисленной по (3.19):

SLУin=(SL*)in U (У*)in. (3.126) «Угловой траектории» (У*)in может не существовать при опреде ленной конфигурации поверхности препятствий в пространстве Puin (непреодолимые при заданных ограничениях препятствия). В этом случае будет отсутствовать и общая траектория SLУin. Вероятность этого наиболее велика при: 1) минимальных значениях индексов тра екторий (SL*)in, поскольку в этом случае траектория (SL*)in проходит ближе к полидистантной поверхности с минимальными значениями полуосей эллипса удалений (Rг)1 и (Rв)1 от реальных препятствий;

2) больших значениях одного или нескольких габаритных размеров гру за (например, перемещение трубы большой длины). Тогда в некото рых точках рассматриваемой траектории (SL*)in может не существо вать разрешенных состояний груза по угловым координатам (рис.

3.31).

8. Общая траектория Траектория (SL*)in SLУin в большинстве слу чаев может быть дополни тельно оптимизирована по составляющей (SL*)in, по Груз скольку если значения по луосей эллипса удалений (Rг)in и (Rв)in превышают величины (Rг)1 и (Rв)1 со Пересечения ответственно, то в отдель груза и препятствий ных точках траектории S*in возможно расположение Рис. 3.31. Пример траектории, в отдельной груза с зазором относи точке которой отсутствуют разрешенные тельно [YЭ]in, который мо состояния груза в заданных пределах жет быть уменьшен без изменения угловых координат изменения угловой ориен тации груза (рис. 3.32, б).

При этом уменьшается и длина траектории (SL*)in, а следовательно, значение целевой функции L*in общей траектории SLУin. Оптимизация осуществляется при помощи методики дискретной локальной опти мизации, изложенной в разделе 3.5, при замороженных значениях ин дексов угловых координат (l=const;

m=const;

dlp=0;

dmp=0) и исклю чении из блок-схемы алгоритма блоков 14 и 15 (см. рис. 3.15).

В результате формируется набор общих субоптимальных траек nдек торий {SLУin} in= mдек, где 0mдекnдек, поскольку некоторых неоптими зированных траекторий SLУin с наименьшими значениями индекса in =0…mдек может не существовать по причине отсутствия соответст вующих «угловых траекторий» У*in. Каждая субоптимальная траекто рия SLУin будет соответствовать определенному значению полуосей эллипса удалений Rг и Rв и может быть оценена по значению целевой функции Lin, определенной по (3.19).

Зазор б) а) Рис. 3.32. Примеры общей траектории движения груза SLУin (а), показаны по следовательные положения оси груза в форме цилиндра и локальной оптимиза ции по линейной составляющей траектории (SL*)in (б) 9. Из нескольких возможных субоптимальных траекторий nдек {SLУin} in= mдек выбирается траектория SLУ* с минимальным значением целевой функции L*. Для этого при помощи известного алгоритма [74] определяется значение индекса um, соответствующее минималь ному значению Lin:

um=Индекс(min({Lin})), (3.127) nдек где {Lin} in= mдек – множество значений целевой функции множества nдек траекторий {SLУin} in= mдек, представляющих собой дискретные траек тории перемещения из sнач в sкон в виде смежных точек вида (3.50):

sнач, s2, s3, …, s(imax–1), sкон.

L*=Lum;

SLУ*=SLУum. (3.128) 10. Выполняется локальная оптимизация лучшей траектории * SLУ по методике, изложенной в разделе 3.5. При этом траектория обновляется.

11. Определяется уточненное значение целевой функции L* оп тимизированной лучшей траектории SLУ* по (3.19).

12. Вывод результатов: L*, SLУ*. Окончание работы алгоритма.

Пуск Ввод исходных данных: sнач=(xн0, yн0, zн0, н0, н0);

sкон=(xк0, yк0, zк0, к0, к0);

v { Rig };

imax;

jmax;

kmax;

lmax;

mmax;

[YПР];

nдек, c, u, opt, lзап_г, lзап_в Определение gmin, Rг, Rв in in=1;

innдек;

in=in+ (Rг)in=lзап_г+gmin+inRг;

(Rв)in=lзап_в+gmin+inRв Построение полидистантной поверхности [YЭ]in вокруг реальной поверхности препятствий [YПР] по методике раздела 3.3 [102] Формирования матрицы весов PDGin подграфа PGrin линейного пространства по «точкам видимости» по методике, изложенной в п. 3 настоящего алгоритма Поиск траектории (SL*)in как кратчайшего пути между двумя вершинами подграфа PGrin (slнач и slкон) при помощи алгоритма Дейкстры Линейная интерполяция траектории (SL*)in на равномерной сетке xi (i[1;

imax]) Построение массива гиперповерхности [Ymin]in по методике раздела 3. i=1:imax k= zi/l l=1:lmax m=1:mmax 17 Нет Да yiYmin(i,k,l,m) Pu(i,l,m)=1 Pu(i,l,m)= Формирования матрицы весов PDGin подграфа PGrin пространства Puin по «точкам видимости» по методике, изложенной в п. 3 настоящего алгоритма Поиск траектории (У*)in как кратчайшего пути между двумя вершинами подграфа PGrin пространства Puin при помощи алгоритма Дейкстры 21 Нет 20 Да (У*)in существует?

Lin=;

in=in+ Рис. 3.33. Блок-схема алгоритма декомпозиции линейных и угловых координат в последовательном исполнении (начало) * * Формирование общей траектории груза: SLУin = (SL )in U (У )in Локальная оптимизация траектории SLУin по составляющей (SL*)in по методике, изложенной в разделе 3.5, при l=const;

m=const in um=Индекс(min({Lin})) L*=Lum;

SLУ*=SLУum * Локальная оптимизация траектории SLУ по методике раздела 3. Вывод результатов:

SLУ*, L* Останов Рис. 3.33. Блок-схема алгоритма декомпозиции линейных и угло вых координат в последовательном исполнении (окончание) Пуск Ввод исходных данных: sнач=(xн0, yн0, zн0, н0, н0);

sкон=(xк0, yк0, zк0, к0, к0);

v { Rig };

imax;

jmax;

kmax;

lmax;

mmax;

[YПР];

nдек, c, u, opt, lзап_г, lзап_в Определение gmin, Rг, Rв 4 in=1 in=2 in= nдек 7 Выполнение блоков Выполнение блоков Выполнение блоков … 5-23 последовательного 5-23 последовательного 5-23 последовательного алгоритма алгоритма алгоритма um=Индекс(min({Lin})) L*=Lum;

SLУ*=SLУum * Локальная оптимизация траектории SLУ по методике раздела 3. Вывод результатов:

SLУ*, L* Останов Рис. 3.34. Блок-схема распараллеленного алгоритма декомпозиции линейных и угловых координат (затемнены блоки, выполняемые параллельно) Блок-схема алгоритма декомпозиции линейных и угловых коор динат в последовательном исполнении приведена на рис. 3.33.

Разработанный алгоритм хорошо поддается распараллеливанию, поскольку вычислительные эксперименты на последовательной реа лизации показали, что время выполнения информационно независи мых блоков 5–23 составляет около 98 % от общего времени выполне ния программной реализации последовательного алгоритма. Согласно (3.96), при fпо=0,01 и числе параллельных процессов pпр=10 возможно ускорение до 8,5 раз по сравнению с последовательным алгоритмом роевого интеллекта (верхняя оценка ускорения Sпр8,5), что подтвер ждено результатами вычислительных экспериментов.

Блок-схема распараллеленного алгоритма декомпозиции линей ных и угловых координат приведена на рис. 3.34.

Вычислительные реализации разработанных последовательного и параллельного вариантов алгоритма декомпозиции линейных и угло вых координат и описанной методики на его основе в средах Microsoft Visual C++ и MATLAB показали работоспособность и эф фективность алгоритмов для решения поставленной задачи.

3.10. Методика планирования траектории на основе модифицированного направленного волнового алгоритма Волновой алгоритм, основанный на алгоритме поиска на графе в ширину, характеризуется максимальной по сравнению с другими ал горитмами поиска простотой реализации и надежностью [55, 74, 175, 215, 219, 227]. Это детерминированный алгоритм со строго заданной последовательностью действий, который гарантированно находит оп тимальное решение за определенное конечное число шагов, меньшее или равное некоторому предельному значению. Это также можно считать достоинством алгоритма. Однако ему свойственны некоторые ограничения и недостатки: прежде всего это экспоненциальная вре менная и пространственная сложность данного алгоритма O(bd) (b – число узлов графа;

d – глубина решения), не позволяющая практиче ски использовать его при больших размерах графа задачи. Понятие больших размеров определяется быстродействием вычислительной техники на момент проведения исследований.

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

необходимо рассматривать граф с единичными стоимостями всех дуг [74, 175]. Если веса различных ребер не равны, может быть использо ван поиск по критерию стоимости, являющийся модификацией по иска в ширину. Однако данная модификация, которая требует вместо развертывания самого поверхностного узла развертывания узла с наименьшей стоимостью пути, в худшем случае имеет временную и пространственную сложность, намного большую, чем поиск в ширину [74, 215, 219, 227]: O(b 1+ с*/ ) (c* – стоимость оптимального решения, – некоторое положительное значение). Это объясняется, во-первых, вычислительными издержками на поддержание приоритетной очере ди узлов, во-вторых, тем, что долго может выполняться проверка больших деревьев, состоящих из множества дуг малой стоимости, но не содержащих оптимальных путей [74, 215, 219, 227].

Существуют также алгоритмы поиска на графах, основанные на различных модификациях волнового алгоритма, которые относятся к информированным стратегиям: A* (Aстар, направленный волновой алгоритм), RBFS и SMA* [74, 224, 232, 234, 241]. Информированные алгоритмы считаются более эффективными, чем неинформированный поиск (классический волновой алгоритм), поскольку рассматриваются не все узлы графа, а только в первую очередь наиболее перспектив ные (в направлении к цели). Однако при применении этих алгоритмов используется эвристическая функция h(n), для которой необходим ее правильный подбор для конкретной задачи, что представляет собой определенную сложность. Кроме того, в описанных эвристических алгоритмах также используются приоритетные очереди узлов, т.е. по являются издержки на сортировку, значительно возрастающие при увеличении размеров очереди. Причем сортировку необходимо про водить при рассмотрении каждой новой вершины графа. В случае, ес ли время на сортировку сравнимо с временем обработки отдельной вершины графа или превышает его, данный фактор становится суще ственным недостатком.

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

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

Описание модификации направленного волнового алгоритма пе ремещения груза, положение которого определяют 3 линейные и 2 уг ловые обобщенные координаты [60]. Предлагаемый модифицирован ный волновой алгоритм отличается отсутствием приоритетной очере ди узлов и соответственно издержек на сортировку узлов. Кроме того, данная модификация, так же, как и A*, являясь направленным волно вым алгоритмом, в то же время не использует эвристическую функ цию. Эвристика предлагаемого алгоритма задана неявно и заключает ся в расположении оси X0 при постановке задачи (см. раздел 3.1), а также в более высоком иерархическом уровне цикла изменения коор динаты x груза по отношению к прочим координатам при распростра нении фронта волны (цикл, меняющий координату x, будет самым внешним в структуре вложенных циклов). Граф также задается неяв но в виде состояний-преемников на равномерной решетке, т.е. не тра тятся ресурсы на описание графа в виде матрицы смежности, провер ку пересечений и т.д.

Алгоритм заключается в выполнении следующей последователь ности шагов [60]:

1. Задание численных значений исходных данных: sнач=(xн0, yн0, v zн0, н0, н0);

sкон=(xк0, yк0, zк0, к0, к0);

{ Rig };

imax;

jmax;

kmax;

lmax;

mmax;

[YПР];

c;

u;

opt;

lзап_г;

lзап_в.

Параметры соответствуют описанным при постановке задачи в разделе 3.1.

2. По методике, изложенной в разделе 3.4, формируется массив [Ymin] гиперповерхности минимальных значений вертикальных коор динат условного центра груза с учетом его угловых координат:

Ymin(i,k,l,m), i[1;

imax];

k[1;

kmax];

l[1;

lmax];

m[1;

mmax].

3. Используя вложенные циклы по i, j, k, l, m, определяющие x, y, z,, соответственно, рассматривают всевозможные сочетания коор динат груза x, y, z, и на дискретной равномерной сетке, и для каж дого сочетания указанных координат в 5-мерном массиве Vfront со храняют информацию о наличии/отсутствии препятствия в текущем узле:

0 при y Ymin (i,k,l,m );

Vfront(i,j,k,l,m) = (3.129) 1 при y Ymin (i,k,l,m ), где y=jl;

i[1;

imax];

j[1;

jmax];

k[1;

kmax];

l[1;

lmax];

m[1;

mmax].

Значение (–1) элемента массива Vfront соответствует наличию пре пятствия в узле, 0 – отсутствию препятствия.

Одновременно происходит инициализация двух других 5-мерных массивов (определения узла-родителя Vrod и значений целевой функ ции перемещения от начальной точки Vdlin):

Vrod(i,j,k,l,m)=0;

Vdlin(i,j,k,l,m)=. (3.130) Элементы массива Vfront могут принимать следующие значения:

(–1) – узел занят препятствием (непроходим);

0 – узел свободен, не пройден и ни разу не просматривался;

1 – узел просматривался, но еще не пройден;

2 – узел пройден (окончательно закрыт).

4. Начальная точка положения груза на равномерной решетке в массиве Vfront помечается как пройденная:

Vfront(1,jнач,kнач,lнач,mнач)=2, (3.131) где jнач= yн0/l ;

kнач= zн0/l ;

lнач= (н0–min)/u ;

mнач= (н0–min)/u. (3.132) 5. Запускается распространение волны из начальной точки. Ис пользуются вложенные циклы по i, j, k, l, m, где i[1;

(imax–1)];

j[1;

jmax];

k[1;

kmax];

l[1;

lmax];

m[1;

mmax].

5.1. Для каждого сочетания индексов j, k, l, m на текущей итера ции i проверяется выполнение условия Vfront(i,j,k,l,m)=2. (3.133) При выполнении данного равенства выполняется п. 5.2, в про тивном случае рассматривается следующее сочетание индексов (j,k,l,m), и вновь выполняется п. 5.1. Текущее сочетание всех индексов (i, j, k, l, m) для краткости названо текущей вершиной si1. После за вершения вложенных циклов по (j,k,l,m), т.е. перед началом следую щей итерации цикла по i, выполняется п. 5.5 алгоритма.

Условие (3.133) позволяет алгоритму пропускать непроверяемые вершины при развертывании дерева поиска (рис. 3.35). Непроверяе мые вершины возникают вследствие ограниченного количества вер шин-преемников у каждой вершины и направлений преемственности.

На каждой итерации цикла i происходит увеличение диапазонных значений индексов всех прочих координат (j,k,l,m), максимально на единицы, до тех пор, пока диапазонные значения не достигнут преде лов исходной сетки j[1;

jmax];

k[1;

kmax];

l[1;

lmax];

m[1;

mmax].

X0 kдmin=i–(imax–kmax) kдmax=(imax+kmax)–i sкон i=imax Направление движения фронта волны i= i= i=1 k=1 k= k=kmax Z0 sнач – свободные непроверяемые вершины;

– свободные проверяемые вершины;

– занятые препятствиями непроверяемые вершины;

– направления открытия вершин алгоритмом Рис. 3.35. Иллюстрация развертывания-свертывания дерева поиска модифицированного волнового алгоритма (двухмерный аналог) Обозначим диапазонные значения индексов jдmax, jдmin, kдmax, kдmin, lдmax, lдmin, mдmax, mдmin. Для сокращения времени работы волнового ал горитма целесообразно задать условия, позволяющие пропускать все вершины, которые будут являться непроверяемыми при свертывании дерева к конечной вершине, поскольку они также не включаются в траекторию перемещения вследствие ограниченного количества на правлений преемственности на равномерной решетке. Ограничения заданы линейными уравнениями, связывающими непосредственно индексы (см. рис. 3.35):

jдmin(i)=i–(imax–jmax);

jдmax(i)=(imax+jmax)–i;

kдmin(i)=i–(imax–kmax);

kдmax(i)=(imax+kmax)–i;

lдmin(i)=i–(imax–lmax);

lдmax(i)=(imax+lmax)–i;

(3.134) mдmin(i)=i–(imax–mmax);

mдmax(i)=(imax+mmax)–i.

Происходит коррекция пределов варьирования индексов j, k, l, m:

j[max(1;

jдmin);

min(jдmax;

jmax)];

k[max(1;

kдmin);

min(kдmax;

kmax)];

l[max(1;

lдmin);

min(lдmax;

lmax)];

m[max(1;

mдmin).

min(mдmax;

mmax)];

(3.135) 5.2. Для каждой текущей вершины si1=(i, j, k, l, m) рассматривает ся ограниченная область-гиперкуб с центром в точке (j, k, l, m) и по стоянным значением индекса (i+1). Для этого индексы j2, k2, l2, m варьируются в следующих диапазонах (область гиперкуба):

j2[(j–1);

(j+1)];

k2[(k–1);

(k+1)];

l2[(l–1);

(l+1)];

m2[(m–1);

(m+1)]. (3.136) То есть просматриваются все состояния-преемники для текущего состояния груза в пространстве (см. рис. 3.18).

Значения индексов j2, k2, l2, m2, варьируемые по (3.136), прове ряются на выполнение условия невыхода за границы диапазонов ис ходной сетки (3.135) и при необходимости корректируются по зави симостям, аналогичным (3.58).

Для каждого сочетания индексов (i+1), j2, k2, l2, m2 проверяется выполнение условия Vfront(i+1,j2,k2,l2,m2)=1. (3.137) При выполнении данного условия, т.е. если вершина-преемник, находящаяся впереди текущей, уже просматривалась, выполняется п. 5.3, в противном случае – п. 5.4.

5.3. Рассчитывается стоимость перемещения от начальной вер шины до вершины-преемника sj1=(i+1,j2,k2,l2,m2) через текущую вершину si1=(i,j,k,l,m):

Lтек=Vdlin(i, j, k, l, m)+Li1,j1, (3.138) где Li1,j1 – значение целевой функции (СВД) между двумя вершинами si1 и sj1, вычисляемое по (3.18).

Если стоимость перемещения от начальной вершины до верши ны-преемника sj1=(i+1,j2,k2,l2,m2) через текущую вершину si1=(i,j,k,l,m) меньше, чем Vdlin(i+1,j2,k2,l2,m2) – рассчитанная ранее стоимость перемещения в вершину sj1 через некоторую другую вер шину, то вновь рассчитанная стоимость заносится в элемент массива Vdlin(i+1,j2,k2,l2,m2), заменяя бывшее до этого значение данного элемента:

Lтек при Lтек Vdlin(i + 1,j 2,k 2,l 2,m2);

Vdlin(i + 1,j 2,k 2,l 2,m2) = Vdlin(i + 1,j 2,k 2,l 2,m2) (3.139) при Lтек Vdlin(i + 1,j 2,k 2,l 2,m2).

Одновременно с заменой значения элемента массива Vdlin при выполнении условия LтекVdlin(i+1,j2,k2,l2,m2) (3.140) рассчитывается Rodтек – код текущей вершины-родителя si1 для вер шины-преемника sj1.

Кодирование вершины-родителя осуществляется при помощи 4-разрядного целого числа в десятичной системе счисления:

Rodтек=1000((j–j2)+2)+100((k–k2)+2)+10((l–l2)+2)+ +((m–m2)+2). (3.141) Если условие (3.140) выполняется, то происходит замена верши ны-родителя для вершины-преемника sj1:

Rodтек при Lтек Vdlin(i + 1,j 2,k 2,l 2,m2);

Vrod(i + 1,j 2,k 2,l 2,m2) = (3.142) Vrod(i + 1,j 2,k 2,l 2,m2) при Lтек Vdlin(i + 1,j 2,k 2,l 2,m2).

5.4. Данный пункт алгоритма выполняется, если вершина преемник sj1 еще ни разу не просматривалась, что формализуется ус ловием Vfront(i+1,j2,k2,l2,m2)=0. (3.143) По (3.141) рассчитывается Rodтек – код текущей вершины родителя si1 для вершины-преемника sj1, который заносится в элемент массива Vrod:

Vrod(i+1,j2,k2,l2,m2)=Rodтек. (3.144) По (3.138) рассчитывается стоимость перемещения Lтек от на чальной вершины до вершины-преемника sj1=(i+1,j2,k2,l2,m2) через текущую вершину si1=(i,j,k,l,m), которая заносится в элемент массива Vdlin:

Vdlin(i+1,j2,k2,l2,m2)=Lтек. (3.145) В элементе массива Vfront с индексами (i+1,j2,k2,l2,m2) сохраня ется информация о том, что вершина-преемник sj1 уже просматрива лась, т.е. выполняется присваивание данному элементу единичного значения по (3.137).

5.5. Данный пункт выполняется после того, как завершились вложенные циклы по (j,k,l,m), на текущей итерации цикла по i, т.е. по сле того, как все возможные вершины-преемники для всех вершин со значением индекса i были посещены. Перед увеличением значения i на единицу выполняется следующая последовательность действий.

Используя вложенные циклы по j,k,l,m, где j[1;

jmax];

k[1;

kmax];

l[1;

lmax];

m[1;

mmax], для каждого сочетания индексов (i+1), j, k, l, m проверяется выполнение условия Vfront(i+1,j,k,l,m)=1. (3.146) При выполнении данного условия вершины следующего за теку щим ряда с одинаковыми значениями координаты x [с индексом (i+1)] закрываются, т.е. соответствующая вершина помечается как пройденная и закрытая:

Vfront(i+1,j,k,l,m)=2. (3.147) Таким образом, помечаются не все вершины ряда с индексом (i+1), а только свободные и при этом просмотренные на текущей ите рации цикла i. Вершины, занятые препятствиями, а также не вошед шие в множество проверяемых вершин в массиве Vfront, остаются не помеченными как закрытые (сохраняются старые значения соответст вующих элементов). Это позволяет исключить их из рассмотрения как вершины-родители на следующей итерации цикла i.

Множество проверяемых вершин на каждой итерации i формиру ется в пространстве состояний объекта-груза, представляющем собой равномерную решетку линейных (x, y, z) и угловых (, ) координат, по принципу развертывания-свертывания дерева поиска. Дерево по иска развертывается из единственной начальной вершины sнач по принципу рассмотрения всех возможных вершин-преемников для множества вершин, рассмотренных на предыдущей итерации i [коор динаты x, по условиям (3.133), (3.146), (3.147)], и свертывается в единственную конечную вершину sкон по граничным условиям (3.135).

Двухмерная иллюстрация развертывания-свертывания дерева поиска (движения фронта волны) приведена на рис. 3.35.

6. После завершения всех вложенных циклов по i, j, k, l, m (про хождения фронта волны) происходит восстановление найденной оп тимальной по значению целевой функции траектории по кодам вер шин-родителей.

6.1. В качестве первой вершины-преемника назначается sкон, для которой из массива Vrod восстанавливается код вершины-родителя:

Rodтек=Vrod(imax,jкон,kкон,lкон,mкон), (3.148) где jкон= yк0/l ;

kкон= zк0/l ;

lкон= (к0–min)/u ;

mкон= (к0–min)/u. (3.149) 6.2. Восстанавливаются индексы вершины-родителя si1=(i,j,k,l,m) по коду Rodтек и индексам вершины-преемника sj1=(i2,j2,k2,l2,m2).

При рассмотрении конечной вершины, с которой начинается восста новление траектории, i2=imax;

j2=jкон;

k2=kкон;

l2=lкон;

m2=mкон. В сим волах программирования с использованием операции получения це лочисленного остатка от деления (%) зависимости выглядят следую щим образом:

dm=Rodтек % 10;

Rodтек= Rodтек – dm;

dl=(Rodтек % 100)/10;

Rodтек= Rodтек – dl10;

dk=(Rodтек % 1000)/100;

Rodтек= Rodтек – dk100;

dj=Rodтек % 1000;

(3.150) dj= dj–2;

dk= dk–2;

dl= dl–2;

dm=dm–2;

i=i2–1;

j=j2+dj;

k=k2+dk;

l=l2+dl;

m=m2+dm. (3.151) С использованием традиционной математической формы записи выражения (3.150) будут иметь следующий вид:

dm=(Rodтек – Rodтек/10 10);

Rodтек= Rodтек – dm;

dl=(Rodтек – Rodтек/100 100)/10;

Rodтек= Rodтек – dl10;

dk=(Rodтек – Rodтек/1000 1000)/100;

Rodтек= Rodтек – dk100;

dj= Rodтек/1000. (3.152) После восстановления индексов i,j,k,l,m пересчитывается код Rodтек по (3.148) с подстановкой значений индексов i2=i;

j2=j;

k2=k;

l2= l;

m2=m. (3.153) Последовательность действий пункта 6.2 алгоритма выполняется в цикле imax раз. В результате формируется траектория S* из точек ви да (3.50) с использованием зависимостей (3.100).

Пуск Ввод исходных данных: sнач=(xн0, yн0, zн0, н0, н0);

sкон=(xк0, yк0, zк0, к0, к0);

v { Rig };

imax;

jmax;

kmax;

lmax;

mmax;

[YПР];

c;

u;

opt;

lзап_г;

lзап_в Построение массива гиперповерхности [Ymin] по методике раздела 3. i jнач= yн0/l ;


kнач= zн0/l ;

lнач= (н0–min)/u ;

i=1;

iimax;

i=i+ mнач= (н0–min)/u ;

j Vfront(1,jнач,kнач,lнач,mнач)=2;

j=1;

jjmax;

j=j+1 Vdlin(1,jнач,kнач,lнач,mнач)= y=jl i 7 i=1;

i(imax–1);

i=i+ k k=1;

kkmax;

k=k+ jдmin=i–(imax–jmax);

jдmax=(imax+jmax)–i;

8 kдmin=i–(imax–kmax);

kдmax=(imax+kmax)–i;

l lдmin=i–(imax–lmax);

lдmax=(imax+lmax)–i;

l=1;

llmax;

l=l+ mдmin=i–(imax–mmax);

mдmax=(imax+mmax)–i;

m m=1;

mmmax;

m=m+1 j 10 j=max(1;

jдmin);

Нет Да ymin(j,k,l,m) jmin(jдmax;

jmax);

j=j+ Vfront(i,j,k,l,m)=0 Vfront(i,j,k,l,m)=–1 k k=max(1;

kдmin);

13 kmin(kдmax;

kmax);

Vrod(i,j,k,l,m)= k=k+ Vdlin(i,j,k,l,m)= l m l=max(1;

lдmin);

lmin(lдmax;

lmax);

16 l=l+ l m k m=max(1;

mдmin);

mmin(mдmax;

mmax);

18 m=m+ j Нет Да 19 2 Vfront(i,j,k,l,m)= i Рис. 3.36. Блок-схема модифицированного волнового алгоритма для пяти учитываемых обобщенных координат груза (начало) 1 Вычисление Li1,j1 (СВД) между вершинами si1=(i,j,k,l,m) и sj1=(i+1,j2,k2,l2,m2) по (3.18) j j2=(j–1);

j2(j+1);

Lтек=Vdlin(i, j, k, l, m)+Li1,j j2=j2+ 29 Нет k2 Да LтекVdlin(i+1,j2,k2,l2,m2) k2=(k–1);

k2(k+1);

k2=k2+ l2 Vdlin(i+1, j2, k2, l2, m2)=Lтек l2=(l–1);

l2(l+1);

l2=l2+ Rodтек=1000((j–j2)+2)+ 31 +100((k–k2)+2)+10((l–l2)+2)+((m–m2)+2) m m2=(m–1);

m2(m+1);

Vrod(i+1, j2, k2, l2, m2)=Rodтек m2=m2+ Да Нет Vfront(i+1,j2,k2,l2,m2)= 39 Да Нет Rodтек=1000((j–j2)+2)+ Vfront(i+1,j2,k2,l2,m2)=0 +100((k–k2)+2)+10((l–l2)+2)+((m–m2)+2) Vrod(i+1, j2, k2, l2, m2)=Rodтек Вычисление Li1,j1 (СВД) между вершинами m si1=(i,j,k,l,m) и sj1=(i+1,j2,k2,l2,m2) по (3.18) 47 Lтек=Vdlin(i, j, k, l, m)+Li1,j l2 Vdlin(i+1, j2, k2, l2, m2)=Lтек 48 Vfront(i+1,j2,k2,l2,m2)= k m j2 l k j Рис. 3.36. Блок-схема модифицированного волнового алгоритма для пяти учитываемых обобщенных координат груза (продолжение) i j j=1;

jjmax;

j=j+ jкон= yк0/l ;

kкон= zк0/l ;

lкон= (к0–min)/u ;

k mкон= (к0–min)/u k=1;

kkmax;

k=k+ l i2=imax;

j2=jкон;

k2=kкон;

l2=lкон;

m2=mкон l=1;

llmax;

l=l+1 66 Rodтек=Vrod(i2,j2,k2,l2,m2) m m=1;

mmmax;

m=m+1 i i=(imax–1);

i1;

i=i– Нет Да dm=Rodтек%10;

Rodтек=Rodтек–dm;

Vfront(i+1,j,k,l,m)= dl=(Rodтек%100)/10;

Rodтек=Rodтек–dl10;

dk=(Rodтек%1000)/100;

Vfront(i+1,j,k,l,m)=2 Rodтек=Rodтек–dk100;

dj=Rodтек% 70 dj= dj–2;

dk= dk–2;

dl= dl–2;

dm=dm– m j=j2+dj;

k=k2+dk;

l=l2+dl;

m=m2+dm l p=i;

xp=il;

yp=jl;

zp=kl;

p=(l–0,5lmax)u;

p=(m–0,5mmax)u k i2=i;

j2=j;

k2=k;

l2= l;

m2=m j Rodтек=Vrod(i2,j2,k2,l2,m2) i Дискретная локальная оптимизация найденной траектории по методике раздела 3. Вывод резуль Останов татов: S*, L* Рис. 3.36. Блок-схема модифицированного волнового алгоритма для пяти учитываемых обобщенных координат груза (окончание) 7. Выполняется локальная оптимизация траектории S* по методи ке, изложенной в разделе 3.5.

8. Определяется значение целевой функции L* оптимизированной траектории S* по (3.19).

9. Вывод результатов: L*, S*. Окончание работы алгоритма.

Блок-схема модифицированного волнового алгоритма перемеще ния груза, положение которого определяют 3 линейные и 2 угловые обобщенные координаты, приведена на рис. 3.36.

Вычислительные реализации модифицированного волнового ал горитма и описанной методики на его основе в средах Microsoft Visual C++ и MATLAB показали работоспособность и эффективность алго ритма для решения поставленной задачи.

3.11. Сравнительный анализ алгоритмических и программных реализаций методик планирования траектории Необходимо провести сравнение разработанных алгоритмов и методик на их основе по принятым в монографии критериям оценки эффективности. Для этого было проведено несколько серий вычисли тельных экспериментов.

Наиболее часто при работе ГПК на строительных площадках, в цехах и складских помещениях встречаются препятствия в виде стен, перекрытий, стеллажей, контейнеров, столбов и свай, которые могут быть описаны в форме параллелепипедов различных размеров [88].

Методом эталонных тестов производилось сравнение разрабо танных методик поиска оптимальной траектории объекта на основе: – направленного волнового алгоритма;

2 – алгоритма роевого интел лекта;

3 – генетического подхода;

4 – алгоритма декомпозиции ли нейных и угловых координат;

5 – алгоритма вероятностной дорожной карты;

6 – распараллеленного алгоритма роевого интеллекта;

7 – рас параллеленного алгоритма декомпозиции линейных и угловых коор динат. Для этого были проведены несколько серий вычислительных экспериментов, моделирующих процесс поиска оптимальной по зна чению целевой функции траектории объекта-груза в среде с полидис тантными поверхностями, построенными вокруг реальных поверхно стей препятствий.

Исходные поверхности препятствий формировались случайным образом из сочетания нескольких параллелепипедов, каждый из кото рых имел случайные размеры. Для всех экспериментов рассматрива лось рабочее пространство в виде куба с размерами 101010 УЛЕ (см. рис. 3.1). Линейные координаты начальной и конечной точек по ложения условного центра груза (начала локальной системы коорди нат груза OgХgYgZg) принимались постоянными для всех эксперимен тов. Начальная точка имела линейные координаты (УЛЕ): [xн0;

yн0;

zн0]=[0;

2;

5], конечная – [xк0;

yк0;

zк0]=[10;

2;

5]. Начальные и конечные значения угловых координат также принимали постоянные нулевые значения (рад): [н0;

н0]=[0;

0];

[к0;

к0]=[0;

0].

Количество разбиений каждой траектории на кусочно-линейные участки принималось равным imax=20. Соответственно максимальные значения индексов остальных координат груза при поиске траектории принимались равными jmax=20;

kmax=20;

lmax=5;

mmax=17.

Сочетание линейных и угловых координат груза позволяет пред ставить область перемещений груза в виде гиперкуба с размерами равномерной сетки индексов (РСИ) 202020517.

В то же время для задания исходной поверхности препятствий, построения полидистантных поверхностей вокруг препятствий и для проведения дискретной локальной оптимизации найденных траекто рий использовалось более подробное описание рабочей области в трехмерном пространстве в виде куба с размерами (РСИ) 100100100. То есть использовался иерархический подход, при ко тором задание исходной поверхности и локальная оптимизация тра ектории проводились с более мелким шагом описания препятствий (0,1 УЛЕ), а собственно поиск траектории с использованием разрабо танных методик – с более крупным шагом описания препятствий (0, УЛЕ). Это позволило более точно провести локальную оптимизацию.

Пуск i1= 2 Ввод исходных данных: i i=1;

ijmax;

i=i+kм YЭ01;

kм i1=i1+ k1= k k=1;

kkmax;

k=k+kм k1=k1+ YЭ05(i1,k1)=YЭ01(i,k) Вывод результатов: k YЭ i Останов Рис. 3.37. Блок-схема алгоритма редукции полидистантной поверхности вокруг препятствий Применение иерархического подхода вызвано большой размер ностью задачи, сложность которой экспоненциально возрастает при уменьшении шага дискретизации координат. Переход от исходного к укрупненному описанию линейных координат выполнялся методом редукции [164]. Использовался коэффициент масштабирования kм ли нейных координат, значение которого принималось равным kм=5. Ал горитм перехода от полидистантной поверхности YЭ01, описанной с мелким шагом, к поверхности YЭ05 с крупным шагом приведен на рис.

3.37.

Для методик, использующих элементы вероятностного выбора (на основе алгоритмов 2, 3 и 5), предварительно были проведены не сколько серий экспериментов, по 1200 независимых экспериментов для каждого сочетания значений варьируемых параметров, на рабочей области с одинаковым детерминированным расположением препятст вий, описываемым следующими условиями на РСИ 100100100 (в качестве примера, рис. 3.38):

Yпр(i,k)=2,5 УЛЕ – при (29i31) (20k80);

Yпр(i,k)=8,0 УЛЕ – при (49i51) (50k100);

Yпр(i,k)=8,0 УЛЕ – при (79i81) (1k50);

Yпр(i,k)=0,0 УЛЕ – в остальных случаях. (3.154) Y Z X Рис. 3.38. Рабочая область тестового примера с детерминированным расположением препятствий Груз в форме цилиндра с габаритными размерами (габаритный диаметр 0,5 УЛЕ и высота 2,0 УЛЕ), был представлен в виде набора точек (cг=12) на поверхности объемного тела с координатами в УЛЕ:

v { Rig }={[0,25;

0;

1;

1];

[0,25;

0;

0;

1];

[0,25;

0;

–1;

1];

[–0,25;

0;

1;

1];

[–0,25;

0;

0;

1];

[–0,25;

0;

–1;

1];

[0;

0,25;

1;

1];

[0;

0,25;

0;

1];

[0;

0,25;

–1;

1];

[0;

–0,25;

1;

1];

[0;

–0,25;

0;

1];

[0;

–0,25;

–1;

1]}. (3.155) Проведение вычислительных экспериментов на тестовом приме ре с детерминированным расположением препятствий позволило обосновать рациональные значения основных внутренних параметров соответствующих алгоритмов с элементами вероятностного выбора для решения поставленной задачи и для последующего сравнения с детерминированными алгоритмами.

Результаты экспериментов на тестовом примере с детерминирован ным расположением препятствий приведены ниже. Для оценки алгорит мов в данных сериях экспериментов использовались 6 частных показате лей: 1) математическое ожидание значений целевой функции неоптими зированной найденной траектории L *н;


2) математическое ожидание зна чений целевой функции той же траектории, оптимизированной при по мощи методики дискретной локальной оптимизации L *;

3) медиана зна чений целевой функции неоптимизированной траектории Me(L*н);

4) ме диана значений целевой функции оптимизированной траектории Me(L*);

5) стандартное отклонение значений целевой функции неоптимизирован ной траектории (L*н);

6) стандартное отклонение значений целевой функ ции оптимизированной траектории (L*). Показатели по дискретному ряду вычисляются по следующим зависимостям [5, 18, 19, 24, 38, 70, 131]:

() 1 ne * Lн = Lн i, * (3.156) ne i = где L*н – значение целевой функции неоптимизированной траектории для данного эксперимента;

ne – число независимых экспериментов.

() 1 ne * L* = L i, (3.157) ne i = где L* – значение целевой функции оптимизированной траектории для данного эксперимента;

ne – число независимых экспериментов.

(( ) ) () () Me L* = L* (ne 2 ) + L* (ne 2 )+1, (3.158) н н н где вектор значений отдельных экспериментов {(L*н)i} ine1 предвари = тельно отсортирован по возрастанию;

количество ne – четное.

) (( ) () () Me L* = L* (ne 2 ) + L* (ne 2 )+1, (3.159) где вектор значений отдельных экспериментов {(L*)i} ine1 предвари = тельно отсортирован по возрастанию;

количество ne – четное.

20,6 15,4 0, 15, Me(L*) 20,4 0, 15,2 (L*н) * Me(L н) 15, 20,2 0, 20 0, L* 14,9 (L*) L *н 19,8 14,8 0, 200 rкол 100 100 200 rкол 300 100 150 200 250 rкол 15, 20,6 0, Me(L*) (L*н) 20, 15 0, Me(L*н) 20,2 L* 14,5 0, (L*) L* н 19,8 0, 50 150 G 50 150 G 350 50 150 G 20,5 15,2 Me(L*н) Me(L*) (L*н) 15, 20 0, 15, 19,5 15,05 0, 19 0, 14, 18,5 (L*) 0, L *н L* 14, 18 14,85 0,6 0, 0,6 0,8 0,6 0, 0,2 0, 0,2 0,4 0,2 0, 0,4 0, 0,2 0,4 0, 0,8 0, 0,8 0,6 0,4 0,8 0, Рис. 3.39. Некоторые результаты экспериментов с использованием алгоритма роевого интеллекта на тестовом примере с детерминированным расположением препятствий ( ).

ne () Lн L* * = н L* i (3.160) н ne i =1 () ne L* L* i (L ) =. (3.161) i =1 ne 18,95 0, 14, Me(L*) (L*н) * Me(L н) 14,15 0, 18, 14, L* 0, 14, 18, 0, (L*) L *н 18,8 0, 13, 10 20 30 40 50 G 70 10 20 30 40 50 G 10 20 30 40 50 G 20,5 14, (L*н) * 0, Me(L н) 20 * Me(L ) 14, 0, 19, 14, (L*) 0, L *н 0, 18,5 L* 18 13, 10 20 30 40 50 C 10 20 30 40 50 C 70 10 20 30 40 50 C Рис. 3.40. Некоторые результаты экспериментов с использованием алгоритма на основе генетического подхода на тестовом примере с детерминированным расположением препятствий Алгоритм роевого интеллекта (2). Исходные данные для экспери ментов принимали следующие значения (по умолчанию): sнач=(0, 2, 5, 0, 0);

sкон=(10, 2, 5, 0, 0);

imax=20;

jmax=20;

kmax=20;

lmax=5;

mmax=17;

rкол=200;

=0,5;

=0,5;

er=3;

G=200;

c=1;

u=/8;

T(1)= [i1,j1] ing j1=1 =0,1;

opt=0,001;

1, v lзап_г=0,5;

lзап_в=0,5. Матрица [Yпр] и множество векторов { Rig } формиро вались по (3.154) и (3.155) соответственно.

На основе анализа представленных (рис. 3.39) и других получен ных для алгоритма роевого интеллекта зависимостей были приняты следующие значения варьируемых собственных параметров алгорит ма для дальнейшего сравнения с другими алгоритмами при стохасти ческом формировании препятствий: rкол=200;

=0,5;

=0,5;

G=200.

Значения остальных параметров сохранялись по умолчанию.

Алгоритм на основе генетического подхода (3). Исходные дан ные для экспериментов принимали следующие значения (по умолча нию): sнач=(0, 2, 5, 0, 0);

sкон=(10, 2, 5, 0, 0);

imax=20;

jmax=20;

kmax=20;

lmax=5;

mmax=17;

G=30;

C=50;

E=C/2;

M=0,1C;

c=1;

u=/8;

opt=0,001;

lзап_г=0,5;

lзап_в=0,5. Матрица [Yпр] и множество векторов v { Rig } формировались по (3.154) и (3.155) соответственно.

На основе анализа представленных (рис. 3.40) и других получен ных для алгоритма на основе генетического подхода зависимостей были приняты следующие значения варьируемых собственных пара метров алгоритма для дальнейшего сравнения с другими алгоритмами при стохастическом формировании препятствий: G=50;

C=50. Значе ния остальных параметров сохранялись по умолчанию.

Алгоритм вероятностной дорожной карты (5). Исходные дан ные для экспериментов принимали следующие значения (по умолча нию): sнач=(0, 2, 5, 0, 0);

sкон=(10, 2, 5, 0, 0);

imax=20;

jmax=20;

kmax=20;

lmax=5;

mmax=17;

ng=400;

c=1;

u=/8;

vopt=0,001;

lзап_г=0,5;

lзап_в=0,5.

Матрица [Yпр] и множество векторов { Rig } формировались по (3.154) и (3.155) соответственно.

22 16,2 2, Me(L*) L *н (L*н) 21 16 20 15,8 1, 19 15,6 L* 18 15, Me(L*н) 0, (L*) 17 15,2 200 600 1000 1400 200 600 1000 1400 200 600 1000 ng ng ng Рис. 3.41. Некоторые результаты экспериментов с использованием алгоритма вероятностной дорожной карты на тестовом примере с детерминированным расположением препятствий: – при заполнении пространства случайно сформированными точками;

- - - – при заполнении пространства квазислучайными точками (последовательности Холтона) При исследовании алгоритма вероятностной дорожной карты была реализована возможность заполнения пространства обобщенных коор динат груза квазислучайными точками в виде последовательностей Холтона [184, 221, 235]. Точки Холтона строятся по известным детер минированным зависимостям [184] и обеспечивают равномерное запол нение пространства. Некоторые методики и алгоритмы оптимизации показывают лучшие результаты при использовании последовательно стей Холтона, чем при использовании случайных последовательностей.

Доказано преимущество использования последовательностей Холтона перед заполнением пространства равномерной сетью [184, 221, 235].

Однако при решении данной задачи поиска оптимальной траек тории груза в пространстве его обобщенных координат с учетом пре пятствий использование последовательностей Холтона не оказало существенного влияния на результаты (рис. 3.41) ввиду достаточно большого количества точек и вследствие этого многовариантности решений.

На основе анализа представленных и других полученных для ал горитма вероятностной дорожной карты зависимостей было принято следующее значение варьируемого собственного параметра алгорит ма (числа точек) для дальнейшего сравнения с другими алгоритмами при стохастическом формировании препятствий: ng=800. Значения остальных параметров сохранялись по умолчанию.

Y Z б) X а) Рис. 3.42. Примеры найденной алгоритмом на основе гене тического подхода траектории на тестовом примере с детерми нированным расположением препятствий: а – до локальной оптимизации;

б – после локальной оптимизации Примеры найденной алгоритмом на основе генетического подхо да траектории S* (точки начала координат системы груза) и этой же траектории после заключительной локальной оптимизации с указани ем положений осей груза в форме цилиндра приведены на рис. 3.42, а и б соответственно. Для неоптимизированной траектории положения осей цилиндра не показаны, чтобы не затемнять рисунок.

Сравнительный анализ разработанных алгоритмов и методик на их основе. Для сравнения алгоритмов использовались статистические критерии, полученные при использовании различных методик, но для одних и тех же численных значений исходных данных задачи [Yпр], ко торые формировались для каждого эксперимента случайным образом.

Была проведена серия из 10000 компьютерных экспериментов, моделирующих процесс поиска оптимальной траектории объемного объекта-груза в среде с полидистантными поверхностями, построен ными вокруг реальных поверхностей препятствий [Yпр], сформиро ванных случайным образом из сочетания нескольких параллелепипе дов, каждый из которых имеет случайные размеры.

Число параллелепипедов n в каждом эксперименте генерирова лось по равномерному закону распределения случайной величины в интервале от 1 до 15. Размеры каждого параллелепипеда формирова лись в пределах (xyz) от 000 УЛЕ до 454 УЛЕ также по равно мерному закону распределения. Допускалось перекрытие объемов и поверхностей параллелепипедов при их наложении [88, 124].

Для каждого эксперимента определялись путем непосредствен ных вычислительных измерений, реализованных программно, значе ния Tр и Me и рассчитывалось по результатам вычислительных изме рений значение Lусл по (3.21), (3.22). Некоторые результаты сравни тельного анализа методик и алгоритмов по принятым критериям оценки эффективности приведены на рис. 3.43 [124]. Исследования проводились на программных реализациях методик и алгоритмов в среде MS Visual C++ на ПК средней производительности (AMD Athlon 64 X2 Dual Core Processor 5600+ 2.90 GHz).

M, Мб Tр, с 6e 24,897 4, 23, 25 4 3, 15 1,758 1, 10 2 0, 2,611 3, 0,782 2,93 1, 5 0 1 2 3 4 5 1 2 3 4 Lусл,% 17, 15, 10 7, 5 2, 1, 1 2 3 4 Рис. 3.43. Результаты сравнительного анализа методик и алгоритмов по приня тым критериям оценки эффективности: 1 – направленный волновой алгоритм;

– алгоритм роевого интеллекта;

3 – алгоритм на основе генетического подхода;

– алгоритм декомпозиции линейных и угловых координат;

5 – алгоритм вероят ностной дорожной карты;

– математическое ожидание значения времени рас четов распараллеленных алгоритмов 2 и 4, верхний предел Поскольку было выбрано 3 самостоятельных критерия оценки алго ритмов и методик, результаты анализа могут быть интерпретированы графически в удобном для восприятия и наглядном виде как совокуп ность векторов в трехмерном пространстве координат [ T р Me Lусл ]. Для этого было проведено масштабирование отображаемых результатов экс периментов по максимальным полученным значениям каждого критерия.

Каждой методике в 3-мерном пространстве критериев ставятся в соот ветствие точка и ее вектор из начала координат. Векторное представле ние разработанных алгоритмов и методик по принятым критериям эф фективности как компонентам векторов, а также проекции векторов на три плоскости ([ T р Me], [ T р Lусл ], [Me Lусл ]) приведены на рис. 3.44.

Lусл, % Lусл, % 4 4 5 3 Tр,с Lусл Tр Me Me, Мб Рис. 3.44. Векторное представление критериев эффективности разработанных алгоритмов и методик При сравнении алгоритмов по принятым критериям оценки эф фективности в трехмерном пространстве положений векторного кри терия эффективности могут быть выделены отдельные области, соот ветствующие оптимальному значению какого-либо одного, двух или всех трех компонент вектора, определяемые условиями вида [124] T р ( T р )max;

Me(Me)max;

Lусл ( Lусл )max, (3.162) где ( T р )max;

(Me)max;

( Lусл )max – максимальные предельно допустимые (заданные) значения критериев.

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

3.45, а, б, в).

Условно быстрые алгоритмы Lусл, % Lусл, % Условно точные алгоритмы 5 4 1 Tр,с Tр,с Me, Мб Me, Мб б) а) Lусл, % Lусл, % Условно компактные алгоритмы 3 Me, Мб Tр,с Tр,с Me, Мб г) в) Рис. 3.45. Области условно быстрых (а), условно точных (б), условно компакт ных (в) алгоритмов и их пересечения (г): – последовательные алгоритмы, по падающие в соответствующую область оптимальности В качестве примера при ( T р )max=5 с;

(Me)max=2 Мб;

( Lусл )max=5% к условно быстрым алгоритмам могут быть отнесены 1, 3 и 5 алго ритмы, к условно точным – 1 и 4 алгоритмы, к условно компактным – 2, 3 и 5 алгоритмы. В случае распараллеливания алгоритмов 2 и 4 они также попадают в область условно быстрых.

Ни один из разработанных алгоритмов не удовлетворяет условию оптимальности по всем трем критериям одновременно, т.е. не входит в область пересечения условно быстрых, условно точных и условно компактных алгоритмов (см. рис. 3.45, г), однако отдельные алгорит мы сочетают оптимальность по двум критериям. В частности, алго ритмы 3 и 5 одновременно быстрые и компактные, причем алгоритм в большей степени. Алгоритмы 1 и распараллеленный 4 одновремен но быстрые и точные, причем алгоритм 1 в большей степени.

Результаты сравнения алгоритмов подтверждают предположение о том, что существует взаимосвязь между оптимальностью алгоритма, ко торая в данном случае выражается его точностью Lусл, и сложностью ал горитма (временной или пространственной), которая в данном случае вы ражается через критерии T р и Me. Т.е. невозможно уменьшить сложность алгоритма (временную либо пространственную, которые также взаимо связаны между собой), не жертвуя при этом его оптимальностью, что хо рошо иллюстрируется алгоритмом на основе генетического подхода.

Использование алгоритма интеллектуальной поддержки САПР выбора методики оптимизации траектории на основе полученных значений частных критериев оценки эффективности показало, что в множество неулучшаемых методик входят методики: № 1 (на осно ве направленного волнового алгоритма), № 3 (на основе генетическо го подхода) и № 7 (распараллеленный алгоритм декомпозиции линей ных и угловых координат).

Рис. 3.46. Пример диаграммы номеров оптимальных методик с тоновой индика цией для плоскости (Me)maxтек= 6 Мб Вывод результатов (трехмерный массив Nопт) осуществлялся в форме совокупности диаграмм с цветовой (тоновой) индикацией.

Пример диаграммы номеров оптимальных методик с тоновой инди кацией для плоскости [ T р Lусл ] при значении (Me)maxтек= 6 Мб при веден на рис. 3.46.

Эксперимент проводился при следующих численных значениях исходных данных для алгоритма интеллектуальной поддержки САПР:

( T р )max=25 c;

(Me)max=6 Мб;

( Lусл )max=20 %;

( T р )=1 c;

(Me)=1 Мб;

r ( Lусл )=1 %;

{( GTML )i}={[3,74 3,31 1,49];

[23,19 1,75 15,91];

[0, 0,95 7,5];

[24,89 4,95 2,6];

[1,78 1,56 17,01];

[3,31 1,75 15,91];

[2,93 4, 2,6]}, i[1;

7].

Учитывая, что при современном уровне развития компьютерной техники требование компактности не является критичным в диапазо не значений всех рассматриваемых алгоритмов (не более 6 Мб), сле дует отметить направленный волновой алгоритм (№ 1) как наиболее точный и в то же время достаточно быстрый. В пользу его перспек тивности для решения поставленной задачи говорит и тот факт, что это детерминированный алгоритм в отличие от всех остальных, кроме алгоритма № 4 (7). Т.е. он находит единственно возможное и посто янное решение задачи при одних и тех же численных значениях ис ходных данных.

4. РАЗРАБОТКА МЕТОДИК ПЛАНИРОВАНИЯ ТРАЕКТОРИИ ПЕРЕМЕЩЕНИЯ ОБЪЕМНОГО ОБЪЕКТА-ГРУЗА В ПРОСТРАНСТВЕ КОНФИГУРАЦИЙ ГРУЗОПОДЪЕМНОГО КРАНА С УЧЕТОМ УГЛОВОЙ ОРИЕНТАЦИИ ГРУЗА И ПРЕПЯТСТВИЙ 4.1. Постановка задачи планирования траектории перемещения грузоподъемным краном груза в пространстве конфигураций грузоподъемного крана с учетом угловой ориентации и препятствий В соответствии с поставленной целью работы необходимо ре шить задачу синтеза оптимальных технологических параметров рабо чего процесса ГПК на примере стрелового автомобильного гидравли ческого крана в соответствии с заданными критериями эффективно сти. Для этого необходимо в качестве предварительного этапа решить задачу планирования траектории перемещения ГПК груза в простран стве конфигураций ГПК с учетом угловой ориентации и препятствий.

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

Это обуславливает постановку задачи в пространстве конфигура ций ГПК. При постановке задачи и при ее дальнейшем решении при няты те же допущения, которые были приняты в разделе 3.1 для гео метрической задачи, сформулированной в декартовых координатах рабочей области и препятствий.

Кроме того, при планировании траектории в пространстве конфи гураций на траекторию дополнительно накладываются естественные ограничения в виде предельно допустимых минимальных и макси мальных конструктивных значений управляемых обобщенных коор динат q8min;

q8max;

q9min;

q9max;

q10min;

q10max.

Препятствия Начальная Конечная точка sнач точка sкон (xн0, yн0, zн0) Y (xк0, yк0, zк0) Yg L* sш Yg Xg Zg (xш0,yш0,zш0) Og Og Zg Xg X Y Z0 Z O X O Рис. 4.1. Начальное и конечное положения перемещаемого груза, начальное положение ГПК (пример) Задано положение базового шасси в неподвижной системе коор динат O0Х0Y0Z0, связанной с рабочей областью перемещений, в виде декартовых координат точки sш начала локальной системы координат шасси O1Х1Y1Z1:

sш=(xш0, yш0, zш0)=(q1, q2, q3), (4.1) где q1, q2, q3 – первые три линейные обобщенные координаты механи ческой системы ГПК (декартовы координаты точки O1 в системе ко ординат O0Х0Y0Z0, рис. 4.1).

Заданы линейные координаты груза в начальной sнач и конечной sкон точках траектории груза в пространстве (УЛЕ) (см. рис. 4.1):

sнач = [xн0;

yн0;

zн0];

sкон = [xк0;

yк0;

zк0], (4.2) где xн0, yн0, zн0 – линейные координаты точки начала локальной систе мы координат груза OgХgYgZg в неподвижной системе координат O0Х0Y0Z0, связанной с рабочей областью перемещений, соответст вующие начальному положению груза;

xк0, yк0, zк0 – линейные коорди наты, соответствующие конечному положению груза.

В собственной локальной системе координат груза OgХgYgZg за v даны координаты множества точек { Rig }, ig[1;

cг] на поверхности объемного тела груза, определяющие его форму. Координаты точек [ ] v заданы векторами вида Rig = xig yig zig 1 T, где xig, yig, zig – коор динаты точки ig в локальной системе координат груза.

В собственной локальной системе координат базового шасси v O1Х1Y1Z1 заданы координаты множества точек { Ris }, is[1;

cs] на по верхности объемного тела шасси, определяющие его форму, в том числе координаты характерных точек четырех гидравлических опор Координаты точек заданы векторами вида (is=1…4).

v Ris = [xis yis zis 1], где xis, yis, zis – координаты точки is базового шас T си в собственной локальной декартовой системе координат шасси.

Также в локальных системах координат стрелы O3Х3Y3Z3 и теле скопического звена Ov Х4Y4Z4 заданы координаты множеств точек v { Rio3 }, io3[1;

co3] и { Rio 4 }, io4[1;

co4] на поверхности объемных тел стрелы и телескопического звена соответственно, определяющие их форму. Координаты точек заданы векторами вида v v Rio3 = [xio3 yio3 zio3 1] и Rio4 = [xio4 yio4 zio4 1] соответственно.

T T В качестве исходных данных задачи выступают lзап_г – запас рас стояния в горизонтальном направлении и lзап_в – запас расстояния в вертикальном направлении, необходимые для построения полидис тантной поверхности YЭ вокруг реальной поверхности препятствий YПР по методике, изложенной в разделе 3.3.

Также исходными данными задачи являются следующие пара метры и коэффициенты: q7 – значение угла поворота поворотной платформы ГПК, достаточное, чтобы обеспечить обход возможных препятствий при перемещении груза из sнач в sкон (q7=/2);

uш – шаг дискретизации угла поворота базового шасси вокруг вертикальной оси Y1 (обобщенной координаты q6) при проверке пересечений шасси и препятствий;



Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 9 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.