网络化系统中的图形状唯一性与角度刚性理论

Shape Uniqueness and Angle Rigidity Theory of Graphs in Networked Systems

摘要

由点与边构成的图形能否通过其内在约束唯一确定形状，对网络化系统协同任务的实现具有重要意义。近年来，作为研究该问题的理论工具，图刚性理论得到了迅速发展。其中，基于角度约束的图刚性理论在工程领域具有广泛适用性，已成为刚性理论的重要分支。论文系统梳理了图的角度刚性理论相关研究进展。首先，从无符号角约束与符号角约束两个方面，分别综述了国内外学者近年来的代表性成果；在此基础上，进一步探讨了角度刚性理论与矩阵补全理论之间的内在联系。最后，总结了该领域现存的开放性问题及未来发展方向，可为基于角度约束的网络化系统协同控制与优化研究提供参考。

Abstract

The ability of a graph embedded in Euclidean space to uniquely determine its global geometric shape through local constraints among nodes and edges is critical for the coordination of networked systems，including sensor network localization and multi-agent formation control. Recently， graph rigidity theory has rapidly evolved as a theoretical tool for addressing this issue. In particular， angle-based rigidity theories have emerged as a significant branch of rigidity theory due to their extensive applicability in engineering. This paper systematically reviews recent advancements in angle-based rigidity theories and their implications for shape uniqueness. This study provides a detailed discussion of rigidity theories based on both unsigned and signed angle constraints. Furthermore， it explores the intrinsic connections between angle-based rigidity theories and matrix completion theory. Finally，it summarizes existing open problems in this field and outlines future research directions， which may inform studies on coordination control and optimization in networked systems based on angle constraints.

Graphical abstract

关键词

图刚性理论 / 角度刚性理论 / 网络化系统 / 刚性编队控制 / 传感器网络定位

Key words

graph rigidity theory / angle rigidity theory / networked systems / rigid formation control / sensor network localization

在网络化系统协同问题中，由网络节点及节点间相互感知关系构成的拓扑图形，其形状唯一性（图1）对协同任务的可实现性具有关键影响^［1-2］。以分布式传感器网络定位场景为例^［3］，网络节点通常处于信息受限环境^［4］，单个节点仅可获取邻接节点间的距离^［5］、距离比值^［6］、方位信息^［7-8］ 与角度信息^［9-11］等局部测量数据，通过与邻接节点的分布式信息交互，完成自身位置状态估计。若网络构型，即由传感器空间位置与相互感知关系共同构成的拓扑结构，无法在局部约束条件下实现唯一确定（图2），则定位问题会出现多解现象。同理，在分布式多智能体编队控制任务中，当局部约束不足以唯一约束期望编队构型时，智能体集群易收敛至非目标队形^［12-16］。因此，围绕距离、方位、角度等典型局部约束，开展拓扑图形形状唯一性的理论分析，是网络化协同系统研究的核心关键。

探究由顶点与连杆构成的框架系统在外部扰动下的响应特征，是刚性理论研究的核心内容。早在1776年，欧拉便对该问题开展研究^［17］，并提出了猜想：在距离约束下，多面体结构具有形状唯一性，仅允许发生由平移与旋转构成的平凡形变。1813年，柯西（Cauchy）关注到这一猜想，并在凸多面体的假设条件下完成了证明^［18］。值得注意的是，在引入距离刚性函数，系统建立基于距离约束的图刚性理论后，文献［19］揭示了一项重要结论——连杆系统的刚性特性主要由其拓扑结构决定，而非顶点的位置配置。受此启发，文献［20］进一步证明了拉曼图是二维无穷小距离刚性的图条件，即对于几乎所有二维顶点位置配置，拉曼图均满足无穷小距离刚性。目前，距离刚性理论的分析范畴已从几何系统拓展至物理结构，并对力学、机器人学等学科领域产生了重要影响^［21］。

受距离刚性理论的启发，基于方位约束的方位刚性理论逐步建立并发展^{［6-7， 22-24］}。方位刚性思想最早在文献［22］中以平行重绘的形式被提出，随后相关学者在二维空间中对其进行了系统性构建^［25-29］。文献［7］将图的方位刚性理论推广至任意维度，并指出在方位约束下图形的形状唯一性（仅允许由平移与缩放构成的平凡形变）等价于无穷小方位刚性。此后，该作者在文献［30］中进一步证明，与无穷小距离刚性类似，无穷小方位刚性的图条件同样为拉曼图。这表明，对于几乎所有顶点配置，在方位约束下拉曼图均可保证形状唯一性。该结论极大推动了图的方位刚性理论在传感器网络定位、多智能体协同编队（图3）及运动结构恢复等协同问题中的应用^［31-34］。

相较于距离、方位等约束，角度约束不依赖于全局坐标系，且允许图形平凡变化的自由度更高（可实现旋转、平移、缩放），近年来受到了广泛关注与深入研究^{［9-11，35-39］}。在文献［25］中，探讨了基于角度约束的编队控制可行性，并给出了若干关键结论。文献［40］提出了一种基于角度约束的环形编队控制算法，可确保网络中受约束的角度收敛至期望值。但期望角度约束无法保证编队队形的形状唯一性，因此难以确保所收敛队形的精确性。为解决这一问题，基于不同角度约束的图刚性理论被相继提出。文献［10］在框架（framework）的研究背景下，首次系统性地研究了基于无符号角（即邻边之间夹角的余弦值）的图刚性理论。文献［11］则在角性结构（angularity）的框架下，基于符号角（即邻边之间的逆时针旋转角度）提出了符号角刚性理论。本文将分别从无符号角刚性理论和符号角刚性理论两个方向出发，系统梳理角度约束在图形形状唯一性方面的研究进展，比较分析各理论的特点与局限，进而对角度刚性理论的研究现状进行总结，并对未来的研究方向进行展望。

