Guaranteed Rendezvous of Agents with Bounded, Varying Speeds

In this section, we generalize the results for identical agents by removing the restriction that requires all $v_i$ 's to be identical. We say that the speed $v_i$ of agent $i$ is bounded if $0 < v_{\min} \le v_i \le v_{\max} < + \infty$ for some constants $v_{\min}$ and $v_{\max}$ . The velocity $v_i$ may change over time. When all agents' speeds in a pursuit are bounded, we say the pursuit is a bounded speed pursuit.

Theorem 13   Bounded speed cyclic pursuit of $n$ Dubins car agents will rendezvous in finite time if the agents maintain their targets in the windshields of span $(-\phi, \phi)$ with

$$\phi < \cos^{-1} \dfrac{nv_{\max} - v_{\min}(1 - \cos \dfrac{\pi}{n})}{nv_{\max}}.$$ (32)

PROOF. For the proof we work with (9) and use the approach in the proof of Lemma 7. The simple polygon case is covered here; the proof for the self-intersecting polygon case then follows that of Lemma 8 similarly, which we do not repeat. Let $\mathcal V$ represent the agents speeds $v_1, \ldots, v_n$ and define $f, h$ , and $g$ as

$$\begin{array}{ll} f(\Theta, \Phi, \mathcal V) &:= \displaysty... ..._i, g(\Theta) &:= \displaystyle\sum _i \theta_i. \end{array}$$ (33)

The structures, $\Theta_{out}$ , $\Theta_{in}$ , and the hyperplane $g - (n-2)\pi = 0$ from Lemma 7 remain the same. For the $\Theta_{in}$ slice by the hyperplane, applying the method of Lagrange multipliers to $f$ as a function of $\theta _i$ 's with constraint $g - (n-2)\pi = 0$ yields that for all $i$ ,

$$v_i\sin (\theta_i + \phi_i) = \lambda.$$ (34)

Once again, holding $\phi_i$ 's fixed, for $f$ to take maximum on the $\Theta_{in}$ slice, for all $i$ , $v_i\sin(\theta_i + \phi_i)$ must take the same value and therefore, must be positive if we keep $\phi < 2\pi/n$ . Let us assume that we pick some $\phi <\pi/n$ , then

$$\displaystyle\sum _i (\theta_i + \phi_i) < (n-2)\pi + n\dfrac{\pi}{n} = (n - 1)\pi.$$ (35)

By the pigeonhole principle, for at least one $k$ , $(\theta_k + \phi_k) < (n - 1)\pi/n$ . Therefore,

$$\begin{array}{ll} f(\Theta,\Phi) &= \displaystyle\sum _i -v_i... ...yle\sum _iv_i - v_{\min} (1 - \cos \dfrac{\pi}{n}). \end{array}$$ (36)

To make $f + h < 0$ , we need $- h > f$ , which is true if

$$\displaystyle\sum _i v_i\cos \phi_i > \displaystyle\sum _iv_i - v_{\min} (1 - \cos \dfrac{\pi}{n}).$$ (37)

One way to satisfy this is to make sure that for each $i$ ,

$$v_i\cos \phi > v_i - \dfrac{v_{\min}}{n}(1 - \cos \dfrac{\pi}{n}),$$ (38)

or equivalently,

$$\phi < \cos^{-1} \dfrac{v_i - \dfrac{v_{\min}}{n}(1 - \cos \dfrac{\pi}{n})}{v_i}.$$ (39)

The right side of (39) achieves the global minimum when $v_i = v_{\max}$ , which gives us (32) as a sufficient condition for $\dot{V} < 0$ on the $\Theta_{in}$ slice. On the $\Theta_{out}$ slice, we have that $f \le \sum v_i - \min\{v_i\}$ , which is less than the last expression in (36); therefore, (32) also works for the $\Theta_{out}$ slice. The finite time guarantee follows the argument from Corollary 9. 

Moving to the intree case, when agents have different speeds, no equivalent of Lemma 11 can be stated since $\dot V < 0$ can no longer be guaranteed. A simple example is illustrated in Fig. 5. Agent $r$ is at the root and does not move. Suppose agent $i$ moves very fast and agents ($j, k$ in the figure) following $i$ barely move. Also assume that all agents are almost colinear. It is straightforward to see that, after a short period of time (the second drawing), the sum of the length of all edges, or $V$ , increases. This suggests that $\dot{V}$ must be positive at some point. However, such a system will still rendezvous. Supposing that the stationary agent is $r$ , at least one agent, say $i$ , is assigned to $r$ . Thus, $\dot{\ell}_{i,r} = -v_i\cos \phi_i < 0$ whenever $\phi < \pi/2$ . Hence, agent $i$ will merge into agent $r$ in finite time, and all other agents will eventually follow. We have proved:

Lemma 14   Bounded speed pursuit of $n$ Dubins car agents with an intree assignment graph will merge into the stationary agent in finite time if the agents maintain their targets in the windshields of span $(-\phi, \phi)$ with $\phi < \pi/2$ .

Figure 5: Bounded speed intree pursuit may not have $V$ dot less than zero at all times.

Since it is not possible to guarantee $\dot V < 0$ at all times for the bounded speed case, a result like Theorem 12 is out of the question. However, since Theorem 13 and Lemma 14 parallel Theorem 4 and Lemma 11, the argument giving us sequential rendezvous in the identical agents case continues to hold:

Theorem 15   Bounded speed pursuit of $n$ Dubins car agents with arbitrary connected, single-target assignment graph will rendezvous in finite time if the agents maintain their targets in the windshields of span $(-\phi, \phi)$ with fixed $\phi$ satisfying (32).