Диссертация (1149252), страница 18

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 18)

. . , ().Теорема 2.5.1. Пусть выполнены предположения утверждения 2.4.2и предположение 2.5.1 и скорости роботов регулируются в соответствиис модифицированным законом.Тогда роботы стремятся к равномерному распределению вдоль целевойэквидистанты (2.4). Точнее, можно так пронумеровать роботов индексом ∈ [0 : − 1], что будет выполнено следующее соотношение: [ ⊕1 (); () ] →perпри → +∞ ∀ ,(2.20)где [ 1 , 2 ] — минимальное расстояние между двумя точками 1 , 2 ∈E(0 ), измеряемое вдоль кривой E(0 ), а символ ⊕ обозначает сложениепо модулю .Данный результат справедлив для обоих сценариев С.1) и С.2).Для доказательства потребуется несколько лемм и следствий из них.Переходя к их обсуждению, предварительно заметим, что рассмотрение можнососредоточить на случае ≥ , где момент времени настолько велик,что i)—iv) утверждения 2.4.2 выполнены при всех ≥ .

Согласно iv)утверждения 2.4.2 роботы могут быть занумерованы в циклическом порядке,который не нарушается со временем. Обозначим за криволинейнуюкоординату (длину дуги) на E(0 ). Эта координата циклична: и ± perсоответствуют одной и той же точке. Кривая E(0 ) ориентирована такимобразом, что область находится по левую сторону движения вдоль E(0 ).Обозначим через |2 − 1 | длину дуги от точки с координатой 1 до точкис координатой 2 , а за () — координату, соответствующую (). Символом o()(в том числе с индексом) будем обозначать любую функцию, котораяэкспоненциально стремится к нулю при → +∞. Далее в доказательствахиспользуются некоторые факты приложения А. Напомним, что их нумерацияначинается с соответствующего символа А.Лемма 2.5.1.

Для любого робота ˙ () − () = o,* ().99Доказательство: Обозначим через (), () базис Френеэквидистанты E(0 ) и через κ 0 () — ее кривизну в точке . Заметим, что () = () и () = ()−[ ()−0 ] [ ()], при этом ˙ = , ˙ = ˙ [ ]и согласно замечаниям А.1.1 и А.1.2 = ( ) при ≈ +∞. Прменяя формулыФрене-Серре [168] ′ = κ , ′ = −κ к эквидистанте E(0 ), получим = ˙ [ ] − ˙ [ ] + [ − 0 ] κ 0 ( ) [ ] ˙ ,⟨ [ ] − [ ]; [ ]⟩ + 1 .˙ =1 + [ − 0 ] κ 0 ( )(2.21)Здесь −0 = o () по лемме А.1.1. Поскольку −0 — это расстояние между и 0 -эквидистантой, при ≈ +∞ также имеем: ‖ − ‖ = o ().

Учитывая,что векторное поле (·) непрерывно и локально липшицево вблизи E(0 ),из последнего уравнения следует, что ‖ ( ) − ( ) ‖ = o (). Для завершениядоказательства остается заметить, что в (2.21) ‖ ( ) ‖ = 1, а и κ 0 ( )ограничены. Используя тот факт, что в (2.16) функция (·) липшицева, приходимк следующему следствию.Следствие 2.5.1. При ≈ +∞ справедливы следующие утверждения:i) если робот ⊕ 1 находится в ОЗУ робота , то ˙ () [ |⊕1 () − ()| ] + o () − ();ii) в противном случае ˙ = ( ) + o,⋆ ().=Лемма 2.5.2. Пусть робот ⊕ 1 является соседом робота и находитсяв его ОЗУ в любой момент времени = , где → +∞ при → +∞. Тогдаlim→+∞ |⊕1 () − ()| ≤ − .Доказательство: Для > 0 функция () := max{|⊕1 ()− ()|; − +}абсолютно непрерывна и почти при всех |⊕1 () − ()| ≤ − + ⇒ ˙() = 0,|⊕1 () − ()| > − + ⇒ ˙() = ˙ ⊕1 () − ˙ ().100Во втором случае робот ⊕ 1 не является соседом робота .

