Материал: 2426

Последовательное использование выражений (3.8), (3.11), (3.3), (3.4), (3.14) с подстановкой значений γн0', ωн0' для начальной точки, а затем γк0', ωк0' для конечной точки положения груза позволяет получить значения γн0, ωн0 и γк0, ωк0 для соответствия условиям задачи

(3.1).

Блок-схема алгоритма предварительной обработки исходных данных в случае их неполного соответствия условиям задачи приведена на рис. 3.4.

После выполнения предварительной обработки данных (в случае ее необходимости) в неподвижной системе координат O0Х0Y0Z0 будет сформирована дискретная матрица высот препятствий YПР(i,k), где i, k

– индексы координат x, z соответственно: i [1; imax]; k [1; kmax]. Линейные и угловые координаты груза заданы на равномерной

дискретной сетке: i [1; imax]; j [1; jmax]; k [1; kmax]; l [1; lmax]; m [1; mmax]. Индексы i, j, k соответствуют линейным перемещениям точки

начала локальной системы координат груза соответственно вдоль осей X0, Y0, Z0, а индексы l, m – двум углам поворота груза γ, ω вокруг собственных осей соответственно (см. рис. 3.1). Задан u – шаг дискретности угловых координат γ и ω.

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

объемного тела груза, определяющие его форму. Координаты точек

ординаты точки ig в локальной системе координат груза.

Кроме того, в качестве исходных данных задачи выступают: lзап_г

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

В качестве целевой функции используются интегральные критерии оптимальности на основе линейных декартовых и угловых координат груза в точках его траектории. Известны такие интегральные критерии, как объем движения W, квадратичный функционал объема движения Wкв, среднее взвешенное длин линейных и угловых перемещений L [71, 120, 221]. Для груза, положение которого описывается пятью обобщенными координатами, функциональные зависимости определения перечисленных критериев выглядят следующим образом:

70

где cx, cy, cz, сγ, сω – весовые коэффициенты линейных и угловых координат груза x, y, z, γ, ω соответственно; x', y', z', γ', ω' – производные координат по времени; t – время перемещения груза из начальной точки в конечную.

Wкв = ò0t (cx × x¢2 (t)+ cy × y¢2 (t)+ cz × z¢2 (t)+ cγ ×γ ¢2 (t)+ cω ×ω¢2 (t))dt ; (3.16)

где cγω – весовой коэффициент угловых координат.

В качестве примера использовалось среднее взвешенное длин линейных и угловых перемещений (СВД) L. В случае дискретного представления траектории СВД Li1,j1 между двумя точками траектории с индексами i1 и j1 (3.17) может быть представлено в виде [38]

Li1, j1 = (xi1 - xj1)2 +(yi1 - yj1)2 +(zi1 - zj1)2 +cγω ×(γi1 -γ j1)2 +(ωi1 -ωj1)2 . (3.18)

Полное выражение целевой функции отдельной траектории S для дискретного представления имеет вид [38]

где imax – число точек отдельной дискретной траектории.

Необходимо найти траекторию S* с оптимальным (минимальным) значением L* целевой функции L, представляющую собой траекторию перемещения из sнач в sкон:

где {Lq} – множество значений целевой функции множества траекторий {Sq}, представляющих собой дискретные траектории перемеще-

ния из sнач в sкон в виде смежных точек sнач, s2, s3, …, s(imax–1), sкон. Представленная формулировка задачи имеет достаточно универ-

сальный характер и допускает решение задачи при помощи различных методик, использующих разные алгоритмические и вычислительные подходы.

71

3.2. Обоснование критериев эффективности для сравнительной оценки методик и алгоритмов планирования траектории

Для сравнительного анализа методик и алгоритмов планирования траекторий движения груза в среде с препятствиями необходимо обосновать критерии эффективности.

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

полноту, оптимальность, пространственную сложность, временную сложность и др. [34, 69, 74, 175, 205].

Полнота алгоритма гарантирует обнаружение существующего решения задачи. Оптимальность обеспечивает нахождение лучшего решения, чем все прочие возможные решения, по значению целевой функции. Пространственная сложность определяется объемом памяти запоминающего устройства, необходимым для работы алгоритма (а также задания исходных и/или выходных данных). Временная сложность зависит от быстродействия работы алгоритма [36, 39, 74, 132, 175, 225].

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

Все критерии также могут быть разделены по степени обобщения на глобальные (обобщенные) и локальные (частные).

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

эталонных тестов (экспериментальный метод) и асимптотический анализ (аналитический метод) [74, 175].

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

72

ные, обычно не поддаются точному математическому анализу, который в этом случае заменяется асимптотическим анализом для наи-

худшего случая.

Методу асимптотического анализа свойственны некоторые недостатки: рассматривается наихудший случай, который может редко встречаться на практике или вообще не встречаться (быстродействие алгоритма в наихудшем случае может быть низким, в то время как он будет превосходить другие алгоритмы по быстродействию в пределах граничных условий конкретной задачи); снижение точности и недостоверность результатов сравнения при небольших объемах входных данных (причем понятие «небольших» объемов зависит от точных характеристик алгоритмов, конкурирующих с анализируемым); не учитывается различная скорость доступа к элементам многомерных массивов в разных языках программирования и др. [35, 37, 39, 74, 132, 175, 225].

Известны очень эффективные с позиции асимптотического анализа алгоритмы (например, фибоначчиевы кучи), которые не используются на практике ввиду сложности программной реализации, больших значений констант, влияющих на общую сложность алгоритмов по сравнению с конкурирующими и т.д. [55, 57, 74, 175].

Трудно теоретически анализировать и т.н. «маленькие хитрости», т.е. некоторые малозначительные детали алгоритма, существенно влияющие на его эффективность. Окончательную оценку алгоритма и методики на его основе, как правило, можно дать лишь после апробации его в практических вычислениях [65].

В качестве частных количественных критериев метода асимптотического анализа используются: асимптотическая временная слож-

ность, асимптотическая пространственная сложность и т.п. [35, 37, 39, 74, 132, 175, 225].

Иногда применяют асимптотический анализ алгоритмов для среднего случая вместо худшего, однако само определение «среднего» варианта также затруднено для сложных алгоритмов и связано с субъективными оценками экспертов и аналитиков, которые должны принять определенные предположения по распределению наборов входных данных и функционированию алгоритма [57, 74, 175].

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

73

тех же численных значений исходных данных задачи, на одной и той же вычислительной машине и на одном языке программирования

[74].

Недостаток метода эталонных тестов – возможную зависимость результатов сравнения от исходных данных задачи – предлагается компенсировать путем проведения достаточно большого числа расчетов (серии из n независимых вычислительных экспериментов) со стохастическими значениями исходных данных с последующей статистической обработкой полученных результатов [38, 88]. Вычислительные эксперименты при этом требуется выполнять на одном и том же оборудовании (одном ПК), алгоритмы реализовать на одном языке программирования. Метод эталонных тестов имеет большую практическую значимость по сравнению с методом асимптотического анализа.

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

Результат применения любого алгоритма для решения задачи, поставленной в разделе 3.1, может быть представлен в виде найденной траектории S*: последовательности точек sp с координатами груза

(xp, yp, zp, γp, ωp), p [1; imax] и значения целевой функции указанной траектории L*, определенного по (3.19).

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

Для количественной оценки оптимальности найденного каждым алгоритмом решения предложено использовать критерий относи-

тельной погрешности к условному глобальному оптимуму:

74