Appendix B: Remaining Proofs

Figure 8: A regular $9$ -gon with agents on the vertices and moving along the lines tangent to the enclosing circle of the $9$ -gon.

PROOF OF LEMMA 3. For $n = 2$ , $\theta_1 = \theta_2 = 0$ and it is possible that $\phi_1 = \phi_2 = \pi/2$ by assumption; substituting these into (9) gives $\dot{V} = 0$ . For $n \ge 3$ , since agents may take arbitrary initial formation, they may lie exactly on the vertices of a regular polygon and have the agents on the next vertex (say clockwise direction, see Fig. 8) as their targets; all agents can also have $\phi_i = \pi/n < \phi$ . In this case, since $\theta_i = \frac{n-2}{n}\pi$ for all $i$ , $\theta_i + \phi_i = \frac{n-1}{n}\pi$ . Substituting these into (9) again gives

$$\dot{V} = \displaystyle\sum _i -v_i(\cos \dfrac{\pi}{n} + \cos \dfrac{n-1}{n}\pi) = 0 .$$ (44)

$\dot{V}$ can be easily made strictly positive by letting $\phi_i > \pi/n$ for all $i$ . 

PROOF OF LEMMA 6. When all $(\theta_i + \phi_i)$ are equal and in the interior of $\Theta_{in}$ , we have $(\theta_i + \phi_i) = \frac{\sum(\theta_i + \phi_i)}{n}$ for all $i$ . Hence, at the stationary point,

$$\begin{array}{ll} f(\Theta, \Phi) & = \displaystyle\sum _i -\... ... \dfrac{(n-2)\pi + \displaystyle\sum _i \phi_i}{n}. \end{array}$$ (45)

By (45), this unique stationary point of $f$ only depends on $\sum \phi_i$ but not on the individual $\phi_i$ 's. Also, fixing $\theta _i$ 's, the maximum of the last expression in (45) increases as $\sum \phi_i$ increases; hence, the upper bound of $f$ is given by (21). 

PROOF OF LEMMA 7. We may fix $\phi_i$ 's, in which case $\Theta_{in}$ forms a $n$ -dimensional cube (including the boundary) in the $n$ -dimensional Euclidean space with $\theta_i, \ldots, \theta_n$ as the coordinates. $\Theta_{in}$ is fully surrounded by $\Theta_{out}$ . Together, $\Theta_{out} \cup \Theta_{in}$ forms a larger $n$ -dimensional cube. Since the $\theta _i$ 's must also satisfy the constraint $\sum \theta_i = (n-2)\pi$ , the valid $\theta _i$ 's for simple polygon formation live on the slice of the $\Theta_{out} \cup \Theta_{in}$ cube cut by the hyperplane $\sum \theta_i - (n-2)\pi = 0$ . Geometrically, the slice through $\Theta_{out}$ forms an annulus on the hyperplane $\sum \theta_i - (n-2)\pi = 0$ , and the slice through $\Theta_{in}$ is the inside of that annulus. Fig. 9 illustrates these for the case of $n = 3$ . By continuity of $f$ , $f \le n - 1$ on the boundary of the $\Theta_{in}$ slice since the boundary is the inner part of the closure of the $\Theta_{out}$ slice. On the other hand, the $\Theta_{in}$ slice is closed and bounded hence compact. By the extreme value theorem, $f$ must take both maximum and minimum value on the $\Theta_{in}$ slice. Therefore, $f$ takes value no more than the larger of $n-1$ and (21) from Lemma 6.

Figure 9: $\Theta _{in}, \Theta _{out}$ and the slices cut by the $g(\Theta ) - (n-2)\pi = 0$ hyperplane, for the case of $n = 3$ and $\sum \phi_i$ $> \pi /2$ .

Combining the $\Theta_{out}$ and $\Theta_{in}$ slices, we obtain for any simple $n$ -gon that (22) holds. To ensure $\dot{V} = h + f < 0$ , we need $-h$ to be more than the right hand side of (22) and rearranging the resulting inequality yields (11). We note that the easily verified fact that for all $n \ge 5, \pi/n < \cos^{-1}((n - 1)/n)$ is used. 

Figure 10: (a) $\theta _i$ 's and $(\pi - \theta _i)$ 's for a self-intersecting polygon, as marked by the solid arcs and dashed arcs, respectively. The arrow marks the walker's walking direction and starting edge. (b) $\theta _i$ 's can be made arbitrarily small by ``pressing'' this polygon from left and right.

