The cyclic case

Figure 4: Two Dubins car agents in a cyclic pursuit.

We start the analysis with cyclic pursuit: the $n$ edges of $G$ form a single polygon. Given the Dubins car model (1) and our control law (3), for two consecutive agents $i$ and $i + 1$ on the polygon, let $\theta _i$ be either of the two angles of the polygon at vertex $i$ . For example, we may use the internal angles for simple (non-self-intersecting) polygons. In the special case of $n = 2$ , $\theta_i = 0$ . Let $\phi_i$ be the angle between $\dot{p}_i$ and the line segment from $p_i$ to $p_{i+1}$ (see Fig. 4). Note that $\phi_i$ is not the same as $\phi$ , half of the windshield span, which is fixed and the same for all $i$ . The angle $\phi_i$ is positive if $\theta _i$ and $\phi_i$ start from different sides with respect to the ray $\overrightarrow{p_ip_{i+1}}$ . The directions in which $\theta_i, \phi_i$ increase are marked with arrows in Fig. 4.

For a specific $\ell _{i,i+1}$ , agent $i$ 's movement will cause it to shorten at a rate of $v_i\cos\phi_i$ ; agent $i + 1$ 's movement will cause it to lengthen at a rate of $v_{i+1}\cos(\pi - (\theta_{i+1} + \phi_{i+1})) = -v_{i+1}\cos(\theta_{i+1} + \phi_{i + 1})$ . The derivative of $\ell _{i,i+1}$ is then

$$\dot{\ell}_{i,i+1} = \Big\langle \dot{p}_{i+1} - \dot{p}_{i}, \fr... ...vert} \Big\rangle = -v_i\cos \phi_i - v_{i+1}\cos(\theta_{i + 1} + \phi_{i+1}).$$ (8)

After summing up (8) for all $i$ and rearranging, we have for the cyclic case

$$\dot{V} = \displaystyle\sum _{i} -v_i(\cos \phi_i + \cos (\theta_{i} + \phi_i)).$$ (9)

For identical agents with unit speed $(v_i = 1)$ , (9) becomes

$$\dot{V} = \displaystyle\sum _i -(\cos \phi_i + \cos (\theta_{i} + \phi_i)).$$ (10)

We want to keep $\dot{V}$ negative at all times prior to rendezvous. From (10) we get

Lemma 3   For any integer $n \ge 2$ , the windshield angle $\phi > \pi/n$ permits trajectories for which $\dot{V} > 0$ .

By Lemma 3, for any $n \ge 2$ and $\phi > \pi/n$ , pursuit cycles exist for which $\dot{V} \ge 0$ . We are now ready to give a sufficient condition for rendezvous.

Theorem 4   Unit speed cyclic pursuit of $n$ Dubins car agents will rendezvous if the agents maintain their targets in the windshields of span $(-\phi, \phi)$ with:

$$0 < \phi \le \left\{\begin{array}{ll} \dfrac{\pi}{2}, & n = 2 ... ...1} \dfrac{n - 1}{n}, & n = 3, 4 \dfrac{\pi}{n}, & n \ge 5 \end{array}\right.$$ (11)

The problem of how the agents can maintain their targets in a given windshield span, which is addressed with Proposition 16, is not part of this theorem. We proceed to prove Theorem 4 by first introducing several lemmas; essentially we want to show that if $\phi$ satisfies (11), then $\dot{V} < 0$ . We may then apply a Lyapunov theorem to conclude. To facilitate the discussion, define the first and second terms of $\dot{V}$ in (10) as

$$\begin{array}{ll} h(\Phi) & = h(\phi_1, \ldots, \phi_n) := \d... ... \displaystyle\sum _i - \cos (\theta_{i} + \phi_i), \end{array}$$ (12)

and we have

$$\dot{V} = h (\Phi) + f(\Theta, \Phi).$$ (13)

