Distributed Consensus for Metamorphic Systems Using a GossipAlgorithm for CAT(0) Metric Spaces ^†

Abstract

We present an application of distributed consensus algorithms to metamorphic systems. A metamorphic system is a set of identical units that can self-assemble to form a rigid structure. For instance, one can think of a robotic arm composed of multiple links connected by joints. The system can change its shape in order to adapt to different environments via reconfiguration of its constituting units. We assume in this work that several metamorphic systems form a network: two systems are connected whenever they are able to communicate with each other. The aim of this paper is to propose a distributed algorithm that synchronizes all of the systems in the network. Synchronizing means that all of the systems should end up having the same configuration. This aim is achieved in two steps: (i) we cast the problem as a consensus problem on a metric space; and (ii) we use a recent distributed consensus algorithm that only makes use of metrical notions.

1. Introduction

Many problems in robotics, computer science and biology involve systems that can be described as reconfigurable or metamorphic. These systems change their state through a set of local rules, and in order to move from a given State A to another given State B, the system has to determine the sequence of local moves that it should perform. Examples of such systems are: metamorphic manufacturing systems [1], phylogenetic trees [2] and metamorphic robots [3].

The examples we will deal with in this paper will be about metamorphic robots, which consists of a collection of individual modules that can connect/disconnect from each other and form a rigid structure, referred to as a configuration or a state. Individual modules can change their position relative to their neighbors, as long as the whole system remains connected and according to a set of local rules. This allows the system to dynamically change its configuration and position. We assume here that we have many identical metamorphic robots that are able to communicate with each other and share information about their respective states. These robots form a communication network that we will assume to be decentralized (i.e., without a central fusion node). We are interested in the problem of distributed consensus among metamorphic systems: each system is in its own initial state, and we would like all of them to end up in a common configuration.

Distributed consensus algorithms have been thoroughly studied, mainly in the cases of vector data [4–6] or ordered data (e.g., [7]). The algorithm in [5], for example, is a distributed algorithm that uses pairwise arithmetic averages of the data. However, without specific assumptions, configurations cannot be averaged. The algorithm presented in [7] relies on pairwise maximum computations. In the setting of metamorphic robots, however, configurations cannot be easily ordered, hence the need to find an appropriate framework.

In [8,9], the authors introduce a mathematical framework for analyzing metamorphic systems based on embedding the state space—the space of all possible states of a given metamorphic system—into a continuous space. This embedding, called the state complex is well suited to a recent consensus algorithm [10] that relies on pairwise midpoint computations. Indeed, the state complex can be equipped with an adequate metric, so as to yield a CAT(0) metric space. Hence, the main contribution of this paper is to propose a distributed consensus algorithm that provably converges and is well adapted to the state space of metamorphic systems.

The paper is organized as follows. The first section details the mathematical background underpinning the metamorphic systems state space embedding, as well as gives a formal description of the consensus problem. The second section exposes the random pairwise midpoint algorithm. Section 3 explains how to compute the midpoint of any two points in a cubical complex. Finally, Section 4 provides numerical simulations for the proposed consensus algorithm.

2. Framework

2.1. Metamorphic Systems: Definition and Examples

There are many examples of metamorphic/reconfigurable systems, such as reconfigurable manufacturing systems [1] and phylogenetic trees [2]. Another example, one in which we will be more interested in this paper, is that of metamorphic robots, which were described by Østergaard et al. in [11] as robotic systems:

• That consist of several identical and physically independent unit modules;
• For which its modules can be connected to each other in many possible ways in order to form rigid structures;
• For which its modules can disconnect and reconnect while the system is active;
• For which it can change the way its modules are connected, i.e., it is fully automatic.

Some of these robots are lattice-based, meaning that the robotic modules occupy a discrete set of possible positions, this set of possible positions forming a lattice. The nature of the lattice depends on the geometry of the modules: it can be hexagonal, squared, dodecahedral, etc. These metamorphic systems can be mathematically described as a collection of states on a graph (see Appendix A).

