13
$\begingroup$

I'm reading a paper (Ants, Crickets and Frogs in Cyclic Pursuit) and trying to understand one of the simpler results.

The following is a paraphrasing of the parts I'm using, but check the paper if more context is needed:

Consider $n$ moving ants $\mathrm{x}_1(t)$ through $\mathrm{x}_n(t)$ in a vector space $\mathcal{L}$. Each ant $\mathrm{x}_i$ moves at all times in the direction of the ant $\mathrm{x}_{i-1}$ (and $\mathrm{x}_1 \to \mathrm{x}_n$) with constant velocity $v$.

For $i = 1,...n$, define the initial conditions as $\mathrm{x}_i(0) = \xi_i$ and the following system of $n$ differential equations:

$$\frac{d}{dt} \mathrm{x}_i(t) = v \ \frac{\mathrm{x}_{i-1}(t) - \mathrm{x}_i(t)}{||\mathrm{x}_{i-1}(t) - \mathrm{x}_i(t)||}$$

We can construct an equivalent model in barycentric coordinates by defining

$$\mathrm{y}_i(t) = \mathrm{x}_{i-1}(t) - \mathrm{x}_i(t)$$

Then for $i = 1,...,n$, we have $\mathrm{y}_i(0) = \xi_{i-1} - \xi_i$ and the following system of equations:

$$\frac{d}{dt} \mathrm{y}_i(t) = v \left(\frac{\mathrm{y}_{i-1}(t)}{||\mathrm{y}_{i-1}(t)||} - \frac{\mathrm{y}_i(t)}{||\mathrm{y}_i(t)||} \right)$$

For this system, we can prove the following:

$\textbf{Lemma 1}$ The difference vectors $\mathrm{y}_i(t)$ have the following properties:

  1. $\sum \mathrm{y}_i = 0$
  2. $\frac{d}{dt} ||\mathrm{y}_i|| = (\cos \alpha_i - 1) v$

Where $\alpha_i$ is the angle between $\mathrm{y}_i$ and $\mathrm{y}_{i-1}$.

$\textbf{Proof:}$ The first part follows by definition and the second comes from projecting $\mathrm{y}_{i-1}$ onto $\mathrm{y}_i$.

Call $T$ the termination time where all ants collide and define $Y(t) = \sum_i ||\mathrm{y}_i(t)||$.

Then comes the part I'm most curious about. They claim

If the speeds are constant and equal, Lemma $1$ part 2 implies that $T \le Y(0)/v$.

I think this works by summing both sides of the second equality to get

$$\sum_i \frac{d}{dt}||\mathrm{y}_i|| = v \sum_i (\cos \alpha_i - 1) \le -v$$

which would prove the claim, but the inequality is where I get stuck.

I'm thinking we can bound the sum somehow by using the fact that $\sum_i \alpha_i \ge 2\pi$, but I'm not quite sure how to do this.

Edit: It appears this claim is false as pointed out by @stewbasic.


I'd still like to get answers for the following:

  1. A general bound for the termination time $T$.

  2. Under what conditions do the ants collide simultaneously?

For simultaneity, a sufficient condition is fine provided it covers the specific case of cube. For example, if a cycle of $n$ ants all start a constant distance $\mathrm{y}(0) = ||\mathrm{y}_i(0)||$ from their pursuer and prey and all start the same distance $d$ from their centroid, is this enough to ensure simultaneity of collision? If it simplifies things, the time bound need only apply to cases that satisfy the sufficient condition for simultaneity.

Specific case: Consider $8$ ants on the corners of a unit cube with pursuit cycle given by

$$(0,0,0) \to (1,0,0) \to (1,1,0) \to (1,1,1) \to (1,0,1) \to (0,0,1) \to (0,1,1) \to (0,1,0)$$

I'd ideally like to get the bound $T \le 2/v$, but even $T \le 8/v$ would acceptable. The actual value is about $1.96$, which I can get from simulation where their convergence path looks like this:

Mathematica graph

Here's an animated version I created:

Animated graph

Edit:

As @VictorZurkowski points out, the proof of Theorem $1$ includes a (not very strict) bound on $T$ which reduces in the constant velocity case to

$$T \le \frac{Y(0)}{v\left(1 - \cos\left(\frac{2\pi}{m}\right)\right)}$$

where $m$ is the number of survivors. For the cube case with unit speed, this becomes

$$T \le \frac{Y(0)}{1\left(1 - \cos\left(\frac{2\pi}{8}\right)\right)} = \frac{8}{\left(1 - \cos\left(\frac{\pi}{4}\right)\right)} = 8\left(2 + \sqrt{2}\right) \approx 27.3137$$

Using symmetry, I think I could get this down to $2 \left(2+\sqrt{2}\right) \approx 6.82843$.

All of the $\alpha_i$ follow one of these two curves where the $y$-axis is in degrees and the $x$-axis is $t$ in percent of of $T$ (at 100% they converge). We can see that they converge to the planar case where $\alpha_i = \frac{\pi}{4} = 45^{\circ}$

Alphas

I believe the planar case is worst case in terms of convergence time and this website has some nice bounds for regular polygons with unit area. If my calculations are correct, an octagon with unit length sides would have path length $2\sqrt{4+3\sqrt{2}} \approx 5.742$.

[To be revised and continued...]