For notational convenience, we use $f$ in place of $f(\Theta, \Phi)$ and $h$ in place of $h(\Phi)$ when it is appropriate to do so. By boundedness of the cosine function, $-n \le h, f \le n$ . Since $0 \le \vert\phi_i\vert < \phi$ for all $i$ , $h$ can be made arbitrarily close to $-n$ by lowering $\phi$ . Therefore, if for every fixed $n$ , there exists some $\delta_n > 0$ such that $f < n - \delta_n$ , some small $\phi$ can be chosen to make $h < -n + \delta_n$ to obtain $\dot{V} = h + f < 0$ . The bound $\phi \le \pi/2$ suffices for $n = 2$ , which is straightforward to verify. Hence, we work with some $n \ge 3$ and first consider the case in which the pursuit cycle of the agents is a simple (non-self-intersecting) polygon; the self-intersecting polygon case then follows similarly. Recall that Lemma 3 suggests that we need $\phi$ to be no more than $\pi/n$ . As we assume that $\vert\phi_i\vert < \phi$ for all $i$ , we need

$$-\pi/n < -\phi < \phi_i < \phi < \pi/n,$$ (14)

adding $0 < \theta_i < 2\pi$ gives,

$$-\frac{\pi}{n} < (\theta_i + \phi_i) < 2\pi + \frac{\pi}{n}.$$ (15)

We partition the $\theta _i$ 's satisfying (15) into two disjoint sets