1 无符号角刚性理论

本章首先介绍文献［9-10］提出的全局无符号角刚性、局部无符号角刚性及无穷小无符号角刚性等概念。其次，基于上述刚性性质，系统梳理现有文献中无符号角约束下的图形形状唯一性相关结论。最后，对当前无符号角刚性理论中的若干开放性问题进行归纳与探讨。

1.1 局部刚性、全局刚性以及无穷小刚性

在d维欧氏空间中，框架（framework）(\mathrm{𝒢},\mathit{p})由无向图\mathrm{𝒢}=(\mathrm{𝒱},\mathrm{ℰ})和配置（configuration）\mathit{p}=[{\mathit{p}}_{\mathrm{1}}^{\mathrm{T}},\dots ,{\mathit{p}}_n^{\mathrm{T}}{]}^{\mathrm{T}}组成，其中{\mathit{p}}_i\in {\mathbf{R}}^d表示节点i\in \mathrm{𝒱}的坐标，并满足任意两点不重合的假设。

为刻画d维欧氏空间中框架(\mathrm{𝒢},\mathit{p})的所有无符号角信息，下面引入无符号角刚性函数：

{\mathit{A}}_{{\mathit{𝒯}}_{\mathrm{𝒢}}}(\mathit{p})={\left[\dots ,{\mathit{b}}_{ji}^{\mathrm{T}}{\mathit{b}}_{jk},\dots \right]}^{\mathrm{T}},(i,j,k)\in {\mathit{𝒯}}_{\mathrm{𝒢}}，（1）

其中：{\mathit{b}}_{ji}、{\mathit{b}}_{jk}为单位向量，分别表示由j点出发指向i\mathrm{、}k两点的相对方位；{\mathit{b}}_{ji}^{\mathrm{T}}{\mathit{b}}_{jk}表示方位所夹角度{\theta }_{ijk}\in [\mathrm{0},\mathrm{\pi })的余弦（图4）；(i,j),(j,k)\in \mathrm{ℰ}\}为角引集，是对所有角度的索引。

由于角度余弦值可在单智能体的局部坐标系下测得，基于无符号角刚性理论的网络化系统协同控制过程无需依赖全局坐标系。值得注意的是，无符号角刚性函数的约束项存在冗余，因此集合{\mathit{𝒯}}_{\mathit{𝒢}}可在充分刻画刚性特征的前提下被替换为其子集 {\overline{\mathit{𝒯}}}_{\mathit{𝒢}}\subset {\mathit{𝒯}}_{\mathit{𝒢}}。将框架(\mathrm{𝒢},\mathit{p})的形状可由无符号角唯一确定定义为：对任意与框架(\mathrm{𝒢},\mathit{p})具有相同无符号角的框架(\mathrm{𝒢},\mathit{q})，其配置\mathit{q}均可表示为关于配置\mathit{p}的整体旋转、平移与放缩变换^［36］。其数学表达式为

\mathit{q}=c\left[{\mathit{I}}_n\otimes \mathit{ℛ}\right]\mathit{p}+{\mathrm{1}}_n\otimes \mathit{\xi }。（2）

其中：c\in \mathbf{R}\backslash \{\mathrm{0}\}为非零缩放系数；\mathit{ℛ}\in \mathrm{O}(d)为d维正交旋转矩阵；\mathit{\xi }\in {\mathbf{R}}^d为平移项量；{\mathrm{1}}_n表示元素全为1的n维列向量；\otimes表示克罗内克积运算。从形状可被无符号角唯一确定的定义可知，相较于距离刚性理论^［5］和方位刚性理论^［7］，无符号角刚性在刻画图形形状的唯一性时具有更宽松的约束条件。下文将具体介绍无符号角刚性的相关基础定义。

定义1 对于在d维欧氏空间中的框架(\mathrm{𝒢},\mathit{p})，若存在一个关于\mathit{p}的邻域U_{\mathit{p}}，使得

{\mathit{A}}_{{\mathit{𝒯}}_{\mathrm{𝒢}}}^{-\mathrm{1}}({\mathit{A}}_{{\mathit{𝒯}}_{\mathrm{𝒢}}}(\mathit{p}))\bigcap U_{\mathit{p}}={\mathit{A}}_{{\mathit{𝒯}}_{\mathrm{𝒦}}}^{-\mathrm{1}}({\mathit{A}}_{{\mathit{𝒯}}_{\mathrm{𝒦}}}(\mathit{p}))\bigcap U_{\mathit{p}}，（3）

则称框架(\mathrm{𝒢},\mathit{p})满足局部无符号角刚性。其中：\mathit{𝒦}表示与\mathrm{𝒢}对应的完全图。

定义2 若d维欧氏空间中的框架(\mathrm{𝒢},\mathit{p})满足

