Материал: 2426
этого наиболее велика при: 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).
В результате формируется набор общих субоптимальных траек-
торий {SLУin}innдек=mдек , где 0≤mдек≤nдек, поскольку некоторых неоптимизированных траекторий SLУin с наименьшими значениями индекса in =0…mдек может не существовать по причине отсутствия соответствующих «угловых траекторий» У*in. Каждая субоптимальная траектория SLУin будет соответствовать определенному значению полуосей
140
эллипса удалений Rг и Rв и может быть оценена по значению целевой функции Lin, определенной по (3.19).
Зазор
а) |
|
б) |
|
||
|
|
Рис. 3.32. Примеры общей траектории движения груза SLУin (а), показаны последовательные положения оси груза в форме цилиндра и локальной оптимизации по линейной составляющей траектории (SL*)in (б)
9. Из нескольких возможных субоптимальных траекторий
{SLУin}innдек=mдек выбирается траектория SLУ* с минимальным значением целевой функции L*. Для этого при помощи известного алгоритма [74] определяется значение индекса um, соответствующее минимальному значению Lin:
|
|
|
um=Индекс(min({Lin})), |
(3.127) |
|
где {Lin}innдек=m |
дек |
– множество значений целевой функции множества |
|||
|
|
|
|
|
|
траекторий {SLУin}innдек=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У*. Окончание работы алгоритма.
141
|
|
|
Пуск |
1 |
|
|
2 |
|
|
|
|
|
|
|
|
|
|
Ввод исходных данных: sнач=(xн0, yн0, zн0, γн0, ωн0); sкон=(xк0, yк0, zк0, γк0, ωк0); |
|
|||||||
{ R |
}; imax; jmax; kmax; lmax; mmax; [YПР]; nдек, cγω, u, δopt, lзап_г, lзап_в |
|
|
|||||
ig |
|
|
3 |
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
Определение gmin, ∆Rг, ∆Rв |
|
|
|
||
|
|
|
|
|
|
|
||
|
|
|
in |
4 |
|
|
|
|
|
|
|
in=1; in≤nдек; |
|
|
|
|
|
|
|
|
in=in+1 |
5 |
|
|
||
|
|
|
|
|
|
|||
|
|
|
(Rг)in=lзап_г+gmin+in∙∆Rг; |
|
|
|
||
|
|
|
(Rв)in=lзап_в+gmin+in∙∆Rв |
|
|
6 |
||
|
|
|
|
|
|
|
|
|
Построение полидистантной поверхности [YЭ]in вокруг реальной поверхности препятствий [YПР] по методике раздела 3.3 [102]
Формирования матрицы весов PDGin подграфа PGrin линейного пространства по «точкам видимости» по методике, изложенной в п. 3 настоящего алгоритма
Поиск траектории (SL*)in как кратчайшего пути между двумя вершинами подграфа PGrin (slнач и slкон) при помощи алгоритма Дейкстры
Линейная интерполяция траектории (SL*)in на равномерной сетке xi (i [1; imax])
Построение массива гиперповерхности [Ymin]in по методике раздела 3.4
|
|
i=1:imax |
|
11 |
||
|
|
|
|
|
||
|
|
|
|
12 |
|
|
|
|
k= zi/ l |
|
13 |
||
|
|
|
|
|||
|
|
l=1:lmax |
|
|||
|
|
|
|
|
||
|
|
m=1:mmax |
|
14 |
||
|
|
|
|
|
||
17 |
Нет |
15 |
Да |
16 |
||
Pu(i,l,m)=1 |
yi≥Ymin(i,k,l,m) |
|
Pu(i,l,m)=0 |
|||
|
|
|
||||
7
8
9
10
18
Формирования матрицы весов PDGin подграфа PGrin пространства Puin по «точкам видимости» по методике, изложенной в п. 3 настоящего алгоритма
|
|
|
|
|
19 |
|
Поиск траектории (У*)in как кратчайшего пути между двумя вершинами |
||||||
|
||||||
подграфа PGrin пространства Puin при помощи алгоритма Дейкстры |
|
|||||
21 |
Нет |
(У*)in существует? |
20 |
Да 1 |
|
|
Lin=∞; in=in+1 |
|
|
||||
Рис. 3.33. Блок-схема алгоритма декомпозиции линейных и угловых координат в последовательном исполнении (начало)
142
1
22
Формирование общей траектории груза: SLУin = (SL*)in U (У*)in
Локальная оптимизация траектории SLУin по составляющей (SL*)in по методике, изложенной в разделе 3.5, при l=const; m=const
24 |
23 |
|||
|
in |
|
|
|
|
|
25 |
|
|
|
um=Индекс(min({Lin})) |
|
|
26 |
|
|
|
|
|
|
L*=Lum; SLУ*=SLУum |
|
|
|
|
|
|
27 |
|
|
|
|
|
|
Локальная оптимизация траектории SLУ* по методике раздела 3.5 
Вывод результатов: 28
SLУ*, L*
Останов 29
Рис. 3.33. Блок-схема алгоритма декомпозиции линейных и угловых координат в последовательном исполнении (окончание)
|
|
|
|
|
|
|
|
Пуск |
1 |
|
|
|
|
2 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Ввод исходных данных: sнач=(xн0, yн0, zн0, γн0, ωн0); sкон=(xк0, yк0, zк0, γк0, ωк0); |
|||||||||||||||||||||
|
|
{ R }; imax; jmax; kmax; lmax; mmax; [YПР]; nдек, cγω, |
u, δopt, lзап_г, lзап_в |
||||||||||||||||||
|
|
|
ig |
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Определение gmin, ∆Rг, ∆Rв |
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
4 |
|
|
|
|
|
|
5 |
|
|
6 |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
in=1 |
7 |
|
|
in=2 |
|
|
|
|
|
in= nдек |
|
||||||||
|
|
|
|
|
|
8 |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
9 |
|
||||||||||
Выполнение блоков |
|
|
|
Выполнение блоков |
|
… |
|
|
Выполнение блоков |
|
|||||||||||
5-23 последовательного |
|
|
5-23 последовательного |
|
|
5-23 последовательного |
|
||||||||||||||
|
алгоритма |
|
|
|
алгоритма |
|
|
|
|
|
|
|
алгоритма |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
um=Индекс(min({Lin})) |
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
11 |
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
L*=Lum; SLУ*=SLУum |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
12 |
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
Локальная оптимизация траектории SLУ* по методике раздела 3.5 |
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
Вывод результатов: |
13 |
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
SLУ*, L* |
14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Останов |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Рис. 3.34. Блок-схема распараллеленного алгоритма декомпозиции линейных и угловых координат (затемнены блоки, выполняемые параллельно)
143
Блок-схема алгоритма декомпозиции линейных и угловых координат в последовательном исполнении приведена на рис. 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 – глубина решения), не позволяющая практически использовать его при больших размерах графа задачи. Понятие больших размеров определяется быстродействием вычислительной техники на момент проведения исследований.
Алгоритм в общем случае осуществляет поиск во все стороны от начального узла графа, при этом обрабатывается очень много лишних узлов, заведомо не содержащих оптимальный путь. Поиск в ширину
144