Материал: 2426

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

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

break=0. (3.104)

4.2. В цикле с идентификатором i2 происходит изменение значения индекса i2 от 1 до некоторого максимального значения i2max, определяемого условием

i2=4; j2 [1;8]

…………………………………………

Рис. 3.23. Графическая интерпретация модификации рекурсивного алгоритма деления отрезка пополам (пример на плоскости, дерево рекурсии)

Изменение индекса i2 на каждой итерации цикла i2 происходит по закону геометрической прогрессии (увеличение в 2 раза):

125

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

(рис. 3.23).

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

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

x2нач=xi1+(xi1–xj1)/(i2∙2); y2нач=yi1+(yi1–yj1)/(i2∙2); z2нач=zi1+(zi1–zj1)/(i2∙2);

γ2нач=γi1+(γi1–γj1)/(i2∙2); ω2нач=ωi1+(ωi1–ωj1)/(i2∙2). (3.110)

Затем во вложенном цикле j2 вычисляются координаты текущей проверяемой точки:

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

break=1. (3.113)

126

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

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

S*={sp}sn= .

p 1

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

Построение массива гиперповерхности [Ymin] по методике раздела 3.4

4

s1=sнач=(xн0, yн0, zн0, γн0, ωн0)

p=2 5 6

ip=Rand∙imax; jp=Rand∙jmax; kp=Rand∙kmax; lp=Rand∙lmax; mp=Rand∙mmax;

xp=ip∙Δl; yp= jp∙Δl; zp=kp∙Δl; γp=(lp–0,5∙lmax)∙Δu; ωp=(mp–0,5∙mmax)∙Δu

7 yp≥Ymin(ip,kp,lp,mp) Нет

Да 8 p=p+1

Рис. 3.24. Блок-схема модифицированного алгоритма ВДК для пяти учитываемых обобщенных координат груза (начало)

127

Рис. 3.24. Блок-схема модифицированного алгоритма ВДК для пяти учитываемых обобщенных координат груза (окончание)

128

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

равномерной решетке S*={sp}ipmax=1 .

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) оптимизацию траекторий трех угловых обобщенных координат груза. Необходимо разработать методику планирования траектории на основе алгоритма декомпозиции линейных и угловых координат.

129