{\mathit{A}}_{{\mathit{𝒯}}_{\mathrm{𝒢}}}^{-\mathrm{1}}({\mathit{A}}_{{\mathit{𝒯}}_{\mathrm{𝒢}}}(\mathit{p}))={\mathit{A}}_{{\mathit{𝒯}}_{\mathrm{𝒦}}}^{-\mathrm{1}}({\mathit{A}}_{{\mathit{𝒯}}_{\mathrm{𝒦}}}(\mathit{p}))，（4）

则称框架(\mathrm{𝒢},\mathit{p})满足全局无符号角刚性。

由上述定义可知，局部无符号角刚性表示框架在配置\mathit{p}的某一邻域内满足刚性，该性质可由全局无符号角刚性推得。全局无符号角刚性则表明，若确定框架(\mathrm{𝒢},\mathit{p})中的所有角度，则可唯一确定其中任意3点构成的角度，即完全图的二维嵌入(\mathrm{𝒦},\mathit{p})中的所有角度。此外，全局（局部）无符号角刚性借助刚性函数刻画角度对框架形状的约束程度，是一种几何性质，可用于判断框架形状的唯一性。然而，在d维欧氏空间中，判断框架(\mathrm{𝒢},\mathit{p})是否满足全局（局部）无符号角刚性通常较为困难。因此，下文将从另一个角度——无穷小无符号角刚性，对无符号角刚性展开分析。

为引入无穷小无符号角刚性，首先给出无穷小无符号角运动与平凡无符号角运动的概念。对于一个瞬时连续运动\dot{\mathit{p}}=\mathit{v}。若该运动满足

{\dot{\mathit{A}}}_{{\mathit{𝒯}}_{\mathrm{𝒢}}}(\mathit{p})=\frac{\partial {\mathit{A}}_{{\mathit{𝒯}}_{\mathrm{𝒢}}}(\mathit{p})}{\partial \mathit{p}}\mathit{v}\triangleq {\mathit{R}}_{\mathit{A}}^{{\mathit{𝒯}}_{\mathrm{𝒢}}}(\mathit{p})\mathit{v}=\mathrm{0}，（5）

则称它为无穷小无符号角运动。其中：{\mathit{R}}_{\mathit{A}}^{{\mathit{𝒯}}_{\mathrm{𝒢}}}(\mathit{p})称为无符号角刚性矩阵。若该运动为平移、旋转与缩放运动的线性组合，则称其为平凡运动。下面给出无穷小无符号角刚性的定义。

定义3 对于d维欧氏空间中的框架(\mathrm{𝒢},\mathit{p})，若其所有无穷小无符号角运动均为平凡运动，则称该框架满足无穷小无符号角刚性。

无穷小无符号角刚性通过刚性矩阵的零空间，刻画框架在角度约束下的连续形变轨迹与形变趋势，是一种代数性质。与全局（局部）无符号角刚性相比，它更易于通过刚性矩阵的谱分析进行判定。综合现有文献对无符号角刚性性质的研究，给出3种刚性性质的内在联系（图5）。

由图5可知，无穷小无符号角刚性可推出局部无符号角刚性。因此，通过分析框架刚性矩阵的零空间，即可判定其局部无符号角刚性。该结论也为无符号角刚性理论在基于梯度下降思想的多智能体编队控制算法设计中的应用提供了理论支撑。尽管文献［10］推测无符号角刚性与方位刚性^［7］具有类似的关联关系，但该结论尚未得到充分验证。

有趣的是，文献［10］的研究同样表明，与距离刚性类似，无符号角刚性主要由网络拓扑结构决定，而非顶点位置的具体配置。也就是说，在给定图结构的前提下，在二维空间中一个框架是否具有角度刚性，对几乎所有顶点构型均成立。该结论进一步说明，无符号角刚性是图的一类通有性质。需要强调的是，框架满足无符号角刚性，并不代表其形状具有唯一性。为便于理解，图6给出了若干实例。其中，红色箭头表示框架存在非平凡运动，对应框架不满足无穷小无符号角刚性。此外，由图6（b）可见，即使框架中所有角度均被确定（即满足全局无符号角刚性），其形状仍有可能无法被唯一确定。下一节将给出无符号角刚性、图约束条件与图形形状唯一性三者间的内在联系。

1.2 关于无符号角约束的图形形状唯一性结论

在基于角度量测的传感器网络定位问题中，各传感器在有限感知（通信）半径r内，可与邻域传感器通信并测得相应的角度，具体如图7所示。该网络可抽象为一个框架(\mathrm{𝒢},\mathit{p})，其几何形状能否由无符号角唯一确定，直接决定基于无符号角约束的传感器网络定位问题是否存在唯一解。文献［36］提出了角度可固定性（angle fixability）的概念，并对此展开了深入研究。

引理1^［36］ 对于二维欧氏空间中的框架(\mathrm{𝒢},\mathit{p})，其形状可由无符号角约束唯一确定，当且仅当该框架同时满足全局无符号角刚性与无穷小无符号角刚性。

引理1表明，若要通过角度约束唯一确定框架形状，需排除两类形态歧义：非平凡的无穷小运动及相同角度下可能存在的翻转歧义。引理1首次给出了框架形状可由角度唯一确定的充要条件。值得注意的是，由于目前判断一个框架是否满足全局无符号角刚性仍较为困难，上述结论难以直接应用于实际问题。因此，基于该结论进一步给出了满足角度可固定性的图约束条件，即双边排序图（bilateration ordering）。

