Angle-Bearing

Angle Rigidity with Bearing-Only Constraints [1]

Introduction

This work is founded on the recognition that pairs of bearing measurements originating from the same robot define angles independently of a coordinate frame. Contrasting with infinitesimally bearing-rigid frameworks, where individual bearings are maintained, infinitesimally shape-similar frameworks, are invariant to translation, rotation, and uniform scaling when the angles of the framework, or, equivalently, the inner-products of bearing pairs as discussed in this work, are maintained.

Preliminaries

Graphs and Frameworks

Frameworks for which any of the vertex positions are the same are referred to as degenerate frameworks. For frameworks in which the positions of the vertices are functions of time, the framework is denoted $G(\mathit{p}(t))=(\mathcal{G},\mathit{p}(t))$; the infinitesimal motion of $G(\mathit{p}(t))$ is $\dot{\mathit{p}}(t)=[{\dot{\mathit{p}}}_1(t{)}^{\mathrm{\top }},{\dot{\mathit{p}}}_2(t{)}^{\mathrm{\top }},\dots {\dot{\mathit{p}}}_n(t{)}^{\mathrm{\top }}{]}^{\mathrm{\top }}$. For notational clarity, time dependence of the vertex positions is omitted when the presentation is unambiguous.

Restricted to the plane, the following definitions, exemplified in Figure 1, are relevant to the results on planar frameworks in Sections: Triangulations and V. TODO

Figure 1: An outerplane graph (black vertices/edges) is a plane graph for which all vertices are on the outer face; its weak dual graph (red vertices/edges) is composed of vertices for each inner face with edges capturing the adjacency of inner faces. Addition of the dashed black edge removes a vertex from the outer face, resulting in a nonouterplanar graph whose weak dual has a cycle.

Definition: planar

A graph $\mathcal{G}$ is planar if it can be drawn in the plane so that its edges intersect only at their ends. The planar embedding of the graph $\mathcal{G}$ is a plane graph.

In other words, plane graphs are frameworks $G(\mathit{p})$ in which the vertices are embedded in the plane, i.e., $\mathit{p}\in {\mathbb{R}}^{2n}$, and the graph $\mathcal{G}$ is planar.

Definition: faces

The faces of a plane graph are the arc-wise-connected open sets partitioned by the embedding of the edges and vertices.

The outer face of a plane graph is the only unbounded face of the plane graph; all other faces are inner faces as depicted in Figure 1. The boundary of a face is the boundary of the associated open set, and faces are adjacent if their boundaries share an edge. The degree of a face is the number of adjacent faces.

Definition: outerplane graph

An outerplane graph is a plane graph for which all vertices lie on the boundary of the outer face.

The adjacency of the faces of a plane graph is described by the weak dual graph, defined as follows.

Definition: weak dual graph

The weak dual graph of a plane graph is the geometric dual graph, in which vertices correspond to faces of the plane graph and edges correspond to adjacency of the faces, less the vertex corresponding to the outer face.

Finally, a labeled graph is denoted $g=(\mathcal{G},\nu ,\xi )$, where $\nu$ is the set of vertex labels, and $\xi$ is the set of edge labels. A graph grammar $\mathrm{\Phi }$ consists of rules, ordered pairs of labeled graphs of the form $r=(g_a,g_b)$; applying $r$ transforms $g_a$ to $g_b$. With an initial labeled graph $g_0,\mathrm{\Phi }$ defines a nondeterministic dynamical system $(g_0,\mathrm{\Phi })$. The trajectory of ( $g_0,\mathrm{\Phi }$ ) is the sequence of graphs attained by applying $\mathrm{\Phi }$, denoted $\tau ={\left\{g_k\right\}}_{k=0}^{\mathrm{\infty }}$.

Affine Sets

The set $A\subseteq {\mathbb{R}}^n$ is affine if $\alpha x+\beta y\in A$ for $x,y\in A$ and $\alpha +\beta =1$. The affine hull of a set $A\subseteq {\mathbb{R}}^n$ is the intersection of all affine sets containing $A$ and is written $\mathrm{aff}\{A\}$; its dimension is denoted $\dim (\mathrm{aff}\{A\})$. The affine hull of the vertex positions of a framework is written $\mathrm{aff}\{\mathit{p}\}=\mathrm{aff}\{{\mathit{p}}_1,{\mathit{p}}_2,\dots ,{\mathit{p}}_n\}$.

An isometric transformation of ${\mathbb{R}}^n$ is a distance-preserving transformation $T:{\mathbb{R}}^n\to {\mathbb{R}}^n$ of the form $T=Mx+c$, where $M\in {\mathbb{R}}^{n\times n}$ is an orthogonal matrix and $c\in {\mathbb{R}}^n$. Affine sets are isometric if there is an isometry $T(A)=B$. The following lemma is important for the developments of Section: Infinitesimal Shape-Similarity.

Lemma 1

Let $A$ and $B$ be affine sets of dimension $r$ in ${\mathbb{R}}^n$. Then, $A$ and $B$ are isometric.

Notation

The rank of a matrix is written as $\mathrm{rank}(\cdot )$; the nullspace of a matrix is denoted by $\mathrm{null}(\cdot )$, and the dimension of the nullspace is written as $\dim (\mathrm{null}(\cdot ))$. Diagonal matrices are denoted by $\mathrm{diag}(\cdot )$, where the arguments appear ordered along the diagonal. The $d\times d$ identity matrix is denoted by $I_d;{\mathbf{1}}_n\in {\mathbb{R}}^n$ is a vector of ones, and $\mathbf{0}$ denotes a vector of zeros. The Kronecnull product is written as $\otimes$.

Infinitesimal Shape-Similarity

In this section, infinitesimal shape-similarity is presented as a tool to describe the types of formations that can be achieved by maintaining the relative angles between robots.

1. Beginning in Section: Infinitesimal Shape-Similarity, infinitesimal shape-similarity is defined.
2. In Section: Shape-Similarity Matrix, the shape-similarity matrix, the primary tool for characterizing frameworks for infinitesimal shape-similarity, is developed.
3. Finally, in Section: Assessing Frameworks for infinitesimal Shape-Similarity, the nullspace of the shape-similarity matrix is examined, yielding a rank condition on the shape-similarity matrix for assessing frameworks for infinitesimal shape-similarity.

Definition of Infinitesimal Shape-Similarity

Figure 2: Interrobot bearings capture direction information relative to a coordinate frame and are represented as unit vectors. Pairs of bearings define angles independently of a coordinate frame; infinitesimal shape-similarity characterizes frameworks for which these angles are maintained.

Consider a framework${}^2$ $G(\mathit{p})$ with vertex positions $\mathit{p}={[{\mathit{p}}_1^{\mathrm{\top }},{\mathit{p}}_2^{\mathrm{\top }},\dots ,{\mathit{p}}_n^{\mathrm{\top }}]}^{\mathrm{\top }}\in {\mathbb{R}}^{dn}$, and denote by $\mathrm{\Theta }$ the angle-set, which contains all $m$ angles formed between 3 distinct, connected vertices in the framework; i.e., $\mathrm{\Theta }=\{(i,k,j)\mid (i,k),(j,k)\in \mathcal{E},i\ne j\}$. For $G(\mathit{p}),$ let $\theta (\mathit{p})={[\dots ,{\theta }_{ikj},\dots ]}^{\mathrm{\top }}\in {\mathbb{R}}^m,\mathrm{\forall }(i,k,j)\in \mathrm{\Theta }$, be the vector of angles formed between 3 distinct, connected vertices, where the angle between the vectors ${\mathit{z}}_{ik}={\mathit{p}}_i-{\mathit{p}}_k$ and ${\mathit{z}}_{jk}={\mathit{p}}_j-{\mathit{p}}_k$ centered on ${\mathit{p}}_k$, shown in Figure 2, is given by

$$\begin{array}{}\text{(1)}& {\theta }_{ikj}={\cos }^{-1}\left(\frac{{\mathit{z}}_{ik}^{\mathrm{\top }}{\mathit{z}}_{jk}}{\Vert {\mathit{z}}_{ik}\Vert \Vert {\mathit{z}}_{jk}\Vert }\right).\end{array}$$

2. As with infinitesimal bearing-rigidity, the edges of $G(\mathit{p})$ represent interrobot bearings; however, pairs of bearings, rather than the bearings themselves, are the quantities of interest in the study of infinitesimal shape-similarity.

Having introduced the angles of $G(\mathit{p})$, consider infinitesimal motions of $G(\mathit{p})$ under which these angles remain constant.