Поэтому согласнолеммам 2.5.1 и 2.5.1˙ ⊕1 () ≤ ( ) + o⊕1,† (),˙ () = ( ) + o,⋆ ()∀ ≈ +∞.Следовательно, ˙() ≤ o () почти при всех . Поскольку при ≈ +∞ ( ) =− + , при ≥ имеем:∫︁− () ≤ ( ) +∫︁∞o ( ) ≤++o ( ) ,∫︁ ∞→+∞lim () ≤ − + +o ( ) ==⇒ lim () ≤ − + →+∞→+∞⇒ lim |⊕1 () − ()| ≤ − + .→+∞Для завершения доказательства остается устремить → 0.

−1Множество всех -предельных распределений R = { }=0 обозначимза R, а координату — за (R).Лемма 2.5.3. | ⊕1 (R) − (R) | ≤ − для всех ∈ [0 : − 1] и R ∈ R.Доказательство: Предположим обратное: существуют и R ∈ R такие,что | ⊕1 (R) − (R) | > − . Пусть — множество всех , при которых ⊕ 1является соседом робота и лежит в его ОЗУ. Введем обозначение := { :|⊕1 (R) − (R)| ≥ − , mes < +∞}. По лемме 2.5.2 ∈ , и поэтому ̸= Ø. Заметим, что mes = +∞, когда | ⊕1 (R) − (R) | < − . Более того,→+∞существуют последовательность −−−−→ +∞ и > 0 такие, что | ⊕1 ( ) − ( ) | ≤ − −3 ∀ .

По лемме 2.5.1 |˙ ()| ≤ < +∞ при ≈ +∞ и для всех .Таким образом, при ≈ +∞ и ∈ ∆ := [ − , + ] имеем:| () − ( )| ≤ ,| |⊕1 () − ()| − |⊕1 ( ) − ( )| | ≤ 2⇒ | ⊕1 () − () | ≤ − − ⇒ ∆ ⊂ ∀ ≈ +∞.Следовательно, mes = +∞.Так как по свойству ii) предположения 2.5.1 − > per , то любая цепочкапоследовательно соседних роботов ( и ⊕ 1) из конечна. То есть существуетробот ∈ такой, что ⊕ 1 ̸∈ .

Положим () := 1, если ∈ , и () := 0101в противном случае; и обозначим за дополнение . По лемме 2.5.1˙ () ≥ [ ( ) + o,⋆ () ] (),]︀ ();˙ ⊕1 () ≤ (− ) + o⊕1 () ⊕1 () + [ ( ) + o⊕1,† () ] ⊕1[︀ () − ( ) () + o() ≤˙ ⊕1 () − ˙ () ≤ (− ) ⊕1 () + ( ) ⊕1 ∩ () + o() ≤≤ −[ ( ) − (− ) ] ⊕1 ∩ () + (− ) ⊕1 ∩ () + ( ) ⊕1[︀]︀≤ −[ ( ) − (− ) ] E () + (− ) + ( ) () + o().Здесь E := ⊕1 ∩ = ⊕1 ∖ , и поэтому mes (E) ≥ mes (⊕1 ) − mes ( ),при этом уменьшаемое равняется +∞, а вычитаемое конечно. Очевидно, чтоmes (E) = +∞.

Произвольно зафиксировав , для () := ⊕1 () − () имеем:( − )]lim [ ⊕1 () − () ] ≤ ( ) − [ ( ) − ∫︁∫︁[︀]︀ ∞−+ ( ) + ( ) () +→+∞∞∫︁∞E () +o() .Второе слагаемое справа равняется −∞, остальные конечны. Следовательно,() → −∞ при → +∞, что нарушает () ≥ 0 ∀ . Полученное противоречиезавершает доказательство. Лемма 2.5.4. Существует такое R ∈ R, что | ⊕1 (R) − (R) | < − ∀ .Доказательство: Предположим обратное: такого R не существует.Для всех R ∈ R лемма 2.5.3 гарантирует существование такого индекса ,при котором | ⊕1 (R) − (R) |=− . Рассмотрим распределениеR с минимальным количеством таких индексов. По свойству ii)из предположения 2.5.1 среди них существует такой индекс , что := |⊕2 (R) − ⊕1 (R)| < − . Также рассмотрим последовательность { },порождающую R, и моменты времени ∈ ( − , + ).