定理1^［36］ 若二维欧氏空间中的图\mathrm{𝒢}包含双边排序子图，则对几乎所有的顶点位置配置，其框架形状可由无符号角约束唯一确定。

图8给出了双边排序图的构造实例。可以看出，双边排序图按顺序依次引入顶点，每个新顶点均可由至少两条不平行直线的交点唯一确定，定理 1 正是基于这一思路得以证明。此外，定理 1 表明，嵌入二维欧氏空间的图，其形状唯一性主要由图的拓扑结构决定，而非顶点坐标。若图\mathrm{𝒢}包含双边排序子图，则在几乎所有顶点位置配置下，无法通过无符号角唯一确定形状的构型集合的测度为零。该图条件为基于无符号角的传感器网络定位、编队控制及多智能体群聚等协同问题的研究提供了理论支撑^［15］。但需要指出的是，定理1给出的仅是充分非必要条件。大量实例表明，许多图条件弱于双边排序图的结构（如拉曼图^［31］），其在二维空间中满足无穷小无符号角刚性的框架，同样满足全局无符号角刚性，而这一内在关系的严格证明至今尚未完成。另一方面，针对三维空间中的无符号角刚性理论，文献［36］证明了若一个二维框架由非退化双边排序图嵌入得到，则其角度可固定性在升维至更高维空间后依然保持。文献［38］进一步研究了无符号角约束下三维凸多面体的刚性特性。尽管目前针对三维空间的无符号角刚性研究已取得若干结果，但大多仅适用于特殊结构，一般性理论仍有待完善。

1.3 无符号角刚性与相关矩阵的精确可补全问题

从全局无符号角刚性的定义可知，这类“由局部信息能否唯一确定整体结构”的问题，在数学上等价于一个低秩相关矩阵（correlation matrix）的精确可补全问题^［41-43］，即在保证矩阵低秩的前提下，仅利用部分已知元素精确重构完整矩阵。图9给出了相关矩阵与无符号角刚性之间关联关系实例。如图9（a）所示，对于存在未知元素的相关矩阵，低秩矩阵补全的目标是在低秩约束下，通过已知项估计其余未知项。从图的角度刚性理论来看，该相关矩阵可视为由二维方位向量堆叠构成的矩阵\mathit{M}=[{\mathit{b}}_{\mathrm{12}},{\mathit{b}}_{\mathrm{14}},{\mathit{b}}_{\mathrm{23}},{\mathit{b}}_{\mathrm{24}},{\mathit{b}}_{\mathrm{34}}{]}^{\mathrm{T}}\in {\mathbf{R}}^{\mathrm{5}\times \mathrm{2}}经代数运算得到的Gram矩阵\mathit{M}{\mathit{M}}^{\mathrm{T}}，矩阵中的已知元素可对应框架中的无符号角，如图9（b）所示。该框架中的无符号角能够约束全部角度关系，且框架满足全局无符号角刚性。因此，基于这些角度约束可唯一确定任意两边之间的内积，从而实现矩阵的精确补全。此外，由于矩阵\mathit{M}的秩不大于2，按此思路得到的补全矩阵自然满足低秩要求。

目前，矩阵补全与图刚性理论之间的内在关联已受到研究者广泛关注。文献［37］基于相对位移的内积提出了图的弱刚性理论，并建立了其与矩阵精确可补全性之间的联系，为矩阵补全理论开辟了新的研究视角。文献［36］则将矩阵补全思想引入基于无符号角约束的半正定规划问题分析中，给出了将角度定位问题松弛为凸优化问题的图条件。

2 符号角刚性理论

符号角刚性理论最初于角性结构（angularity）的研究背景下被提出^［11］，后续在框架理论体系中得到进一步拓展与完善^［44］。与无符号角刚性理论类似，符号角刚性理论同样依托刚性函数对图中的角度约束进行数学表征，并借助全局刚性、局部刚性及无穷小刚性的概念，系统描述角度对几何形状的约束程度。本章首先分别介绍角性结构和框架范畴下的符号角刚性理论，及其在图形形状唯一性方面的研究进展；然后，总结并分析当前符号角刚性理论中尚未解决的若干开放性问题。

2.1 角性结构下的刚性理论及相关结论

在二维空间中，角性结构(\mathrm{𝒱},\mathrm{𝒜},\mathit{p})由点集\mathrm{𝒱}，角度索引集\mathrm{𝒜}\subset \{(i,j,k)|i\ne j\ne k,i,j,k\in \mathrm{𝒱}\}以及配置\mathit{p}=[{\mathit{p}}_{\mathrm{1}}^{\mathrm{T}},\dots ,{\mathit{p}}_n^{\mathrm{T}}{]}^{\mathrm{T}}\in {\mathbf{R}}^{\mathrm{2}n}共同构成，且满足任意两点互不重合的非退化假设。角度索引集中的元素(i,j,k)\in\mathrm{𝒜}表示从方位{\mathit{b}}_{ji}逆时针旋转到方位{\mathit{b}}_{jk}所形成的符号角{\alpha }_{ijk}\in [\mathrm{0,2}\mathrm{\pi })（图10），可通过下述公式计算得到

{\alpha }_{ijk}=\left\{\begin{array}{cc}\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{c}\mathrm{o}\mathrm{s}\left({\mathit{b}}_{jk}^{\mathrm{T}}{\mathit{b}}_{ji}\right),& \mathrm{i}\mathrm{f}{\mathit{b}}_{jk}^{\mathrm{T}}{\mathit{b}}_{ji}^{\perp }\ge \mathrm{0},\\ \mathrm{2}\mathrm{\pi }-\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{c}\mathrm{o}\mathrm{s}\left({\mathit{b}}_{jk}^{\mathrm{T}}{\mathit{b}}_{ji}\right),& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{。}\end{array}\right.（6）

从符号角的计算公式可以看出，其测量同样不依赖于全局坐标系，但要求测量单元在平面内对顺时针、逆时针方向的判定保持统一。此外，与普通框架不同，角性结构以角度约束与顶点集为核心表征要素，即先确定角度约束，再形成网络拓扑，可看作一类带有预设约束集的特殊框架。为刻画角性结构的符号角约束，引入符号角刚性函数：

{\mathrm{𝒮}}_{\mathrm{𝒜}}(\mathit{p})={\left[\dots ,{\alpha }_{ijk},\dots \right]}^{\mathrm{T}},(i,j,k)\in \mathrm{𝒜}。（7）

由该刚性函数的形式可知，与无符号角刚性不同，角性结构的符号角刚性函数直接选取网络中的部分角度作为约束条件。这一特性能有效减少冗余约束，从而降低实际应用场景中的计算复杂度。

类似于无符号角刚性理论，在角性结构体系下，同样可以定义局部符号角刚性、全局符号角刚性与无 穷小符号角刚性3类概念。结合现有文献对符号角刚性基本性质的研究成果^［11］，给出三者间的逻辑关联（图11）。对比可知，符号角刚性各性质的内在关系与无符号角刚性体系类似。

文献［11］构造了角性结构中局部符号角刚性无法推出全局符号角刚性的反例。但需强调，该反例并不适用于完整角度约束下的框架模型，无法否定框架全部角度约束满足时，局部刚性与全局刚性的等价关系。文中，称角性结构(\mathrm{𝒱},\mathrm{𝒜},\mathit{p})（框架(\mathrm{𝒢},\mathit{p})）的形状可由符号角唯一确定，意味着对任意与该角性结构（框架）具有相同无符号角的角性结构(\mathrm{𝒱},\mathrm{𝒜},\mathit{q})（框架(\mathrm{𝒢},\mathit{q})），其配置\mathit{q}均可表示为关于配置\mathit{p}的整体旋转、平移以及放缩。其数学表达式为

\mathit{q}=c\left[{\mathit{I}}_n\otimes {\mathit{ℛ}}_{\mathrm{o}}\left(\theta \right)\right]\mathit{p}+{\mathit{I}}_n\otimes \mathit{\xi }。（8）

其中：c\in {\mathbf{R}}^{+}为缩放系数；{\mathit{ℛ}}_{\mathrm{o}}(\theta )\in \mathrm{S}\mathrm{O}(\mathrm{2})为特殊正交旋转矩阵；\mathit{\xi }\in {\mathbf{R}}^{\mathrm{2}}为平移项量；\theta \in [\mathrm{0,2}\mathrm{\pi })。注意到，符号角刚性理论在形状唯一性约束中仅保证图形在\mathrm{S}\mathrm{O}(\mathrm{2})变换下的自由度，而无符号角刚性理论则允许图形在\mathrm{O}(\mathrm{2})变换下的形状唯一性。因此，符号角刚性对形状唯一性的约束条件更为严格。

为探究角性结构的形状能否由符号角约束唯一确定， 文献［11］基于顺序构造思想，先后提出一类全局符号角刚性图（图12），并给出了满足全局符号角刚性的一类三角角性结构^［45-46］（图13）。这两类图条件可保证在一般（generic）配置^［37］下，角性结构的形状可被唯一确定，即在几乎所有顶点位置配置中，该结构均满足全局符号角刚性。需要注意的是，角性结构的定义依赖于预先给定的符号角约束集。这一局限性导致角度刚性特性与图结构之间的直接关联难以建立，因此，目前尚无法给出符号角约束下形状唯一可确定的充分必要图条件。

2.2 框架背景下的符号角刚性理论与相关结论

为克服角性结构因预设定角引集所产生的局限性，文献［47］考虑给定框架(\mathrm{𝒢},\mathit{p})内全部符号角约束，提出了框架背景下的符号角刚性理论。通过建立该理论与方位刚性理论的关联，完整揭示了局部符号角刚性、全局符号角刚性与无穷小符号角刚性三者间的内在联系（图14）。

在此基础上，文献［44］分别从代数与组合角度，给出了符号角刚性用于形状确定性的充要条件。

定理2^［44］ 给定二维欧氏空间中的框架(\mathrm{𝒢},\mathit{p})，其形状可由符号角约束唯一确定，当且仅当该框架满足无穷小符号角刚性，或同时满足非退化性与全局符号角刚性。

定理3^［44］ 给定二维欧氏空间中具有一般（generic）构型的框架(\mathrm{𝒢},\mathit{p})，其形状可由符号角约束唯一确定，当且仅当\mathrm{𝒢}包含一个拉曼子图。

图15所示的拉曼图实例，无法直接采用文献［11］与文献［45］的构造方法生成。值得注意的是，虽然上述结论通过引入图中全部角度约束，避免了对预设角引集的依赖，但实际应用中会产生较大的计算开销。为此，文献［44］进一步提出角引图（angle index graph）的概念，用以刻画符号角约束与刚性特性的内在关联，并设计了一种多项式时间复杂度算法，求解保障符号角刚性与形状唯一性所需的最少角度约束条件。该成果已应用于分布式传感器网络定位及多智能体编队控制领域，并从理论层面保证了算法具备全局收敛性。

由于二维空间特有的顺、逆时针概念难以直接推广至高维空间，现有角性结构与框架符号角刚性理论的研究成果均局限于二维场景。如何合理定义高维空间中的符号角，将基于符号角约束的刚性理论体系拓展至高维范畴，并建立对应的形状唯一性判定条件，是一个极具挑战性的科学问题。

2.3 符号角刚性与对称矩阵的精确可补全问题

作为图角度刚性理论的重要分支，符号角刚性理论与精确矩阵补全问题同样存在紧密联系。受欧几里得距离矩阵补全问题（Euclidean distance matrix completion problem）的启发^［48-49］，若将符号角类比为边与边之间的距离，则符号角刚性问题可等价为图16所示的对称矩阵补全问题，其中所有矩阵元素均处于[\mathrm{0,1}]。针对图16（a）含未知元素的对称矩阵，其已知元素为方位间符号角除以\mathrm{2}\mathrm{\pi }的计算值。图 16 （b） 对应的框架在该组符号角约束下可唯一确定全部符号角，且满足全局符号角刚性，因此能够依托已知元素实现矩阵精确补全。

文献［50］将对称矩阵的未知元素解释为d维空间中两点间的距离，借助距离刚性理论，把未知对称矩阵的精确补全问题 （NP完全问题）转化为d维欧式空间中的图实现问题，并进一步探讨了矩阵的精确可补全性。然而，基于该思路求得的补全解，在何种条件下能够满足半正定性、低秩性等约束，仍是一个悬而未决的难题。相较而言，基于符号角刚性理论的对称矩阵补全方法虽具备扎实的理论基础，但同样面临此类亟待解决的困境。

3 分析总结与未来展望

本文系统梳理了图角度刚性理论的两大核心分支：无符号角刚性理论与符号角刚性理论。前者基于角度余弦值构建约束，可适配更高维空间，但其在形状唯一性刻画方面的研究已面临瓶颈；后者则利用带有方向信息的符号角建立约束，现已在二维空间中建立便于工程应用的形状唯一性充要条件，但其在高维空间中的刚性定义与理论体系尚未确立。表1总结了角度刚性理论与其他刚性理论在不同维度下的差异特征。尽管两类理论已在传感器网络定位、多智能体编队控制等网络化系统协同控制问题中展现出良好的应用潜力，但角度刚性理论整体仍面临若干关键难题与挑战。

（ⅰ）无穷小无符号角刚性与全局无符号角刚性的关联性研究。现有结果表明，无穷小无符号角刚性或可推导出全局无符号角刚性，进而建立角度可固定性的充要条件，但该猜想暂缺乏严格的理论证明。厘清二者的内在联系，将有力推动无符号角刚性理论在多智能体协同控制等领域的应用，同时为高维空间中刚性特性与形状唯一性的相关研究提供理论支撑。

（ⅱ）图的刚性理论与矩阵补全理论的关联性研究。从矩阵补全视角分析，相较于符号角刚性理论，无符号角刚性理论的核心区别与突出优势，在于其对应关联矩阵具备低秩特性。据此，满足无符号角刚性在数学层面等价于低秩关联矩阵的精确可补全问题；且在保证补全矩阵满足低秩约束的前提下，仅依靠部分已知元素，即方位间内积，便可实现整个矩阵的精确重构。相比之下，符号角刚性虽同样与对称矩阵补全问题密切相关，但受自身定义限制，无法如无符号角刚性一般，直观判别补全矩阵的低秩属性。鉴于全局符号角刚性的简易判别条件已初步建立，且满足该性质所需的最小角度约束也已明确，因此，探究基于符号角刚性理论的矩阵补全方法，同样具备广阔的研究前景与应用价值。

（ⅲ）角度刚性理论向高维空间的拓展研究。无符号角刚性理论在高维空间中的形状唯一性条件、各类刚性性质的内在关联，以及对应的图结构刻画，目前仍处于初步研究阶段。符号角刚性方面，至今仍缺乏适用于三维及以上空间、统一且实用的定义与测量方法。建立并完善高维角度刚性理论，不仅能够补全高维欧氏空间中图刚性理论的体系漏洞，还能为多智能体协同、高维传感器网络定位等复杂协同问题，提供更具针对性的分析工具与坚实的理论支撑。

在实际工程应用中，感知信息易受噪声干扰、目标遮挡、通信中断等非理想因素的影响。尽管已有相关文献探讨带噪声角度测量的定位问题，但多数研究基于对噪声模型的理想假设，且缺乏充足的实物实验验证。如何将现有理论结论拓展至非理想感知环境，充分考虑实际场景中不确定性因素对算法性能的影响，并建立对应的可定位性判定条件与容错控制策略，仍是亟待解决的前沿课题。

综上所述，角度刚性理论作为图论、几何学与控制理论的交叉研究方向，其进一步的发展与突破，不仅将持续为网络化系统自主协同控制提供强有力的理论支撑，还将为相关技术的工程化应用开辟更广阔的发展前景。

参考文献

[1] 沈林成，牛轶峰，朱华勇.多无人机自主协同控制理论与方法［M］.北京：国防工业出版社，2013.

[2] OH K K， PARK M C， AHN H S. A survey of multi-agent formation control［J］. Automatica， 2015， 53： 424-440.

[3] ASPNES J， EREN T， GOLDENBERG D K， et al. A theory of network localization［J］. IEEE Transactions on Mobile Computing， 2006， 5（12）： 1663-1678.

[4] ANDERSON B D O， YU Changbin， FIDAN B， et al. Rigid graph control architectures for autonomous formations［J］. IEEE Control Systems Magazine， 2008， 28（6）： 48-63.

[5] KRICK L， BROUCKE M E， FRANCIS B A. Stabilisation of infinitesimally rigid formations of multi-robot networks［J］. International Journal of Control， 2009， 82（3）： 423-439.

[6] CAO Kun， HAN Zhimin， LI Xiuxian， et al. Ratio-of-distance rigidity theory with application to similar formation control［J］. IEEE Transactions on Automatic Control， 2020， 65（6）： 2598-2611.

[7] ZHAO Shiyu， ZELAZO D. Bearing rigidity and almost global bearing-only formation stabilization［J］. IEEE Transactions on Automatic Control， 2016， 61（5）： 1255-1268.

[8] MICHIELETTO G， CENEDESE A， ZELAZO D. A unified dissertation on bearing rigidity theory［J］. IEEE Transactions on Control of Network Systems， 2021， 8（4）：1624-1636.

[9] 井冈山.多智能体编队控制的新图论方法［D］.西安：西安电子科技大学， 2018.

[10] JING Gangshan， ZHANG Guofeng， LEE H W J， et al. Angle-based shape determination theory of planar graphs with application to formation stabilization［J］. Automatica， 2019， 105： 117-129.

[11] CHEN Liangming， CAO Ming， LI Chuanjiang. Angle rigidity and its usage to stabilize multiagent formations in 2-D［J］. IEEE Transactions on Automatic Control， 2021， 66（8）： 3667-3681.

[12] LIN Zhiyun， WANG Lili， CHEN Zhiyong， et al. Necessary and sufficient graphical conditions for affine formation control［J］. IEEE Transactions on Automatic Control， 2016， 61（10）： 2877-2891.

[13] ZHAO Shiyu. Affine formation maneuver control of multiagent systems［J］. IEEE Transactions on Automatic Control， 2018， 63（12）： 4140-4155.

[14] TRINH M H， MUKHERJEE D， ZELAZO D， et al. Formations on directed cycles with bearing-only measurements［J］. International Journal of Robust and Nonlinear Control， 2018， 28（3）： 1074-1096.

[15] JING Gangshan， WANG Long. Multiagent flocking with angle-based formation shape control［J］. IEEE Transactions on Automatic Control， 2020， 65（2）： 817-823.

[16] ZHANG Xiaozhen， YANG Qingkai， XIAO Fan， et al. Linear formation control of multi-agent systems［J］. Automatica， 2025， 171： 111935.DOI：10.1016/j.automatica.2024.111935 .

[17] EULER L. Opera Postuma Mathematica et Physica ［M］. FUSS P H， FUSS N， ed. Petropoli： Typis Academiae Imperialis Scientiarum Petropolitanae， 1862： 494-496.

[18] CAUCHY A L. Sur les polygones et les polyèdres ： second mémoire［J］. Journal de l'École polytechnique， 1813， IX（XVIe cahier）： 87-99.

[19] ASIMOW L， ROTH B. The rigidity of graphs， II［J］. Journal of Mathematical Analysis and Applications， 1979， 68（1）： 171-190.

[20] JACKSON B. Notes on the rigidity of graphs［Z］. Levico Terme： ADONET-CIRM School on Graphs and Algorithms， 2007： 31.

[21] THORPE M F， DUXBURY P M. Rigidity theory and applications［M］. New York： Kluwer Academic/Plenum Pub， 1999.

[22] WHITELEY W. Parallel redrawing of configurations in 3-space［C］//Proceedings of the Workshop on Rigidity and Flexibility of Structures. Toronto：［s.n.］， 2008.DOI：10.13140/RG.2.2.20412.80009 .

[23] Whiteley W. Some matroids from discrete applied geometry［C］//Matroid Theory （Seattle， WA， 1995）. Providence： American Mathematical Society， 1996：171-311.

[24] SERVATIUS B， WHITELEY W. Constraining plane configurations in computer-aided design： Combinatorics of directions and lengths［J］. SIAM Journal on Discrete Mathematics， 1999， 12（1）： 136-153.

[25] EREN T， WHITELEY W， MORSE A S， et al. Sensor and network topologies of formations with direction， bearing， and angle information between agents［C］//42nd IEEE International Conference on Decision and Control. Piscataway， NJ， USA：IEEE.2004：3064-3069.

[26] EREN T， WHITELEY W， BELHUMEUR P N. A theoretical analysis of the conditions for unambiguous node localization in sensor networks［R］. New York： Columbia University， Computer Science Department， 2004. CUCS-032-04.

[27] EREN T， WHITELEY W， BELHUMEUR P N. Using angle of arrival （bearing） information in network localization［C］//Proceedings of the 45th IEEE Conference on Decision and Control.Piscataway， NJ， USA：IEEE. 2007： 4676-4681.

[28] EREN T. Formation shape control based on bearing rigidity［J］. International Journal of Control， 2012， 85（9）： 1361-1379.

[29] ZELAZO D， FRANCHI A， GIORDANO P R. Rigidity theory in SE（2） for unscaled relative position estimation using only bearing measurements［C］//2014 European Control Conference （ECC）.Piscataway， NJ， USA：IEEE. 2014： 2703-2708.

[30] ZHAO Shiyu， SUN Zhiyong， ZELAZO D， et al. Laman graphs are generically bearing rigid in arbitrary dimensions［C］//2017 IEEE 56th Annual Conference on Decision and Control （CDC）.Piscataway， NJ， USA：IEEE. 2018： 3356-3361.

[31] ZHAO Shiyu， ZELAZO D. Localizability and distributed protocols for bearing-based network localization in arbitrary dimensions［J］. Automatica， 2016， 69： 334-341.

[32] ARRIGONI F， FUSIELLO A. Bearing-based network localizability： A unifying view［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2019， 41（9）： 2049-2069.

[33] LI Xiaolei， LUO Xiaoyuan， ZHAO Shiyu. Globally convergent distributed network localization using locally measured bearings［J］. IEEE Transactions on Control of Network Systems， 2020， 7（1）： 245-253.

[34] ZHAO Shiyu， ZELAZO D. Bearing rigidity theory and its applications for control and estimation of network systems：Life beyond distance rigidity［J］. IEEE Control Systems Magazine， 2019， 39（2）： 66-83.

[35] FANG Xu， LI Xiaolei， XIE Lihua. Angle-displacement rigidity theory with application to distributed network localization［J］. IEEE Transactions on Automatic Control， 2021， 66（6）： 2574-2587.

[36] JING Gangshan， WAN Changhuang， DAI Ran. Angle-based sensor network localization［J］. IEEE Transactions on Automatic Control，2022，67（2）：840-855.

[37] JING Gangshan， ZHANG Guofeng， JOSEPH LEE H W， et al. Weak rigidity theory and its application to formation stabilization［J］. SIAM Journal on Control and Optimization， 2018， 56（3）： 2248-2273.

[38] CHEN Liangming， CAO Ming. Angle rigidity for multiagent formations in 3-D［J］. IEEE Transactions on Automatic Control， 2023， 68（10）： 6130-6145.

[39] LI Kun， SHEN Zhixi， JING Gangshan， et al. Angle-constrained formation control under directed non-triangulated sensing graphs［J］.Automatica，2024，163：111565.DOI：10.1016/j.automatica.2024. 111565 .

[40] ZHAO Shiyu， LIN Feng， PENG Kemao， et al. Distributed control of angle-constrained cyclic formations using bearing-only measurements［J］. Systems & Control Letters， 2014， 63： 12-24.

[41] BARRETT W， JOHNSON C R， TARAZAGA P. The real positive definite completion problem for a simple cycle［J］. Linear Algebra and Its Applications， 1993， 192： 3-31.

[42] KUROWICKA D， COOKE R M. Completion problem with partial correlation vines［J］. Linear Algebra and Its Applications， 2006， 418（1）： 188-200.

[43] TANIGAWA S I. Singularity degree of the positive semidefinite matrix completion problem［J］. SIAM Journal on Optimization， 2017， 27（2）： 986-1009.

[44] HUANG Jinpeng， JING Gangshan. Signed angle rigid graphs for network localization and formation control［J/OL］. IEEE Transactions on Automatic Control，2026：1-16.

[45] CHEN Liangming. Triangular angle rigidity for distributed localization in 2D［J］.Automatica，2022，143：110414.DOI：10.1016/j.automatica.2022.110414 .

[46] CHEN Liangming， SUN Zhiyong. Globally stabilizing triangularly angle rigid formations［J］. IEEE Transactions on Automatic Control， 2023， 68（2）： 1169-1175.

[47] HUANG Jinpeng， JING Gangshan. On the equivalence between signed angle rigidity and bearing rigidity［C］//IEEE 64th Conference on Decision and Control （CDC）.Piscataway， NJ， USA：IEEE.2026： 5935-5940.

[48] BLUMENTHAL L M. Theory and applications of distance geometry［M］. 2nd ed. Bronx， New York： Chelsea Publishing Company， 1970.

[49] CRIPPEN G M， HAVEL T F. Distance geometry and molecular conformation［M］. Taunton， Somerset， England： Research Studies Press，1988.

[50] LAURENT M. Cuts， matrix completions and graph rigidity［J］. Mathematical Programming，1997，79（1）：255-283.

[51] JACKSON B， JORDÁN T. Connected rigidity matroids and unique realizations of graphs［J］. Journal of Combinatorial Theory， Series B，2005，94（1）：1-29.DOI：10.1016/j.jctb.2004.11.002 .

基金资助

国家重点研发计划青年科学家项目(2025YFA1018800)

国家自然科学基金面上项目(62573068)

国家自然科学基金重点项目(62533002)