Материал: 2426

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

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

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

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

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

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

Исходные поверхности препятствий формировались случайным образом из сочетания нескольких параллелепипедов, каждый из которых имел случайные размеры. Для всех экспериментов рассматривалось рабочее пространство в виде куба с размерами 10×10×10 УЛЕ (см. рис. 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].

156

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

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

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

Рис. 3.37. Блок-схема алгоритма редукции полидистантной поверхности вокруг препятствий

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

157

уменьшении шага дискретизации координат. Переход от исходного к укрупненному описанию линейных координат выполнялся методом редукции [164]. Использовался коэффициент масштабирования kм линейных координат, значение которого принималось равным kм=5. Алгоритм перехода от полидистантной поверхности YЭ01, описанной с мелким шагом, к поверхности YЭ05 с крупным шагом приведен на рис. 3.37.

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

Y0 Z0

X0

Рис. 3.38. Рабочая область тестового примера с детерминированным расположением препятствий

Груз в форме цилиндра с габаритными размерами (габаритный диаметр 0,5 УЛЕ и высота 2,0 УЛЕ), был представлен в виде набора точек (cг=12) на поверхности объемного тела с координатами в УЛЕ:

158

{ 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]:

где L*н – значение целевой функции неоптимизированной траектории для данного эксперимента; ne – число независимых экспериментов.

где L* – значение целевой функции оптимизированной траектории для данного эксперимента; ne – число независимых экспериментов.

где вектор значений отдельных экспериментов {(L*н)i}ine=1 предварительно отсортирован по возрастанию; количество ne – четное.

159