Устремим → +∞, → 0. По лемме 2.5.1lim ˙ ⊕1 () ≤ (),lim ˙ () ≥ (− ),lim [ ˙ ⊕1 () − ˙ () ] ≤ () − (− ) < 0.102Следовательно, существуют > 0 и ∈ ( , + ) такие, что ⊕1 ( )− ( ) ≤⊕1 ( ) − ( ) − ∀ ≈ +∞. Уменьшая и сдвигая к , можно добиться,чтобы при всех ≈ +∞| ⊕1 (R) − (R) | < − ⇒ | ⊕1 ( ) − ( ) | ≤ − − .Выбрав сходящуюся подпоследовательность из { [ 1 ( ), . . . , ( )] }и перейдя к ее пределу, получим -предельное распределение с меньшимчислом индексов , для которых | ⊕1 − | = − , что противоречитопределению R. Лемма 2.5.5.

| ⊕1 (R) − (R) | < − для всех ∈ [0 : − 1] и R ∈ R.Доказательство: По лемме 2.5.4 существует распределение R ∈ R,при котором | ⊕1 (R) − (R) | < < + < − для всех . Увеличивая (если необходимо), можно обеспечить для робота отсутствие торможенияпри | ⊕1 () − () | ≥ и достаточно большом . Из временнойпоследовательности, порождающей R, возьмем момент времени такой, что∫︀ ∞ ∑︀|⊕1 ( ) − ( )| < и |o ()| < + − , где o (·) заимствованоиз леммы 2.5.1. Переходом к большему можно добиться, чтобы робот ⊕1 былсоседом робота и находился в его ОЗУ всякий раз, когда |⊕1 () − ()| ≤ +при ≥ .

Функции() := max | ⊕1 () − () |, () := max {(); }(2.22)абсолютно непрерывны и при почти всех ˙() = 0, если () ≤ ,˙() = (),˙если () ≥ ()˙ = ˙ 0 ⊕1 () − ˙ 0 (),где 0 — индекс первого максимума в (2.22). При ≥ из леммы 2.5.1 следует,что для () ≥ () ≤ + ⇒ ˙() = ˙ 0 ⊕1 () − ˙ 0 () == [ | 0 ⊕2 () − 0 ⊕1 () | ] + o0 ⊕1 () − 0 ⊕1 − [ | 0 ⊕1 () − 0 () | ] + o0 () ≤∑︁≤ oΣ () :=| o () |.103Следовательно, () ≤ + ⇒ ˙() ≤ oΣ () почти при всех ≥ .

Для крайнейлевой компоненты связности [ , + ) множества { ≥ : () < + } имеем:∫︁ ∈ [ , + ) ⇒ () ≤ ( ) +oΣ () < + (+ − ) = + .Следовательно, + = +∞, т.е. () < + < − ∀ ≥ , откуда следуетзаключение леммы. Доказательство теоремы 2.5.1: Непрерывное отображение R ∈ R ↦→M(R) := max=0,..., −1 | ⊕1 (R) − (R) | достигает своего максимума ∆maxв некотором R.

Пусть { } — последовательность, порождающая R. Покажем,что ∆max ≤ per .Предположим обратное: ∆max > per , т.е. для некоторого робота | − ⊕1 | = ∆max > |⊕2 − ⊕1 | (здесь R в записи (R) опущено).По лемме 2.5.5 ∆max < − , а по свойству iii) из предположения 2.5.1евклидово расстояние между роботами и ⊕ 1 превышает .

Характеристики

Список файлов диссертации