S Ébastien Briot
email: sebastien.briot@ls2n.fr

Paolo Robuffo Giordano

Physical Interpretation of Rigidity for Bearing Formations: Application to Mobility and Singularity Analyses

Research on formation control and cooperative localization for multi-robot systems has been an active field over the last years. A powerful theoretical framework for addressing formation control and localization, especially when exploiting onboard sensing, is that of formation rigidity (mainly studied for the cases of distance and bearing measurements). Rigidity of a formation depends on the topology of the sensing/communication graph but also on the spatial arrangement of the robots, since special configurations ('singularities' of the rigidity matrix), which are hard to detect in general, can cause a rigidity loss and prevent convergence of formation control/localization algorithms based on formation rigidity. The aim of this paper is to gain additional insights into the internal structure of bearing rigid formations by considering an alternative characterization of formation rigidity using tools borrowed from the mechanical engineering community. In particular, we show that bearing rigid graphs can be given a physical interpretation related to virtual mechanisms, whose mobility and singularities can be analyzed and detected in an analytical way by using tools from the mechanical engineering community (Screw theory, Grassmann geometry, Grassmann-Cayley algebra). These tools offer a powerful alternative to the evaluation of the mobility and singularities typically obtained by numerically determining the spectral properties of the bearing rigidity matrix (which typically prevents drawing general conclusions). We apply the proposed machinery to several case formations with different degrees of actuation, and discuss known (and unknown) * Address all correspondence to this author. singularity cases for representative formations. The impact on the localization problem is also discussed.

Introduction

Formation control and cooperative localization for multi-robot teams has been a topic of extensive research over the last years [START_REF] Fox | Distributed multirobot exploration and mapping[END_REF][START_REF] Michael | Cooperative manipulation and transportation with aerial robots[END_REF][START_REF] Giordano | A passivity-based decentralized strategy for generalized connectivity maintenance[END_REF][START_REF] Hausman | Cooperative multi-robot control for target tracking with onboard sensing[END_REF][START_REF] Montijano | Vision-based distributed formation control without an external positioning system[END_REF][START_REF] Michieletto | Bearing rigidity theory in SE(3)[END_REF][START_REF] Palacios-Gasós | Distributed coverage estimation and control for multi-robot persistent tasks[END_REF]. Among the many challenges, considerable efforts are still devoted to devising decentralized formation controllers and/or localization schemes based on only local (onboard) sensing and communication. When considering these sensing/communication requirements, one has to face several challenges related to the decentralized design of the control/estimation algorithms, as well as the constraints arising from the use of onboard sensors. For instance, typical sensors only measure part of the relative pose among robot pairs (e.g., a distance or a bearing vector), while knowledge of the full relative pose is often needed for implementing formation control schemes. Also, a sensor provides measurements naturally expressed in the body-frame of the robot carrying it, and therefore one also faces the need of letting the robots agree over some common shared frame where to express all the individually collected measurements for then communicating them to the other robots in the group.

In this context, a powerful theoretical framework for addressing decentralized formation control/localization from onboard sensing is that of formation rigidity [START_REF] Anderson | Rigid graph control architectures for autonomous formations[END_REF]. The tools from rigidity theory (and, in particular, the notion of infinitesimal rigidity) have been widely exploited in the community, by first focusing on the cases of distance rigidity [START_REF] Spica | Active Decentralized Scale Estimation for Bearing Based Localization[END_REF][START_REF] Dimarogonas | On the stability of distance-based formation control[END_REF][START_REF] Dimarogonas | Further results on the stability of distance-based multi-robot formations[END_REF][START_REF] Krick | Stabilisation of infinitesimally rigid formations of multi-robot networks[END_REF][START_REF] Oh | Formation control of mobile agents based on inter-agent distance dynamics[END_REF][START_REF] Garcia De Marina | Controlling rigid formations of mobile agents under inconsistent measurements[END_REF] (i.e., assuming that the robots are equipped with a distance sensor), and, more recently, by considering the case of bearing 1 rigidity [START_REF] Michieletto | Bearing rigidity theory in SE(3)[END_REF][START_REF] Cornejo | Scale-free coordinates for multi-robot systems with bearing-only sensors[END_REF][START_REF] Shames | Analysis of noisy bearing-only network localization[END_REF][START_REF] Zhao | Bearing rigidity and almost global bearing-only formation stabilization[END_REF][START_REF] Zelazo | Bearing-Only Formation Control Using an SE(2) Rigidity Theory[END_REF][START_REF] Schiano | A rigidity-based decentralized bearing formation controller for groups of quadrotor UAVs[END_REF][START_REF] Zhao | Translational and scaling formation maneuver control via a bearing-based approach[END_REF][START_REF] Zhao | Bearing rigidity theory and its applications for control and estimation of network systems: Life beyond distance rigidity[END_REF][START_REF] Schiano | Bearing rigidity maintenance for formations of quadrotor uavs[END_REF][START_REF] Trinh | Formations on directed cycles with bearingonly measurements[END_REF] (which is, instead, representative of onboard cameras).

Formation rigidity depends on the topology of the sensing/communication graph (presence of 'enough measurements/edges') but also on the spatial arrangement of the robots, since special spatial alignments can cause a rigidity loss and, as a consequence, prevent convergence of formation control/localization algorithms based on formation rigidity. While (infinitesimal) rigidity can be characterized by analyzing the spectral properties of the so-called distance/bearing rigidity matrix, this characterization is often numerical, since no closed-form for the singular values of the rigidity matrix exists in any non-trivial case. Therefore, it may be hard to draw general (geometrical) conclusions about the possible loss of rigidity for a given topology/spatial arrangement of the robots (e.g., identifying for a given topology all the group 'degenerate' configurations that may lead to a rigidity loss).

The aim of this paper is, thus, to address these points by providing an alternative characterization of formation rigidity using tools from an apparently disconnected field: parallel robotics. Indeed, although historically separated, the fields of rigidity and parallel robotics share many underlying points. For instance, in both cases one is interested in characterizing how well the sensor measurements (for multi-robots) or leg lengths (in parallel robotics) can condition the pose of the single/multiple robots. However, while the multi-robot community has mostly focused on numerical/iterative methods for solving the formation control/localization problems, the parallel robotics community has always proposed a vast literature on analytical tools for dealing with, e.g., possible singularities in the robot structures. The goal of this paper is, then, to adopt (and adapt) the well-established analysis tools of the parallel robotics community to the study of formation rigidity for multi-robot systems by providing a physical interpretation of rigid graphs. In particular, we will show that such a physical interpretation can lead to a better understanding of the formation control/localization problem, and can help solving critical issues such as analyzing the internal mobility of the formation or finding its singularity, near which iterative methods fail to converge.

