Алгоритм построение матрицы смежности графа поверхности с препятствиями для поиска кратчайшей траектории перемещения груза автокраном

Размещено на http://www.allbest.ru/

Сибирская государственная автомобильно-дорожная академия (СибАДИ)

Алгоритм построения матрицы смежности графа поверхности с препятствиями для поиска кратчайшей траектории перемещения груза автокраном

М.С. Корытов

Аннотация

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

Ключевые слова: автокран, матрица смежности графа, поверхность с препятствиями, поиск пути, кратчайшая траектория.

Введение

При перемещении грузов автомобильными кранами, как правило, не ставится задачи точной отработки траектории перемещения груза. Однако существуют ситуации, при которых задание определенной траектории перемещения груза необходимо. Такие ситуации могут иметь место, например, при наличии различных препятствий между начальным и конечным положениями груза. Наличие препятствий предусматривает их обход с какой-либо стороны, а следовательно, возникает задача управления грузом в трех координатах пространства и минимизации пути [1, 2].

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

Необходимо переместить груз из начального положения в конечное, минуя препятствия, расположение и форма которых известны. Дополнительно необходимо минимизировать длину траектории перемещения. Форма и размеры груза предполагаются известными.

Все преобразования в трехмерном пространстве могут быть сведены к композиции двух преобразований: вращения и переноса вдоль координатных осей. Это позволяет разделить и выполнять по отдельности: 1) нахождение траектории определенной точки груза в трехмерном пространстве с препятствиями; 2) оптимизацию траекторий трех угловых координат груза.

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

Существуют традиционные подходы к решению задачи поиска минимального пути. Наиболее эффективны алгоритмы на взвешенных графах. Это относительно сложные алгоритмы. Все более простые алгоритмы не гарантируют, что путь обязательно будет найден, и найденный путь будет именно кратчайшим [3, 4].

Алгоритмы поиска путей на графе работают с 2-мерным массивом чисел, описывающим пространство с препятствиями как граф. Разработаны и используются готовые программные реализации ряда из перечисленных алгоритмов. Чтобы их использовать, необходимо подготовить исходные данные в виде матрицы смежности графа [4].

Р и с. 1 Пространственная равномерная решетка (пример): o - свободные узлы; ? - занятые препятствием узлы

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

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

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

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

Если для какого-либо узла пространственной решетки вертикальная координата z будет меньше высоты эквидистантной поверхности в точке с данными координатами x и y (то есть узел будет находиться внутри препятствия), то расстояние между данным узлом и всеми его рассматриваемыми узлами-соседями принимается на графе равным бесконечности (?) [3, 4].

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

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

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

Р и с. 2 Точки поверхности (пример): o - не учитываемые в графе; ? - учитываемые в графе

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

Размещено на http://www.allbest.ru/

Р и с. 3 Упрощенная блок-схема алгоритма создания матрицы смежности

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

Таким образом, алгоритм создания матрицы смежности по «точкам видимости» будет следующим (рис. 3): 1) преобразование системы координат, в которой описывается поверхность препятствий, с целью расположения начальной и конечной точек вдоль одной из осей координат (центроаффинное преобразование); 2) формирование последовательного списка точек поверхности, учитываемых в графе (вершин графа) в виде одномерного вектора; 3) последовательный перебор всех вершин графа с первой до предпоследней и проверка каждого текущего узла на условие «видимости» относительно всех вершин с большими, чем у текущего узла, порядковыми номерами в списке вершин.

Выполнение п. 1 алгоритма возможно следующим образом. Пусть имеются точки начала и цели (конца) перемещения с координатами [x₁ z₁ y₁] и [x_n z_n y_n] соответственно в исходной системе координат X'Y'Z' (рис. 4). Переход от исходной к преобразованной системе координат будет осуществляться поворотом вокруг вертикальной оси Z. Угол поворота б будет равен

atn((x_n- x₁)/(y_n- y₁)). (1)

Точка с координатами x, y, z в исходной системе координат XYZ будет иметь в преобразованной системе координат X'Y'Z' следующие значения координат:

'=x•cos(б)-y•sin(б); y'= x•sin(б)+y•cos(б); z'=z. (2)

Р и с. 4 Преобразование системы координат (вид сверху, навстречу оси Z)

Подобным образом необходимо получить значения координат в преобразованной системе X'Y'Z' для всех точек поверхности. Затем в преобразованной системе координат необходимо сформировать ту же поверхность, но уже на новой равномерной дискретной сетке X'Y' с заданным шагом. Для этого предлагается использовать известный способ двухмерной табличной линейной интерполяции.

Выполнение п. 2 алгоритма происходит в следующем порядке. Рабочая область с препятствиями задана в виде двухмерного массива чисел - высот точек поверхности z'_ij.

При помощи циклов, меняющих i и j в последовательности [i, затем j], осуществим перебор каждой точки сетки с высотой z'_ij и проверим выполнение условия z'_ij>min(z₁, z_n). При выполнении данного условия точка заносится в список узлов графа. Первой в списке предварительно ставится начальная точка (№1 на рис. 2), последней - конечная (№74 на рис. 2).

Выполнение п. 3 алгоритма предлагается осуществлять следующим способом. Выполняется последовательный перебор всех вершин графа из списка, и для каждой текущей вершины m=2, 3, …, n осуществляется построение прямой в пространстве между данной вершиной и всеми вершинами с большими номерами (m+1, m+2, …, n). Прямая разбивается на p отрезков в соответствии с шагом дискретности, и на данной прямой рассматриваются p промежуточных точек. Для каждой из промежуточных точек проверяется условие превышения ее вертикальной координаты над поверхностью. Если для всех p точек прямой, соединяющей узел m с узлом (m+q), q=1, …, (n-m), данное условие выполняется, делается вывод о том, что узлы m и (m+q) «видимы» между собой, и информация об этом заносится в матрицу смежности графа.

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

Выводы

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

Библиографический список

1. Правила устройства и безопасной эксплуатации грузоподъемных кранов и кранов-манипуляторов: ПБ 10-382-00 и ПБ 10-257-98. Новосибирск: Сиб. унив. изд-во, 2007. 335 с.

2. Правила техники безопасности при эксплуатации стреловых самоходных кранов: ВСН 274-88. М.: СтройИнфо, 2007. 22 с.

3. Dijkstra E.W. A note on two problems in connexion with graphs / Numerische Mathematik 1, 1959. pp. 269-271.

4. 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).

Размещено на Allbest.ru