Definition: angle-consistent motions

Infinitesimal motions $\mathit{p}$ of the framework $G(\mathit{p})$ are angle-consistent motions if $\frac{\mathrm{d}}{\mathrm{d}t}\theta (\mathit{p}(t))=\mathbf{0},\mathrm{\forall }t⩾0$; the trajectory $\{\mathit{p}(t)\}$ of the framework $G(\mathit{p})$ is angle-consistent if $\dot{\mathit{p}}$ is angle-consistent.

Of particular interest are angle-consistent infinitesimal motions that preserve the shape of $G(\mathit{p})$, where the shape refers to the initial angles of the corresponding complete framework $G^{\kappa }(\mathit{p}(0))$. Geometric intuition and parallels with graph rigidity correctly suggest that the shape of the framework will be maintained by only applying infinitesimal translations, rotations, and uniform scalings to the framework; however, depending on the underlying graph topology, there may exist angle-consistent motions of $G(\mathit{p})$ that do not preserve its shape-infinitesimal shape-similarity captures this notion.

Definition: infinitesimally shape-similar

The framework $G(\mathit{p}(t))$ is infinitesimally shape-similar if all angle-consistent trajectories only result in translations, rotations, and uniform scalings of $G(\mathit{p}(0))$.

Infinitesimal shape-similarity, as defined in Definition above, requires that all angle-consistent motions of the framework be shape-preserving, which is a property that depends on the underlying graph topology and does not hold for frameworks at large; for example, consider the frameworks of Figure 3.

Furthermore, in order for frameworks to be infinitesimally shape-similar, the angles between vertices in the framework must be defined; thus, the frameworks under consideration must have at least 3 vertices and not be degenerate. The following subsections develop analytical tools to determine whether a given framework is infinitesimally shape-similar.

Figure 3: The left framework is infinitesimally shape-similar. In contrast, the right frameworks are not infinitesimally shape-similar because, due to network topology and pathological configuration, angle-consistent motion along the dotted lines is not a translation, rotation, or uniform scaling.

Shape-Similarity Matrix

This subsection develops the shape-similarity matrix, the primary tool for investigating the infinitesimal shape-similarity of a given framework. To begin, consider angle-consistent motions of $G(\mathit{p})$. Rather than considering the time derivatives of these angles directly, the time derivatives of the cosines of these angles are shown to be zero along angle-consistent trajectories of $G(\mathit{p})$; this alternate formulation results in the same shape-similarity matrix, but avoids indeterminate forms in the derivative as discussed later.

Proposition 1:

For angles ${\theta }_{ikj}$ as described in $(1)$, ${\dot{\theta }}_{ikj}=0$ if and only if $\frac{\mathrm{d}}{\mathrm{d}t}\cos \left({\theta }_{ikj}\right)=0$.

Details of Proof

Suppose ${\dot{\theta }}_{ikj}=0$; then,

$$\begin{array}{}\text{(2)}& \frac{\mathrm{d}}{\mathrm{d}t}\cos \left({\theta }_{ikj}\right)=-\sin \left({\theta }_{ikj}\right){\dot{\theta }}_{ikj}=0.\end{array}$$

Now, suppose $\frac{\mathrm{d}}{\mathrm{d}t}\cos \left({\theta }_{ikj}\right)=0$; this implies that $\cos \left({\theta }_{ikj}\right)=c_1$, where $c_1\in [-1,1]$ is a constant. Thus, ${\theta }_{ikj}={\cos }^{-1}\left(c_1\right)=c_2$, where $c_2\in [0,\pi ]$ is a constant, so ${\dot{\theta }}_{ikj}=0$.

$◻$

By Proposition 1, the time derivatives of the cosines of the angles of an angle-consistent framework are zero. Exploiting this fact, the structure of the shape-similarity matrix is revealed by examining the time derivative of the cosine of an arbitrary angle ${\theta }_{ikj}$ along angle-consistent trajectories of $G(\mathit{p})$

$$\frac{\mathrm{d}}{\mathrm{d}t}\cos \left({\theta }_{ikj}\right)=\frac{\mathrm{d}}{\mathrm{d}t}\left(\frac{{\mathit{z}}_{ik}^{\mathrm{\top }}{\mathit{z}}_{jk}}{\Vert {\mathit{z}}_{ik}\Vert \Vert {\mathit{z}}_{jk}\Vert }\right)=\frac{\partial \cos \left({\theta }_{ikj}\right)}{\partial \mathit{p}}\dot{\mathit{p}}=0.$$

Because it depends only on ${\mathit{p}}_i,{\mathit{p}}_j$, and ${\mathit{p}}_k$, the partial derivatives of $\cos \left({\theta }_{ikj}\right)$ w.r.t. all other vertex positions are zero; thus,

$$\begin{array}{}\text{(3)}& \begin{array}{rl}\frac{\mathrm{d}}{\mathrm{d}t}\cos \left({\theta }_{ikj}\right)=& {\gamma }_{ikj}(Q_{{\mathit{z}}_{ik}}^{\mathrm{\top }}\left({\mathit{z}}_{jk}\right){\dot{\mathit{p}}}_i+Q_{{\mathit{z}}_{jk}}^{\mathrm{\top }}\left({\mathit{z}}_{ik}\right){\dot{\mathit{p}}}_j\\ & -(Q_{{\mathit{z}}_{ik}}^{\mathrm{\top }}\left({\mathit{z}}_{jk}\right)+Q_{{\mathit{z}}_{jk}}^{\mathrm{\top }}\left({\mathit{z}}_{ik}\right)){\dot{\mathit{p}}}_k)=0\end{array}\end{array}$$

where ${\gamma }_{ikj}={(\Vert {\mathit{z}}_{ik}\Vert \cdot \Vert {\mathit{z}}_{jk}\Vert )}^{-1}$, and $Q_{{\mathit{z}}_{jk}}\left({\mathit{z}}_{ik}\right)\in {\mathbb{R}}^d$ is the component of ${\mathit{z}}_{ik}$ orthogonal to ${\mathit{z}}_{jk}$ given by

$$Q_{{\mathit{z}}_{jk}}\left({\mathit{z}}_{ik}\right)=(I_d-\frac{{\mathit{z}}_{jk}{\mathit{z}}_{jk}^{\mathrm{\top }}}{{\Vert {\mathit{z}}_{jk}\Vert }^2}){\mathit{z}}_{ik}.$$

Repeating this process for all $m$ angles in $\theta (\mathit{p})$ specifying the framework of $n$ vertices, $(3)$ takes the form

$$\begin{array}{}\text{(4)}& \frac{\mathrm{d}}{\mathrm{d}t}\cos (\theta (\mathit{p}))=\mathrm{\Gamma }(\mathit{p})R_S(\mathit{p})\dot{\mathit{p}}=\mathbf{0}\end{array}$$

where:

• $\cos (\theta (\mathit{p}))$ denotes the elementwise cosine of the vector $\theta (\mathit{p})$,
• $R_S(\mathit{p})\in {\mathbb{R}}^{m\times dn}$ is the shape-similarity matrix,
• $\mathrm{\Gamma }(\mathit{p})=\mathrm{diag}(\dots ,{\gamma }_{ikj},\dots )\in {\mathbb{R}}^{m\times m}$ is a diagonal matrix of positive scalars associated with rows of $R_S(\mathit{p})$.

Each row of the expression in $(3)$ corresponds with an angle. The element ${\mathit{m}}_{aq}\in {\mathbb{R}}^{1\times d}$ of $R_S(x)$ corresponds to the component of the angle $a$ contributed by vertex $q$; if vertex $q$ is not one of the 3 vertices defining the angle $a$, then ${\mathit{m}}_{aq}=0$. For example, the shape-similarity matrix of the triangle between ${\mathit{p}}_i$, ${\mathit{p}}_j$, and ${\mathit{p}}_k$ is

$$\begin{array}{}\text{(5)}& R_S(\mathit{p})=\left[\begin{array}{ccc}{Q}_{{\mathit{z}}_{ij}}^{\mathrm{\top }}\left({\mathit{z}}_{kj}\right)& K({\mathit{z}}_{kj},{\mathit{z}}_{ij})& Q_{{\mathit{z}}_{kj}}^{\mathrm{\top }}\left({\mathit{z}}_{ij}\right)\\ K({\mathit{z}}_{ji},{\mathit{z}}_{ki})& Q_{{\mathit{z}}_{jk}}^{\mathrm{\top }}\left({\mathit{z}}_{ki}\right)& Q_{{\mathit{z}}_{ki}}^{\mathrm{\top }}\left({\mathit{z}}_{ji}\right)\\ Q_{{\mathit{z}}_{ik}}^{\mathrm{\top }}\left({\mathit{z}}_{jk}\right)& Q_{{\mathit{z}}_{jk}}^{\mathrm{\top }}\left({\mathit{z}}_{ik}\right)& K({\mathit{z}}_{ik},{\mathit{z}}_{jk})\end{array}\right],\end{array}$$

