Диссертация (1145289), страница 52
Текст из файла (страница 52)
Если такого пути в итогене существует, то в качестве результата принимается вариант с наименьшим расходом топлива.В обоих случаях найденное приближенное решение необходимо уточнить всоответствии с процедурой, описанной выше.Важно отметить, что начальное предположение о совпадении фактическойи заданной скорости при поиске пути на графе может быть опущено. Для этогоможно считать, что объект движется по каждому ребру графа с фактической скоростью и вес ребра графа вычислять на основе этой фактической скорости. Приэтом заданную скорость для реализации найденного маршрута следует находитьиз уравнения (8.1.4), считая фактическую скорость известной.
Усложнение такоговарианта определяется лишь тем, что при построении графа необходимо проверять выполнение дополнительного ограничения, определяемого возможностьюреализации выбранной фактической скорости с учетом ограниченного ресурсаприводов.Рассмотрим несколько утверждений, обосновывающих использованиепредлагаемых вычислительных алгоритмов для построения маршрутов движения.В рамках приводимых ниже теорем предполагается, что фактическая и заданнаяскорости движения совпадают. Отметим, что это ограничение не является существенным, и теоремы могут быть расширены на более общий случай.Т е о р е м а 8 . 1 . Пусть заданы начальная точка A(ψ 0 ,λ 0 ) и конечная точка B(ψ1 ,λ1 ) , причем λ 0 < λ1 и ψ 0 < ψ1 , момент отправления из начальной точкиt0 , а также статические Ω kg , k = 1, m и динамические Ω aj , j = 1, n ограничениятакие, что Ω kg ⊂ Ω , k = 1, m , Ω aj ⊂ Ω , j = 1, n , Ω = {(ψ, λ ) : λ 0 ≤ λ ≤ λ1 , ψ 0 ≤ ψ ≤ ψ1 }.Пусть выполняются условия Ω kg I ∂Ω = ∅ , k = 1, m и Ω aj I ∂Ω = ∅ , j = 1, n , где∂Ω – граница множества Ω .
Тогда всегда существует допустимый маршрут(r, v ) , соединяющийточки A(ψ 0 ,λ 0 ) и B(ψ1 ,λ1 ) , и находящийся внутри множе-330ства Ω .~Доказательство. Рассмотрим множества Ω kg , k = 1, m – цилиндрическиеповерхности с образующей, параллельной оси времени Ot и направляющей Γkg ,~являющейся контуром множества Ω kg .
При этом каждую из поверхностей Ω kg ограничим снизу плоскостью t = t 0 , а сверху – плоскостью t = t1 ≤ T1 , где T1 – конеч~ный момент задания прогноза. Поверхности Ω kg представляют статические огра~ничения в трехмерном пространстве. Аналогично, пусть Ω aj , j = 1, n – цилиндрические поверхности с образующей, параллельной оси времени Ot и направляющей Γ ja , являющейся контуром множества Ω aj . При этом каждую из поверхностей~Ω aj ограничим снизу и сверху плоскостями t = t j1 и t = t j 2 , где [t j1 , t j 2 ] – интервал~задания динамического ограничения Ω aj .
Поверхности Ω aj представляют динамические ограничения в трехмерном пространстве. Построим множество М , яв~~ляющееся выпуклой оболочкой множеств Ω kg и Ω aj , то есть~~ ~~M = conv{Ω1g ,..., Ω mg , Ω1a ,..., Ω an } .(8.2.2)~Введем в рассмотрение цилиндрическое множество Ω , которое имеет образующую, параллельную оси времени Ot , и направляющую ∂Ω , совпадающую с~границей множества Ω . Пусть множество M = Ω \ M – часть пространства, не~включающая ограничения.
Заметим, что, в силу условий теоремы, M ⊂ Ω и, следовательно, множество M не является пустым. В частности, оно включает в себя~начальную точку A(ψ 0 , λ 0 , t 0 ) и луч p , заданный уравнениями λ = λ1 , ψ = ψ1 ,t = u , где u ≥ t 0 – вещественное число. Тогда задача формирования маршрута со-~стоит в поиске такой ломаной с началом в точке A и с концом на луче p , которая~~не пересекает ни одно из множеств Ω kg и Ω aj .Покажем, что допустимое множество в указанной задаче не является пустым. Действительно, построим произвольный маршрут, который целиком содер-331жится в множестве M и удовлетворяет ограничениям на скорость (8.1.6). В простейшем случае в качестве искомого можно принять маршрут, который проходит~по границе множества Ω . При этом первая часть маршрута представляет собойпрямую ψ = ψ 0 , λ = λ 0 + vt , t ∈ [t0 , t0 + t '] , где t ' =λ1 − λ 0и движение происходит сvпостоянной скоростью v , находящейся в пределах (8.1.6).
Аналогично, втораячасть маршрута определяется прямой λ = λ1 , ψ = ψ 0 + vt , t ∈ [t0 + t ' , t0 + t '+t ' '] с темже значением скорости v , где t ' ' =ψ1 − ψ 0. Разбивая этот маршрут на конечноеvчисло участков, получаем искомую ломаную в трехмерном пространстве и соответствующую ей пару векторов (r, v ) . ■Согласно рис. 8.1.1, представим маршрут в трехмерном пространстве лома~ной линией, проходящей через точки A(ψ 0 , λ 0 , t 0 ) = M 1 ψ1' , λ'1 , t1' , M 2 ψ '2 , λ'2 , t 2' ,((())())~…, M p ψ 'p , λ' p , t 'p , B (ψ1 , λ1 , t1 ) = M p +1 ψ 'p +1 , λ' p +1 , t 'p +1 . Заметим, что координаты()промежуточных точек M i ψ i' , λ'i , ti' , i = 1, p + 1 полностью определяются паройвекторов (r, v ) , задающей маршрут движения. Тогда будем представлять маршруткак множество точек в трехмерном пространстве следующего видаR(r, v ) = {(ψ, λ, t ) | ψ = αψ i' + (1 − α)ψ i' +1 , λ = αλ'i + (1 − α )λ'i +1 ,t = αti' + (1 − α )t i' +1 , α ∈ [0,1], i = 1, p }.(8.2.3)Итак, каждой паре векторов (r, v ) , задающей маршрут, взаимно-однозначно соответствует ломаная (8.2.3) в трехмерном пространстве, проходящая через точки{M i }ip=+11 .Т е о р е м а 8 .
2 . Пусть заданы начальная точка A(ψ 0 , λ 0 ) и конечная точка B(ψ1 , λ1 ) , причем λ 0 < λ1 и ψ 0 < ψ1 , момент отправления из начальной точкиt = t 0 и T1 – конечный момент задания прогноза. При отсутствии статических идинамических ограничений функционал времени перехода J T на множестве допустимых маршрутов достигает своего наибольшего и наименьшего значения.332Доказательство. Пусть задан допустимый маршрут (r, v ) , соединяющийначальную A(ψ 0 , λ 0 ) и конечную B(ψ1 , λ1 ) точки. Этому маршруту в трехмерномпространстве соответствует ломаная {M i }ip=+11 .В соответствии с ограничением (8.1.6), скорость v подвижного объекта ограничена значениями: vmin ≤ v ≤ vmax . Это значит, что для момента времени t расстояние ρ , пройденное объектом, также ограничено значениямиvmin t ≤ ρ ≤ vmax t .(8.2.4)Рассмотрим два конуса K1 и K 2 , заданные уравнениями{= {(ψ, λ, t ) | (ψ − ψ}≤ 0}.2K1 = (ψ, λ, t ) | (ψ − ψ 0 ) + (λ − λ 0 ) − vmint2 ≤ 0 ,K22022)2 + (λ − λ 0 )2 − vmaxt2Определим пересечение этих конусов с октантом, в котором должен находитьсямаршрут движения:K1+ = K1 I {(ψ, λ, t ) | ψ ≥ ψ 0 , λ ≥ λ 0 , t ≥ t0 , t ≤ T1},K 2+ = K 2 I {(ψ, λ, t ) | ψ ≥ ψ 0 , λ ≥ λ 0 , t ≥ t0 , t ≤ T1}.Тогда, с учетом ограничения (8.2.4), допустимый маршрут должен находитьсявнутри множества K r = K 2+ \ K1+ .
При этом начальная точка любого допустимого~маршрута совпадает с точкой A(ψ 0 , λ 0 , t 0 ) , а конечная – должна принадлежатьлучу l, уравнения которого имеют видψ = ψ 0 , λ = λ 0 , t = u, u ≥ t0 .Учитывая ограничения на скорость (8.2.4), фактически конечная точка каждого маршрута должна принадлежать отрезкуB2 (ψ 2 , λ 2 , t max ) , t min =ρvmax, t max =ρvmin, ρ=B1 B2 , где(ψ1 − ψ 0 )2 + (λ1 − λ 0 )2B1 (ψ1 , λ1 , t min ) ,– расстояниемежду начальной и конечной точками.Итак, множество допустимых маршрутов (r, v ) состоит из всевозможныхломаных, состоящих из p звеньев, которые расположены внутри или на границе~множества K r , причем начальная точка ломаной совпадает с точкой A(ψ 0 , λ 0 , t 0 ) ,333а конечная лежит на отрезке B1 B2 .
Ясно, что это множество ограничено и замкнуто, то есть является компактом.При этом функционал времени перехода J T , при условии совпадения фактической и заданной скорости, является непрерывной функцией, вычисляемой поформулеJT =SpS1 S 2++ ... +,V1 V2Vpгде S1 , S 2 ,..., S p – длины участков ломаной, а V1 ,V2 ,...,V p – скорости движения поэтим участкам. По теореме Вейерштрасса отсюда следует, что функция J T намножестве допустимых маршрутов достигает своего минимального и максимального значений. ■О п р е д е л е н и е 8 .
1 . Будем называть δ -окрестностью маршрута (r, v )множество Ω δ точек трехмерного пространства, таких чтоΩ δ (r, v ) = {P(ψ, λ, t ) : ρ(P, Pr ) ≤ δ, Pr (ψ r , λ r , t r ) ∈ R (r, v )},где ρ(P, Pr ) =(ψ − ψ r )2 + (λ − λ r )2 + (t − t r )2(8.2.5)– евклидова метрика.Т е о р е м а 8 . 3 . Пусть допустимый маршрут (r, v ) состоит из конечногочисла p локсодромических участков, причем ψ 0 < ψ1 , λ 0 < λ1 и существует егоδ -окрестность Ω δ , которая не содержит ограничений. Тогда для любого числа0 < ε < δ можно подобрать такие параметры ∆λ s , ∆ψ s и ∆t s построения графа,для которых существует допустимый путь на графе со временем перехода, отличающимся от времени перехода на исходном маршруте (r, v ) не более, чем навеличину ε .Доказательство. Построим ломаную {M i }ip=+11 , соответствующую маршруту(r, v ) .Введем следующие обозначения: ∆λ s = a , ∆ψ s = b , ∆t s = c .
Построимтрехмерную сеть с параметрами a, b, c внутри прямоугольного параллелепипедаψ 0 ≤ ψ ≤ ψ1 , λ 0 ≤ λ ≤ λ1 , t 0 ≤ t ≤ T1 ,где T1 – конечный момент задания прогноза. При этом в качестве начальной точ-334~ки сетки примем точку A(ψ 0 , λ 0 , t 0 ) .Построим ломаную, вершины которой проходят через узлы данной сетки, инаходящуюся в δ -окрестности исходного допустимого маршрута (r, v ) .
Пусть на~чальная точка ломаной совпадает с вершиной A(ψ 0 , λ 0 , t 0 ) = M 1 ψ1' , λ'1 , t1' . Рас-(())смотрим точку M 2 ψ '2 , λ'2 , t 2' допустимого маршрута. Найдем ближайшую к нейточку сети среди точек, расположенных в плоскости t = t 2'' трехмерной сети, гдеt 2'' ≥ t 2' , но при этом ∆t 2 = t 2'' − t 2' < ∆t s = c . Нетрудно видеть, что для минимальногорасстояния ρ min выполняется неравенство∆t 22ρ min ≤(a2 + b2a2 + b22+≤ c +.44)((8.2.6))Обозначим через M 2' ψ '2' , λ''2 , t 2'' ближайшую к M 2 ψ '2 , λ'2 , t 2' точку, принадлежа-()щую трехмерной сети. С учетом (8.2.6), для того чтобы точка M 2' ψ '2' , λ''2 , t 2'' попадала в ε -окрестность исходного маршрута достаточно, чтобы выполнялось условиеa2 + b2c +≤ ε2 .42(8.2.7)()С другой стороны, для того чтобы точка M 2' ψ '2' , λ''2 , t 2'' была достижима из()точки M 1 ψ1' , λ'1 , t1' достаточно, чтобы выполнялось условиеa 2 + b2≤ V1∆t2 .2(8.2.8)Тогда вместо исходной сети построим новую сеть с параметрамиt2' − t1'ψ '2 − ψ1'λ'2 − λ'1a1 =, b1 =, c1 =,N1tN1ψN1λгде натуральные числа N1ψ , N1λ , N1t выбираются так, чтобы для величин a1, b1, c1выполнялись ограничения (8.2.7) и (8.2.8).Теперь()рассмотрим(второй)участокломаной,соединяющийточкиM 2 ψ '2 , λ'2 , t 2' и M 3 ψ 3' , λ'3 , t3' .
Найдем ближайшую к M 3 точку сети с параметра-335ми a1 , b1 и c1 среди точек, расположенных в плоскости t = t3'' этой сети, где t3'' ≥ t3' ,но при этом c1 ≤ ∆t3 = t3'' − t3' ≤ 2c1 . Тогда для минимального расстояния ρ min выполняется неравенствоρmin ≤(∆t32a12 + b12a12 + b122+≤ 4c1 +.44)((8.2.9))Обозначим через M 3' ψ 3'' , λ''3 , t3'' ближайшую к M 3 ψ 3' , λ'3 , t3' точку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