Representing the various states of a metamorphic system by their lattice configuration will prove to be insufficient for finding a simple consensus protocol. Indeed, the lattice representation does not provide an ordering of states. Following [8], we represent a system configuration as a point in a cubical complex $\mathcal{S}$, called the state complex (see, also, Appendix B for a definition). The zero-dimensional skeleton of this complex is the set of states, and two vertices are linked by an edge if their corresponding states differ by a single action of a generator (see Appendix A). A k-cube of the complex represents k commutative movements, i.e., movements that are non-overlapping whatever their order (see [8] for a rigorous definition).

An example of a metamorphic system is the robotic arm, which consists of attached links, inside a grid with one of its extremities attached to the base point (0, 0) of the grid (see Figure 1).

We assume in this work that the metamorphic systems form a network; two systems are connected whenever they are able to communicate with each other. The aim is to synchronize all of the systems that compose the network, i.e., all of the systems should have the same configuration, as shown in the example of Figure 2.

Having described the model chosen for metamorphic systems, we next review the mathematical framework of the consensus problem.

2.2. Framework of the Consensus Problem

2.2.1. Network

Following the approach of [5], we model the network of metamorphic systems by a connected graph G = (V, E) with vertices V representing the metamorphic systems (agents) and whose edges E represent the communication links between these agents. We assume the graph to be undirected, which means that if an agent can communicate with another agent, then the converse is also true; this hypothesis is not too unrealistic if we suppose that all of the agents are identical and that the movement speed of the agents is very small compared to their communication speed. When a communication link exists between two agents, we say that the two agents are neighbors. We denote by $\mathcal{N}$(v) the set of all neighbors of the agent v ∈ V.

As in [5], we assume that the time model is asynchronous, i.e., that each agent has its own Poisson clock that ticks with a common intensity λ (the clocks are identically made), and moreover, each clock is independent of the other clocks. When an agent clock ticks, the agent is able to perform some computations and wake up some neighboring agents. This time model has the same probability distribution as a global single clock ticking with intensity Nλ and selecting uniformly randomly a single agent at each tick. This equivalence is described, e.g., in [5]. Notice also that link e = {v, w} is not necessarily used by agents v and w at a given time: v or w might not be awakened.

2.3. Communication

At a given time k, we denote by V_k the agent whose clock ticked and by W_k the neighbor that was in turn awaken. Therefore, at time k, the only communicating agents in the whole network are V_k and W_k. A single link is then active at each time; hence, at a given time, most links are not used. We assume that (V_k, W_k) are independent and identically distributed and that the distribution of V_k is uniform over the network, while the distribution of W_k is uniform in the neighborhood of V_k. More precisely, the probability distribution of (V_k, W_k) is given by:

