Название задачи про заячьи бега

Vlad128

есть N зайцев в трехмерном пространстве. Каждый обладает постоянной скоростью (одинаковой для всех зайцев) и бежит по направлению к следующему по счету (последний бежит по направлению к первому). Опыты (sic!) показывают, что у системы есть устойчивая траектория, напоминающая эллипс. Есть ли исследования этой дин. системы, где все про нее рассказано? Как называется задача? Самим подумать тоже можно, я вот что-то не придумал :)

blackout

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

Vlad128

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

Damrad

в такой постановке достаточно расставить зайцев так, чтобы расстояние между ними было равно как раз этому скачку. и будет цикл :)

Vlad128

ну это понятно. А какие из подобных расположений будут устойчивыми? Я же изначально задаю положение случайно.

Vlad128

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

Damrad

будут устойчивыми, например, некоторые из тех, у которых после каждого шага расстояния остаются прежними :)

Damrad

а что за опыты кстати?

Vlad128

:grin: ну как, программка на матлабе

Vlad128

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

Vlad128

надо просто рубануть условия устойчивости по якобиану наверное :)

Vlad128

похоже реально, там якобиан получается с 6ю ненулями в каждой строке. Условие на собственные значения может быть довольно хитрым. Исходя из практики получается, что там что-то вроде w - 2pi / N < C * N / v, где v — "скорость" (длина прыжка N --- число зайцев, w — максимум угла между соседними лучами, C — некоторая константа. Т.е. чем меньше прыжок, тем более округлые трактории.

mtk79

опыты — это случайно разбросанные трехмерные массивы точек с известным только сеятелям распределением?
вообще, в курсе линейной алгебры учили, что эллипс — это плоская фигура. ее наличие свидетельствует о том, что в R^3 есть выделенная плоскость R^2, нормаль к которой (наличие метрики я заключил из существования равной по модулю скорости) задает выделенное направление, что противоречит изотропности R^3.
Или же нет усреднений по исходным положениям, и все это относится к уже коткретному, пусть и случайному, начальному распределению точек?
В общем, разгадка кроется в описании того, что такое
 
Опыты (sic!)

Vlad128

ее наличие свидетельствует о том, что в R^3 есть выделенная плоскость R^2, нормаль к которой (наличие метрики я заключил из существования равной по модулю скорости) задает выделенное направление, что противоречит изотропности R^3.
я же не говорил, что всегда к одному эллипсу :) нормали к этим эллипсам тоже могут быть распределены как-то (равномерно).
Распределяются точки равномерно в единичном кубе, ничего хитрого не выдумывал.

mtk79

а про аналогичную двумерную задачу что известно?
т.е. если известно такое же для двумерного распределения, то остается только найти плоскость, куда выполащивается траектория, и направление итоговой котовасии
хотя термин "напоминает эллипс" — это фантастика.
существование траектории — это окончательный процесс, когда она замыкается — или же уже после того, как она начала "напоминать", она может продолжать сжиматься?
ПС. Что происходит при хаотических столкновениях зверьков?

Vlad128

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

Sergey79

Казалось-бы расстояние между любой парой соседних зайцев должно все время уменьшаться.
почему? может они по кругу бегают друг за другом

mtk79

площадь вписанного многоугольника меньше площади круга

Damrad

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

Sergey79

да где там в условии сказано, что пространство то плоское? Бегают по кругу, потому что он может и есть геодезическая, никуда не денутся, зайчики

mtk79

ну и зря. имхо, что-то казалось бы простое, но не очень
А вот племянник мчится быстро
Как за блондинкою грузин

Например, момент импульса не сохраняется (по идее). Неплохо было бы найти инварианты (кроме числа зайцев, если, конечно, никто из них не сдохнет до наступления стационарного режима) в такой задаче
Кроме того, при наличии характерного времени [math]$$\tau=\frac{1}{v} \sup_{i,k=1..N}|x_i-x_k|$$[/math] есть еще зависимость от N, причем я не уверен, что для любых начальных конфигураций точек

griz_a

Правильно ли я понимаю, что тебя интересуют стационарные распределения марковской цепи в [math]$R^{3N}$[/math] с дискретным временем и несчетным множеством состояний?

griz_a

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

Sergey79

Чтобы бегать по кругу, скорость должна быть направлена по касательной
а заецу и не надо бежать по кругу, он-то будет бежать по прямой.

Natasha80

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

Sergey79

Если величина прыжка меньше какого-то из расстояний, то сумма расстояний уменьшается =>
если зайцы распределены по диаметру S^3, то что тогда?

Vlad128

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

Vlad128