where $K({\mathit{z}}_{kj},{\mathit{z}}_{ij})=-Q_{{\mathit{z}}_{ij}}^{\mathrm{\top }}\left({\mathit{z}}_{kj}\right)-Q_{{\mathit{z}}_{kj}}^{\mathrm{\top }}\left({\mathit{z}}_{ij}\right)$. Along angle-consistent trajectories of $G(\mathit{p})$, the time derivatives of each ${\theta }_{ikj}$ can also be written using $(2)$ and $(3)$

$$\begin{array}{}\text{(6)}& \begin{array}{rl}{\dot{\theta }}_{ikj}=& {\lambda }_{ikj}(Q_{{\mathit{z}}_{ik}}^{\mathrm{\top }}\left({\mathit{z}}_{jk}\right){\dot{\mathit{p}}}_i+Q_{{\mathit{z}}_{jk}}^{\mathrm{\top }}\left({\mathit{z}}_{ik}\right){\dot{\mathit{p}}}_j\\ & -(Q_{{\mathit{z}}_{ik}}^{\mathrm{\top }}\left({\mathit{z}}_{jk}\right)+Q_{{\mathit{z}}_{jk}}^{\mathrm{\top }}\left({\mathit{z}}_{ik}\right)){\dot{\mathit{p}}}_k)=0\end{array}\end{array}$$

where ${\lambda }_{ikj}=-{\gamma }_{ikj}/\sin \left({\theta }_{ikj}\right)$. Repeated for $m$ angles along angle-consistent trajectories, $\dot{\theta }=\mathrm{\Lambda }(\mathit{p})R_S(\mathit{p})\dot{\mathit{p}}=0$, where $\mathrm{\Lambda }(\mathit{p})=\mathrm{diag}(\dots ,{\lambda }_{ikj},\dots )\in {\mathbb{R}}^{m\times m}$.

The expression in $(6)$ was originally used to develop the shape-similarity matrix. In this formulation, the behavior of ${\dot{\theta }}_{ikj}$ is unclear when ${\theta }_{ikj}$ is $0$ or $\pi$ because of the division by $\sin \left({\theta }_{ikj}\right)$, which results in an indeterminate form; in contrast, the formulation in $(3)$ does not suffer this limitation and enables the following observation.

Remark 1

Consider $(3)$; when the angle ${\theta }_{ikj}$ formed between the 3 vertices is zero or $\pi ,\frac{\mathrm{d}}{\mathrm{d}t}\cos \left({\theta }_{ikj}\right)=0$ regardless of $\dot{\mathit{p}}$. In effect, for certain configurations, all infinitesimal motions of $G(\mathit{p})$ are angle-consistent, which is significant because a framework that is infinitesimally shape-similar in one configuration may not be in another; such pathologies are discussed in the next section.

Assessing Frameworks for Infinitesimal Shape-Similarity

This subsection develops tools for assessing arbitrary frameworks for infinitesimal shape-similarity; examination of the nullspace of the shape-similarity matrix is central in this development. Consider the following theorem, which follows from the construction of the shape-similarity matrix.

Theorem 1

Infinitesimal motions $\dot{\mathit{p}}$ of the framework $G(\mathit{p})$ are angle-consistent if and only if

$$\dot{\mathit{p}}\in \mathrm{null}(R_S(\mathit{p})).$$

Details of Proof

Suppose $\dot{\mathit{p}}$ is an angle-consistent motion of $G(\mathit{p})$; by Definition of angle-consistent motions, $\dot{\theta }(\mathit{p})=\mathbf{0}$. By Proposition 1 and the construction of $R_S(\mathit{p})$, this implies that $\frac{\mathrm{d}}{\mathrm{d}t}\cos (\theta (\mathit{p}))=\mathrm{\Gamma }(\mathit{p})R_S(\mathit{p})\dot{\mathit{p}}=\mathbf{0}$, so $\dot{\mathit{p}}\in \mathrm{null}(R_S(\mathit{p}))$. Now, suppose that $\dot{\mathit{p}}\in \mathrm{null}(R_S(\mathit{p}))$; $\frac{\mathrm{d}}{\mathrm{d}t}\cos (\theta (\mathit{p}))=\mathrm{\Gamma }(\mathit{p})R_S(\mathit{p})\dot{\mathit{p}}=\mathbf{0}$, so by Proposition 1 and Definition of angle-consistent motions, $\dot{\mathit{p}}$ is an angle-consistent motion of $G(\mathit{p})$.

$◻$

From Theorem 1, $\mathrm{null}(R_S(\mathit{p}))$ characterizes the angle-consistent motions of $G(\mathit{p})$, which is particularly significant when assessing the available motions of multirobot formations under angle maintenance. By Definition, $G(\mathit{p})$ is infinitesimally shape-similar if the only $\dot{\mathit{p}}$ in $\mathrm{null}(R_S(\mathit{p}))$ are infinitesimal translations, rotations, and uniform scalings. The following presentation builds upon Theorem 1 and develops a basis for $\mathrm{null}(R_S(\mathit{p}))$ of infinitesimally shape-similar $G(\mathit{p})$. To facilitate this development, the following definition is first introduced.

Definition: oriented

The points $\mathit{p}={[{\mathit{p}}_1^{\mathrm{\top }},{\mathit{p}}_2^{\mathrm{\top }},\dots ,{\mathit{p}}_n^{\mathrm{\top }}]}^{\mathrm{\top }}\in {\mathbb{R}}^{dn}$ are oriented if the last $(d-\dim (\mathrm{aff}\{\mathit{p}\}))$ coordinates of each point are zero; i.e., if ${\mathit{p}}_i={[{\mathit{p}}_{i,1},\dots ,{\mathit{p}}_{i,p},0,\dots ,0]}^{\mathrm{\top }},\mathrm{\forall }i=1,\dots ,n$. A framework $G(\mathit{p})$ is oriented if the vertices $\mathit{p}$ are oriented.

Note that $0⩽\dim (\mathrm{aff}\{\mathit{p}\})⩽d$, so $(d-\dim (\mathrm{aff}\{\mathit{p}\}))$ may be $0$ when the dimension of the affine hull of the points is sufficiently high. For example, 3 vertices in the plane are always oriented if they are not collinear or collocated because the dimension of the affine hull of the vertices is $2$.

As demonstrated shortly, oriented frameworks facilitate examination of $\mathrm{null}(R_S(\mathit{p}))$ for the development of a basis; towards this result, denote the standard basis vectors of ${\mathbb{R}}^d$ by ${\mathit{e}}_{\alpha }\in {\mathbb{R}}^d,\alpha =1,\dots ,d$, and denote by $S_{\beta }\in {\mathbb{R}}^{d\times d},\beta =1,\dots ,(\genfrac{}{}{0ex}{}{d}{2})$, skew symmetric matrices formed by left and right multiplying the matrix $S=\left[\begin{array}{cc}0& 1\\ -1& 0\end{array}\right]$ by distinct two-combinations of the standard basis vectors; i.e.,

$$S_{\beta }\in \{\left[e_i{e}_j\right]S{\left[e_i^{\mathrm{\top }}{e}_j^{\mathrm{\top }}\right]}^{\mathrm{\top }}\mid 1⩽i<d,i<j⩽d\}.$$

The following theorem can now be stated.

Theorem 2

Let $G(\mathit{p})$ be an oriented framework and $\dim (\mathrm{aff}\{\mathit{p}\})>1;G(\mathit{p})$ is infinitesimally shape-similar if and only if a basis${}^3$ for $\mathrm{null}(R_S(\mathit{p}))$ can be formed from: ${\mathbf{1}}_n\otimes {\mathit{e}}_{\alpha },\alpha =1,\dots ,d;\mathit{p}$; and the nonzero vectors of $(I_n\otimes S_{\beta })\mathit{p}$, $\beta =1,\dots ,(\genfrac{}{}{0ex}{}{d}{2})$.

3. Using the definition of oriented frameworks, the linear independence of the basis vectors is established in the proof of Theorem 2, which facilitates the determination of the nullity of the shape-similarity matrix

