Laman Graphs are Generically Bearing Rigid in Arbitrary Dimensions
Provides a graph-theoretic foundation for constructing bearing rigid networks in arbitrary dimensions, solving a key problem in multi-agent formation control.
The paper proves that Laman graphs are generically bearing rigid in arbitrary dimensions, meaning networks with Laman graphs as underlying structure are bearing rigid for almost all configurations.
This paper addresses the problem of constructing bearing rigid networks in arbitrary dimensions. We first show that the bearing rigidity of a network is a generic property that is critically determined by the underlying graph of the network. A new notion termed generic bearing rigidity is defined for graphs. If the underlying graph of a network is generically bearing rigid, then the network is bearing rigid for almost all configurations; otherwise, the network is not bearing rigid for any configuration. As a result, the key to construct bearing rigid networks is to construct generically bearing rigid graphs. The main contribution of this paper is to prove that Laman graphs, which can be generated by the Henneberg construction, are generically bearing rigid in arbitrary dimensions. As a consequence, if the underlying graph of a network is Laman, the network is bearing rigid for almost all configurations in arbitrary dimensions.