$$\begin{array}{ll} \Theta_{out} &= \{(\theta_1, \ldots,\theta_... ...a_i + \phi_i \in [\frac{\pi}{2}, \frac{3\pi}{2}]\}. \end{array}$$ (16)

On $\Theta_{out}$ , for at least one $i$ , $-\cos (\theta_i + \phi_i) < 0$ . We immediately have $f < n - 1$ on $\Theta_{out}$ . The following lemma tells us how $f$ behaves on $\Theta_{in}$ .

Lemma 5   Unit speed cyclic pursuit of $n$ Dubins car agents with simple polygon pursuit cycle and satisfying (14) has the property that $f(\Theta, \Phi)$ has a single stationary point on the interior of $\Theta_{in}$ .

PROOF. If we fix $\phi_i$ 's, then $f$ , as a linear combination of cosine functions of $\theta _i$ 's, is bounded and continuous. Recall that for simple polygons, we may use the internal angles as $\theta _i$ 's. A simple polygon has the property that its internal angles sum up to $(n-2)\pi$ [35], which gives us,

$$g (\Theta) = g(\theta_1, \ldots, \theta_n) := \displaystyle\sum _i \theta_i = (n-2)\pi.$$ (17)

Again, we use $g$ in place of $g(\Theta)$ for notational convenience. Both $f$ and $g$ are analytic functions over the $\theta _i$ 's. We may use $g - (n-2)\pi = 0$ as the equality constraint to apply the method of Lagrange multipliers [26] over $f$ . The method produces the Lagrangian,

$$\begin{array}{ll} \Lambda(\theta_1, \ldots, \theta_n, \lambda... ...lambda(\displaystyle\sum _i \theta_i - (n - 2)\pi). \end{array}$$ (18)

The possible stationary points of $f$ satisfy $\nabla_{\theta_1, \ldots, \theta_n, \lambda} \Lambda = 0$ , or equivalently,

$$\sin (\theta_i + \phi_i) = \lambda, \quad \textrm{for all } i.$$ (19)

From (14) and (17),

$$(n-3)\pi < \displaystyle\sum _i (\theta_i + \phi_i) < (n-1)\pi.$$ (20)

As a side note, the $\Theta_{in}$ slice may be empty when $n \le 5$ by the first inequality of (20). For any $n \ge 3$ , by the pigeonhole principle [41], for at least one $i$ , $(\theta_i + \phi_i)$ must be in the range $(0, \frac{n-1}{n}\pi)$ , which means that for that $i$ , $\sin(\theta_i + \phi_i) = \lambda > 0$ . By (19), for all $i$ , $\sin(\theta_i + \phi_i) = \lambda > 0$ . This forces $f$ to have a single stationary point on the interior of $\Theta_{in}$ . 

Lemma 6   At the stationary point in Lemma 5,

$$\begin{array}{c} f(\Theta, \Phi) \le -n\cos \dfrac{(n-2)\pi + n\phi}{n}. \end{array}$$ (21)

Lemma 7   Unit speed cyclic pursuit of $n$ Dubins car agents with simple polygon pursuit cycle has the property

$$f(\Theta, \Phi) \le \max \Big\{-n\cos \frac{(n-2)\pi + n\phi}{n}, n-1\Big\}$$ (22)

and $\dot{V} < 0$ , if the agents maintain their targets in the windshields of span $(-\phi, \phi)$ with $\phi$ satisfying (11).

The key property making the proof of Lemma 7 work is that the internal angles of any simple polygon in the plane sum up to $(n-2)\pi$ , which is less than $n\pi$ . We can then choose $\phi$ to make $\sum(\theta_i + \phi_i)$ less than $n\pi$ and the pigeonhole principle guarantees that some $(\theta_i + \phi_i)$ will be less than $\pi$ . In turn, it is guaranteed by the method of Lagrange multipliers that for all $i$ , $(\theta_i + \phi_i)$ must take the same value $\lambda$ and must be less than $\pi$ for $f$ to take extreme values on the $\Theta_{in}$ slice. Combining the $\Theta_{in}$ , $\Theta_{out}$ slices then gives the result. The same technique can be applied when the polygon is not a simple one:

Lemma 8   Unit speed cyclic pursuit of $n$ Dubins car agents with self-intersecting polygon pursuit cycle has the property $\dot{V} < 0$ if the agents maintain their targets in the windshields of span $(-\phi, \phi)$ with $\phi$ satisfying (11).

PROOF OF THEOREM 4. Having proved that the agents may choose a windshield span satisfying (11) to ensure $\dot{V} < 0$ , by the standard Lyapunov theorem on asymptotic stability with respect to a set (see, e.g., [24]), all agents will rendezvous. The attractive set here is the ``diagonal'' in $\mathbb{R}^{2n}$ , in fact, its $\rho$ -neighborhood in which $\rho$ is the merging radius. Note that the introduction of $\rho$ also addresses the issue that our $V$ is not differentiable when some agents are in the same location; however, the result is valid even without this regularization (because a Lyapunov function with respect to an invariant set need not be differentiable on that set itself [24]). 

Once $\phi$ is fixed, the right side of (22) is determined, which leads easily to the existence of some $\delta_{\phi} > 0$ for which $\dot{V} < -\delta_{\phi}$ for all time $t>0$ . This yields:

Corollary 9   System in Theorem 4 achieves rendezvous in finite time.

It is natural to ask whether the system is stable in the sense of Lyapunov: will some agents get arbitrarily far away from the rest during the converging process? The answer is no. Denoting $V_0$ as the value of $V$ at $t=0$ , we formalize the notion with the following proposition:

Proposition 10   For the system in Theorem 4, $\dot{V} \le 0$ ensures that all agents are inside a bounding disc with radius at most $\frac{V_0}{2\sqrt{3}}$ for all time $t\ge 0$ .

PROOF. In a cyclic pursuit, the candidate Lyapunov function, $V$ , is exactly the circumference of the pursuit cycle. Given any two different agents $i,j$ on the pursuit cycle, there are two disjoint, undirected paths from $i$ to $j$ . One of these two paths must be no more than $V/2$ in total length and by repeated application of the triangle inequality, the straight line distance between $i,j$ cannot exceed $V/2$ . The $2D$ version of Jung's theorem [17,18] then tells us that there exists a bounding circle of the point set of all agents with radius no more than $\frac{V}{2\sqrt{3}}$ . Since $\dot{V} \le 0$ , $V \le V_0$ for all $t\ge 0$ . Hence, there is no blowup prior to convergence (i.e., the system is stable in the sense of Lyapunov).