Материал: 2426

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

массива чисел – высот точек поверхности YЭ(i,k), где i [1; imax]; k [1; kmax]; imax – число точек рассматриваемой области вдоль оси X0; kmax –

число точек вдоль оси Z0. При помощи циклов, меняющих i и k в заданной последовательности (i, затем k), осуществляется перебор каждой точки сетки с высотой YЭ(i,k) и проверка выполнения условия

YЭ(i,k)>min[yн0, yк0]. (3.117)

При выполнении данного условия текущий узел графа Gr заносится в список узлов подграфа PGr. Первой в списке предварительно ставится начальная точка (1 на рис. 3.28), последней – конечная (89 на рис. 3.28). Последняя точка имеет номер i2кон [83].

Выполнение п. 3.1 алгоритма предлагается осуществлять следующим способом. Выполняется последовательный перебор всех

вершин подграфа из списка i2 [2; i2кон], и для каждой текущей вершины осуществляется построение прямой в пространстве между те-

кущей вершиной и всеми вершинами с большими номерами: j2 [i2+1; i2кон]. Прямая разбивается на k2кон отрезков в соответствии с заданным шагом дискретности l, и на данной прямой на равном расстоянии друг от друга расстанавливаются k2кон промежуточных точек, каждая со своими координатами в пространстве. Каждая из промежуточных точек прямой имеет координаты

где k2 [ 1; k2кон]; k2кон=(Lлин)i2,j2/ l.

Для каждой точки проверяется условие превышения ее вертикальной координаты над соответствующей вертикальной координатой

где i3= xk2/ l ; k3= zk2/ l .

Если для всех k2кон точек отдельной прямой, соединяющей узел i2 с узлом j2, данное условие выполняется, делается вывод о том, что узлы i2 и j2 «видимы» между собой, информация об этом сохраняется в бинарной (булевой) переменной (Vid=1), и длина прямой (Lлин)i2,j2

135

между двумя точками в трехмерном пространстве вычисляется по выражению

Рис. 3.29. Блок-схема алгоритма формирования матрицы весов PDG подграфа PGr

136

В противном случае длина принимается равной бесконечно большому значению (Vid=0):

(Lлин)i2,j2=∞. (3.121)

Информация о «видимости» заносится в виде длины прямой (Lлин)i2,j2 в матрицу смежности подграфа. Матрица весов PDG подграфа PGr, список вершин которого состоит из i2кон элементов, будет иметь размеры (i2кон×i2кон). Элементы матрицы заполняются соответствующими значениями:

PDG=[(Lлин)i2,j2]ii22кон,j2=1. (3.122)

Блок-схема алгоритма создания матрицы весов подграфа по описанной методике приведена на рис. 3.29.

Из найденных любым алгоритмом поиска кратчайшего пути на графе траекторий {(SL*)in}innдек=1 каждая представляет собой последова-

тельность из нескольких вершин sl подграфа PGr: SL*={slp}snp=1.

4. Осуществляется линейная интерполяция каждой найденной траектории из множества {(SL*)in}innдек=1 на равномерной сетке обоб-

щенной координаты xi (i [1; imax]) по известному алгоритму [65, 191] для вычисления обобщенных координат yi, zi. В результате интерполяции формируются траектории точки в трехмерном пространстве, представляющие собой последовательности из смежных вершин, за-

данных на равномерной решетке SL*={slp}ipmax=1 .

Линейные траектории состоят каждая из последовательно располагающихся вдоль оси X0 точек вида

где xp [0∙Δl; imax∙Δl].

Т.е. каждая из найденных траекторий представлена в виде набора точек с равномерно возрастающими значениями вдоль одной из осей координат X0 через равные интервалы.

5. Для каждой из найденных траекторий {(SL*)in}innдек=1 создается

3-мерное пространство с препятствиями {Puin}innдек=1 соответственно,

состоящее из одной линейной x и из двух угловых координат объекта: γ и ω. Для создания пространства Puin груз перемещается из начального положения в конечное по траектории (SL*)in с шагом квантования

137

l точки начала системы координат груза вдоль оси X0. В каждом из промежуточных положений груза на траектории (SL*)in (рис. 3.30, а) рассматриваются с шагом квантования u все возможные сочетания его варьируемых угловых координат γ и ω в заданных (3.40) граничных пределах.

X0 ω γ в)

Рис. 3.30. К определению разрешенных и запрещенных состояний груза для заданной траектории точки его начала системы координат (примеры): а – траектория (SL*)in точки начала системы координат и одно из промежуточных положений груза на ней; б – области разрешенных и запрещенных состояний груза в отдельной точке; в – пространство Puin из одной линейной

и двух угловых координат

C использованием гиперповерхности минимальных значений вертикальных координат условного центра груза [Ymin]in, сформированной по методике, описанной в разделе 3.4, формируется простран-

ство с препятствиями {Puin}innдек=1 . При рассмотрении двух угловых ко-

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

138

движения (SL*)in формируется пространство Puin, в котором задана область препятствий, т.е. запрещенных состояний груза (рис. 3.30, в).

Пространство Pu представлено в виде трехмерного массива битовых элементов:

где i [1; imax]; k= zi/ l ; l [1; lmax]; m [1; mmax]; yi, zi – соответствую-

щие координаты точки i траектории SL*.

6. Учитывая, что начальное и конечное положения груза заданы при постановке задачи, включая угловую ориентацию (γн0, γк0, ωн0, ωк0), это определит положение начальной и конечной точек груза в пространстве Puin и позволит найти кратчайшую траекторию с учетом угловых координат. В результате для каждой траектории точки условного центра груза (SL*)in находится соответствующая «угловая траектория» У*in, минимизированная по угловым перемещениям груза с учетом заданных ограничений на значения угловых координат.

Множество «угловых траекторий» {(У*)in}innдек=1 формируется аналогич-

но траекториям {(SL*)in}innдек=1 с формированием матрицы весов PDGin

пространства Puin на дискретной равномерной сетке координат с шагами дискретизации l (для x), u (для γ и ω) и поиском кратчайшего пути на графе (п. 3 настоящего алгоритма). Для пространств Puin используется собственное выражение целевой функции, учитывающее только угловые координаты:

7. При совмещении линейной (SL*)in и угловой (У*)in траекторий формируется общая траектория груза SLУin вида (3.50), которая может быть оценена по значению целевой функции L*in, вычисленной по

(3.19):

«Угловой траектории» (У*)in может не существовать при определенной конфигурации поверхности препятствий в пространстве Puin (непреодолимые при заданных ограничениях препятствия). В этом случае будет отсутствовать и общая траектория SLУin. Вероятность

139