$\endgroup$
  • 1
    $\begingroup$ You should include the definition that $\alpha_i$ is the angle between $\mathbf y_i$ and $\mathbf y_{i-1}$. $\endgroup$ – Rahul Aug 26 '16 at 5:43
  • $\begingroup$ Yes, of course. Thank you. I will edit it. $\endgroup$ – Alexis Olson Aug 26 '16 at 5:44
  • $\begingroup$ I believe $\sum_i\alpha_i$ is exactly $2\pi$ if the $\alpha_i$ are taken with signs. Then maybe the inequality $\cos\alpha\ge1-\frac12\alpha^2$ (from the Taylor series) can help bound the $\sum_i(\cos\alpha_i-1)$ term. $\endgroup$ – Rahul Aug 26 '16 at 5:54
  • 1
    $\begingroup$ That is that case if the ants are in a plane, but certainly not necessarily true in more dimensions. $\endgroup$ – Alexis Olson Aug 26 '16 at 5:56
  • 1
    $\begingroup$ There is no reason to have a simultaneous collision in general. Imagine the scenario when ant 1 is moving towards ant 2, which is nearby, while ant 2 is moving towards ant 3 that initially is far away on the ray going from ant 2 to ant 1. Clearly, ant 1 will intercept ant 2 in a harsh collision even if they don't stay on one line all the time. There is no a priori reason why the situation like that won't eventually arise even from some innocently looking generic initial setting if the pursuit order is fancy... $\endgroup$ – fedja Sep 3 '16 at 2:28
1
+50
$\begingroup$

This seems to be not true. Consider the case where the ants start on successive vertices of a regular $n$-gon (in the plane). By symmetry, their positions will always form a regular $n$-gon, so $$ \alpha_i=\frac{2\pi}n. $$ Now Lemma 1 part 2 gives $$ \frac{d}{dt}Y(t)=-kv $$ where $$ k=n\left(1-\cos\left(\frac{2\pi}n\right)\right). $$ Thus $T=Y(0)/(kv)$. Now $k\to0$ as $n\to\infty$ (asymptotically it is $\frac{2\pi^2}n$) so we can choose $n$ with $k<1$. Explicitly if $n=20$ then $k\approx0.97887$ (see wolframalpha). Then $T>Y(0)/v$.

$\endgroup$
  • $\begingroup$ Thanks. I'll have to check closely to make sure I'm not missing something. The text explicitly says "the only conconfigurations leading to equality are those for which $C(0)$ is a perfect polygon" so it would seem rather sloppy of them for this exact case to be a counterexample. $\endgroup$ – Alexis Olson Sep 1 '16 at 6:07
  • $\begingroup$ Their claim also doesn't make sense intuitively. As $n\rightarrow\infty$ their bound for $T$ goes to a constant, but the ants get closer and closer to just moving along the circumference of the circle at speed $v$. It's possible that this case is the worst, so the bound should be $T\leq Y(0)/(kv)$ (haven't thought carefully about it). $\endgroup$ – stewbasic Sep 1 '16 at 6:21
  • $\begingroup$ I wonder about regular $n$-gons of fixed radius $||x_i||$ rather than fixed edge length $||y_i||$. According to this, unit area $n$-gons path lengths approach $n \pi^{-3/2}$. So $X(0) = n$ means in the limit $T = X(0)/(v\pi^{3/2})$. $\endgroup$ – Alexis Olson Sep 1 '16 at 7:03
  • $\begingroup$ I meant sending $n\to\infty$ with $Y(0)$ fixed, which is roughly the same as fixing $\|x_i\|$ (either way the initial configuration approaches a particular circle). Why are you dividing $X(0)$ by the path length $s_n$? $T$ should be $s_n/v$ which is asymptotically proportional to $n$. $\endgroup$ – stewbasic Sep 1 '16 at 23:03
  • $\begingroup$ @AlexisOlson for your edited question, I think you also need to specify the order of the ants - ie which vertex is being targeted by which? $\endgroup$ – stewbasic Sep 1 '16 at 23:06
1
$\begingroup$

In Section 1 (the one about Ants), Theorem 1 says:
"Termination must therefore occur before [$(\cos(2\pi /m)-1) \int_0^t \min v_i(s)\;ds$] assumes the value $-\sum ||y_i(0)||$ ." (1)

In case of constant speed, this statement translates to $T \le (1-\cos(\frac{2\pi}{m}))^{-1}\frac{Y(0)}{v}$, where $m$=number of survivors by termination time.

In particular, @stewbasic basic example does not contradict the statement, since in that case the number of survivors by temination time is $n$.

In your example of 8 points at the vertices of a cube, whether $T\le 2$ depends on the speed $v$ that you are considering.

$\mathbf{\text{Note}}$: To prove (1), Bruckstein et alt. use that $\alpha_i \ge \frac{2\pi}{m}$ for some $i$, which does not seem to follow from the result they quote. i.e.: it is not clear that the proof of the bound for $T$ is without gaps.

$\endgroup$
  • $\begingroup$ I meant $T \le 2$ for unit speed. In other words, $T \le 2/v$. $\endgroup$ – Alexis Olson Sep 5 '16 at 16:31
  • $\begingroup$ After a second look, there is an obvious mis-statement in Lemma 3, Section V of the paper you refer to. Where it says "$\sum_{i=1}^n \alpha_i \le 2\pi$" it should say "$\sum_{i=1}^n \alpha_i \ge 2\pi$", from where it follows that $\alpha_i \ge \frac{2\pi}{m}$ for some $i$. $\endgroup$ – VictorZurkowski Sep 5 '16 at 17:46
  • 1
    $\begingroup$ The statement I claimed was false was that $T\leq Y(0)/v$, made near the end of page 9. $\endgroup$ – stewbasic Sep 5 '16 at 22:42
  • $\begingroup$ I missed that line. I stopped at the top of page 8. $T\leq Y(0)/v$ is wrong, as @stewbasic example shows. $\endgroup$ – VictorZurkowski Sep 6 '16 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.