Не, ну это типа полного решения, оно меня не интересует, мне интересно качественное исследование динамической системы: состояния равновесия (ну это очевидно их устойчивость. Т.е. какие состояния будут наблюдаться (== быть устойчивыми) при каких параметрах и почему.

Natasha80

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

sashok01

Хм, а попробуй схему более высокого порядка. По сути у тебя щас явный метод эйлера, да еще из большим шагом по времени - такой метод не ругает только ленивый. Если тебе нужны найти характеристики системы, то как ты обоснуешь, что то, что ты насчитал, описывает систему и с гладкими траекториями?

Vlad128

нет-нет. С непрерывной все просто, там нет устойчивых предельных множеств кроме точки. Я сейчас переключился обратно на дискретную. Просто непрерывная возникла как-то так в середине, думал, поможет чем-то, а нет.

sashok01

до, кстати, пример "аналитического "стационарного решения - зайцы в вершинах правильного n-угольника и величина скачка равна ребру n-угольника.
UPD1: более общее - замкнутая фигура (не обязательно плоская) с равными ребрами и величинами скачков, равными ребру. Каждый шаг происходит "перенумерация" зайцев
UPD2: как-то твои зайцы больше на лягушек похожи :)

Natasha80

В непрерывном случае нет гладких решений. В гладком решении скорость в каждой точке направлена по касательной => это геодезическая => это прямая. Но прямая не замкнута.
А негладкие решения есть. Если вырожденных точек (т.е. точек с нулевой скоростью) конечное число, то это многоугольник, в каждой точке которого скорость нулевая. Это аналог дискрентого многоугольника, в каждой вершине которого сидит по два зайца. Каждый раз половина зайцев прыгает в следующую вершину, а другая половина сидит на месте, потому что уже догнали следующего.

Vlad128

еще раз: стационарное != устойчивое. Множество стационарных состояний очевидно, меня интересует вопрос их устойчивости, т.е. вот на практике я запускаю процесс из случайного начального состояния. И вот там в основном характер получающихся предельных состояний одинаков (например, правильные N-угольники при определенных параметрах, при других — более заковыристые множества). Причем если уж получается правильный N-угольник, то при другом случайном выборе точек тоже получается правильный N-угольник, но другой (по-другому ориентированный, в другом месте расположенный, но понятно, с той же стороной).

sashok01

картинка для привлечения внимания:

начальное состояние -правильный 7ми-угольник с радиусом описанной окружности 1, скорости задаются равными ребру + случайная добавка из отрезка [-0.025,0.025], во время процесса скорости остаются постоянными. Можно для этого случая постараться доказать устойчивость
UPD надо сформулировать понятие устойчивости, а то этот многоугольник вращается c малой скоростью - соответственно координаты узлов движутся
UPD4: правильный 40-угольник, скорость равна ребру + [-0.005,0.005]

UPD2: случайное начальное положение 40 точек в квадрате [-0.5,0.5]x[-0.5,0.5] со случайными скоростями из отрезка [-0.025,0.025]:

Тут ваще никакой устойчивости
UPD3:случайное начальное положение 40 точек в квадрате [-0.5,0.5]x[-0.5,0.5] со случайными скоростями из отрезка [0,0.05]:

Vlad128

случайные скорости не нужны. Понятие устойчивости — стандартное, по ляпунову.
хорошие картинки, чем делал?

sashok01

по ляпунову как раз нет устойчивости - узлы медленно движутся в случае правильного семиугольника. гифки делал с помощью gnuplot, вычисления на си.

Vlad128

во втором и третьем случае скорость именно 0 + случайная составляющая?

sashok01

В первом случае скорость равна a + eps*0.025
Во втором - a + eps*0.005
a - ребро правильного N-угольника ( a=2R*sin(PI / N ) )
В третьем - eps*0.025 (т.е. от -0.025 до 0.025)
В четвертом - 0.025 + eps*0.025 (т.е. от 0 до 0.05)
eps берется из интервала [-1,1]. Распределена вроде бы равномерно (с помощью генератора rand из <stdlib.h> )

gr_nik

У меня немного по-другому получается.
 