PROOF OF LEMMA 8. When the polygon is self-intersecting, the internal angles are no longer well defined; therefore, the constraint, $g$ , will change. However, for our purpose of calculating $\dot{\ell}_{i,j}$ , we can always pick the smaller of the two angles at any vertex of the polygon, since such choice does not affect the value of the cosine function. We define these angles as $\theta _i$ and look at $\sum (\pi - \theta_i)$ . If we start from any edge of a polygon, self-intersecting or not, and walk along the edges to get back to the starting edge, all the $(\pi - \theta _i)$ 's must add up to at least $2\pi$ (see Fig. 10(a)). This is true since the walker must turn at least a cycle to get back and $\sum (\pi - \theta_i)$ is exactly the sum of the angles turned. Thus $\sum \theta_i \le (n-2)\pi$ . The constraint function $g(\Theta)$ can again be defined as that in (17). For self-intersecting polygon, $g$ can be arbitrarily close to 0 (see Fig. 10(b)). Therefore, $0 < g \le (n-2) \pi$ and (20) becomes

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

As stated in Lemma 7, we only need to worry about the part of $\{\theta_i + \phi_i\}$ that belongs to $\Theta_{in}$ . That is, the interesting $\theta _i$ 's must comply to

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

We may fix $g$ satisfying (47) as a constraint and apply the method of Lagrange multipliers similarly; bounds from Lemma 7 clearly hold. 

Figure 11: Dubins car agent $i$ that just loses its target $j$ at point $A$ .

PROOF OF PROPOSITION 16. We look at the instant $t$ when agent $i$ just loses sight of agent $j$ . If agent $j$ is within distance $\rho$ of $i$ then they must have merged; suppose not. The setting is shown in Fig. 11: Agent $i$ is initially located at $A$ and the ray $\overrightarrow{AC}$ can be imagined as the right boundary of agent $i$ 's field of view (shaded area in figure); it cannot see anything to the right of $\overrightarrow{AC}$ . Let $\vert AC\vert = \rho$ , the merging radius. At that instant, agent $i$ 's field-of-view cone is rotating around $A$ with angular velocity $\omega_i$ . To stay out of $i$ 's windshield, agent $j$ 's velocity projection on the direction perpendicular to $AC$ must be greater than $\rho \omega_i$ . If $\rho\omega_i > v_j$ , then once $v_i$ starts to rotate, it will be able to get $j$ back into its windshield again. This condition is equivalent to (40). 

PROOF OF PROPOSITION 17.

Figure 12: Agent at $A$ turns along a circle with center $O$ of radius $r$ , leaving the small solid circle as its trace. The two large dotted circles are of distance $\rho$ to the agent at $A$ and $A'$ . The shaded disc denotes the intersection of all discs with radius $\rho$ from the agent as it turns a full cycle.

First let us assume that $i$ travels at constant speed $v_i$ . In Fig. 12, assume that agent $i$ is initially located at $A$ and turns clockwise around $O$ with radius $r$ . As it turns around, the intersection of all discs of radius $\rho$ with $i$ as the moving center is again a disc (the shaded area $C$ ) of radius $\rho - r$ centered at $O$ (This can be easily shown: any point inside $C$ is in all of the moving discs of radius $\rho$ and any point outside $C$ is not in at least one of the moving discs). Since any agent falling into $C$ will merge with $i$ , to avoid being found by $i$ , an agent, say $j$ , must move outside $C$ and as $i$ turns two full cycles, $j$ must turn at least one full cycle to avoid appearing in $i$ 's windshield. Hence, if it takes less time for $i$ to turn two cycles than for $j$ to turn one cycle,

$$\frac{2 \times 2\pi r}{v_i} < \frac{2\pi(\rho - r)}{v_j},$$ (48)

agent $i$ will then find an existing agent or merge with it. The inequality (48) yields the condition

$$\omega_i = \frac{v_i}{r} > \frac{2v_j + v_i}{\rho}.$$ (49)

Selecting (41) is then enough to guarantee that $G$ regains liveness and the system will rendezvous. If $v_i$ is not constant, since $\omega_i$ remains a constant by assumption, the intersection must have a minimum radius of $v_{\min}/\omega_i$ from $O$ . In this case, we need

$$\frac{2 \times 2 \pi}{\omega_i} < \frac{2\pi(\rho - v_{\min}/\omega_i)}{v_j},$$ (50)

which is also satisfied by (41). Lastly, (40) from Proposition 16 is also satisfied.