$$\mathbb{P}[V_k=v,W_k=w]=\{\begin{array}{ll}\frac{1}{N}\frac{1}{\mathrm{deg}(v)}\hfill & \mathrm{if}v~w\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$$

Notice that this probability is not symmetric in (v, w). It is going to turn out to be convenient to also consider directly the link {V_k, W_k}, forgetting which node was the first to wake up and which node was second. In this case, $\mathbb{P}[\{V_k,W_k\}=\{v,w\}]$ is of course symmetric in (v, w). One has:

$$\mathbb{P}[\{V_k,W_k\}=\{v,w\}]=\{\begin{array}{ll}\frac{1}{N}(\frac{1}{\mathrm{deg}(v)}+\frac{1}{\mathrm{deg}(w)})\hfill & \mathrm{if}v~w\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$$

The communication framework considered here is standard [5].

2.3.1. Data Space

Each node v ∈ V can store a value $x_v\in \mathcal{S}$ that lies in a cubical complex $\mathcal{S}$ (see Appendix B).

We assume that the cubical complex is equipped with the metric d induced from the Euclidean metric on each cube. The skeleton of the complex is a metric graph called the transition graph and is denoted.

Initially, each node v has an initial value x_v(0), and X₀ = (x₁(0),…, x_N(0)) is the tuple of initial values. A consensus state has the form X_∞ = (x_∞,…, x_∞) with: $x_{\infty }\in \mathcal{S}$. We denote by x_v(k) the value stored by the agent v ∈ V at time k and X_k = (x₁(k),…, x_N(k)) the global state of the system at that instant.

We want to apply a distributed algorithm in order to achieve the consensus state. $(\mathcal{S},d)$ being a metric space, a candidate algorithm could be the average pairwise midpoint [10] algorithm. This algorithm requires $(\mathcal{S},d)$ to be a CAT(0) metric space.

Definition 1. Let (M, d) be a metric space. A geodesic curve c in X is a map c : [0, l] → X from a closed interval I = [0, l] to X, such that, for all t.t′ ∈ I:

$$d(c(t),c(t^{\prime }))=|t-t^{\prime }|$$

A metric space is said to be geodesic if and only if, for any two points x, y ∈ X, there exists a geodesic c : [0, l] → X, such that c(0) = x and c(l) = y.

Definition 2 (CAT(0) inequality). Assume (X, d) is a geodesic metric space (a metric space in which any two points can be related by a geodesic) and Δ = (c₀, c₁, c₂) is a geodesic triangle with vertices p = c₀(0), q = c₁(0) and r = c₂(0). Let$\overline{\mathrm{\Delta }}=(\overline{p},\overline{q},\overline{r})$ denote a comparison triangle (a triangle with the same edge lengths as Δ) in the Euclidean space${ℝ}^2$. Δ is said to satisfy the CAT(0) inequality if, for any x = c₀(t) and y = c₂(t′), one has:

$$d(x,y)\le \overline{d}(\overline{x},\overline{y})$$

where$\overline{x}$ is the unique point of$[\overline{p},\overline{q}]$, such that$d(p,x)\le \overline{d}(\overline{x},\overline{y})$, and$\overline{y}$ on$[\overline{p},\overline{r}]$, such that$d(p,y)=\overline{d}(\overline{p},\overline{y})$.

A geodesic metric space is said to be locally CAT(0) if any geodesic triangle of sufficiently small perimeter verifies the CAT(0) inequality. It is said to be globally CAT(0) if any geodesic triangle verifies the CAT(0) inequality.

For a thorough introduction to the subject, see [12,13].

Any state complex can be shown to be a locally CAT(0) space [14]. The global CAT(0) proprietyrequires an additional constraint on the state complex. In [14], a combinatorial criterion based on the notion of posets with inconsistent pairs is provided to verify whether a state complex is globally CAT(0).

Assumption 1. We shall make the fundamental assumption that the state complex of any metamorphic system involved in this paper is globally CAT(0). This assumption, while restrictive, still covers many interesting examples, like the robotic arm [3], phylogenetic trees [2], the hexagonal system [8], etc.

The following proposition links the existence and uniqueness of geodesics and midpoints with the CAT(0) property:

Proposition 1. If x and y are two points in a globally CAT(0) space X, then there is but one geodesic γ : [0, 1] → X, such that γ(0) = x and γ(1) = y, which we will denote from now on as [x, y]. The midpoint of x and y is defined as$\langle \frac{x+y}{2}\rangle :=[x,y]\left(\frac{1}{2}\right)$ and is always well defined and unique.

Now that the working framework is set (connected and undirected communications graph, Poisson clocks, data space, etc.), we will propose in the next section a consensus algorithm based on the gossip protocol [5] adapted to CAT(0) metric spaces.

3. Algorithm

3.1. Description

In this section, we expose a distributed algorithm that relies on distributed midpoint computation in $\mathcal{S}$ to drive a system of identical metamorphic systems into a consensus configuration—the random pairwise midpoint algorithm [10]—which works as follows: At each count of the virtual global clock, one node v is selected uniformly randomly from the set of agents V. The node v then randomly selects a node w from the neighbors of v in the communications graph. Both node v and w then compute and update their value to $\langle \frac{x_v+x_w}{2}\rangle$.

This algorithm is well defined, since for any couple of points $x,y\in \mathcal{S}$, their midpoint exists and is unique. This is due to the fact that $\mathcal{S}$ is a globally CAT(0) space.

Algorithm 1. Random Pairwise Midpoint.

Input: a graph G = (V, E) and the initial nodes configuration Xv(0), v ∈ V for all k > 0 do

At instant k, uniformly randomly choose a node Vk from V and a node Wk uniformly randomly from $\mathcal{N}(V_k)$.

Update:

$X_{V_k}(k)=\langle \frac{X_{V_k}(k-1)+X_{W_k}(k-1)}{2}\rangle$

$X_{W_k}(k)=\langle \frac{X_{V_k}(k-1)+X_{W_k}(k-1)}{2}\rangle$

Xv (k) = Xv (k − 1) for v ∉ {Vk,Wk}

end for

Algorithm 1. Random Pairwise Midpoint.

Input: a graph G = (V, E) and the initial nodes configuration Xv(0), v ∈ V for all k > 0 do

At instant k, uniformly randomly choose a node Vk from V and a node Wk uniformly randomly from $\mathcal{N}(V_k)$.

Update:

$X_{V_k}(k)=\langle \frac{X_{V_k}(k-1)+X_{W_k}(k-1)}{2}\rangle$

$X_{W_k}(k)=\langle \frac{X_{V_k}(k-1)+X_{W_k}(k-1)}{2}\rangle$

Xv (k) = Xv (k − 1) for v ∉ {Vk,Wk}

end for

This algorithm belongs to the class of consensus protocols, which has been shown to achieve convergence towards a consensus state in [15]; the convergence rate is established as linear in [10]. This assumes, however, that it is possible to compute the midpoint of any two points with reasonable complexity. While there is no closed expression for the midpoint of any two points in $\mathcal{S}$, there is a procedure described in the next section that permits the computation of the midpoint.

4. Computing the Midpoint

In [16], an algorithm is given for computing means and medians in general CAT(0) metric spaces; we are here interested in finding the midpoint $\langle \frac{x+y}{2}\rangle$ of any two given points x and y of a CAT(0) cubical complex $\mathcal{S}$, so we first determine the geodesic [x, y] between x and y.

Let x = (x₁ … x_N) and y = (y₁ … y_N) be the coordinates of x and y in the current standard embedding of $\mathcal{S}$ in ${\mathbb{Z}}^N$ (see Appendix C for an exposition of the standard embedding).

Then, we define v = (v₁,…, v_N) and w = (w₁,…, w_N), such that for i ∈ {1,…, N}:

$$\{\begin{array}{ll}{v}_i=0\hfill & \mathrm{if}{x}_i\le 0.5\hfill \\ v_i=1\hfill & \mathrm{if}{x}_i>0.5\hfill \end{array}$$

Additionally:

$$\{\begin{array}{ll}{w}_i=0\hfill & \mathrm{if}{y}_i\le 0.5\hfill \\ w_i=1\hfill & \mathrm{if}{y}_i>0.5\hfill \end{array}$$

v and w are, respectively, the closest vertices of $\mathcal{S}$ to x and y (see Figure 3).

Next, we re-root the cubical complex at v and change the labeling of its vertices consequently, as well as the coordinates of x and y. To obtain the new coordinates of any point a = (a₁,…, a_N) in the new standard embedding, we update: a_i,new = 1 − a_i,old if v_i = 1 and a_i,new = a_i,old if v_i = 0 (see Figures 3 and 4).

We denote by I_w = {i ∈ {1,…N}|w_i = 1}, the order ideal associated with the vertex w. Now that the complex is re-rooted, we need to find the cubical sequence that contains the geodesic between x and y. According to [14], a valid sequence (C_k)_1≤k≤n = (I_k, M_k)_1≤k≤n of cubes containing the geodesic, consists of a sequence of order ideals I₁ ⊂ I₂ ⊂ ⋯ ⊂ I_n = I_w and maximal antichains M_k ⊂ I_k, 1 ≤ k ≤ n (see Appendix B for the representation of individual cubes of a complex). To find this sequence, we take the subset of minimal elements of I_w and I₁, and set M₁ = I₁. Then, in order to form C_k = (I_k, M_k) from C_k−1 = (I_k−1, M_k−1), we take the subset of minimal elements m_k of Q−I_k−1, put I_k = I_k−1 ∪ m_k and let M_k be the maximal antichain of I_k. Using this procedure until I_k = P, we obtain a valid cube sequence, which contains the geodesic. In the example of Figures 3 and 4, we have: I₁ = {2, 3}, M₁ = {2, 3} and I₂ = {2, 3, 4}, M₂ = {2}.

After the cube sequence has been determined, we then have to find the ‘breakpoints’ from which the geodesic passes. The points {p₁,…, p_n−1} are such that: ‖x − p₁‖ + ‖p₁ − p₂‖ + ⋯ + ‖p_n−1 − p_n‖ + ‖p_n − y‖ is minimal and that for each k ∈ {1,…, n − 1} p_k ∈ F_k with F_k being the common frontier of (I_k, M_k) and (I_k+1, M_k+1), which is the cubical cell (I_k, M_k ∩ M_k+1). This problem can be cast as a touring problem with n polyhedral regions and 2n facets [14].

$$\begin{array}{c}\min t_0+t_1+\cdots +t_n\\ \forall k\in \{0\dots n\}:t_k\ge \parallel p_k-p_{k+1}\parallel \\ p_k\in F_k,k=1\dots n\\ p_0=x,p_{n+1}=y\end{array}$$

The touring problem is a second order cone optimization problem, for which numerical solvers exist. We solve the touring problem and obtain a series of points p₁…p_n and the distances t₁…t_n−1 between p_k and p_k+1 (see Figure 5).

Knowing the sequence of points (p_i)_1≤i≤n and distances (t_i)_0≤i≤n, we want to determine the midpoint of x and y; we have two cases:

Case 1: n > 0.

First, we determine the cubical cell of (C_k)_1≤k≤n+1 that contains the midpoint. Let $i_0=\min \{1\le i\le n|d(x,p_i)\ge \frac{d(x,y)}{2}\}$; then, we have: $\langle \frac{x+y}{2}\rangle \in C_{i_0}$ and $\langle \frac{x+y}{2}\rangle \in \left[p_{i_0},p_{i_0+1}\right]$. Using the convention p₀ = x and p_n+1 = y, the analytic expression of $\langle \frac{x+y}{2}\rangle$ is:

$$\langle \frac{x+y}{2}\rangle =p_{i_0}+\frac{D}{t_{i_0}}(p_{i_0+1}-p_{i_0})$$

with:

• $D=\frac{1}{2}\left|{\displaystyle \sum {}_{k=0}^{i_0-1}{t}_k-{\displaystyle \sum {}_{k=i_0+1}^{n+1}{t}_k-t_{i_0}}}\right|:\mathrm{If}2\le i_0\le n-1$.
• $D=\frac{1}{2}{t}_{i_0}:\mathrm{If}{i}_0=1$.
• $D=\frac{1}{2}\left|t_{i_0}-{\displaystyle \sum {}_{k=0}^{i_0-1}{t}_k}\right|:\mathrm{If}{i}_0=n$.

Case 2: n = 0.

In this case, x and y belong to the same cubical cell, and we have: $\langle \frac{x+y}{2}\rangle =\frac{x+y}{2}$.

5. Numerical Results

In this section, we apply the previously described algorithm to two examples of a lattice-based metamorphic systems, the robotic arm, and the hexagonal lattice robot.

To understand why the robotic arm is CAT(0), one must construct a poset with inconsistent pairs associated with the state complex of the arm (see Appendix B.2).

Definition 3. Define for any robotic arm with n articulations R_n the set P_n = {(x, y)|y ≥ 0, y ≤ x, x ≤ n − 1}, and define the partial order relation ≤, such that (x₁, y₁) ≤ (x₂, y₂) if and only if x₁ ≤ x₂ and y₁ ≤ y₂.

Using the partially ordered set P_n, we can show that the state complex of R_n is CAT(0) through the following proposition:

Proposition 2. [3] Let${\mathcal{S}}_n$ be the cubical complex of R_n rooted at the state where the arm is completely horizontal.

Then, there is a bijection between the possible states of R_n and the order ideals of P_n.

We analyze the convergence of the pairwise midpoint algorithm using as a criterion the variance function:

Definition 4. Given a configuration$x=(x_1,\dots ,x_N)\in {\mathcal{S}}^N$, the variance function is defined as:

$${\sigma }^2(x)=\frac{1}{N}{\displaystyle \sum _{\{v,w\}\in {\mathrm{P}}_2(V)}{d}^2(x_v,x_w)}$$

where d is the distance between two points in$\mathcal{S}$

If σ²(x) = 0, then x₁ = x₂ ⋯ = x_N, and we have achieved a consensus state. In [10], it is proven that for a sequence of points X(k) = (x₁(k),…, x_N(k)) generated according to the pairwise midpoint algorithm, the function σ² converges to zero at a linear rate.

Theorem 1. Let X_k = (x₁(k),…, x_N(k)) denote the sequence of random variables generated by Algorithm 1; then, there exists L < 0, such that,

$$\underset{k\to \infty }{\lim \sup }\frac{\log \mathrm{E}[\sigma (X_k)]}{k}\le L$$

In order to randomly sample a set of initial coordinates, we begin by assigning to each metamorphic system a vector (x₁,…, x_N), where each x_i is sampled randomly and uniformly from the interval [0, 1]. Then, we do the following: we check if there exists i, j, such that i ≺ j and x_j ≠ 0; if so, then set x_i = 1 (the ≺ relation being the partial order of the poset associated with the cubical complex $\mathcal{S}$ in its initial rooting).

5.1. Results for the Robotic Arm

We plot the log-variance log σ² as a function of the number of iterations k, for a complete graph of 10 robotic arms of n = 7 joints (see Figure 6), then for a path graph of 10 robotic arms of the same type. In both cases, we observe in Figure 7 a linear curve with a negative slope in accordance with the results of [10]. In the case of the path graph, however, the slope is smaller than for the complete graph.

5.2. Results for the Planar Hexagonal Lattice

The same analysis is applied to the hexagonal lattice system [8], which is a connected aggregate of hexagonally-shaped modules that occupy a planar lattice. Its graph representation and associated cubical complex can be seen in Figure 8.

We observe similar patterns as for the robotic arms experiment; in Figure 9 the function log σ² decreases at a linear rate for both the complete graph and the path graph cases.

6. Conclusions

The random pairwise midpoint algorithm can be successfully applied to discrete combinatorial systems, like the case of metamorphic systems. This is a non-trivial example of a purely metric application of this algorithm, whose exponential convergence towards a consensus state has been confirmed through numerical experiments on two examples of metamorphic systems. The same method could be applied to the space of phylogenetic trees. Another application could be that of distributed optimization, where N identical metamorphic systems, each with its own utility function $f_i:\mathcal{S}\to ℝ:i\in \{1,\dots ,N\}$, try to minimize a collective objective function $\frac{1}{N}{\displaystyle \sum {}_{i=1}^N{f}_i}$; the underlying communication network has no fusion node.