Splitting Rigid Formations

Abstract

Consider a network of sensors able to move in 2-dimensional space. We may aim to impose distance constraints between certain sensors to ensure every pair of sensors maintain their distance from one another under any continuous movement. This property is known as rigidity. Rigidity may be required to ensure that no sensor will move out of range of any other sensor during movement. However, there arise situations which require us to decompose a rigid formation into two or more rigid sub-formations, perhaps to avoid an obstacle, to pursue different missions, or to allow merging of part of the original formation with another formation. The paper demonstrates that it is not always possible to decompose a rigid formation into rigid sub-formations without adding new distance constraints. The paper also discusses how to decompose a formation into connected but not necessarily rigid sub-formations (to which edges could be added to ensure rigidity of the sub-formations). We show it is always possible to decompose a rigid formation into two connected sub-formations, one of which has arbitrary order, without the addition of any new distance constraints, and we present an algorithm to do this. Although the sub-formations may not be rigid, the connectedness property ensures that no agent or group of agents can deviate too far away from the rest of the agents in the same connected component, and any agent can communicate with any other agent (perhaps via intermediate agents) in the same sub-formation. This will allow rigidity to be recovered within each connected sub-formation by applying existing algorithms.