::: detail Details of proof To prove Theorem 2, the proposed basis vectors are first shown to be in $\mathrm{null}(R_S(\mathit{p}))$ and linearly independent. The proof then follows from Definition of infinitesimally shape-similar and Theorem 1.

To show that each proposed basis vector lies in the nullspace of the shape-similarity matrix of $G(\mathit{p})$, examine an arbitrary row of $R_S(\mathit{p})$ as in $(3)$. An arbitrary row of $R_S(\mathit{p})$ as in $(3)$ multiplied by an arbitrary vector $(\mathbf{1}\otimes c_{\alpha }),\alpha =1,\dots ,d$, yields

$$(Q_{{\mathit{z}}_{ik}}^{\mathrm{\top }}\left({\mathit{z}}_{jk}\right)+Q_{{\mathit{z}}_{jk}}^{\mathrm{\top }}\left({\mathit{z}}_{ik}\right)-Q_{{\mathit{z}}_{ik}}^{\mathrm{\top }}\left({\mathit{z}}_{jk}\right)-Q_{{\mathit{z}}_{jk}}^{\mathrm{\top }}\left({\mathit{z}}_{ik}\right))e_{\alpha }=0;$$

thus, $(\mathbf{1}\otimes e_{\alpha })\in \mathrm{null}(R_S(\mathit{p})),\mathrm{\forall }\alpha =1,\dots ,d$. Multiplying an arbitrary row of $R_S(\mathit{p})$ by $\mathit{p}$ yields

$$Q_{{\mathit{z}}_{ik}}^{\mathrm{\top }}\left({\mathit{z}}_{jk}\right){\mathit{z}}_{ik}+Q_{{\mathit{z}}_{jk}}^{\mathrm{\top }}\left({\mathit{z}}_{ik}\right){\mathit{z}}_{jk}=0;$$

thus, $\mathit{p}\in \mathrm{null}(R_S(\mathit{p}))$. Finally, multiplying an arbitrary row of $R_S(\mathit{p})$ by an arbitrary vector of $(I_n\otimes S_{\beta })\mathit{p},\beta =1,\dots ,(\genfrac{}{}{0ex}{}{d}{2})$

$$\begin{array}{rl}& Q_{{\mathit{z}}_{ik}}^{\mathrm{\top }}\left({\mathit{z}}_{jk}\right)S_{\beta }{\mathit{z}}_{ik}+Q_{{\mathit{z}}_{jk}}^{\mathrm{\top }}\left({\mathit{z}}_{ik}\right)S_{\beta }{\mathit{z}}_{jk}\\ =& {\mathit{z}}_{jk}^{\mathrm{\top }}{S}_{\beta }{\mathit{z}}_{ik}+{\mathit{z}}_{ik}^{\mathrm{\top }}{S}_{\beta }{\mathit{z}}_{jk}=0\end{array}$$

which follows from the skew symmetric property of $S_{\beta }$; thus, $(I_n\otimes S_{\beta })\mathit{p}\in \mathrm{null}(R_S(\mathit{p})),\mathrm{\forall }\beta =1,\dots ,(\genfrac{}{}{0ex}{}{d}{2})$.

Having established that each of the proposed basis vectors lies in $\mathrm{null}(R_S(\mathit{p}))$, linear independence is now shown. Begin by considering the vectors ${\mathbf{1}}_n\otimes {\mathit{e}}_{\alpha },\alpha =1,\dots ,d$, which are mutually orthogonal because the standard basis vectors are mutually orthogonal; i.e.,

$${({\mathbf{1}}_n\otimes {\mathit{e}}_i)}^{\mathrm{\top }}({\mathbf{1}}_n\otimes {\mathit{e}}_j)={\mathit{e}}_i^{\mathrm{\top }}({\mathbf{1}}_n^{\mathrm{\top }}\otimes I_d)({\mathbf{1}}_n\otimes I_d){\mathit{e}}_j=\mathbf{0}.$$

Now consider linear independence of the vectors ${\mathbf{1}}_n\otimes {\mathit{e}}_{\alpha }$, $\alpha =1,\dots ,d$, and $\mathit{p}$. Suppose that $\mathit{p}$ is linearly dependent of the vectors ${\mathbf{1}}_n\otimes {\mathit{e}}_{\alpha },\alpha =1,\dots ,d$, then there exist nontrivial ${\zeta }_{\alpha }\in \mathbb{R},\alpha =1,\dots ,d$, such that

$$\begin{array}{}\text{(7)}& \mathit{p}=\sum _{\alpha =1}^d{\zeta }_{\alpha }({\mathbf{1}}_n\otimes {\mathit{e}}_{\alpha }).\end{array}$$

Because of the sparse structure of ${\mathbf{1}}_n\otimes {\mathit{e}}_{\alpha }$, which can affect only the $\alpha$-coordinate of each vertex, $(7)$ would require that all ${\mathit{p}}_1={\mathit{p}}_2=\dots ={\mathit{p}}_n$ and result in $\dim (\mathrm{aff}\{\mathit{p}\})=0$, contradicting the assumption that $\dim (\mathrm{aff}\{\mathit{p}\})>1$; thus, $\mathit{p}$ is linearly independent of ${\mathbf{1}}_n\otimes {\mathit{e}}_{\alpha },\mathrm{\forall }\alpha =1,\dots ,d$.

To show linear independence of $\mathit{p}$ and the vectors $(I_n\otimes S_{\beta })\mathit{p}$, $\beta =1,\dots ,(\genfrac{}{}{0ex}{}{d}{2})$, note that the matrix $I_n\otimes S_{\beta }$ is skew symmetric, so ${\mathit{p}}^{\mathrm{\top }}(I_n\otimes S_{\beta })\mathit{p}=0$, and $\mathit{p}$ is linearly independent of the vectors $(I_n\otimes S_{\beta })\mathit{p},\mathrm{\forall }\beta =1,\dots ,(\genfrac{}{}{0ex}{}{d}{2})$.

Linear independence of the vectors $(I_n\otimes S_{\beta })\mathit{p},\beta =1,\dots ,(\genfrac{}{}{0ex}{}{d}{2})$, requires examination of the effect of multiplying $\mathit{p}$ by $I_n\otimes S_{\beta }$; to do this, multiply ${\mathit{p}}_i$ by $S_{\beta }$. Such multiplication swaps two of the coordinates of ${\mathit{p}}_i$, negates one of them, and sets the rest to zero. For example, consider the following instantiation of ${\mathit{p}}_i$ and $S_{\beta }$ in ${\mathbb{R}}^3$ :

$$S_{\beta }{\mathit{p}}_i=\left[\begin{array}{ccc}0& 1& 0\\ -1& 0& 0\\ 0& 0& 0\end{array}\right]\left[\begin{array}{l}{\mathit{p}}_{i,1}\\ {\mathit{p}}_{i,2}\\ {\mathit{p}}_{i,3}\end{array}\right]=\left[\begin{array}{c}{\mathit{p}}_{2,i}\\ -{\mathit{p}}_{1,i}\\ 0\end{array}\right].$$

The Kronecker product repeats this effect for each vertex position in $\mathit{p}$. Because $\mathit{p}$ is oriented, the last $(d-\dim (\mathrm{aff}\{\mathit{p}\}))$ coordinates of each vertex position are zero, so there are exactly $(\genfrac{}{}{0ex}{}{d}{2})-(\genfrac{}{}{0ex}{}{d-\dim (\mathrm{aff}\{\mathit{p}\})}{2})$ nonzero vectors of $(I_n\otimes S_{\beta })\mathit{p},\beta =1,\dots ,(\genfrac{}{}{0ex}{}{d}{2})$; linear independence of these nonzero vectors is examined.

Suppose that some of the nonzero vectors of $(I_n\otimes S_{\beta })\mathit{p},\beta =1,\dots ,(\genfrac{}{}{0ex}{}{d}{2})$, are linearly dependent of the rest; let $q$ be the number of linearly independent vectors, and without loss of generality, order them such that the vectors $(I_n\otimes S_{\beta })\mathit{p},\beta =1,\dots ,q$, are linearly independent. There must exist nontrival ${\zeta }_{\beta }\in \mathbb{R},\beta =1,\dots ,q$, such that each linearly dependent vector, e.g., $(I_n\otimes S_{q+1})\mathit{p}$, can be written as

$$\begin{array}{}\text{(8)}& (I_n\otimes S_{q+1})\mathit{p}=\sum _{\beta =1}^q{\zeta }_{\beta }(I_n\otimes S_{\beta })\mathit{p}\end{array}$$

From the sparse structure of $I_n\otimes S_{\beta }$, no values of ${\zeta }_{\beta }$ for $\beta =1,\dots ,q$ can satisfy $(8)$, and the expression in $(8)$ holds only for ${\mathit{p}}_1={\mathit{p}}_2=\dots ={\mathit{p}}_n$, which contradicts the assumption that $\dim (\mathrm{aff}\{\mathit{p}\})>1$; thus, the nonzero vectors of $(I_n\otimes S_{\beta })\mathit{p}$, $\beta =1,\dots ,(\genfrac{}{}{0ex}{}{d}{2})$, are linearly independent.

Now, consider linear independence of the vectors ${\mathbf{1}}_n\otimes e_{\alpha }$, $\alpha =1,\dots ,d$, and the nonzero vectors of $(I_n\otimes S_{\beta })\mathit{p}$, $\beta =1,\dots ,(\genfrac{}{}{0ex}{}{d}{2})$. Choose an arbitrary $(I_n\otimes S_{\beta })\mathit{p}$ and suppose that it is linearly dependent of ${\mathbf{1}}_n\otimes {\mathit{e}}_{\alpha },\alpha =1,\dots ,d$, then there exists nontrivial ${\zeta }_{\alpha }$ such that

$$\begin{array}{}\text{(9)}& (I_n\otimes S_{\beta })\mathit{p}=\sum _{\alpha =1}^d{\zeta }_{\alpha }(I_n\otimes {\mathit{e}}_{\alpha })\end{array}$$

Because of the sparse structure of $I_n\otimes e_{\alpha }$, which affects only the $\alpha$-coordinates of all of the vertices, $(9)$ implies that ${\mathit{p}}_1={\mathit{p}}_2=\dots ={\mathit{p}}_n$, contradicting the assumption that $\dim (\mathrm{aff}\{\mathit{p}\})>1$. Thus, ${\mathbf{1}}_n\otimes e_{\alpha },\alpha =1,\dots ,d$, and nonzero $(I_n\otimes S_{\beta })\mathit{p},\beta =1,\dots ,(\genfrac{}{}{0ex}{}{d}{2})$, are linearly independent.

Having demonstrated linear independence of the basis vectors in Theorem 2, the proof can be completed.

• The vectors ${\mathbf{1}}_n\otimes e_{\alpha },\alpha =1,\dots ,d$ correspond with translations;
• The vector $\mathit{p}$ corresponds with uniform scaling;
• The nonzero vectors $(I_n\otimes S_{\beta })\mathit{p},\beta =1,\dots ,(\genfrac{}{}{0ex}{}{d}{2})$, correspond with rotations.

By Definition of infinitesimally shape-similar, if $G(\mathit{p})$ is infinitesimally shape-similar, then by Theorem 1 , the only vectors in $\mathrm{null}(R_S(\mathit{p}))$ result in infinitesimal translations, rotations, and uniform scalings, so the vectors of Theorem 2 form a basis for $\mathrm{null}(R_S(\mathit{p}))$. The converse follows from Theorem 1; vectors in $\mathrm{null}(R_S(\mathit{p}))$ are angle-consistent motions of the framework. If the vectors of Theorem 2 form a basis for $\mathrm{null}(R_S(\mathit{p}))$, then the only angle-consistent motions of $G(\mathit{p})$ are infinitesimal translation, rotation, and uniform scaling, so $G(\mathit{p})$ is infinitesimally shape-similar by the related definition.

$◻$

:::

Having found a basis for the nullspace of the shape-similarity matrix of oriented frameworks, the following statements complete the analysis by first proving the existence of isometries that orient arbitrary frameworks and then proving invariance of $\mathrm{null}(R_S(\mathit{p}))$ to such transformations.

Proposition 2

Let $\mathit{p}={[{\mathit{p}}_1^{\mathrm{\top }},{\mathit{p}}_2^{\mathrm{\top }},\dots ,{\mathit{p}}_n^{\mathrm{\top }}]}^{\mathrm{\top }}\in {\mathbb{R}}^{dn}$. There exists an isometry $T:{\mathbb{R}}^d\to {\mathbb{R}}^d$ such that $\overline{\mathit{p}}={[T{\left({\mathit{p}}_1\right)}^{\mathrm{\top }},T{\left({\mathit{p}}_2\right)}^{\mathrm{\top }},\dots ,T{\left({\mathit{p}}_n\right)}^{\mathrm{\top }}]}^{\mathrm{\top }}$ is oriented.

Details of Proof

By construction, $\dim (\mathrm{aff}\{\mathit{p}\})=\dim (\mathrm{aff}\{\overline{\mathit{p}}\})$. By definition and Lemma 1, there exists an isometric transformation $T$ such that aff $\{\overline{\mathit{p}}\}=T(\mathrm{aff}\{\mathit{p}\})$, which satisfies $\overline{\mathit{p}}={[T{\left({\mathit{p}}_1\right)}^{\mathrm{\top }},T{\left({\mathit{p}}_2\right)}^{\mathrm{\top }},\dots ,T{\left({\mathit{p}}_n\right)}^{\mathrm{\top }}]}^{\mathrm{\top }}$.

$◻$

As an example for Definition of oriented and Proposition 2, consider a framework of 2 vertices in the plane; by Proposition 2, an isometry exists that translates and rotates the vertices such that they are oriented along the horizontal axis.

Lemma 2

The nullspace of the shape-similarity matrix is invariant to isometric transformations.

Details of Proof

Let $T:{\mathbb{R}}^d\to {\mathbb{R}}^d$ be an isometric transformation; thus, for a point ${\mathit{p}}_i\in {\mathbb{R}}^d,T\left({\mathit{p}}_i\right)=M{\mathit{p}}_i+c$, where $c\in {\mathbb{R}}^d$ is a translation and $M\in {\mathbb{R}}^{d\times d}$ is an orthogonal matrix. Consider an arbitrary angle in a framework $G(\mathit{p})$ formed between the transformed vertices $T\left({\mathit{p}}_i\right),T\left({\mathit{p}}_k\right)$, and $T\left({\mathit{p}}_j\right)$ as in $(1)$, and verify that it is invariant under the isometry

$$\begin{array}{rl}\cos \left({\theta }_{ikj}\right)& =\frac{{(T\left({\mathit{p}}_i\right)-T\left({\mathit{p}}_k\right))}^{\mathrm{\top }}(T\left({\mathit{p}}_j\right)-T\left({\mathit{p}}_k\right))}{\Vert T\left({\mathit{p}}_i\right)-T\left({\mathit{p}}_k\right)\Vert \Vert T\left({\mathit{p}}_j\right)-T\left({\mathit{p}}_k\right)\Vert }\\ & =\frac{{({\mathit{p}}_i-{\mathit{p}}_k)}^{\mathrm{\top }}{M}^{\mathrm{\top }}M({\mathit{p}}_j-{\mathit{p}}_k)}{\Vert M{\mathit{p}}_i-M{\mathit{p}}_k\Vert \Vert M{\mathit{p}}_j-M{\mathit{p}}_k\Vert }\\ & =\frac{{({\mathit{p}}_i-{\mathit{p}}_k)}^{\mathrm{\top }}({\mathit{p}}_j-{\mathit{p}}_k)}{\Vert {\mathit{p}}_i-{\mathit{p}}_k\Vert \Vert {\mathit{p}}_j-{\mathit{p}}_k\Vert }\end{array}$$

Thus, the time derivative $\frac{\mathrm{d}}{\mathrm{d}t}\cos \left({\theta }_{ikj}\right)$ is invariant under the isometric transformation, so the shape-similarity matrix and its nullspace are invariant to isometric transformations.

$◻$

Proposition 2 and Lemma 2 support the following corollary.

Corollary of Theorem 2

Let $G(\mathit{p})$ be a framework where $\dim (\mathrm{aff}\{\mathit{p}\})>1$, and denote the corresponding oriented framework by $G(\overline{\mathit{p}})$. The basis vectors in Theorem 2 for $\mathrm{null}(R_S(\overline{\mathit{p}}))$ are basis vectors for $\mathrm{null}(R_S(\mathit{p}))$.

Details of Proof

By Proposition 2, there exists an isometric transformation between $\mathit{p}$ and $\overline{\mathit{p}}$, and by Lemma 2, $\mathrm{null}(R_S(\mathit{p}))=\mathrm{null}(R_S(\overline{\mathit{p}}))$ and, thus, share the basis vectors of Theorem 2.

$◻$

The results in Theorem 1 and Corrollary of Theorem 2 facilitate understanding of the available motions of multirobot teams maintaining angles and underpin the design of the formation-control strategies of Section V TODO; furthermore, these results yield a rank condition for evaluating frameworks for infinitesimal shapesimilarity.

Theorem 3

The framework $G(\mathit{p})$ is infinitesimally shape-similar if and only if

$$\begin{array}{}\text{(10)}& \begin{array}{rl}& \mathrm{rank}(R_S(\mathit{p}))\\ =& dn+\frac{1}{2}\dim (\mathrm{aff}\{\mathit{p}\})(\dim (\mathrm{aff}\{\mathit{p}\})+1)-d(\dim (\mathrm{aff}\{\mathit{p}\})+1)-1.\end{array}\end{array}$$

Details of Proof

The necessary and sufficient condition of Theorem 3 is proved for 3 cases of the dimension of the affine hull of the vertices of the framework.

1. Let $G(\mathit{p})$ be a framework with $\dim (\mathrm{aff}\{\mathit{p}\})=0$. Such a framework is degenerate; it is not infinitesimally shape-similar, and the shape-similarity matrix, and thus the rank of the shape-similarity matrix, is undefined and does not satisfy $(10)$.
2. Let $G(\mathit{p})$ be a framework with $\dim (\mathrm{aff}\{\mathit{p}\})=1$; the corresponding shape-similarity matrix is a matrix of zeros. By Theorem 1, all infinitesimal motions of the framework are angle-consistent, so $G(\mathit{p})$ is not infinitesimally shape-similar; furthermore, $\mathrm{rank}(R_S(\mathit{p}))=0$ and does not satisfy $(10)$.
3. Consider frameworks $G(\mathit{p})$ with $\dim (\mathrm{aff}\{\mathit{p}\})>1$. The nullity of the shape-similarity matrix is the number of basis vectors for $\mathrm{null}(R_S(\mathit{p}))$. Theorem 2 and Corrollary of Theorem 2 present such a basis, and as a direct result, a framework $G(\mathit{p})$ is infinitesimally shape-similar if and only if

$$\dim \left(\mathrm{null}(R_S(\mathit{p}))\right)=-\frac{1}{2}\dim (\mathrm{aff}\{\mathit{p}\})(\dim (\mathrm{aff}\{\mathit{p}\})+1)+d(\dim (\mathrm{aff}\{\mathit{p}\})+1)+1,$$

where from the proof of Theorem 2, and the extension to unoriented frameworks in Corrollary 2.1, there are $d$ basis vectors for translations, one basis vector for uniform scaling, and $(\genfrac{}{}{0ex}{}{d}{2})-(\genfrac{}{}{0ex}{}{d-\dim (\mathrm{aff}\{\mathit{p}\})}{2})$ basis vectors for rotations. The rank condition in $(10)$ follows from the necessary and sufficient condition on the nullity of the shape-similarity matrix in Theorem 2.

$◻$

The following corollary to Theorem 3 is presented for frameworks whose affine hull has sufficient dimension.

Corollary of Theorem 3

Let $G(\mathit{p})$ be a framework with

$$\dim (\mathrm{aff}\{\mathit{p}\})=\underset{\mathit{p}\in {\mathbb{R}}^{dn}}{max}[\dim (\mathrm{aff}\{\mathit{p}\})].$$

$G(\mathit{p})$ is infinitesimally shape-similar if and only if