Точки изначально случайно расположены в квадрате [0; 1]X[0; 1].
У меня скорость фиксированная, правда я её ограничиваю, когда точки близко друг у другу (меньше 0.005 тогда в каждый момент точка преодолевает половину расстояния до следующей (я это сделал, потому что тогда точки начинали "перепрыгивать" слишком далеко, чего бы не было в непрерывном варианте, а ещё проблемы с делением на маленькое число). Тогда, как бы я не генерировал сначала, точки сближаются друг к другу и начинают бегать по замкнутой кривой, которая продолжает сжиматься.

sashok01

Если скорость одинакова для всех, а расположение случайное в квадрате [-0.5,0.5]x[-0.5,0.5] (40 зайцев):
скорость 0.01:

скорость 0.02:

скорость 0.04:

скорость 0.08:

скорость 0.08 дубль два:

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

iri3955

Так вроде уже написали. Множество стационарных состояний - замкнутые ломаные с одинаковой длиной звена, равно шагу. И только они.

sashok01

Пусть координаты i-го зайца [math]$(x_i,y_i)$[/math] . Он прыгает в направлении (i+1)-го зайца, который имеет координаты [math]$(x_i,y_i + \rho)$[/math] (без ограничения общности). После шага координаты i-го зайца стали [math]$(x_i,y_i+a)$[/math], a (i+1) - го - [math]$(x_i+a\cos(\phiy_i + \rho+a\sin(\phi$[/math]. Вычисляем новое расстояние:
[math]$  \rho' =\sqrt{ (x_i +a \cos(\phi) - x_i)^2 + (y_i+a\sin(\phi)+\rho - y_i -a)^2  } = \sqrt { a^2 \cos^2(\phi) + \rho^2 + a^2(1-\sin(\phi^2 -2a\rho(1-\sin(\phi) ) } = \linebreak =\sqrt{a^2\cos(\phi)^2+\rho^2+a^2-2a^2\sin(\phi)+a^2\sin(\phi)^2 - 2a\rho + 2a\rho\sin(\phi)} =\linebreak =\sqrt{a^2\cos^2(\phi) +a^2 \sin^2(\phi) + \rho^2 + a^2 - 2a\rho -2a^2\sin(\phi) + 2a\rho\sin(\phi)} = \sqrt{a^2 + \rho^2 - 2a\rho+ a^2  + 2a\sin(\phi\rho-a)} = \sqrt{a^2 + (a-\rho)^2 + 2a\sin(\phi\rho-a)}  $[/math]

iri3955

Куда-то делась \phi в результате. И из полученного пока не следует сходимость

sashok01

del

iri3955

> члены с [math]$\phi$[/math] сократились, изменил пост, теперь выкладки более подробные.
Они не могли сократиться, [math]$\rho'$[/math] зависит от этого угла. А значит и последующие
выкладки не совсем корректны.
Даже видно, где ошибка: [math]$\sin(\phi) + \cos(\phi) \ne 1$[/math]

sashok01

ах да, там описка - квадраты должны быть. А ваще проведи свои выкладки и покажи, что зависит от угла

iri3955

У меня нет выкладок. Координата i-го зайца после прыжка фиксирована, координата i+1-го лежит на окружности, центр, которой отличается от координаты i-го, значит, расстояние зависит от угла. В твоих выкладках ошибка во втором равенстве, там не будет 2х челнов [math]$2a\rho\sin(\phi)$[/math]

sashok01

согласен, исправил ошибку

gr_nik

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

iri3955

C непрерывными как раз проще. Они все стягиваются в точку.
Допустим кол-во зайцев n. Тогда либо за конечное время их станет меньше n (один из зайцев догоняет другого и они ведут себя как один либо они стягиваются в точку. Второе можно оценить так.
Зайцы представляют собой n-угольник. Значит одни из углов не больше [math]$\frac{n-2}n\pi$[/math]. Тогда скорость сближения соответствующих зайцев
не меньше, чем [math]$a(1 - \cos(\frac{2\pi}n$[/math]. Остальные зайцы как минимум не отдаляются друг от друга, значит, периметр уменьшается со скоростью, не меньшей, чем оно же [math]$a(1 - \cos(\frac{2\pi}n$[/math]. Значит, либо какой-нибудь заяц за это время догонит следующего и строится аналогичная оценка с меньшим числом вершин, либо они все сходятся в одну точку и их становится больше n.
А с дискрентым сходимость есть не всегда (например, 2 зайца на расстоянии, меньшем длины шага будут прыгать с периодом 2).

Evgewkin

Есть ли исследования этой дин. системы, где все про нее рассказано? Как называется задача?

ИМХО, ключевые слова "cyclic pursuit". Похоже на обзоры:
BEHROOZI, F., & GAGNON, R. (1979). CYCLIC PURSUIT IN A PLANE. Journal
of Mathematical Physics, 20(11 2212-2216. doi:10.1063/1.524000
Richardson, T. (2001). Stable polygons of cyclic pursuit. Annals of
Mathematics and Artificial Intelligence, 31(1-4
147-172. doi:10.1023/A:1016678406688
Richardson, TJ. (2001). Non-mutual captures in cyclic pursuit. Annals
of Mathematics and Artificial Intelligence, 31(1-4
127-146. doi:10.1023/A:1016670220800
Моделирование:
Solis, F. J., & Yebra, C. (2010). Modeling the pursuit in natural
systems: A relaxed oscillation approach. Mathematical and Computer
Modelling, 52(7–8 956-961. doi:10.1016/j.mcm.2010.02.018
Оставить комментарий
Имя или ник:
Комментарий: