Source-linked AI summary
Bearing Rigidity Theory and its Applications for Control and Estimation of Network Systems: Life Beyond Distance Rigidity
Shiyu Zhao, Daniel Zelazo
TL;DR
Distributed control and estimation can be difficult when agents measure only relative bearings rather than relative positions or distances. This review develops bearing rigidity as the architectural basis for bearing-based formation control and network localization, synthesizes associated algorithms and simulations, and identifies unresolved limitations involving graph directionality and reference frames.
Problem
The paper addresses formation control and network localization for multi-agent systems whose sensing may be limited to relative bearings.
Method
The review presents bearing rigidity theory and applies it to bearing-based localization, formation control, and bearing-only formation control.
Results
The review summarizes conditions, distributed protocols, control laws, and simulation examples for bearing-based localization and formation-control problems.
Takeaways & Limitations
Bearing rigidity provides a framework for analyzing and designing distributed control and estimation with bearing-only sensors such as cameras or sensor arrays.
Takeaways & Limitations
The reviewed results rely substantially on undirected graphs and global reference frames, while complete bearing-only control without such assumptions remains unresolved.
Abstract
from arXiv · showhide
The problem of distributed control and estimation for multi-agent systems with limited sensing capabilities is a practical challenge motivated by incomplete and imperfect sensing. This article addresses an important case where each agent in a network can only sense the relative bearings to their nearest neighbors. The study of this topic is motivated mainly by the rapid development of bearing-only sensors such as optical cameras or sensor arrays. This article provides a tutorial review on this topic focusing on the problems of formation control and network localization. A key component of this review is a presentation of the recently developed bearing rigidity theory, which defines a necessary architectural feature of multi-agent systems aiming to solve these two problems. This article presents a high-level summary of recently developed algorithms solving these problems, various simulation examples, and discussions pointing to the relevant literature and important remaining challenges in this area.
BEARING RIGIDITY THEORY
Bearing rigidity identifies when neighbor bearings determine a network’s geometric pattern, with infinitesimal bearing rigidity providing both uniqueness and a rank-based test. The review connects these conditions to localization and formation-control protocols, while noting assumptions and remaining sensing limitations.
- Properties of Infinitesimal Bearing Rigidity: Infinitesimal bearing rigidity uniquely determines node positions up to translation and scaling, and is characterized by a rank condition on the bearing rigidity matrix.The rank condition also means all infinitesimal bearing motions are trivial.
- Construction of Infinitesimally Bearing Rigid Networks: All Laman graphs are generically bearing rigid in arbitrary dimensions, but the Laman condition is sufficient rather than necessary.In the plane, generic bearing rigidity is equivalent to being Laman.
- Construction of Infinitesimally Bearing Rigid Networks: 2n −3 edges guarantee bearing rigidity for Laman graphs in arbitrary dimensions, although three-dimensional generically bearing rigid graphs can require fewer edges.Constructing all generically bearing rigid graphs remains an open problem.
- Bearing-Based Localizability: Bearing localizability is equivalent to nonsingularity of Bff and intuitively requires every infinitesimal bearing motion to involve at least one anchor.Infinitesimal bearing rigidity with at least two anchors is a sufficient condition for localizability.
- Distributed Localization Protocols: A distributed localization protocol globally localizes the network if and only if the network is bearing localizable, using orthogonal projection matrices as edge weights.This projection-matrix structure distinguishes the protocol from scalar-weight consensus protocols.
- Bearing-Based Formation Control: Bearing-based formation control is mathematically equivalent to stationary bearing-based localization for single-integrator agents, and several controls achieve global stability under bearing localizability.For bearing-only control with no leaders, an infinitesimally bearing-rigid target yields global convergence of the inter-agent bearings, while centroid and scale can remain invariant in another control law.
NOTATIONS FOR NETWORKS AND FORMATIONS
The paper models a network as an undirected graph whose vertices are mapped to agent positions, with edge and bearing vectors describing inter-agent geometry.
- Network representation: A network consists of a graph G=(V,E) with each vertex i mapped to a position p_i in R^d.The configuration stacks all node positions into p, while E specifies information-sharing relationships.
- Network representation: For an undirected graph, (i,j) is an edge exactly when (j,i) is an edge, and N_i denotes node i’s neighbors.The graph has m undirected edges, and an orientation is used for matrix constructions.
- Geometric quantities: For edge (i,j), the edge vector is e_ij=p_j-p_i and the unit bearing vector is g_ij=e_ij/∥e_ij∥.The bearing points from p_i to p_j, with e_ij=-e_ji and g_ij=-g_ji.
- Matrix notation: Stacked edge vectors satisfy e=(H⊗I_d)p, where H is associated with an oriented graph.The paper uses Null(·), Range(·), the all-ones vector 1_n, Euclidean or spectral norms, and the identity matrix I_d.
KEY DEFINITIONS IN BEARING RIGIDITY THEORY
Bearing rigidity characterizes when a network’s edge bearings determine its geometry locally or globally, while infinitesimal bearing rigidity tests whether all bearing-preserving motions are trivial.
- Bearing equivalence and congruency: Bearing equivalency requires corresponding edge bearings to agree between two networks with the same graph.Bearing congruency strengthens this requirement by requiring corresponding bearings to agree for every pair of nodes.
- Bearing rigidity: A network is bearing rigid when every sufficiently close bearing-equivalent realization is also bearing congruent.This is a local uniqueness condition controlled by some positive neighborhood radius ϵ.
- Bearing rigidity: A network is globally bearing rigid when every bearing-equivalent realization, without a proximity restriction, is bearing congruent.Global bearing rigidity therefore uses an arbitrary realization rather than only nearby alternatives.
- Infinitesimal bearing rigidity: The bearing rigidity matrix is the Jacobian of the bearing function and has matrix-vector form RB(p)=diag(Pg_1/∥e_1∥,...,Pg_m/∥e_m∥)(H⊗I_d).The projection matrices remove motion components along the corresponding bearing directions.
- Infinitesimal bearing rigidity: An infinitesimal bearing motion satisfies RB(p)δp=0, and it is trivial when it represents only network translation and scaling.Infinitesimal bearing rigidity means that every infinitesimal bearing motion is trivial.
- Relations among notions: Infinitesimal bearing rigidity implies both bearing rigidity and global bearing rigidity, while bearing rigidity and global bearing rigidity imply each other.These relations are summarized in Figure S1.
KEY DEFINITIONS IN DISTANCE RIGIDITY THEORY
Distance rigidity characterizes uniqueness of network geometry from inter-node distances, with local, global, and infinitesimal forms defined analogously to bearing rigidity.
- Distance equivalence and congruency: Distance equivalency requires corresponding edge lengths to match between two networks with the same graph.Distance congruency requires corresponding distances to match for every pair of nodes.
- Distance rigidity: A network is distance rigid when every sufficiently close distance-equivalent realization is also distance congruent.The definition uses a positive neighborhood radius ϵ around the original configuration.
- Distance rigidity: A network is globally distance rigid when every distance-equivalent realization is distance congruent, without restricting the realization’s proximity.This is the global counterpart of local distance rigidity.
- Infinitesimal distance rigidity: The distance rigidity matrix is the Jacobian of the distance function and is constructed from the edge vectors and graph incidence structure.The paper introduces its matrix-vector form RD(p) for analyzing distance-preserving motions.
- Infinitesimal distance rigidity: An infinitesimal distance motion satisfies RD(p)δp=0, and it is trivial when it represents only network translation and rotation.Infinitesimal distance rigidity requires all infinitesimal distance motions to be trivial.
- Relations among notions: Both infinitesimal and global distance rigidity imply distance rigidity, but infinitesimal and global distance rigidity do not imply each other.These relations are summarized in Figure S2.
AN ORTHOGONAL PROJECTION MATRIX
The orthogonal projection matrix removes the component of a vector parallel to a nonzero direction and provides key algebraic tools for bearing rigidity analysis.
- Definition and geometry: For any nonzero x in R^d, P_x is the orthogonal projection onto the subspace perpendicular to x.The paper uses P_x as shorthand for P(x).
- Matrix properties: P_x is symmetric and satisfies P_x x=0, with Null(P_x)=span{x}.It is positive semidefinite, with one zero eigenvalue and d−1 eigenvalues equal to one.
- Matrix properties: Two nonzero vectors are parallel if and only if projecting one onto the orthogonal complement of the other gives zero.This property links projection matrices to bearing alignment.
- Dimension-specific forms: In two dimensions, P_x can be written using any nonzero normal vector x^⊥ as x^⊥(x^⊥)^T/∥x^⊥∥^2.For unit x in R^3, the projection also satisfies P_x=−[x]^2.
- Role in bearing rigidity: Projection matrices are central to bearing rigidity theory and its applications.Their geometric and algebraic properties are used to analyze bearing constraints and perturbations.
BEARING LAPLACIAN OF NETWORKS
The bearing Laplacian is a matrix-weighted graph Laplacian whose edge weights encode inter-neighbor bearing projections. For anchored networks, its follower block preserves positive semidefiniteness and relates follower and anchor positions.
- Definition: The bearing Laplacian combines the network graph structure with projection-matrix weights determined by inter-neighbor bearings.It has the same structure as a weighted graph Laplacian, with each edge weighted by its bearing projection matrix.
- Properties: For undirected graphs, the bearing Laplacian is symmetric and positive semi-definite.
- Anchored networks: With anchors and followers, the bearing Laplacian partitions into anchor and follower blocks, including B_ff ∈ R^(dn_f × dn_f).
- Anchored networks: The follower block B_ff is positive semi-definite and satisfies B_ff p_f = −B_fa p_a.
LAMAN GRAPHS AND HENNEBERG CONSTRUCTION
Laman graphs provide a sparse combinatorial foundation for rigidity, while bearing rigidity differs from distance rigidity in its invariance and higher-dimensional behavior. Henneberg operations generate exactly the minimally infinitesimally distance-rigid graphs in the plane.
- Laman graphs: A Laman graph has m = 2n − 3 edges and every subset of k ≥ 2 vertices spans at most 2k − 3 edges.
- Henneberg construction: Henneberg construction adds vertices through vertex addition or edge splitting while preserving the Laman condition.Starting from an edge, these operations generate Laman graphs, and every Laman graph admits such a construction.
- Bearing versus distance rigidity: Bearing rigidity determines a network pattern up to translation and scaling, whereas distance rigidity fixes the pattern through inter-neighbor distances.
- Bearing versus distance rigidity: Infinitesimal bearing rigidity is equivalent to infinitesimal distance rigidity in two dimensions.
- Higher-dimensional behavior: Laman graphs are generically bearing rigid in arbitrary dimensions, with at most 2n − 3 edges sufficient, unlike distance rigidity beyond two dimensions.
BEARING RIGIDITY THEORY FOR SE(2)
SE(2) bearing rigidity extends bearing-based analysis to networks whose agents have both positions and orientations. Its infinitesimal motions include translations, scalings, and coordinated rotations, and the framework supports estimation and formation control.
- SE(2) networks: An SE(2) network assigns each vertex a position in R^2 and an orientation in S^1 within a directed graph.
- Bearing representation: The directed bearing function maps SE(2)^n configurations to the collection of directed local bearings.
- Rigidity matrix: The directed bearing rigidity matrix is defined as the Jacobian of the directed bearing function.
- Infinitesimal motions: Infinitesimal SE(2) bearing motions preserve directed bearings, with trivial motions given by translations, scalings, and coordinated rotations.A coordinated rotation combines each agent’s body-axis rotation with a rigid-body rotation of the network.
- Applications: SE(2) rigidity theory has been applied to distributed relative-position estimation and formation control, with related extensions to SE(3).
AUTHOR INFORMATION
The article lists Shiyu Zhao and Daniel Zelazo as researchers working in control, systems, aerospace engineering, and related fields.
- Shiyu Zhao: Shiyu Zhao is a Lecturer in Automatic Control and Systems Engineering at the University of Sheffield.
- Daniel Zelazo: Daniel Zelazo is an Assistant Professor of Aerospace Engineering at the Technion – Israel Institute of Technology.