$$\mathrm{rank}(R_S(\mathit{p}))=\{\begin{array}{ll}dn-\frac{1}{2}d(d+1)-1,& n⩾d\\ \frac{1}{2}(n-2)(n+1),& n<d\end{array}.$$

Details of Proof

The rank condition in $(10)$ can be conditioned on the relative values of $n$ and $d$. First, suppose $n>d;\underset{\mathit{p}\in {\mathbb{R}}^{dn}}{max}[\dim (\mathrm{aff}\{\mathit{p}\})]=d$, for which $(10)$ reduces to $\mathrm{rank}(R_S(\mathit{p}))=dn-\frac{1}{2}d(d+1)-1$. Similarly, for $n=d$, $p=\underset{\mathit{p}\in {\mathbb{R}}^{dn}}{max}[\dim (\mathrm{aff}\{\mathit{p}\})]=d-1$, and the rank condition reduces to $\mathrm{rank}(R_S(\mathit{p}))=dn-\frac{1}{2}d(d+1)-1$. Finally, for $n<d,p=\underset{\mathit{p}\in {\mathbb{R}}^{dn}}{max}[\dim (\mathrm{aff}\{\mathit{p}\})]=n-1$, in which case, $\mathrm{rank}(R_S(\mathit{p}))=\frac{1}{2}(n-2)(n+1)$.

$◻$

The rank conditions in Theorem 3 and Corollary of Theorem 3 are important tools when analyzing frameworks for infinitesimal shape-similarity, which will be demonstrated in Section: Triangulations where the rank of the shape-similarity matrix is examined explicitly to evaluate a class of frameworks for use in formation control. Beyond their utility in this example, the rank conditions enable further understanding of the significance of the framework embedding. As suggested in Remark 1, the particular embedding of $\mathit{p}$ has a fundamental effect on the infinitesimal shape-similarity of $G(\mathit{p})$; the following definition characterizes frameworks for which the rank of the shape-similarity matrix does not attain its maximum over all embeddings.

Definition: pathological

A framework $G(\mathit{p})$ is pathological ${}^4$ if

$$\mathrm{rank}(R_S(\mathit{p}))<\underset{\mathit{p}\in {\mathbb{R}}^{dn}}{max}\left[\mathrm{rank}(R_S(\mathit{p}))\right]$$

and nonpathological otherwise.

4. pathological defined in other research described frameworks for which any vertices were collocated or collinear, while its definition here is defined in terms of the rank of the shape-similarity matrix and describes frameworks that do not achieve infinitesimal shape-similarity due to the particular configuration of the vertices.

As a canonical example, a framework of collinear vertices, such as that shown in Figure 3, is pathological because its shapesimilarity is a matrix of zeros as noted in the proof of Theorem 3. The following result follows from Definition of pathological.

Theorem 4

If $G(\mathit{p})$ is a pathological framework, then it is not infinitesimally shape-similar.

of Proof

If $G(\mathit{p})$ is a pathological framework, then by Definition of pathological, $\mathrm{rank}(R_S(\mathit{p}))<\underset{\mathit{p}\in {\mathbb{R}}^{dn}}{max}\left[\mathrm{rank}(R_S(\mathit{p}))\right]$. For any $G(\mathit{p})$, $\underset{\mathit{p}\in {\mathbb{R}}^{\mathrm{dn}}}{max}\left[\mathrm{rank}(R_S(\mathit{p}))\right]⩽dn+\dim (\mathrm{aff}\{\mathit{p}\})(\dim (\mathrm{aff}\{\mathit{p}\})+1)/2-d(\dim (\mathrm{aff}\{\mathit{p}\})+1)-1$, with equality if and only if $G(\mathit{p})$ is infinitesimally shape-similar by Theorem 3. Because

$$\mathrm{rank}(R_S(\mathit{p}))<dn+\dim (\mathrm{aff}\{\mathit{p}\})(\dim (\mathrm{aff}\{\mathit{p}\})+1)/2-d(\dim (\mathrm{aff}\{\mathit{p}\})+1)-1$$

$G(\mathit{p})$ is not infinitesimally shape-similar.

$◻$

Remark 2

Assessing frameworks $G(\mathit{p})$ for infinitesimal shape-similarity highlights the importance of both the network topology described by $\mathcal{G}$ and the embedding $\mathit{p}$. Notably, the topology qualifies $G(\mathit{p})$ for infinitesimal shape-similarity, and the embedding determines whether $G(\mathit{p})$ is infinitesimally shape-similar. Relating Theorem 3 and Theorem 4, pathological frameworks with insufficient affine hull dimension do not satisfy the rank condition; for example, a fully connected framework of four vertices in ${\mathbb{R}}^5$ having $\dim (\mathrm{aff}\{\mathit{p}\})=2$ is pathological with $\mathrm{rank}(R_S(\mathit{p}))=4$, but is infinitesimally shape-similar with $\mathrm{rank}(R_S(\mathit{p}))=5$ when embedded such that $\dim (\mathrm{aff}\{\mathit{p}\})=3$. Remarkably, in ${\mathbb{R}}^2$ and ${\mathbb{R}}^3$, the spaces of most interest for robot teams, the rank condition of Corollary of Theorem 3 always evaluates to the first case, and such frameworks are pathological only if the vertices are collinear.

A Class of Infinitesimally Shape-Similar Frameworks: Triangulations

Previously, infinitesimal shape-similarity was introduced to characterize the motions available to teams of robots in which angles in the formation are maintained. To demonstrate the significance of this development in the context of multirobot formations, this section examines triangulations, a structured class of planar frameworks.

• Beginning in Section: Defining Triangulations, triangulations are precisely defined.
• In Section: Triangulations are infinitesimally Shape-Similar, triangulations are shown to be infinitesimally shape-similar.
• Finally, Section: Class of Triangulations describes a mechanism for generating a class of triangulations.

Defining Triangulations

This subsection precisely defines triangulations, the frameworks of interest to this work.

Definition: near-triangulation $(1^{\text{st}})$

A near-triangulation is a plane graph all of whose inner faces have degree $3$.

Definition: near-triangulation $(2^{\text{nd}})$

A triangulation is a near-triangulation whose outer face is a cycle. ${}^5$

5. An equivalent definition for triangulated disks is: the outer face is a cycle if the edges and vertices on the outer face form a cycle.

The $2^{\text{nd}}$ Definition of near-triangulation, which captures the features of the class of frameworks of interest, differs from other definitions of the term triangulation. For example, in the past research, triangulations refer to maximal planar graphs, which are plane graphs whose faces have degree $3$. The choice to define triangulations as in the $2^{\text{nd}}$ Definition of near-triangulation was made to improve clarity in the terminology of this work.

Relating the $2^{\text{nd}}$ Definition of near-triangulation to the results presented in Section: Infinitesimally Shape-Similarity, triangulations are planar objects; these frameworks are embedded in the plane with $\mathit{p}\in {\mathbb{R}}^{2n}$. Furthermore, as a consequence of the $2^{\text{nd}}$ Definition of near-triangulation, triangulations are nondegenerate and nonpathological.

Triangulations are Infinitesimally Shape-Similar

Having defined triangulations, this section justifies interest in this class of frameworks by showing that triangulations are infinitesimally shape-similar. To begin, consider the following theorem pertaining to the complete framework $G^{\kappa }(\mathit{p})$.

Theorem 5

If the complete framework $G^{\kappa }(\mathit{p})$ with $n⩾3$ vertices is nonpathological and nondegenerate, then it is infinitesimally shape-similar. ${}^6$

6. Theorem 5 and its proof reflect changes to the definition of pathological frameworks.

Details of Proof

If the complete framework $G^{\kappa }(\mathit{p})$ with $n⩾3$ vertices is nonpathological and nondegenerate, then the corresponding shape-similarity matrix $R_S(\mathit{p})$ satisfies

$$\mathrm{rank}(R_S(\mathit{p}))=\underset{\mathit{p}\in {\mathbb{R}}^{dn}}{max}\left[\mathrm{rank}(R_S(\mathit{p}))\right].$$

Because the complete graph contains all edges, and thus all angles, the rank of the shape-similarity matrix of the complete framework satisfies

$$\mathrm{rank}(R_S(\mathit{p}))=\underset{\mathcal{E}}{max}\left[\underset{\mathit{p}\in {\mathbb{R}}^{dn}}{max}\left[\mathrm{rank}(R_S(\mathit{p}))\right]\right]$$

and equals the rank condition in $(10)$, so by Theorem 3, $G^{\kappa }(\mathit{p})$ is infinitesimally shape-similar.

$◻$

Note that the triangle is both a triangulation and a complete framework, so by Theorem 5, it is infinitesimally shape-similar; using this fact, the result in Theorem 6 follows by induction.

Theorem 6

Triangulations are infinitesimally shape-similar. ${}^7$

7. It's proved that triangulated frameworks are infinitesimally shapesimilar. Theorem 6 and its proof reflect clarifications to the definitions of triangulations and pathology; furthermore, the proof is restructured to emphasize the edge additions that do not increase the rank of the shape-similarity matrix.

Details of Proof

The theorem is proved by induction, and for the purpose of this proof, $G\left({\mathit{p}}^k\right)$ refers to a triangulation of $k$ vertices; the corresponding shape-similarity matrix is $R_S\left({\mathit{p}}^k\right)$.

Consider the triangulation $G\left({\mathit{p}}^3\right)$, which, by Theorem 5, is infinitesimally shape-similar with $\mathrm{rank}\left(R_S\left({\mathit{p}}^3\right)\right)=2$. Suppose $G\left({\mathit{p}}^{k-1}\right)$ is an infinitesimally shape-similar triangulation with $m$ angles. Connect $x_k$ to adjacent vertices $x_i$ and $x_j$ on the outer face by two edges (Figure 4, left). The triangulation is $G\left({\mathit{p}}^k\right)$, whose shape-similarity matrix can be written as

$$R_S\left({\mathit{p}}^k\right)=\left[\begin{array}{cc}{R}_S\left({\mathit{p}}^{k-1}\right)& 0\\ A\left({\mathit{p}}^k\right)& B\left({\mathit{p}}^k\right)\end{array}\right],$$

where $R_S\left({\mathit{p}}^{k-1}\right)\in {\mathbb{R}}^{m\times 2(k-1)},A\left({\mathit{p}}^k\right)\in {\mathbb{R}}^{q\times 2(k-1)},B\left({\mathit{p}}^k\right)\in {\mathbb{R}}^{q\times 2}$, and $q$ is the number of new angles formed by the vertex/edge-addition. The matrix $A\left({\mathit{p}}^k\right)$ is composed of orthogonal projections of vectors including $x_k$ onto vectors not including $x_k$, and $B\left({\mathit{p}}^k\right)$ is formed of orthogonal projections onto vectors including $x_k$.

Consider the reduced shape-similarity matrix ${\overline{R}}_S\left({\mathit{p}}^k\right)$ of $G\left({\mathit{p}}^k\right)$ formed by considering only the three angles of the new triangle created by the vertex/edge-addition rather than the $q$ new angles (Figure 4, center), which can be written as

$${\overline{R}}_S\left({\mathit{p}}^k\right)=\left[\begin{array}{cc}{R}_S\left({\mathit{p}}^{k-1}\right)& 0\\ \overline{A}({\mathit{p}}_i,{\mathit{p}}_j,{\mathit{p}}_k)& \overline{B}({\mathit{p}}_i,{\mathit{p}}_j,{\mathit{p}}_k)\end{array}\right]$$

where $\overline{A}({\mathit{p}}_i,{\mathit{p}}_j,{\mathit{p}}_k)$ and $\overline{B}({\mathit{p}}_i,{\mathit{p}}_j,{\mathit{p}}_k)$ are the rows of $A\left({\mathit{p}}^k\right)$ and $B\left({\mathit{p}}^k\right)$ corresponding with the three angles of the new triangle. Because ${\overline{R}}_S\left({\mathit{p}}^k\right)$ has $q-3$ fewer rows than $R_S\left({\mathit{p}}^k\right)$, $\mathrm{rank}\left({\overline{R}}_S\left({\mathit{p}}^k\right)\right)⩽\mathrm{rank}\left(R_S\left({\mathit{p}}^k\right)\right)⩽2k-4$.

Replacing $\overline{A}({\mathit{p}}_i,{\mathit{p}}_j,{\mathit{p}}_k)$ with zeros yields the block diagonal matrix ${\hat{R}}_S\left({\mathit{p}}^k\right)$, which is related to $R_S\left({\mathit{p}}^k\right)$ through the rank relationship: $\mathrm{rank}\left({\hat{R}}_S\left({\mathit{p}}^k\right)\right)⩽\mathrm{rank}\left(R_S\left({\mathit{p}}^k\right)\right)$.

From the construction of the shape-similarity matrix,

$$B({\mathit{p}}_i,{\mathit{p}}_j,{\mathit{p}}_k)=\left[\begin{array}{c}-Q_{{\mathit{z}}_{ik}}^{\mathrm{\top }}\left({\mathit{z}}_{jk}\right)-Q_{{\mathit{z}}_{jk}}^{\mathrm{\top }}\left({\mathit{z}}_{ik}\right)\\ Q_{{\mathit{z}}_{kj}}^{\mathrm{\top }}\left({\mathit{z}}_{ji}\right)\\ Q_{{\mathit{z}}_{ki}}^{\mathrm{\top }}\left({\mathit{z}}_{ij}\right)\end{array}\right]$$

The rank of $B({\mathit{p}}_i,{\mathit{p}}_j,{\mathit{p}}_k)$ is at most $2$. If the last two rows of $B({\mathit{p}}_i,{\mathit{p}}_j,{\mathit{p}}_k)$ were linearly dependent then there would exist a nonzero $\alpha \in \mathbf{R}$ such that $\alpha Q_{{\mathit{z}}_{kj}}\left({\mathit{z}}_{ji}\right)=Q_{{\mathit{z}}_{ki}}\left({\mathit{z}}_{ij}\right)$, which rewritten as $-\alpha Q_{{\mathit{z}}_{kj}}\left({\mathit{z}}_{ij}\right)=Q_{{\mathit{z}}_{kt}}\left({\mathit{z}}_{ij}\right)$, can be expanded to

$$-\alpha (I_2-\frac{{\mathit{z}}_{kj}{\mathit{z}}_{kj}^{\mathrm{\top }}}{{\Vert {\mathit{z}}_{kj}\Vert }^2}){\mathit{z}}_{ij}=(I_2-\frac{{\mathit{z}}_{ki}{\mathit{z}}_{ki}^{\mathrm{\top }}}{{\Vert {\mathit{z}}_{ki}\Vert }^2}){\mathit{z}}_{ij}.$$

Such an $\alpha$ would require that ${\mathit{z}}_{ki}$ be parallel with ${\mathit{z}}_{kj}$, contradicting the fact that $G\left({\mathit{p}}^k\right)$ is a triangulation. Thus $\mathrm{rank}\left(B({\mathit{p}}_i,{\mathit{p}}_j,{\mathit{p}}_k)\right)=2$, and ${\hat{R}}_S\left({\mathit{p}}^k\right)$ is block diagonal:

$$\begin{array}{rl}\mathrm{rank}\left({\hat{R}}_S\left({\mathit{p}}^k\right)\right)& =\mathrm{rank}\left(R_S\left({\mathit{p}}^{k-1}\right)\right)+\mathrm{rank}\left(B({\mathit{p}}_i,{\mathit{p}}_j,{\mathit{p}}_k)\right)\\ & =2k-4\end{array}$$

Because $\mathrm{rank}\left({\hat{R}}_S\left({\mathit{p}}^k\right)\right)⩽\mathrm{rank}\left(R_S\left({\mathit{p}}^k\right)\right),R_S\left({\mathit{p}}^k\right)$ satisfies the rank condition in $(10)$ for infinitesimal shape-similarity.

To complete the proof, consider additional edges that could be added to $G\left({\mathit{p}}^k\right)$ such that the resulting framework is still a triangulation (Figure 4, right). Denote the shape-similarity matrix resulting from these edge-additions by ${\overline{R}}_S\left({\mathit{p}}^k\right)$. The edge-additions produce angles, so ${\overline{R}}_S\left({\mathit{p}}^k\right)$ has more rows than $R_S\left({\mathit{p}}^k\right)$. Accordingly,

$$2k-4=\mathrm{rank}\left(R_S\left({\mathit{p}}^k\right)\right)⩽\mathrm{rank}\left({\overline{R}}_S\left({\mathit{p}}^k\right)\right)⩽2k-4$$

so any edge-additions between vertices in the triangulation do not affect the rank, which was already at its maximum. By induction, triangulations are infinitesimally shape-similar.

$◻$

Figure 4: Angles produced by vertex/edge-addition to aid in visualization of the proof of Theorem 6. The left image shows the angles produced by the addition of x_k(p_k in the content), the center image shows the reduced set of angles, and the right image shows the angles resulting from edge-addition.

Remark 3

The proof of Theorem 6 highlights the importance of the underlying repeated structure of triangulations. In the proof, each additional triangle created through vertex/edge addition increases the rank of the shape-similarity matrix of the triangulation by exactly $2$. Applied to control strategies for mobile robot formations described by triangulations, the proof of Theorem 6 suggests an approach in which one robot maintains $2$ angles for each triangular face; Section: Preliminaries pursues this approach. The proof highlights the importance of the underlying repeated structure of triangulations. In the proof, each additional triangle created through vertex/edge addition increases the rank of the shape-similarity matrix of the triangulation by exactly $2$; this observation can be leveraged when controlling formations of mobile robots described by triangulations by requiring that one robot for each triangular face maintain $2$ angles of that triangle.

A Class of Triangulations

Having established that all triangulations are infinitesimally shape-similar, this section highlights maximally outerplane graphs, a class of triangulations amenable to formation control by multirobot teams in the plane as described in Remark 3.

Definition: maximally outerplane graph

A maximally outerplane graph is a simple plane graph (a plane graph for which there are no parallel edges or loops) for which any edge addition results in a graph which is not an outerplane graph.

Figure 5: Relationship between near-triangulations, triangulations, and maximally outerplane graphs. Triangulations are near-triangulations whose outer face is a cycle; maximally outerplane graphs are triangulations for which the weak dual graph is a tree.

Figure 5 distinguishes maximally outerplane graphs from the broader class of triangulations. Maximally outerplane graphs with at least 3 vertices are triangulations as in the $2^{\text{nd}}$ Definition of near-triangulations, so they are infinitesimally shape-similar. Furthermore, the weak dual graph of a maximally outerplane graph is a tree; this is related to the observation of Remark 3.

To construct maximally outerplane graphs, define the graph grammar $\mathrm{\Phi }=\left\{r_1\right\}$ consisting of the rule defined in Figure 6. Vertices are labeled by their degrees, denoted $d_i$ for $i=1,\dots ,n$. Edges are labeled as $\sigma$ when they are on the outer face of the plane graph, or $\iota$ when it is not; $r_1$ connects a disconnected vertex to two vertices across a $\sigma$ edge.

Figure 6: The rule r_1 connects disconnected vertices across adjacent vertices on the outer face of a maximally outerplane graph.

Theorem 7

Let ${\mathcal{G}}_0$ be an initial plane graph consisting of $n$ vertices in which three vertices form a triangle and the rest are disconnected. Let $g_0=({\mathcal{G}}_0,\nu ,\xi )$ be an initial labeled graph where vertex $i$ is labeled $d_i$, the degree of vertex $i$, and the three edges are labeled $\sigma$. Let $\mathrm{\Phi }=\left\{r_1\right\}$ be the graph grammar, where $r_1$ is defined ${}^{14}$ as in Figure 6. For the system $(g_0,\mathrm{\Phi })$, the graphs ${\mathcal{G}}_k\in {\left\{g_k\right\}}_{k=0}^n$ have a single connected component, which is a maximally outerplane graph.

Details of Proof

The theorem will be proved by induction. The connected component of the initial plane graph ${\mathcal{G}}_0$ is a maximally outerplane graph. Consider ${\mathcal{G}}_k\in {\left\{g_k\right\}}_{k=0}^n$ for arbitrary $k<n$. By assumption, the single connected component of ${\mathcal{G}}_k$ is a maximally outerplane graph.

Apply $r_1$ to ${\mathcal{G}}_k$. The graph grammar $\mathrm{\Phi }=\left\{r_1\right\}$ connects a zero degree vertex to two adjacent vertices connected by a $\sigma$ edge on the outer face. Applying $r_1$ results in the maximally outer plane graph ${\mathcal{G}}_{k+1}$ because the new vertex can always be placed in the outer face of ${\mathcal{G}}_k$ such that the new vertex is on the boundary of the outer face, no vertex is removed from the boundary of the outer face, the two new edges intersect other edges only at the vertices, and ${\mathcal{G}}_k$ is edge maximal. By induction, the connected component of ${\mathcal{G}}_k\in {\left\{g_k\right\}}_{k=0}^n$ is a maximally outerplane graph.

$◻$

Remark 4

Numerous methods can be employed to produce triangulations:

• using embedded graph grammars;
• Delaunay triangulation of a set of points; etc.

Similarly, there are various procedures for generating maximally outerplane graphs; e.g., ear clipping of certain polygons produces maximally outerplane graphs. The graph grammar $\mathrm{\Phi }=\left\{r_1\right\}$ is notable because of the implicit role of the weak dual of the maximally outerplane graph and its relationship to the proof of Theorem 6, in which triangular faces are incorporated along the weak dual; this structure is exploited in the Section V-B TODO when controlling mobile robot formations described by maximally outerplane graphs.

References

1. Infinitesimal Shape-Similarity for Characterization and Control of Bearing-Only Multirobot Formations, IEEE, by Ian Buckley and Magnus Egerstedt in TRO.