In order to give a physical interpretation of bearing rigidity, we will extend a concept developed by the first author in the recent years which is named "hidden robot". This concept was first introduced in [START_REF] Briot | Minimal representation for the control of Gough-Stewart platforms via leg observation considering a hidden robot model[END_REF][START_REF] Briot | The hidden robot: an efficient concept contributing to the REFERENCES analysis of the controllability of parallel robots in advanced visual servoing techniques[END_REF] in order to determine the singularity cases of a vision-based controller dedicated to parallel robots [START_REF] Andreff | Vision-based control of a Gough-Stewart parallel mechanism using legs observation[END_REF]. It was then extended to more general cases, such as the observation of image points [START_REF] Briot | Revisiting the determination of the singularity cases in the visual servoing of image points through the concept of "hidden robot[END_REF] or image lines [START_REF] Briot | Singularity cases in the visual servoing of three image lines[END_REF].

The basic idea shown in [START_REF] Briot | The hidden robot: an efficient concept contributing to the REFERENCES analysis of the controllability of parallel robots in advanced visual servoing techniques[END_REF][START_REF] Briot | Revisiting the determination of the singularity cases in the visual servoing of image points through the concept of "hidden robot[END_REF] is that the mappings involved in the visual observation of geometric primitives (for estimating the pose of an object or for visual servoing) are equivalent to mappings representing the geometric and kinematic properties of given closed-loop mechanisms. By geometric property, we mean that the solutions of the Forward Geometric Model of the closed-loop mechanism under consideration are also the solutions of the 3-D localization problem associated with the considered observations. By kinematic property, we mean that the singularities of the inverse kinematic Jacobian matrix of the mechanism are the same as the singularities of the interaction matrix relating the time variation of the visual features and the camera velocity. By finding this correlation, it was then possible to study the singularities of the controller, by using advanced tools coming from the mechanical engineering community (e.g. the Grassmann-Cayley algebra [START_REF] Ben-Horin | Singularity analysis of a class of parallel robots based on Grassmann-Cayley algebra[END_REF] and/or the Grassmann geometry [START_REF] Merlet | Parallel Robots[END_REF]). The interest in using these tools is that they are (most of the time) able to provide simple geometric interpretations of the singularity cases.

In this paper, we show that:

• any bearing formations can be represented by a virtual closed-loop mechanism hidden within the mapping used in the bearing rigidity graph; • based on the definition of this virtual closed-loop mechanism, tools developed in the parallel robotics community and, even more generally, in the mechanical engineering community, can be used for analyzing the mobility and singularities bearing formations.

The proposed machinery is then applied to several case studies involving planar and 3D agents with different degrees of actuation (fully-actuated and 'quadrotor-like') for illustrating the benefits of the approach in understanding the internal mobility and possible singularities of the considered formations. The implications for what concerns the problem of cooperative localization are also discussed, by showing that not all singularities of the bearing rigidity matrix have the same impact on the possibility of recovering the agent poses from the available measurements. The rest of the paper is organized as follows. Section 2 reviews the main modeling assumptions and recaps some key notions of bearing rigidity and related concepts. Section 3 shows the physical interpretations involved in the bearing rigidity graph. Then, in Section 4, tools for mobility analysis are provided. Section 5 deals with the problem of singularities of the mapping. Discussions on how the approach can be generalized are made in Section 6. Finally, conclusions are drawn in Section 7.

Recalls and notations

In this work, we consider a group of N agents able to measure their relative bearing vector and to exchange data over a communication channel. Let W : {O, x W , y W , z W } be the world frame (with z W representing the vertical/gravity direction), and A i : {O i , x A i , y A i , z A i } the body-frame attached to each agent in the group. Let q i = (p i , R i ) be the configuration of each agent in W , with p i being the position of O i in W and R i the orientation of A i w.r.t. W .

In the scope of this work, we consider three possible representative cases: (i) fully-actuated 3D agents, for which 3), (ii) quadrotor-like agents for which

