Диссертация (1145289), страница 51
Текст из файла (страница 51)
Пусть для i -го шага задания прогноза, соответствующего интервалу времени [ T0 + (i − 1) ∆T , T0 + i ∆T ], определены опасные зоны Ω aj , j ∈1, M i . Аналогично статическим ограничениям, каждое множество Ω aj описывается замкнутымконтуром Γ aj вида (8.2.1). Тогда каждой плоской области Ω aj соответствует втрехмерном пространстве в системе координат Oψλ t множество точек, ограниченное цилиндрической поверхностью с образующей, параллельной оси Ot . Но, вотличие от статических запретных зон, для динамических ограничений указанноемножество точек ограничено также сверху и снизу плоскостями t = T0 + (i − 1) ∆Tи t = T0 + i∆T . На рис.
8.2.1 приведен пример отображения статических и динами-324ческих запретных зон в трехмерном пространстве.Time (hours)403020102001500100010080060050400200lambda (km)00psi (km)Рис. 8.2.1. Представление статических и динамических запретных зонв трехмерном пространстве.Для получения начального приближения к оптимальному решению задач(8.1.15), (8.1.16) будем полагать, что фактическая и заданная скорости совпадают.Построим в рассматриваемом трехмерном пространстве сеть в следующих пределах изменения координат:ψ ∈ [ψ 0 , ψ1 ], λ ∈ [λ 0 , λ1 ], t ∈ [t0 ,T1 ] ,где t0 = T0 – время отправления из начальной точки A(ψ 0 , λ 0 ) .
Выберем некоторый шаг сетки по каждой из координат: ∆ψ s , ∆λ s и ∆t s , причем шаг ∆t s удобноопределить кратным периоду ∆T смены прогноза погодных условий, то есть∆T = l∆t s , где l ≥ 1 – целое число. В итоге получим трехмерную сеть (решетку), ψ − ψ0 λ − λ0 + 2 , Nλ = 1число узлов которой равно N ψ N λ N t , где N ψ = 1 + 2, ∆ψ s ∆λ s Nt =T1 − t 0+ 1.∆t sПостроим прямую p в пространстве с уравнением: ψ = ψ1 , λ = λ1 . Отметим,что конечная точка маршрута не закреплена, но она должна принадлежать пря-325мой p . При этом в задаче поиска маршрута с наименьшим временем переходаконечная точка должна иметь наименьшее возможное значение аппликаты.В дальнейшем будем представлять маршрут движения объекта ломаной втрехмерном пространстве, причем узлами этой ломаной примем узлы построенной выше сети.В итоге задача поиска оптимального по времени маршрута сводится к построению такой ломаной линии, которая начинается в точке O и заканчивается вточке, лежащей на прямой p , которой соответствует минимальное значение времени t .
При этом указанная линия не может пересекать множества, представляющие статические и динамические запретные зоны. Кроме того, эта линиядолжна удовлетворять ограничениям на максимальную и минимальную допустимую скорость движения объекта и следовать строго по возрастанию значенийвдоль оси аппликат (времени).Для решения поставленной задачи сформируем граф, узлы которого совпадают с узлами построенной трехмерной сети. Вычеркнем все точки, которые попадают внутрь или на границу множеств, определяющих статические и динамические запретные области.
Кроме того, вычеркнем все точки, в которые нельзяпопасть из-за ограничения скорости (8.1.6).Для того чтобы построить ребра, соединяющие вершины графа, рассмотрим[]один из его узлов – точку с координатами (ψ i , λ j , t k ) , где i ∈ 1, N ψ , j ∈ [1, N λ ],k ∈ [1, N t − 1] . Будем соединять ребрами только те точки, которые расположены всоседних плоскостях по оси аппликат, то есть в плоскостях t = t k и t = t k +1 .В силу ограничения (8.1.6), найдем минимальное и максимальное расстояния, которое может пройти объект за время ∆T :ρ min = vmin ∆T , ρ max = vmax ∆T .Тогда для узла (ψ i ,λ j , t k ) следует рассматривать только те точки (ψ r , λ s , t k +1 ) вплоскости t = t k +1 , которые входят в область достижимости:22ρ ∈ [ρ min , ρ max ], ρ = (ψ i − ψ r ) + (λ j − λ s ) .326Соединим отрезками пары точек (ψ i , λ j , t k ) и (ψ r , λ s , t k +1 ) , если выполняются следующие условия:1) отрезок с концами в указанных точках не пересекает и не содержитсявнутри ни одного из контуров Γkg статических ограничений;2) отрезок с концами в указанных точках не пересекает ни одно из множеств в трехмерном пространстве, определяющих динамические ограничения.Отметим, что оба условия проверяются достаточно просто.
В первом случаенеобходимо использовать алгоритм, который находит точки пересечения отрезкаи многоугольника. Проверка второго условия также сводится к использованиюуказанного алгоритма. Действительно, найдем сначала все точки пересечения отрезка с концами в вершинах (ψ i , λ j , t k ) и (ψ r , λ s , t k +1 ) и контура Γ aj опасной зоныΩ aj . Пусть (ψ h , λ h ) , h = 1, nh – координаты точек пересечения.
Для каждой из этихточек найдем соответствующий момент времени попадания объекта в эту точкупо формулеt h = tk +∆t s(ψ h − ψ i ).ψ r − ψiЕсли хотя бы для одной из этих точек выполняется условие t h ∈ [t1al , t 2al ] , то ребромежду рассматриваемыми узлами (ψ i , λ j , t k ) и (ψ r , λ s , t k +1 ) не устанавливается.Здесь [t1al , t 2al ] – интервал времени, на котором задана опасная зона Ω aj .Если условия 1 и 2 выполняются, то между вершинами(ψ r , λ s , t k +1 )(ψ i , λ j , tk )иустанавливается ребро. Каждому ребру графа присваивается вес,равный времени движения по ребру при условии, что фактическая и заданнаяскорости совпадают. В результате перебора всех вершин графа в соответствии сописанным алгоритмом создается матрица смежности вершин.
Полученный графявляется ориентированным, так как движение по его ребрам возможно только повозрастанию значения времени.Заметим, что чем меньшие значения имеют шаги трехмерной сетки327∆ψ s , ∆λ s и ∆t s , тем более близким к оптимальному маршруту будет найденноерешение. Но, с другой стороны, уменьшение шага сетки означает увеличениечисла узлов графа и размерности матрицы смежности вершин. Следовательно,увеличивается и время вычислений, которое должно быть как можно меньшим ине может превышать интервала смены прогноза погодных условий ∆T . Однако,приведенный алгоритм построения графа очевидным образом распараллеливается, что позволяет существенно уменьшить время его работы.Для нахождения оптимального (по времени в пути) маршрута необходимо вкачестве начальной точки принять вершину A(ψ 0 , λ 0 ) графа.
В качестве конечнойточки нужно взять вершину B(ψ1 , λ1 ) графа, принадлежащую прямой p , котораяимеет минимально возможное значение аппликаты t = t f .Далее, следует найти кратчайший путь на графе, соединяющий эти две точки. Если такого пути не существует, то в качестве конечной точки нужно взятьследующую точку, принадлежащую прямойpсо значением аппликатыt = t f + ∆t s и т.д.Отметим, что минимальное возможное время попадания в конечную точкуопределяется формулой t min =ρ( A, B), где ρ( A, B ) – расстояние между точками Avmaxt и B .
Соответственно индекс f для момента времени t = t f равен min + 1 . ∆t s Найденный таким образом маршрут будем использовать в качестве начального приближения для решения исходной оптимизационной задачи (8.1.15).Улучшить этот маршрут можно посредством решения задачи оптимизации(8.1.14) с помощью численных методов нелинейного программирования, в частности последовательного квадратичного программирования [107].Другой способ уточнения состоит в построении локального конечного набора траекторий в окрестности найденного начального приближения и поискенаилучшего варианта среди них.
Подробно этот подход обсуждается в следую-328щем параграфе. Тем не менее, в обоих случаях описанная процедура служит дляулучшения приближенного решения, и оптимизация здесь выполняется не навсем множестве допустимых маршрутов, а лишь в окрестности найденного начального приближения.Отметим, что в качестве веса каждому ребру графа можно присвоить значение расстояния между двумя точками. Тогда результатом оптимизации пути награфе будет кратчайший маршрут с наименьшим временем перехода.Рассмотрим теперь алгоритм решения задачи (8.1.16), то есть процедурупостроения субоптимального по расходу топлива маршрута. Так же как и в предыдущем алгоритме, сначала необходимо сформировать граф и каждому ребруэтого графа присвоить вес.
Но, в отличие от предыдущего варианта, вес ребраследует принять равным расходу топлива при движении по ребру, который вычисляется по формуле:w = ρ(V )t ,где ρ(V ) – удельный расход топлива при заданной скорости V , t – время движения по ребру. Далее, в зависимости от постановки задачи, возможны два вариантаработы алгоритма. Опишем каждый из них.1) Требуется минимизировать расход топлива при ограничении допустимого времени t max нахождения в пути. В этом случае для построения оптимальногомаршрута будем перебирать последовательно конечные точки, принадлежащиепрямой p со значением аппликаты, не превышающим t max . Для каждой из этихточек найдем кратчайший путь на графе, то есть путь с наименьшим расходомтоплива.
В качестве результата, среди найденных вариантов, примем ту ломануюв пространстве, для которой время перехода наименьшее.2) Требуется минимизировать время в пути с заданной экономией топливаот номинального значения. В этом случае также будем перебирать последовательно конечные точки пути, принадлежащие прямой p , начиная с наименьшеговозможного значения времени t = t f . Но, в отличие от предыдущего варианта, бу-329дем увеличивать значение аппликаты t = t f + k∆t s ( k > 0 – целое число) до техпор, пока расход топлива превышает заданный предел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
