Материал: 2426

Общее 5-мерное пространство конфигураций груза разбивается на два частично перекрывающихся 3-мерных пространства. Предлагаемая методика на основе алгоритма декомпозиции линейных и угловых координат заключается в выполнении следующей последова-

тельности шагов [64, 82, 89, 101, 121]:

1. Задание численных значений исходных данных: sнач=(xн0, yн0,

zн0, γн0, ωн0); sкон=(xк0, yк0, zк0, γк0, ωк0); { Rig }; imax; jmax; kmax; lmax; mmax;

[YПР]; nдек, cγω, u, δopt; lзап_г; lзап_в.

2. С использованием методики построения полидистантных поверхностей вокруг препятствий в трехмерном пространстве, изложенной в разделе 3.3, строим nдек полидистантных поверхностей вокруг реальной поверхности препятствий с различными значениями горизонтальной Rг и вертикальной Rв полуосей эллипса удалений. Значе-

где in [1; nдек]; lзап_г – минимальный допустимый запас расстояния между произвольной точкой на поверхности груза и поверхностью препятствий в горизонтальном направлении; ∆Rг – шаг приращения величины Rг; gmin=min{| Rig |}– расстояние от начала системы коорди-

нат груза до ближайшей точки на поверхности груза. Значения Rв варьировались в пределах

где lзап_в – минимальный допустимый запас расстояния между произвольной точкой на поверхности груза и поверхностью препятствий в вертикальном направлении; ∆Rв – шаг приращения величины Rв.

Отличие при построении полидистантных поверхностей в том, что Rг и Rв определяются не по (3.33), а по (3.114) и (3.115).

Полидистантные поверхности обозначаются как {[YЭ]in}innдек=1 . Шаги приращений ∆Rг и ∆Rв подбираются таким образом, чтобы поверхность [YЭ]nдек соответствовала удалению от реальной поверхности

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

сзапасом lзап_г.

3.С использованием известных алгоритмов поиска кратчайшего

пути на графе [216, 246], находим траектории {(SL*)in}innдек=1 перемеще-

130

ния точки начала системы координат груза из начального положения slнач=(xн0, yн0, zн0) в конечное slкон=(xк0, yк0, zк0) в трехмерном пространстве с поверхностями препятствий {[YЭ]in}innдек=1 соответственно (рис.

3.25), оптимальные по выражению целевой функции для линейных координат (длины прямой):

Рис. 3.25. Примеры найденных оптимальных траекторий точки при различных значениях Rг и Rв

При этом матрица смежности графа формируется по точкам видимости по методике, изложенной ниже [64, 122].

Имеется граф Gr с конечным количеством вершин: Gr=(Sr, Er),

множество ребер. Общее количество вершин графа Gr определяется количеством рассматриваемых точек равномерной сетки линейных

координат: ng=imax∙jmax∙kmax.

Алгоритмы поиска путей на графе работают с 2-мерным массивом чисел, описывающим пространство с препятствиями как граф. Пространство может быть двухмерным (карта), трехмерным (пространство) или многомерным. Недостатком графовых алгоритмов является резкое снижение производительности при увеличении размерности пространства. Чтобы использовать алгоритмы поиска кратчайшего пути на графе, необходимо подготовить исходные данные, опи-

сывающие граф, в виде матрицы весов графа DG=[(Lлин)i1,j1]ng =

i1, j1 1

131

ординат (3.116) между двумя точками в пространстве – вершинами графа.

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

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

Рис. 3.27. Направления перемещения от узла к соседям:

а– в пределах одного ряда; б – в пределах двух рядов;

в– в пределах трех рядов

Для каждого узла возможно рассмотрение соседних узлов в пределах одного ряда, в пределах двух или нескольких рядов (рис. 3.27).

132

Если для какого-либо узла пространственной решетки вертикальная координата y будет меньше высоты полидистантной поверхности в точке с текущими координатами x и z (т.е. узел будет находиться внутри препятствия), то расстояние между данным узлом и всеми его рассматриваемыми узлами-соседями принимается на графе равным бесконечности: Lлин=∞ [64, 216, 246].

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

Улучшить эффективность поиска кратчайшего пути в среде с препятствиями можно за счет изменения алгоритма подготовки матрицы весов графа. Предлагается, во-первых, уменьшить количество вершин графа, сформировав из него подграф, принимая в рассмотрение только точки, расположенные на поверхности препятствий выше определенного уровня, например уровня нижней из двух точек начала/окончания пути (рис. 3.28). Свободные узлы (вне препятствий), равно как и узлы, находящиеся внутри препятствий, при этом способе исключаются из рассмотрения, что значительно уменьшает размеры матрицы смежности и ускоряет поиск пути. Исключение составляют две точки: начальная и конечная, которые учитываются, хотя находятся вне препятствий. Начальная точка будет первой в списке вершин подграфа, конечная – последней. Рассматриваемые точки будут располагаться на равномерной сетке относительно координат x и z.

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

133

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

Рис. 3.28. Точки поверхности (пример):

o – не учитываемые в подграфе; ● – учитываемые в подграфе

Последовательность предлагаемой методики создания матрицы весов по «точкам видимости» [83]:

3.1.Формирование последовательного списка точек поверхности, учитываемых в подграфе PGr (вершин полного графа Gr, расположенных на поверхности препятствий выше определенного уровня) в виде одномерного вектора.

3.2.Последовательный перебор всех вершин графа с первой до предпоследней и проверка каждого текущего узла на условие «видимости» относительно всех вершин с большими, чем у текущего узла, порядковыми номерами в списке вершин.

134