q i = (p i , R i ) ∈ SE(
q i = (p i , R i ) ∈ R 3 × S 1 (
in this case, R i is the rotation matrix around the vertical z W axis which is parameterized by a single angle see, e.g., [START_REF] Schiano | Bearing rigidity maintenance for formations of quadrotor uavs[END_REF][START_REF] Schiano | A rigidity-based decentralized bearing formation controller for groups of quadrotor UAVs[END_REF]), and (iii)

q i = (p i , R i ) ∈ SE(2)
for representing planar agents.

A directed framework, denoted as (G, q), is a pair consisting of:

• a directed graph G = (V , E), where V = {1 . . . N} is the vertex set and E ⊆ V × V the edge set [START_REF] Godsil | Algebraic Graph Theory[END_REF];

• a total configuration q = (q 1 , . . . , q N ) such that each vertex v i ∈ V in the graph is associated to the configuration q i . The agent relative bearing β i j (from agent i to agent j, and expressed in the body frame of agent i) is finally defined as

β i j (q i , q j ) = R T i p j -p i p j -p i . (1)
Presence of an edge (i, j) in E represents the possibility for agent i to measure the relative bearing β i j towards agent j.

Graph G is taken as a directed one, since we do not require, in general, reciprocity of the relative bearing measurements.

The notion of bearing rigidity can be characterized from an infinitesimal perspective by introducing the so-called directed bearing function and associated bearing rigidity matrix. The directed bearing function associated to a framework (G, q) is given by

β(q) = β e 1 . . . β e |E| (2)
where e 1 . . . e |E| stand for the |E| edges in E labeled according an arbitrary order. The world frame rigidity matrix B W G is the matrix linking the time-derivative β of the previous bearing function to all twists V i of frames A i grouped into the vector V by the relation:

β = B W G (q)V, B W G (q) ∈ R k|E|×s N (3)
where

• V = [V T 1 ... V T N ] T , in which V i is the twist of the frame
A i in the world frame;

• k is the dimension of the position vectors q i (k = 2 for planar agents and k = 3 for 3D agents), and s is the number of independent parameters in

q i (s = 3 in SE(2), s = 4 in R 3 × S 1 and s = 6 in SE(3)).
A framework is considered infinitesimally rigid at some q if and only if [START_REF] Michieletto | Bearing rigidity theory in SE(3)[END_REF][START_REF] Schiano | A rigidity-based decentralized bearing formation controller for groups of quadrotor UAVs[END_REF][START_REF] Eren | Formation shape control based on bearing rigidity[END_REF] rank

B W G (q) = s N -(s + 1) (4)
or also

dim N (B W G (q)) = s + 1 ( 5
)
where N (•) denotes the nullspace of a matrix. The (s + 1)dimensional nullspace of the bearing rigidity matrix is also well understood: it corresponds to s free rigid-body motions for the global formation in space (e.g., two translations on the plane and a rotation around the vertical axis in the SE(2) case [START_REF] Eren | Formation shape control based on bearing rigidity[END_REF] (s = 3), three translations and a rotation around a vertical axis in the R 3 × S 1 case [START_REF] Schiano | A rigidity-based decentralized bearing formation controller for groups of quadrotor UAVs[END_REF] (s = 4), three translations and three rotations in the SE(3) case [START_REF] Michieletto | Bearing rigidity theory in SE(3)[END_REF] (s = 6)), plus a scaling w.r.t. a reference point.

Physical interpretation of the bearing rigidity graph

In the present section, thanks to the concept of hidden robot [START_REF] Briot | The hidden robot: an efficient concept contributing to the REFERENCES analysis of the controllability of parallel robots in advanced visual servoing techniques[END_REF], we provide a physical interpretation of the elementary edges (Fig. 1) for the cases SE(2), R 3 × S 1 and SE(3) exploiting the definition of virtual kinematic chains that can be associated to the bearing measurements.

Physical interpretation in SE(2)

In this case all agents move in a plane P : (O, x W , y W ) (z W being the vector normal to P ).

Let us start with the case represented in Fig. 1(a). The agent i measures the bearing β i j w.r.t. agent j, but this measurement is not reciprocal. The bearing measurement β i j is equivalent to requiring that the agent j lies on a line passing through i whose direction in the frame A i is known (and given by the bearing β i j ). With this single measurement, the distance and relative orientation between agents i and j remain undefined.

Mechanically speaking, the simplest kinematic chain able to provide the aforementioned geometric constraints is a kinematic chain made of a planar RPR architecture (Fig. 2(a)), meaning that the chain consists of an active revolute (R) joint with an axis along z W passing through O i (the origin of the frame A i attached to agent i), followed in series by a passive prismatic (P) joint lying on the plane P and with direction ζ i j = --→ O i O j and then a passive revolute (R) joint with an axis along z W passing through O j (the origin of the frame A j attached to agent j). Other types of chains could be devised, but they would be more complex and have little interest for the mobility and singularity analyses developed in the following. The reader interested in defining kinematic chains for given types of motions can find additional information in [START_REF] Kong | Type Synthesis of Parallel Mechanisms[END_REF].

Let us now consider the second case represented in Fig. 1(b). The agent i can measure the bearing β i j w.r.t. agent j, and likewise agent j can measure the bearing β ji w.r.t. agent i (note that, in general, β i j = β ji ). These two measurements are equivalent to require that agent j lies on a line passing through i and whose direction in both frames A i and A j is known (and given by the bearings β i j and β ji ). With these two measurements one cannot recover the distance between i and j but it is possible to fix the relative orientation between the agents i and j.

Mechanically speaking, the same type of information can be obtained with a kinematic chain made of a planar RPR architecture (Fig. 2(b)), meaning that the chain is made of an active revolute (R) joint with an axis along z W passing through O i , followed in series by a passive prismatic (P) i j (a) i measures j but j does not measure i i j (b) i measures j and j measures i joint lying in the plane P and of direction ζ i j = --→ O i O j and then an active revolute (R) joint with an axis along z W passing through O j . The two active revolute joints are necessary to fix the direction of the line passing through O i and O j in both frames A i and A j , i.e. they are a virtual representation of the bearing of j in the frame A i and the bearing of i in the frame A j . Their displacements are a measure of the bearings β i j and β ji .

Physical interpretation in

R 3 × S 1
In this case all agents move in 3D space, but the axis z A i of any agent i is constrained to stay directed along the axis z W of the world frame. As explained, this case is representative of many applications involving quadrotor UAVs in non-aggressive flight regimes [START_REF] Schiano | Bearing rigidity maintenance for formations of quadrotor uavs[END_REF][START_REF] Schiano | A rigidity-based decentralized bearing formation controller for groups of quadrotor UAVs[END_REF][START_REF] Zelazo | Bearing-only formation control using an se(2) rigidity theory[END_REF].

Let us start again with the case represented in Fig. 1(a). Once again, with this single measurement, one cannot recover the distance between i and j nor the relative orientation among i and j, except for the fact that both z A i and z A j must be parallel to the world-frame axis z W .

Mechanically speaking, the same type of information can be obtained with a kinematic chain made of a spatial UPRR architecture (Fig. 3(a)), meaning that the chain is made of an active cardan (or universal U) joint with the first axis along ζ 1 i j = z W and the second axis

ζ 2 i j = z W × --→ O i O j (i.e.
perpendicular to z W and --→ O i O j ) both passing through O i , followed in series by a passive prismatic (P) joint of direction

ζ 3 i j = --→ O i O j
and then a cardan (made of two orthogonal revolute joints) whose first joint with an axis of direction ζ 2 i j is active and whose second joint with an axis along ζ 1 i j = z W is passive, both joint axes passing through O j . The active cardan joint is necessary to fix the bearing of j in the frame A i while the active R joint of the last cardan joint is also active in order to allow for the last revolute joint to have its axis directed along z W .

Let us now consider the second case represented in

W z ij ζ 3 i O j O W z ij ζ 2 ij ζ 2 A i x A i y A j x A j y (a)
Virtual kinematic chain corresponding to the case given in Fig. 1(a): a serial UPRR chain (the first R joint of the last U joint is active, not the second joint directed along z W ) . With the two measurements, one cannot recover the distance between i and j but it is possible to obtain the relative orientation between the agents i and j. Mechanically speaking, the same type of information can be obtained with a kinematic chain made of a spatial UPU architecture (Fig. 3(b)), meaning that the chain consists of an active cardan (or universal U) joint with the first axis along ζ 1 i j = z W and the second axis

W z ij ζ 3 i O j O W z ij ζ 2 ij ζ 2 A i x A i y A j x A j y (
ζ 2 i j = z W × --→ O i O j both passing through O i , followed in series by a passive prismatic (P) joint of di- rection ζ 3 i j = --→ O i O j
and then an active cardan (U) joint with a first axis of direction ζ 2 i j and a second axis along ζ 1 i j , both passing through O j . The two active cardan joints are necessary to fix the bearing of j in the frame A i and the bearing of i in the frame A j . Their displacements are a measure of the bearings β i j and β ji .

Physical interpretation in SE(3)

In this case all agents move in 3D space without any constraint.

Again, let us start with the case represented in Fig. 1(a). With this single measurement, one cannot recover neither the distance nor the relative orientation between agents i and j.

Mechanically speaking, the same type of information can be obtained with a kinematic chain made of a spatial UPS architecture (Fig. 4(a)), meaning that the chain consists of an active cardan (U) joint centered in O i , followed in series by a passive prismatic (P) joint of direction --→ O i O j and then a passive spherical (S) joint at O j . The active cardan joint is necessary to fix the bearing of j in the frame A i and its displacement is a measure of the bearing β i j . The passive spherical joint prevents to know the orientation of j in A i . It should be noted that the same motion could also be performed fully equivalently by a UCU chain, i.e. a chain made of an active cardan joint centered in O i , followed in series by a passive cylindrical (C) joint of direction --→ O i O j (i.e. a combination of a prismatic joint and a revolute joint with identical axes) and then a passive cardan joint centered in O j .

Let us now consider the second case represented in Fig. 1(b). With these two measurements, one cannot recover the distance between i and j but it is possible to constrain

ij ζ 3 i O ij ζ 2 ij ζ 1 ij ζ 4 ij ζ 5 j O ij ζ 6 A i x A i y A j x A j y A i z A j z (a)
Virtual kinematic chain corresponding to the case given in Fig. 1 part of the rotation between the agents i and j: frames A i and A j can only rotate around the axis directed along --→ O i O j and passing through O i and O j .

(a): a serial UPS chain ij ζ 3 i O ij ζ 2 ij ζ 1 ij ζ 4 ij ζ 5 j O A i x A j x A j z A i z (b)
Mechanically speaking, the same type of information can be obtained with a kinematic chain made of a spatial UCU architecture (Fig. 4(b)), meaning that the chain is made of an active cardan joint centered in O i , followed in series by a passive cylindrical (C) joint of direction --→ O i O j and then an active cardan joint centered in O j . The two active cardan joints are necessary to fix the bearing of j in the frame A i and the bearing of i in the frame A j . Their displacements are a measure of the bearings β i j and β ji .

Assembly of two kinematic chains

Stacking bearing measurements in a graph corresponds to assembling the kinematic chains associated with each measurement. However, this would lead to the design of virtual kinematic chains with redundant joints which are useless. For instance, let us consider the graph shown in Fig. 5(a). Let us deal with this example in SE(2). Assembling straightforwardly the two kinematic chains associated with each graph edge leads to the virtual kinematic chain shown in Fig. 5(b). It appears that, at O j , two actuated revolute joints are superposed (they share the same axis). There is a joint redundancy here, as the motion of the first one can be compensated by the second one without any change in the bearing measurement between agents j and k. As a result, the kinematic chain can be simplified by suppressing one of the two revolute joints at O j so that the serial chain given in Fig. 5(c) is kept to perform the same equivalent motion.

Another important example is when it is necessary to consider graphs with unidirectional bearing measurements between two agents only, such as the one in Fig. 6(a). Let us deal with this example again in SE [START_REF] Michael | Cooperative manipulation and transportation with aerial robots[END_REF]. Assembling straightforwardly the two kinematic chains associated with each graph edge leads to the virtual kinematic chain shown in Fig. 6(b). It appears that, at O j , an actuated revolute joint is superposed with a passive one (they share the same axis). There is a also a joint redundancy here, as the motion of the active joint has no effect because of the free rotation allowed by the previous passive revolute joint. As a result, the kinematic chain can be simplified by suppressing the active rev-i j k

(a) i "looks at" j, j "looks at" i, j "looks at" k, k "looks at" j olute joint at O j so that the serial chain given in Fig. 6(c) is kept to perform the same equivalent motion.

W z ij ζ i O j O W z k O W z jk ζ (
Obviously, with the representation shown in Fig. 6(c), we lose the information that " j "looks at" k, k "does not look at" j". However, the problem we investigate is not how to pass from a mechanism to a rigidity graph, but the inverse. Therefore the deletion of the active joint in Fig. 6(c) has no impact on the further analyses.

Once these equivalent kinematic chains are known, one can study their mobility (a notion that can be used in order to check whether a formation is rigid or not) and their singularities (that are equivalent to the singularities of the bearing rigidity matrix).

Mobility analysis

In this section, we used virtual kinematic chains defined thanks to the concept of hidden robot in order to analyze the mobility of different types of formations.

General conditions for mobility analysis of a single loop mechanism

The mobility m of a single loop mechanism can be computed by using the following formula [START_REF] Waldron | The constraint analysis of mechanisms[END_REF] (for several loop i j k

(a) i "looks at" j, j "does not look at" i, j "looks at" k, k "does not look at" j

W z ij ζ i O j O W z k O W z jk ζ (b) Equivalent virtual mechanism in SE(2): two serial RPR chains in series.
The dark-gray joints are actuated 2): a serial RPRPR chain. The dark-gray joints are actuated Fig. 6. Two connected edges in bearing rigidity graphs with two bearing measurements only mechanisms, formulas can be found in [START_REF] Gogu | Structural Synthesis of Parallel Robots[END_REF][START_REF] Huo | A geometric algebra approach to determine motion/constraint, mobility and singularity of parallel mechanism[END_REF]):

W z ij ζ i O j O W z k O W z jk ζ (c) Simplified virtual mechanism in SE(
m = ∑ i f i -p (6)
in which f i is the number of degrees of freedom of the joint i of the mechanism and p is the number of independent degrees of freedom of the end-effector of the serial chain obtained when opening the loop 1 . The value of p can be computed by finding the rank of the kinematic Jacobian matrix of the serial chain, or equivalently, because the i-th column of the kinematic Jacobian matrix is a unit twist ζ i j characterizing the displacement of the end-effector when the j-th freedom of joint i is activated only, by analyzing the rank of the twist system of the chain [START_REF] Briot | Dynamics of Parallel Robots -From Rigid Links to Flexible Elements[END_REF]. With these conditions, it is thus possible to find the internal mobility of the virtual mechanism associated with a given formation. If the formation is rigid, we should find a mobility of one corresponding to the expansion/retraction of the formation relative to a reference point. Note that, the internal mobility being possible thanks to the displacement of the passive joints of the virtual mechanism only (the active joints correspond to the bearing measurements which are considered fixed, so the active joints cannot move), this mo-bility is computed by considering the freedoms of the chain made of the passive joints only.

In the next section, we analyze the mobility of two well known formations in order to show the validity of the approach.

Case studies 4.2.1 Case 1

Let us consider first the formation of three agents in SE(3) shown in Fig. 7(a): since the interaction graph is complete (presence of all possible directed edges), the formation is infinitesimally rigid away from 'singular configurations' that involve special alignments among the three agents (e.g., all three agents lying on a same line). When removing the active cardan joints of the equivalent virtual mechanism as they have no effect on the computation of the mobility of the passive chain (except for degenerated cases, i.e. singularities, see section 5), this formation is equivalent to a closed-loop mechanism composed of three passive cylindrical joints, as shown in Fig. 8(a). In a frame attached to the agent at O 1 , the unit twists defining the motion of the passive C joint between points O i and O j (i, j=1,2,3) are expressed as, when computed at O 1 :

ζ i1 = x j -x i y j -y i z j -z i 0 0 0 T (7) ζ i2 = ---→ O 1 O i × --→ O i O j T x j -x i y j -y i z j -z i T (8)
in which [x k y k z k ] T are the coordinates of the point O k in the frame attached to the agent at O 1 . In these vectors, the three first components represents the translational part of the twist while the three last components are associated with the rotational part. It is easy to see that the twist system ζ composed of the six twists ζ i1 and ζ i2 for i = 1, 2, 3 is of rank five. This twist system is the twist system of the serial chain obtained when opening the loop, thus the end-effector of the serial chain has five independent motions. Applying the formula [START_REF] Michieletto | Bearing rigidity theory in SE(3)[END_REF], knowing that each cylindrical joint has two independent motions, i.e. f i = 2, we thus have

m = ∑ i f i -p = 3 × 2 -5 = 1 (9)
which means that only a single degree of freedom of internal mobility exists for the virtual closed-loop system, or also that the formation is rigid as expected.

Case 2

Now, let us analyze a formation of four agents but in i.e. singularities, see section 5), this formation is equivalent to a closed-loop mechanism composed of four passive prismatic joints, as shown in Fig. 8(b). In a frame attached to the agent at O 1 , the unit twists defining the motion of the passive P joint between points O i and O j (i, j=1,2,3,4) are expressed as, when computed at O 1 :

ζ i = x j -x i y j -y i z j -z i 0 0 0 T . ( 10
)
It is easy to see that the twist system ζ composed of the four twists ζ i for i = 1, 2, 3, 4 is of rank three. This twist system is the twist system of the serial chain obtained when opening the loop, thus the end-effector of the serial chain has three independent motions. Applying the formula (6), knowing that each prismatic joint has one independent motion, i.e. f i = 1, we have

m = ∑ i f i -p = 4 × 1 -3 = 1 ( 11
)
which means that only a single degree of freedom of internal mobility exists for the virtual closed-loop system, or also that the formation is rigid. This is true as long as the four agents do not belong to the same plane, because in this case all P joints belong to the same plane and the corresponding twist system ζ i has a rank two, leading to a mobility m = 2 for the closed-loop chain, or a loss of rigidity for the formation. Note that, contrarily to the previous case, the interaction graph in Fig. 7(b) is not complete, and, therefore, formation rigidity cannot be concluded by a simple visual inspection of the graph (as in the previous case). The proposed mobility analysis is thus a possible simple alternative to, e.g., the numerical evaluation of the rank of the bearing rigidity matrix (as often done).

Singularity analysis

In this section, we used virtual kinematic chains defined thanks to the concept of hidden robot in order to analyze the singularities of different types of formations.

General conditions of singularity

Singularity of formations appears at some given configurations q of the agents for which the mobility of the formation is increased or, differently said, when the bearing rigidity matrix loses rank (thus, becoming lower than s N -(s + 1)). Locally, an additional internal motion of the formation is allowed, which is also the case for the virtual mechanism associated with the formation.

For a mechanism, these singularities are called Type 2 (or parallel) singularities [START_REF] Gosselin | Singularity analysis of closed-loop kinematic chains[END_REF] 2 . They appear when at least two solutions of the forward geometric model are identical [START_REF] Merlet | Parallel Robots[END_REF], or analogously, when the inverse Jacobian matrix J inv of the mechanism is rank deficient [START_REF] Merlet | Parallel Robots[END_REF]. Kinematically speaking, there exists a non-null vector t s defined such that J inv t s = 0 while q = 0, i.e. the actuators are fixed (which means that t s is in the null space of J inv ). Analytically characterizing the loss of rank of the matrix J inv by analyzing its determinant (if square) or its nullspace is almost unfeasible due to the mathematical complexity of the problem [START_REF] Merlet | Parallel Robots[END_REF]. However, as known in mechanics, if a rigid body has an uncontrollable motion, this means that it is not fully constrained by the system of wrenches applied on it, i.e. the static equilibrium is not ensured. As this uncontrollable motion appears only at a singularity, this means that locally the system of actuation wrenches, i.e. wrenches transmitted from the actuators to the platform by the legs, is degenerated. Analyzing the loss of rank of the system of wrenches is usually easier [START_REF] Merlet | Parallel Robots[END_REF].

For a given leg i, any actuation wrench denoted by ξ i j is reciprocal to the unit twists ζ ik characterizing the displacements of the passive joints [START_REF] Bonev | Geometric analysis of parallel mechanisms[END_REF], i.e. ξ T i j ζ ik = 0 for any j and k. This means that the virtual power developed by the wrench ξ i j along the direction of motion ζ ik is null; in other words, the actuator j of the leg i cannot transmit a wrench ξ i j to the platform along the direction

ζ ik .
In what follows, we consider some case studies for the analysis of the wrench system and its degeneracy. graph (for a total of six edges/bearing measurements). When removing the active cardan joints of the equivalent virtual mechanism, as they have no effect on the computation of the singularity of the passive chain, except for parameterizing the change in configuration of the virtual mechanism which is taken into account in the symbolic expression of the twists of the passive joints (see below), this formation is equivalent to a closed-loop mechanism composed of three passive prismatic joints, as shown in Fig. 10(a). In order to compute the singularity, one needs to:

• fix the displacement of one of the passive joints so that the internal motion can be suppressed: here we fix the motion of the joint between O 1 and O 2 • virtually open the loop between the remaining passive joints: here we open the loop at O 3 .

Thus, the studied mechanism is decomposed into two serial legs, each of them made of a single passive joint aligned along O i and O 3 . In a frame attached at agent O 1 , the unit twists defining the motion of the passive P joint between points O i and O 3 (i=1,2) are expressed as, when computed at O 3 , as:

ζ i = x j -x i y j -y i z j -z i 0 0 0 T . (12)
As a result, there exist five unit actuation wrenches ξ i j = [f T i j m T i j ] T which are reciprocal to ζ i . When expressed in the frame attached at agent O 1 , they are given by

ξ i1 = 0 0 0 1 0 0 T ( 13
)
ξ i2 = 0 0 0 0 1 0 T ( 14
)
ξ i3 = 0 0 0 0 0 1 T (15) ξ i4 = n T 0 0 0 T (16) ξ i5 = n × ---→ O i O 3 T 0 0 0 0 0 T (17)
in which n = ---→ O 1 O 3 × ---→ O 2 O
3 is a vector normal to the plane containing both prismatic joints. ξ i1 , ξ i2 and ξ i3 are pure moments around x W , y W and z W , respectively. ξ i4 and ξ i5 are pure forces along n and n × ---→ O i O 3 respectively. Considering now the complete system of wrenches ξ stacking all ten wrenches ξ i j for i = 1, 2 and j = 1 . . . 5, it can be seen that it is of full rank (i.e. of rank 6) as long as ---→ O 1 O 3 and ---→ O 2 O 3 are not colinear, i.e. points O 1 , O 2 and O 3 are aligned, which is indeed a well-known singularity of this formation (due to the alignment of the three agents on the same line).

Case 2

Let us consider the another formation of three agents in R 3 × S 1 with only four measurements Fig. 9(b) instead of six (as in the previous case). The passive equivalent virtual mechanism is equivalent to a closed-loop mechanism composed of three passive prismatic joints and two passive revolute joints of axis z W , as shown in Fig. 10(b). Here, we fix the displacement of one of the passive prismatic joints between O 1 and O 2 so that we can suppress the internal motion and we virtually open the loop between the remaining passive joints at O 3 . As a result, the studied mechanism is decomposed into two serial legs:

• one of them composed of a passive prismatic joint along O 1 and O 3 whose unit twist is denoted as ζ 1 , and followed by a passive revolute joint at O 3 and of axis z W whose unit twist is denoted as ζ 3 ; • the second one being composed of a passive revolute joint at O 2 and of axis z W whose unit twist is denoted as ζ 4 , followed by a passive prismatic joint along O 2 and O 3 whose unit twist is denoted as ζ 2 .

In a frame attached at agent O 1 , the unit twists defining the motion of the passive P joint between points O i and O 3 (i = 1, 2) are expressed as, when computed at O 3 :

ζ i = x j -x i y j -y i z j -z i 0 0 0 T (18)
while the twist defining the motions of the passive revolute joints are at O 3 :

ζ 3 = 0 0 0 0 0 1 T (19) ζ 4 = -(y j -y i ) x j -x i 0 0 0 1 T . (20)
The wrenches reciprocal to the chain O 1 O 3 twists (i.e. ζ 1 and ζ 3 ) are

ξ 11 = 0 0 0 1 0 0 T (21)
ξ 12 = 0 0 0 0 1 0 T ( 22
)
ξ 13 = -(y 3 -y 1 ) x 3 -x 1 0 0 0 0 T ( 23
)
ξ 14 = -(z 3 -z 1 ) 0 x 3 -x 1 0 0 0 T (24)
which are two pure moments around x W and y W , and two pure forces along [-(y 3y 1 )

x 3 -x 1 0] T and [-(z 3 - z 1 ) 0 x 3 -x 1 ] T ,
ξ 22 = 0 0 0 0 1 0 T (26) ξ 23 = -x 32 z 32 -y 32 z 32 x 2 32 + y 2 32 0 0 0 T ( 27
)
ξ 24 = y 32 -x 32 0 0 0 x 2 32 + y 2 32 T (28)
where x 32 = x 3x 2 , y 32 = y 3y 2 and z 32 = z 3z 2 . ξ 21 and ξ 22 are two pure moments around x W and y W , respectively, while ξ 23 is a pure force applied at O 3 of direction [-x 32 z 32y 32 z 32 x 2 32 + y 2 32 ] T and ξ 23 is a pure force applied at O 2 of direction [y 32x 32 0] T .

Considering now the complete system of wrenches ξ stacking all ten wrenches ξ i j for i = 1, 2 and j = 1 . . . 4, it can be seen that it is no more of full rank (i.e. of rank lower than 6) as long as: It is worth noting that, while the first two singularities are well-understood (see, e.g., [START_REF] Franchi | Modeling and control of uav bearing-formations with bilateral highlevel steering[END_REF]), the third one is less evident. An advantage of the proposed singularity analysis is, therefore, the possibility to identify all possible singularities of a given framework.

Other cases

Skipping all mathematical derivations, we introduce here other examples of singularity cases for the formation of four agents shown in Fig. 12 in the SE(2) and SE(3) configuration spaces (representative of planar agents and of fullyactuated agents in 3D). Using straightforwardly the methodology developed in section 3, the virtual mechanisms can be found for both configuration spaces. It should be mentioned that, in both examples, considering that the system made of agents O 1 , O 2 , O 3 is known to be bearing rigid, except if the agents are aligned, we can directly replace them in Fig. 13 by a rigid platform for an easier visualization.

In SE(2), the equivalent virtual mechanism is a 3 -RPR planar parallel robot depicted in Fig. 13(a). Singularities of this robot appear when at least three agents are aligned (well known case) or when all agents belong to the same circle (Fig. 14(a)) [START_REF] Tischler | A spatial extension of Cardanic movement: its geometry and some derived mechanisms[END_REF][START_REF] Chablat | Self motions of a special 3-RPR planar parallel robot[END_REF], which, to the best of our knowledge, is again a singular case not known in the community. In this case, the singularity leads to a self motion [START_REF] Karger | Classification of all self-motions of the original Stewart-Gough platform[END_REF], i.e. an infinity of possible configurations for the same measurements (Fig. 14(a)). In other words, it is impossible to reconstruct the pose for the set of given measurements because an infinity of solutions exists. This result can be extended to a system of n agents as shown in Fig. 15: if all n agents are on the same circle, we have the same type of self motion [START_REF] Briot | Revisiting the determination of the singularity cases in the visual servoing of image points through the concept of "hidden robot[END_REF][START_REF] Tischler | A spatial extension of Cardanic movement: its geometry and some derived mechanisms[END_REF].

In SE(3), the equivalent virtual mechanism is a 3 -UPS spatial parallel robot depicted in Fig. 13(b). Singularity of this robot appears when at least three agents are aligned (well known case) or when agent 4 belongs to the cylinder whose basis is the circumcircle to the three others (Fig. 14(b)) [START_REF] Briot | Revisiting the determination of the singularity cases in the visual servoing of image points through the concept of "hidden robot[END_REF][START_REF] Michel | Singularities in the determination of the situation of a robot effector from the perspective view of 3 points[END_REF] (which again, to the best of our knowledge, is not a singular configuration identified in existing literature). In this case, the singularity leads to a gained infinitesimal motion [START_REF] Briot | Revisiting the determination of the singularity cases in the visual servoing of image points through the concept of "hidden robot[END_REF], and also to the merging of two solutions of the forward kinematic problem. Observing a fourth agent as shown in Fig. 15 (for n = 5) leads to a 4 -UPS spatial parallel robot which still has some singularities (more complex to analyze but studied in [START_REF] Hamel | Riccati observers for the non-stationary PnP problem[END_REF]).

An illustration of the effect of the singularity on the rank of the bearing rigidity matrix associated with the formation of four drones given in Fig. 12 in Fig. 16. In this figure, we show the value of the 8-th smallest singular value of the bearing rigidity matrix when: (a) in SE( 2), when all agents belong to the same circle (gained finite motion, also called self motion)

• drones at O i (i = 1, 2, 3) have the configurations p 1 = [1 0 1] T , p 2 = [-0.5 0.866 1] T , p 3 = [-0.5 -0.866 1] T , R 1 = R 2 = R
O 1 O 2 O 3 O 4 (b) in SE(3)
, when agent 4 belongs to the cylinder whose basis is the circumcircle to the three others (gained infinitesimal motion) Fig. 14. Singularities of the formation in Fig. 12.

O 1 O 2 O 3 O n O 4 O n-1
Fig. 15. Rigid formation of n agents: agents 1 to n -1 are constrained to have a rigid formation by nature, agent n observes all agents, but they do not observe them.

It can be observed that, as previously discussed, the rank of the bearing rigidity matrix is decreased (i.e., the 8-th smallest singular value vanishes) when the fourth drone reaches the contour of the cylinder of singularity mentioned above. It can also be shown that the singularities of the formation shown in Fig. 12 (in SE(2) or in SE(3) but even in R 3 × S 1 ) disappear as soon as an additional bearing measurement is added to the formation, e.g. O 1 also measuring O 4 (except for the singularity occurring when at least three drones are aligned).

We finally wish to highlight an important remark: the reported singularities do not have the same impact for what concerns formation control and localization. For instance, in case a bearing-based decentralized localization algorithm is employed for recovering the pose of the agents from the measured bearings (see, e.g., [START_REF] Schiano | A rigidity-based decentralized bearing formation controller for groups of quadrotor UAVs[END_REF]), the localization algorithm would fail to converge in both the SE(2) and SE(3) cases studied above, since the rigidity matrix is rank deficient at the true robot configuration. However, while the SE(2) case is singular because an infinity of self-motions exist (and, thus, a unique pose cannot be recovered), the SE(3) case is singular because two solutions of the forward geometric model merge. In this case, one could still leverage existing analytical methods [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applicatlons to image analysis and automated cartography[END_REF][START_REF] Kneip | A novel parametrization of the perspective-three-point problem for a direct computation of absolute camera position and orientation[END_REF] which would allow to recover the correct pose of the agents despite the bearing rigidity matrix not being full-rank (and, thus, iterative algorithms, such as the one in [START_REF] Schiano | A rigidity-based decentralized bearing formation controller for groups of quadrotor UAVs[END_REF], would not converge). This then further shows the relevance of the proposed analysis for obtaining better insights into the properties and singularities of bearing formations.

Discussions

The case studies developed in this paper were mostly based on formations containing a single loop. Obviously, the approach can be extended to more general classes of problem (several loops). For this, it is necessary to split the problem into sub-classes, by splitting the graph into a given set of independent loops which should be analyzed independently. For instance, taking the graph in Fig. 12, we first need to analyze the mobility/singularity of the loop made of the three agents 1, 2 and 3, which is a rigid graph as long as the three agents are not aligned. Then analyzing the loop made of any set of three agents i, j and 4 (i, j = 1, 2, 3), one can see, in SE(2) or in SE [START_REF] Giordano | A passivity-based decentralized strategy for generalized connectivity maintenance[END_REF], that these loops have more than a single internal mobility. However, the entire mechanical system equivalent to all four agents is known to be fully actuated, so the formation is rigid.

The concepts presented in this paper are a basis of tools that can help solving more complex problems linked to formation control or cooperative localization, for instance:

• analyzing the mobility or singularities of formations including both distance and bearing measurements, knowing that distance measurements lead to the following equivalent kinematic chains:

-RPR chains in SE(2) equivalent to the one shown in Fig. 2 but with the revolute joints which are passive while the prismatic joint is active -RRPRR chains in R 3 × S 1 equivalent to the one shown in Fig. 3(a) but with the first revolute joint of the U joint at O i which is passive while the prismatic joint is active -SPS chains in SE(3) made of two passive spherical joints at points O i and O j , respectively, and an active prismatic joints between them.

• answering questions such as what is the minimal set of measurements for obtaining a (minimally) rigid formation.

These points are left as future works.

Conclusions

Research on formation control has attracted a large attention over the past years. A powerful theoretical framework for addressing control and localization issues is that of formation rigidity (developed both for distance and bearing measurements). Indeed, the tools from rigidity theory (and, in particular, the notion of infinitesimal rigidity) have been widely exploited in the community in order to, for instance, understanding what is the minimum number of measurements, geometrically characterizing the (infinitesimal) motions of a formation that preserve desired shapes, or even reconstructing the formation shape/pose from the local measurements. Formation rigidity depends on the topology of the sensing/communication graph but also on the spatial arrangement of the robots, since special configurations (singularity cases of the rigidity matrix), which are hard to detect in general, can cause a rigidity loss and, as a consequence, prevent convergence of formation control/localization algorithms based on formation rigidity.

In this paper, we have addressed these points by providing an alternative characterization of formation rigidity using tools from an apparently disconnected field: parallel robotics. We have shown that bearing rigid graphs can be given a physical interpretation related to virtual mechanisms, whose mobility and singularities can be analyzed and detected in an analytical way by using tools from the mechanical engineering literature (Screw theory, Grassmann geometry, Grassmann-Cayley algebra, and so forth). These tools offer a powerful alternative to the computation of the mobility and singularities w.r.t. the numerical evaluation of the spectrum of the bearing rigidity matrix (as often done), with which general conclusions are usually difficult to provide.

Examples of analytical computation of the mobility and singularities of classical and less classical formations have been provided for different agent models (planar/3D, fullyactuated and quadrotor-like), and (to the best of our knowledge) novel singularities for these cases have been illustrated. The impact of the singularities on the localization problem has also been also discussed, as well as the extension of our results to formations of agents with both distance and bearing measurements.

In conclusion, we believe that opening the multi-robot community to the (vast) literature developed by the parallel robotics community for dealing with mobility and singularity issues can be a major asset for better addressing the funda-mental problems of formation control and localization from onboard sensing. With this work, we aimed at showing the possible many benefits from such a cross-fertilization which, as discussed, ought to bring novel tools and insights into the design of control/localization algorithms for multi-robot systems.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Elementary edges in bearing rigidity graphs

Fig. 3 .

 3 Fig. 3. Virtual kinematic chains corresponding to the elementary edges for R 3 × S 1 . The dark-gray joints are the actuated joints.

Fig. 1 (

 1 Fig.1(b). With the two measurements, one cannot recover the distance between i and j but it is possible to obtain the relative orientation between the agents i and j. Mechanically speaking, the same type of information can be obtained with a kinematic chain made of a spatial UPU architecture (Fig.3(b)), meaning that the chain consists of an active cardan (or universal U) joint with the first axis along ζ 1 i j = z W and the second axis ζ 2 i j = z W ×

  Fig. 4. Virtual kinematic chains corresponding to the elementary edges for SE(3). The dark-gray joints are the actuated joints.

Fig. 5 .

 5 Fig. 5. Two connected edges in bearing rigidity graphs with four bearing measurements

R 3 ×

 3 S 1 and with the topology shown in Fig.7(b). When removing the active cardan joints of the equivalent virtual mechanism as they have no effect on the computation of the mobility of the passive chain (except for degenerated cases, four agents moving inR 3 × S 1

Fig. 7 .Fig. 8 .

 78 Fig. 7. Formations whose mobility is studied.

5. 2 Fig. 9 .

 29 Fig. 9. Rigid formations of three agents in R 3 × S 1 .

Fig. 10 .

 10 Fig. 10. Equivalent mechanical system.

21 =

 21 respectively. The wrenches reciprocal to the chain O 2 O 3 twists (i.e. ζ 2 and ζ 4 ) are ξ

• O 1 ,

 1 O 2 and O 3 aligned, which is a well known singularity of this formation, • points O 2 and O 3 are aligned along a vertical axis: in this case, O 1 can freely rotate around the line (O 2 O 3 ) (Fig. 11(a)), • points O 1 , O 2 and O 3 belong to an horizontal plane. In this case, the equivalent mechanism degenerates into the planar mechanism depicted in Fig. 11(b) which has an internal mobility of 2.

3 O 1 O 2 O 3 O ' 2 (Fig. 11 .

 3123211 Fig. 11. Equivalent planar mechanical systems when the three agents in the formation of Fig. 9(b) are in singularity.

O 1 O 2 O 3 O 4 Fig. 12 .Fig. 13 .

 2341213 Fig. 12. Rigid formation of four agents with 9 bearing measurements.

3 =

 3 I 3 (I 3 being the identity matrix), • drone at O 4 takes the configurations p 4 = [x y 0] T , R 4 = 1 3 for varying values of x and y.

10

 10

Fig. 16 .

 16 Fig. 16. Values of the 8th smallest singular value of the bearing rigidity matrix for the formation given in Fig. 12 in SE(3) when: (i) drones at O i (i = 1, 2, 3) have the configurations p 1 = [1 0 1] T , p 2 = [-0.5 0.866 1] T , p 3 = [-0.5 -0.866 1] T , R 1 = R 2 = R 3 = 1 3 (1 3 being the identity matrix), (ii) drone at O 4 takes the configurations p 4 = [x y 0] T , R 4 = 1 3 for varying values of x and y.

The loop can be opened everywhere, but in order to simplify the analysis, it is usually opened so that all kinematic chains have equivalent complexity.

We would like to mention that Type 1 (or serial) singularities are singularities equivalent to singularities of serial chains and have no effect on the computation of the singularities of the bearing rigidity matrix.

Acknowledgements

This work was supported by the projects PROMPT and RAPID funded by the RFI AtlanSTIC2020, and by the ANR, Project ANR-14-CE27-0007 SenseFly.