close

Вход

Забыли?

вход по аккаунту

?

Использование алгоритмов поиска пути перемещения груза автокраном на графах.

код для вставкиСкачать
УДК 621.87
ИСПОЛЬЗОВАНИЕ АЛГОРИТМОВ ПОИСКА ПУТИ ПЕРЕМЕЩЕНИЯ ГРУЗА
АВТОКРАНОМ НА ГРАФАХ
В.С. Щербаков, М.С. Корытов
В статье рассматриваются способы описания среды с препятствиями и результаты решения задачи поиска
кратчайшего пути перемещения груза автокраном при помощи алгоритмов на графах. Проводится сравнение рассматриваемых способов по трудоемкости
Ключевые слова: автокран, поверхность, препятствия, путь, траектория
При перемещении грузов автомобильными
кранами, как правило, не ставится задачи точной отработки траектории перемещения груза. Достаточно
обеспечить достижение финишной точки, кроме того, необходимо обеспечить ряд условий при движении груза, например, ограничения ускорения, сохранения ориентации груза в некоторых (обычно
довольно широких) пределах (иногда достаточно,
чтобы груз не опрокинулся). При перемещении емкостей с жидкостями или хрупких грузов требования могут быть более жесткими [1, 2, 3].
Однако существуют ситуации, при которых задание определенной траектории перемещения груза
необходимо. Такие ситуации могут иметь место, например, при наличии различных препятствий между
начальным и конечным положениями груза. В этом
случае возможно: 1) поднятие груза выше препятствий и его перемещение над ними; 2) можно обходить препятствия сбоку без поднятия груза над ними, особенно если высота препятствий достаточно
велика или они вообще непреодолимы по высоте
для данной конструкции автокрана. Таким образом,
наличие препятствий предусматривает их обход с
какой-либо стороны, а следовательно, возникает задача минимизации пути.
Использование методик поиска кратчайшего
пути в системе автоматического управления автокраном позволит перемещать груз по оптимальной
траектории, обеспечивая минимизацию расстояния
(а следовательно, повышение производительности),
и одновременно плавность перемещения (ограничение первых двух производных: скорости и ускорения).
Необходимо переместить груз из начального
положения в конечное, минуя препятствия, расположение и форма которых известны. Дополнительно
необходимо минимизировать длину траектории перемещения. Форма и размеры груза предполагаются
известными.
Все преобразования в трехмерном пространстве могут быть сведены к композиции двух преобразований: вращения и переноса вдоль координатных
осей. Это позволяет разделить и выполнять по отдельности: 1) нахождение траектории определенной
точки груза в трехмерном пространстве с препятствиями; 2) оптимизацию траекторий трех угловых
обобщенных координат груза.
Выполнение п. 1 предполагает расчет и оптимизацию пути перемещения характерной точки начала координат системы груза в среде с поверхностями-препятствиями, представляющими собой
пространственные эквидистантные (равноудаленные) поверхности от реальных поверхностейпрепятствий.
Существует несколько традиционных подходов к решению задачи поиска кратчайшего пути.
Наиболее известны алгоритмы, работающие на взвешенных графах. Имеется граф с конечным количеством вершин (рис. 1). Граф представляет собой
множество вершин, некоторые из которых соединены ребрами. Если каждое ребро обладает числом
(весом), такой граф называют взвешенным. Вес ребер графа в нашем случае соответствует расстоянию
между точками рассматриваемой области.
Вершина 1
0.75
Вершина 4
0.75
0.68
0.51
0.86
Вершина 3
0.9
0.22
0.61
Вершина 5
0.12
0.99
Вершина 2
0.22
Щербаков Виталий Сергеевич – СибАДИ, д-р техн. наук,
профессор, тел. (3812) 65-04-55
Корытов Михаил Сергеевич – СибАДИ, канд. техн. наук,
доцент, тел. (3812) 65-03-18
Вершина 6
Рис. 1. Пример графического изображения
взвешенного графа
Классическим алгоритмом поиска пути на графе считается алгоритм Дейкстры [4, 5]. Задаются
начальная и конечная вершины, необходимо найти
между ними кратчайший путь. Е. Дейкстра разработал алгоритм для прохода по графам, грани которых
имеют различный вес. На каждом шаге алгоритм
ищет необработанные узлы близкие к стартовому,
затем просматривает соседей найденного узла, и устанавливает или обновляет их соответствующие
расстояния от старта по минимальному значению.
При этом используется приоритетная очередь. При
достижении конечной вершины выстраивается путь
к начальной вершине в обратном направлении, по
критерию минимальности пути.
Частным случаем алгоритма Дейкстры является т.н. «волновой» алгоритм. Также на графах используют другие распространенные алгоритмы поиска кратчайшего пути: поиск в ширину (в англоязычной литературе его называют BFS – «breadth-first
search»), алгоритм Беллмана-Форда (Bellman-Ford) и
др [6].
Алгоритмы поиска путей на графе работают с
2-мерным массивом чисел, описывающим пространство с препятствиями как граф. Пространство может
быть двухмерным (карта), трехмерным (пространство) или многомерным. К сожалению, недостатком
графовых алгоритмов является резкое снижение
производительности при увеличении размерности
пространства.
Существуют еще более сложные алгоритмы, в
частности т.н. «генетический алгоритм» и «муравьиный алгоритм», которые, в том числе, могут использоваться для поиска кратчайшего пути [7, 8, 9].
Однако, эти алгоритмы наиболее эффективно работают в распределенных нестационарных сетях с меняющимися параметрами и требуют гораздо больших временных затрат по сравнению с традиционными алгоритмами поиска пути на графах [9].
j= jmin,(jmin+1),…jmax
наличие связи от вершины-строки к вершинестолбцу (либо наоборот). В нашем случае это число
будет расстоянием между двумя точками в пространстве – вершинами графа.
Чтобы подготовить матрицу смежности, представим трехмерное пространство с препятствиями в
виде трехмерного массива точек – узлов равномерной пространственной решетки и одновременно –
вершин графа (рис. 2).
Пусть количество вершин в рассматриваемом
графе n, описывающем рассматриваемую часть рабочей области, равно
n=(imax–imin)·(jmax–j min)·(kmax–kmin),
(1)
где imax, imin, jmax, j min, kmax, kmin – номера начальных и
конечных индексов трехмерного массива точек
вдоль осей x0 (i), y0 (j) и z0 (k) инерциальной системы
координат соответственно, определяющие область,
достаточную для рассмотрения и поиска кратчайшего пути.
k+1
k
k–1
i+1
i
j–1
j
j+1
а)
j–2
j–1
j
j+1
j+2
б)
k+3
k+2
k+1
k
k–1
k–2
y0
i+3
z0
i+2
k=kmin,
(kmin+1)…
kmax
i+1
j–3
i=imin,(imin+1),… imax
x0
j–2
j–1
j
j+1
j+2
i
j+3
в)
Рис. 2. Пространственная равномерная решетка (пример):
o – свободные узлы; ● – занятые препятствием узлы
Рис. 3. Направления перемещения от узла к соседям: а – в
пределах одного ряда; б – в пределах двух рядов; в – в
пределах трех рядов
Разработаны и используются уже готовые программные реализации ряда из перечисленных алгоритмов для графов, в том числе в таких мощных математических пакетах, как MATLAB. Чтобы их использовать, необходимо подготовить исходные данные в виде матрицы смежности графа [10]. Матрица
смежности – таблица, где как столбцы, так и строки
соответствуют вершинам графа. В каждой ячейке
этой матрицы записывается число, определяющее
Используем для перехода от номеров индексов
текущей рассматриваемой точки пространства к номеру p вершины в списке вершин графа зависимость:
p=(jmax–jmin+1)·(kmax–kmin+1)·(i–imin)+
(2)
+(j–jmin)·(kmax–kmin+1)+(k–kmin+1),
где i, j, k – номера индексов текущей вершины вдоль
осей x0 (i), y0 (j) и z0 соответственно.
Чтобы установить влияние количества возможных направлений перемещения от заданного узла к соседним узлам решетки на точность поиска
пути, рассмотрим варианты соединения каждого узла с узлами соседних рядов: - в пределах одного ряда; - в пределах двух рядов; - в пределах трех рядов
(рис. 3). Обозначим количество рассматриваемых
рядов-соседей m.
1
2
4
3
а)
1
2
4
l=
(x
1
− x2 ) + ( y1 − y2 ) + (z1 − z2 ) ,
б)
1
3
2
в)
Рис. 4. Траектории найденных путей, полученных по алгоритмам поиска на графах (пространственный вид) для
вариантов соединения узлов графа: а – на один ряд; б – на
два ряда; в – на три ряда; 1 – метод Дейкстры без оптимизации; 2 – метод Дейкстры с оптимизацией; 3 – метод
Беллмана-Форда без оптимизации; 4 – метод БеллманаФорда с оптимизацией
Количество направлений возможных перемещений будет составлять
(3)
nr=m·(2·m+1)2.
2
2
2
(4)
причем x=i·∆l, y=j·∆l, z=k·∆l, где ∆l – расстояние между двумя ближайшими соседними узлами дискретной пространственной решетки вдоль любой из
осей инерциальной системы координат (которые
считаем равными между собой).
Если для какого-либо узла пространственной
решетки вертикальная координата zk=k·∆l будет
меньше высоты эквидистантной поверхности zEij в
точке с данными индексами i и j и координатами x и
y (то есть узел будет находиться внутри препятствия), то расстояние между данным узлом и всеми
его рассматриваемыми узлами-соседями примем на
графе равным бесконечности (∞) [5, 10].
На рис. 4 в качестве примера представлены результаты поиска кратчайшего пути на графе для эквидистантной поверхности с помощью двух наиболее эффективных алгоритмов поиска: Дейкстры и
Беллмана-Форда. Начальная точка имеет координаты [x y z] = [0 10 3], конечная – координаты [x y z] =
[17 10 3]. Шаг решетки принимался равным ∆l=0,1
м. Для каждого метода (Дийкстры, Беллмана-Форда)
рассмотрены три варианта соединения узлов графа:
на один ряд, на два ряда, на три ряда. Длина пути lp
для указанных вариантов представлена в табл. 1.
Таблица 1
Значения длины пути lp для различных методов и
количества рядов, м
Метод
Количество
рядов
1
2
3
3
4
Для (m=1, 2, 3) nr будет равно соответственно
9, 50 и 147. Расстояние l между двумя вершинами
графа (1 и 2) будет рассчитываться по формуле
Дейкстры
БеллманаФорда
23.394
23.503
23.566
21.701
21.347
22.022
Сравнительный анализ данных табл. 1 показывает, что наилучшие результаты дает метод Беллмана-Форда при количестве рядов, равном 2. То есть,
можно сделать вывод о том, что увеличение количества рассматриваемых рядов-соседей не всегда повышает точность поиска, кроме того, при этом наблюдается резкое (в геометрической прогрессии)
увеличение временных затрат на подготовку матрицы смежности графа, что затрудняет практическое
использование алгоритма при количестве рядовсоседей m≥3.
Оптимизация найденных траекторий устранением
промежуточных точек в пределах видимости
Анализ траекторий, приведенных в качестве
примера на рис. 4, показывает, что в свободном пространстве, не занятом препятствиями, найденная
траектория не всегда проходит по кратчайшему расстоянию. Предлагается уменьшить длину найденных траекторий путем обработки полученных результатов по алгоритму, устраняющему промежу-
точные точки в пределах видимости между препятствиями.
Суть алгоритма заключается в следующем.
Пусть найденная траектория представлена в виде
двухмерного массива координат точек
⎡ x1 ,x2 ,...xi ,...,x n ⎤
⎢ y ,y ,...y ,...,y ⎥ .
(5)
i
n⎥
⎢ 1 2
⎢⎣ z1 ,z 2 ,...z i ,...,z n ⎥⎦
Возьмем первую и вторую точки в списке [x1 y1
z1]T, [x2 y2 z2]T, проведем между ними прямую линию, разобьем полученный отрезок на m отрезков,
разделив длину исходного отрезка l на шаг дискретности пространственной решетки ∆l:
m=окр.(l/∆l).
(6)
Получим
m
точек
с
координатами
[x1_2(j) y1_2(j) z1_2(j)]T,
j=1,2,…m.
Координаты
[x1_2(j) y1_2(j) z1_2(j)]T будут промежуточными между
двумя точками исходного массива. Для точек исходного массива с индексами o и p промежуточные
точки рассчитываются по линейным зависимостям:
xo_p(j)=xo+(xp–xo)·(j/m);
yo_p(j)=yo+(yp–yo)·(j/m);
(7)
zo_p(j)=zo+(zp–zo)·(j/m).
Для каждой полученной точки проверим выполнение условия превышения ее вертикальной координаты z1_2(j) над вертикальной координатой эквидистантной поверхности zE1_2(j) в точке с соответствующими значениями x1_2(j), y1_2(j):
(8)
z1_2(j)>zE1_2(j).
Если условие (8) выполняется для всех j, то
возьмем первую и третью точки в списке [x1 y1 z1]T,
[x3 y3 z3]T и для них проделаем аналогичную процедуру, и т. д. до тех пор, пока не будет достигнута
конечная точка исходного массива координат.
[x4 y4 z4]T[xk yk zk]T
[x6 y6 z6]T
[x1 y1 z1]T
[x3 y3 z3]T
[x2 y2 z2]T
[x9 y9 z9]T
[x7 y7 z7]T
[x8 y8 z8]T
Рис. 5. Пример, иллюстрирующий оптимизацию дискретной траектории устранением промежуточных точек в пределах видимости: (- - -) – исходная траектория; (─) – оптимизированная траектория
Если для какой-либо точки из исходного массива координат траектории условие (8) для любой из
промежуточных точек соединяющего отрезка выполняться не будет (то есть не будет видимости изза препятствия), данные об этом сохраняются в одномерном массиве a из n элементов. Элементы массива a – это нули при выполнении условия, и единицы при невыполнении. Тогда, если максимальный
номер точки из исходного массива, для которой вы-
полняется условие (для всех промежуточных точек
соединяющего отрезка), обозначить k, то необходимо взять точку k–1 из исходного массива, и уже для
нее рассматривать отрезки [xk yk zk]T [xk+1 yk+1 zk+1]T,
[xk yk zk]T [xk+2 yk+2 zk+2]T, … и т. д. по описанному алгоритму, пока не достигнем конечной точки исходного массива (рис. 5).
В результате выполнения алгоритма оптимизации найденных траекторий при пост-обработке, из
исходного массива точек получается массив, как
правило, меньшего размера, точек оптимизированной траектории t(1:3,s).
Длина пути для всех оптимизированных траекторий, полученных методами Дийкстры и БеллманаФорда, для рассматриваемого примера, при любом
количестве учитываемых рядов-соседей (см. табл. 1)
уменьшается. Об этом свидетельствуют данные
табл. 2. Однако здесь также увеличение количества
рассматриваемых рядов-соседей не всегда повышает
точность поиска. Вообще, влияние количества рассматриваемых рядов-соседей на точность оптимизации незначительно. После оптимизации лучшие результаты показывает метод Дийкстры, однако превышение его точности над методом Беллмана-Форда
также незначительно.
Таблица 2
Значения длины пути lp после оптимизации
траекторий, м
Метод
Количество
рядов
1
2
3
Дейкстры
БеллманаФорда
18.989
18.855
18.835
19.257
19.069
19.179
Поскольку для нахождения кратчайшего пути
в пространстве используются численные методы задания матрицы смежности и поиска на графах, то
при достаточно малом шаге пространственной решетки использование представленных алгоритмов
может оказаться трудоемкой и длительной процедурой.
Проведем оценку трудоемкости предлагаемых
алгоритмов по времени вычисления в зависимости
от метода, количества рассматриваемых рядовсоседей и шага дискретности пространственной решетки.
В качестве среды моделирования, в которой
происходила реализация алгоритмов, использовался
пакет прикладных программ для решения задач технических вычислений MATLAB. На встроенном
языке программирования MATLAB по приведенным
выше алгоритмам были написаны программыскрипты. Это позволило использовать возможности
профилировщика MATLAB для точного измерения
затрат времени на выполнение программ в целом и
их отдельных строк.
В табл. 3 представлены временные затраты на
создание матриц смежности графа для количества
рассматриваемых рядов-соседей 1, 2 и 3. Шаг дискретности пространственной решетки ∆l в данной
серии экспериментов принимался фиксированным:
∆l=0,1 м. Матрица смежности в качестве примера
создавалась для области с размерами 1×2×2 м и
имела размер 4000×4000= 16000000 элементов (поскольку 1/0,1×2/0,1×2/0,1=4000). Использовался вид
разреженных матриц MATLAB, позволяющий значительно снизить емкость матрицы в памяти. Создание матриц смежности велось по алгоритму, описанному выше.
Таблица 3
Затраты вычислительного времени алгоритма
создания матрицы смежности графа, с
Шаг дискретности
решетки, м
0,05
Количество
рядов
1
11.348
2
184.854
3
2520.218
0,1
0,15
0,2
0.723
5.836
59.137
0.222
1.038
4.805
0.072
0.244
0.752
В табл. 4 представлены временные затраты на
поиск пути на графе, описывающем пространство
для рассматриваемой в качестве примера области
размерами 17×3×3 м с дискретностью решетки 0,1
м. Результаты поиска представлены на рис. 4.
Таблица 4
Затраты вычислительного времени алгоритма
поиска пути, с
Метод
Количество
рядов
1
2
3
Дейкстры
БеллманаФорда
0.546
2.871
8.564
0.546
3.120
9.311
Вычисления производились на персональном
компьютере, имеющем следующие характеристики:
- Процессор: AMD Athlon 64 X2 Dual Core Processor
5600+ 2.90 GHz; - Память (RAM): 4,00 ГБ; - Тип
системы: 32-разрядная операционная система.
Анализ полученных результатов позволяет
сделать вывод о том, что при создании матрицы
смежности графа целесообразно уменьшить количество рассматриваемых рядов-соседей до одного, поскольку это незначительно увеличивает длину оптимизированной траектории, но в то же время сильно уменьшает временные вычислительные затраты
на подготовку матрицы смежности.
Литература
1. Правила устройства и безопасной эксплуатации
грузоподъемных кранов и кранов-манипуляторов: ПБ 10382-00 и ПБ 10-257-98. – Новосибирск: Сиб. унив. изд-во,
2007. – 335 с.
2. Котельников, В.С. Комментарий к правилам устройства и безопасной эксплуатации грузоподъемных кранов (ПБ 10-382-00) / В.С. Котельников, Н.А. Шишков. –
М.: МЦФЭР, 2007. – 720 с.
3. Правила техники безопасности при эксплуатации
стреловых самоходных кранов: ВСН 274-88. – М.: СтройИнфо, 2007. – 22 с.
4. Dijkstra, E.W. A note on two problems in connexion
with graphs / Numerische Mathematik 1, 1959. – pp. 269-271.
5. Богомолов, А.М. Алгебраические основы теории
дискретных систем / А.М. Богомолов, В.Н. Салий. – М.:
Наука. Физматлит, 1997. – 368 c.
6. Bellman, R. On a Routing Problem / Quarterly of
Applied Mathematics 16(1), 1958. – pp. 87-90.
7. Панченко, Т.В. Генетические алгоритмы: учебнометодическое пособие / Под ред. Ю. Ю. Тарасевича. – Астрахань: Издательский дом «Астраханский университет»,
2007. – 87 с.
8. Dorigo, M. The ant system: optimization by a colony of cooperating agents / M. Dorigo, V. Maniezzo, A. Colorni // IEEE Transactions on Systems, Man, and Cybernetics,
Part B, № 26, 1996. – pp. 29-41.
9. Штовба, С.Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях, 2003. – №4. – С. 7075.
10. Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). The
Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).
Сибирская государственная автомобильно-дорожная академия
USE OF A WAY SEARCH ALGORITHMS THE MOVING OF CARGO
BY A TRUCK CRANE ON GRAPHS
V.S. Shcerbakov, M.S. Korytov
In article ways the description of environment with obstacles and results of the decision a problem of search the
shortest way of moving cargo a truck crane by means of algorithms on columns are considered. Comparison of considered
ways on labour input is spent
Key words: truck, surface, obstacles, path, trajectory
Документ
Категория
Без категории
Просмотров
5
Размер файла
505 Кб
Теги
автокраны, алгоритм, перемещении, использование, пути, груз, поиск, графах
1/--страниц
Пожаловаться на содержимое документа