betaFeedback

WorksEngineering

Distributed Shaping of Robot Swarms Through Spatial Moments of Arbitrary Order

Abstract

This paper shapes a swarm into a target pattern, such as a figure taken from an image, by controlling its spatial moments. The image is sampled into a reference configuration whose centroid and covariance set the position and principal spreads of the formation, while its higher-order moments, expressed in covariance-normalized (whitened) coordinates, encode the remaining shape. In contrast with geometric formation control, which prescribes distances, bearings, or relative positions between specific agents, this specification concerns the swarm as a whole and assigns no agent to a particular place. The key mechanism is orthogonalization in the swarm's own empirical inner product: projecting negative-gradient velocities onto the complement of low-degree polynomials sampled at the agents makes every higher-order correction preserve all lower-order moments exactly. The resulting hierarchical controller has lower triangular error dynamics and converges locally exponentially for any positive gains, so orders can be added without undoing those already achieved. A joint alternative regulates the higher moments together through a regularized Gauss–Newton step while preserving the centroid and covariance dynamics. We give bounds on the number of agents and sufficient conditions for regularity. Both controllers admit a distributed implementation that uses only relative positions and neighbor communication and retains local exponential convergence when estimation is sufficiently fast. In a distributed simulation on a sparse graph, 350 agents form an airplane from an unstructured swarm through moments up to order ten; the hierarchy reaches the full specification, while the joint law approaches it with smaller velocities.

Introduction

Formation control usually prescribes where each agent should be relative to the others, through relative displacements, distances, bearings, or angles [1] [2, 3, 4, 5, 6]. Many collective tasks are instead specified by how the group is distributed in space: a sensing swarm may need to spread more along one direction than another, concentrate toward one side of a region, or take on a recognizable shape, such as a figure taken from an image, regardless of which agent occupies which location. Prescribing individual destinations then imposes agent-specific constraints that the task does not require, which raises the question of which collective quantities should serve as formation variables and how agent-level feedback can regulate them.

J. Chen and H. Garcia de Marina are with the Department of Computer Engineering, Automation, and Robotics, and the Institute of Mathematics (IMAG) at the University of Granada, Spain. E-mails: [email protected]; [email protected]. This work was supported by the ERC Starting Grant iSwarm (101076091) and the ERC Proof of Concept Grant Aerosense (101289893).

Distribution-level approaches answer this question in different ways (Table 1). Density-feedback methods drive the swarm with measured or estimated densities, using local density measurements [7], mean-field feedback [8], spatial-bin occupancies [15], or sample-point masses [16]. PDE-constrained optimization solves an optimal control problem for the density dynamics, yielding boundary actuation [9] or velocity fields that need neither online density estimation nor communication [10]. Both generate complex patterns but describe the target through a full density profile or its discretization. Moment-based control is a finite-dimensional alternative when the task specifies selected distributional features: moments are invariant to agent labeling and can be estimated through neighbor communication without reconstructing a density.

Early moment-based designs regulate first and second moments. Belta and Kumar [11] control a robot group through an abstraction given by its centroid, orientation, and covariance-based spread; Freeman et al. [12] and Yang et al. [13] estimate the first and second inertial moments by consensus while the agents drive them to prescribed values, with convergence conditions for the coupled estimation and control dynamics; and our dispersion formation control [17] regulates the covariance eigenvalues while preserving the centroid. Second-order descriptors, however, fix only the position, principal directions, and spreads. Centering the positions, expressing them along the principal axes, and normalizing each spread yields a whitened cloud with zero mean and identity covariance that these descriptors do not see: very different shapes, such as a Gaussian-like cloud and the airplane of Figure 1, can share exactly the same covariance.

Figure 1. From a target image to moment specifications. (a) Binary target image. (b) Reference configuration of N=350N=350 agents sampled from the image support, with its centroid (order one) and covariance (order two; ellipse at two standard deviations with principal axes). The dispersion controller u(2)u^{(2)} regulates the principal spreads λ∗\lambda^*; without a prescribed centroid (u(1)=0u^{(1)}=0), the position and orientation of the formation remain free, and the dashed ellipse is an equally valid placement. (c) Whitened reference w∗w^* with zero mean and identity covariance; its standardized moments S3∗,…,SK∗S_3^*,\ldots,S_K^* encode the remaining shape and are regulated by u(3:K)u^{(3:K)} without altering orders one and two.

Higher-order descriptors originate in image analysis, where an image is represented by its moments with respect to polynomial bases, such as Legendre and Zernike polynomials, that are orthogonal over the image domain [18], [19]. Liu et al. [14] transfer this representation to swarms: the Legendre or pseudo-Zernike moments of a target image are broadcast to the robots, and each robot follows the negative gradient of a weighted moment-error cost, estimated by a self-healing distributed estimator; this requires each robot to know its own absolute position in a common frame, provided by an external tracking system in the experiments, which achieve higher-order shapes with 50 robots under heavy packet loss. Alternatively, robots can be assigned to goal locations sampled from the target shape in a common frame, typically provided by external localization [20]–[22], or self-assemble through local rules [23]; assignment reproduces the target support precisely but ties each robot to a specific goal, whereas moment specifications prescribe a class of configurations rather than a unique one.

ApproachControl targetImplementationRequired informationArchitectureCross-order preservation
Density feedback [7], [8]Density profileDensity-error feedbackMeasured / estimated density; localization variesDistributed / mean-fieldNot explicitly enforced
PDE-constrained optimization [9], [10]Density profilePDE-constrained optimal controlDensity model; position for field execution1Global design; execution variesNot explicitly enforced
Second-order moment control [11]–[13]Centroid and covariance (inertial moments)Abstraction-based or gradient feedback; consensus estimationAbsolute positions in a common frame; neighbor messagesCentralized abstraction / distributedNo higher orders
Image-moment control [14]Higher-order image moments (Legendre, pseudo-Zernike) on a fixed domainGradient of weighted moment error; optimization-based estimationGlobal position in a common frame; neighbor messagesDistributed executionNot enforced; orders weighted empirically
Proposed moment-based controlFinite-order central moments, covariance-normalized; any dimensionProjected feedback; distributed estimationRelative positions in local frames with common orientation; neighbor messagesDistributed executionAll lower orders (hierarchical); centroid and covariance (joint)

Table 1. Comparison of distribution-level formation control approaches.

Regulating higher moments through agent velocities raises three difficulties. First, the orders are coupled: a velocity that corrects a third moment generally also changes the centroid and covariance. The bases in [14] are orthogonal over the continuous image domain, not over the finite set of agent positions, so a gradient step toward one order perturbs the others, and the orders are balanced by empirically tuned gains. Second, a finite swarm has finitely many velocity directions; once lower moments are preserved, a nonzero higher-order error may produce no corrective velocity, depending on the configuration and not only on the order (in the plane, for instance, full third-order regulation needs at least five agents). Third, moments are global quantities, and estimating them while the formation moves couples estimation errors to the motion; in [14], local stability is shown at full-rank equilibria with exact moments, and the coupled estimation and control dynamics are left for future work.

This paper addresses these difficulties while retaining the label-free moment specification. We define desired formations by realizable central moments through any finite order in arbitrary spatial dimension, normalized by the covariance and aligned by one common orthogonal transformation. Unlike moments evaluated in a fixed frame on a bounded domain, which prescribe absolute position, size, and orientation together with shape, this specification separates translation and principal spreads from higher-order shape and recovers the dispersion objective of [17] at order two. We project negative-gradient velocity directions onto the orthogonal complements of polynomial sample spaces, that is, we orthogonalize with respect to the swarm’s own empirical inner product rather than a fixed image domain. The resulting hierarchical controller preserves every lower-order moment exactly under each higher-order correction, so adding orders never undoes the dispersion or lower-order shape already achieved; its error dynamics are lower triangular and converge locally exponentially for any positive gains. A joint alternative regulates the selected higher moments together while preserving the centroid and covariance dynamics.

We give necessary bounds on the number of agents and sufficient polynomial-sampling conditions for regularity. Both controllers admit distributed implementation through a two-layer estimator that needs only relative-position measurements and neighbor communication, with no global positioning system, and a slow–fast analysis shows that they retain local convergence under sufficiently fast and accurate estimation and a smooth principal-frame realization. In a distributed simulation on a sparse communication graph, 350 agents form an airplane from an unstructured swarm through moments up to order ten; the hierarchy reaches the full moment specification, whereas the joint law approaches it with smaller velocities.

Section II formulates the problem, Section III develops the projected moment controllers, Section IV presents the distributed implementation, and Sections V and VI give numerical studies and conclusions.

Preliminaries and Problem Formulation

Notation

Let NN be the number of agents and dd the spatial dimension. Indices i,j∈{1,…,N}i,j \in\{1,\ldots,N\} identify agents. For a vector xi∈Rdx_i \in\mathbb{R}^d, (xi)a1(x_i)_{a_1} denotes its a1a_1-th coordinate, where a1∈{1,…,d}a_1 \in\{1,\ldots,d\}; the agent and coordinate indices are independent. We write x=(x1,…,xN)x = (x_1,\ldots,x_N) for a collection of agent vectors. Given one quantity fif_i per agent, i=1,…,Ni=1,\ldots,N, which may be a scalar, a vector, or a matrix, EN[f]:=N−1∑ifi\mathbb{E}_N[f] := N^{-1}\sum_i f_i denotes its entrywise average over the agents, and EN[f(x)]:=N−1∑if(xi)\mathbb{E}_N[f(x)] := N^{-1}\sum_i f(x_i) for a function ff evaluated at the agent vectors; these are finite averages, not probabilistic expectations. The symbols ⊤\top, IdI_d, 11, and ∥⋅∥\|\cdot\| denote transpose, the d×dd \times d identity matrix, the all-ones vector of the required dimension, and the Euclidean vector norm (also written ∥⋅∥2\|\cdot\|_2). For matrices AA and BB, A⊗BA \otimes B denotes their Kronecker product; for vectors, ⊗\otimes denotes the tensor product of Section II-C. For matrices of the same size, ⟨A,B⟩F:=tr⁡(A⊤B)\langle A,B\rangle_F := \operatorname{tr}(A^\top B) and ∥A∥F2:=⟨A,A⟩F\lVert A\rVert_F^2 := \langle A,A\rangle_F are the Frobenius inner product and squared norm. Here tr⁡\operatorname{tr} denotes the trace, and diag⁡(x)\operatorname{diag}(x) forms a diagonal matrix from a vector xx. For a symmetric matrix, A≻0A \succ0 (A⪰0A \succeq0) means positive (semi)definiteness. The orthogonal group is O(d):={Q∈Rd×d:Q⊤Q=Id}O(d) := \{Q \in\mathbb{R}^{d \times d}: Q^\top Q = I_d\}.

Graph Theory

The communication network is an undirected graph G=(V,E)\mathcal{G} = (\mathcal{V},\mathcal{E}), where V={1,…,N}\mathcal{V} = \{1,\ldots,N\} is the agent set and E\mathcal{E} is the edge set, with no self-loops. Agent ii has neighbors Ni:={j:(i,j)∈E}\mathcal{N}_i := \{j : (i,j) \in\mathcal{E}\}. The adjacency matrix A=[aij]∈RN×NA = [a_{ij}] \in\mathbb{R}^{N \times N} has aij=1a_{ij}=1 on edges and zero otherwise; the Laplacian is LG:=diag⁡(A1)−AL_{\mathcal{G}} := \operatorname{diag}(A\mathbf{1})-A. It is symmetric positive semidefinite and satisfies LG1=0L_{\mathcal{G}}\mathbf{1}=0. If G\mathcal{G} is connected, its nullspace is ker⁡LG=span⁡{1}\ker L_{\mathcal{G}} = \operatorname{span}\{\mathbf{1}\} and its second-smallest eigenvalue satisfies λ2(LG)>0\lambda_2(L_{\mathcal{G}})>0. The distributed implementation in Section IV uses a fixed connected graph. We also allow symmetric positive edge weights aij=ajia_{ij}=a_{ji}, with the same Laplacian formula and properties.

From matrices to tensors

Each covariance entry averages a product of two position coordinates, or simply coordinates for short, so the covariance needs two indices and is a matrix. A third-order moment averages products of three coordinates and needs three indices; an order-mm moment needs mm. Tensors are the arrays that hold such data. An order-mm tensor TT over Rd\mathbb{R}^d has entries Ta1⋯amT_{a_1\cdots a_m}, where each index aℓ∈{1,…,d}a_\ell\in\{1,\ldots,d\} selects a coordinate; the array has dmd^m entries, and indices may repeat. These coordinate indices are unrelated to the agent index ii. Vectors and matrices are tensors of orders one and two.

Tensor powers. The tensor product multiplies entries: for x,y∈Rdx,y \in\mathbb{R}^d, (x⊗y)a1a2=(x)a1(y)a2(x \otimes y)_{a_1a_2} = (x)_{a_1}(y)_{a_2}, so x⊗y=xy⊤x \otimes y = xy^\top. Repeating it gives the tensor power

(x⊗m)a1⋯am=∏ℓ=1m(x)aℓ.(x^{\otimes m})_{a_1\cdots a_m} = \prod_{\ell=1}^{m}(x)_{a_\ell}.

whose entries are all products of mm coordinates of xx. The average EN\mathbb{E}_N applies entrywise to tensors as well. Thus, for the centered (barycentric) positions ziz_i of Section II-D, the covariance is EN[zz⊤]=EN[z⊗z]\mathbb{E}_N[zz^\top] = \mathbb{E}_N[z \otimes z], and the order-mm moment is EN[z⊗m]\mathbb{E}_N[z^{\otimes m}]. As a running example, take d=2d=2, m=3m=3, and x=(1,2)⊤x=(1,2)^\top. Fixing the last index of T:=x⊗3T:=x^{\otimes3} displays it as two 2×22 \times2 slices, T::a3T_{::a_3} with entries (T::a3)a1a2=Ta1a2a3(T_{::a_3})_{a_1a_2}=T_{a_1a_2a_3}:

T::1=(1224),T::2=(2448).T_{::1}=\begin{pmatrix}1&2\\2&4\end{pmatrix},\qquad T_{::2}=\begin{pmatrix}2&4\\4&8\end{pmatrix}.

Each entry equals 2k2^k, where kk is the number of indices equal to 2; e.g., T122=4T_{122}=4.

Symmetry. A tensor is symmetric if permuting its indices leaves its entries unchanged, as for x⊗mx^{\otimes m} and for every moment tensor. An entry of a symmetric tensor depends only on how many times each coordinate appears among its indices, so the space Sym⁡m(Rd)\operatorname{Sym}^m(\mathbb{R}^d) of symmetric tensors has (d+m−1m)\binom{d+m-1}{m} independent entries. For d=2d=2 this count is m+1m+1: in the example, T111=1T_{111}=1, T112=T121=T211=2T_{112}=T_{121}=T_{211}=2, T122=T212=T221=4T_{122}=T_{212}=T_{221}=4, and T222=8T_{222}=8.

Inner products and norms. For tensors T,UT,U of the same order, the Frobenius inner product and norm extend the matrix definitions:

⟨T,U⟩F=∑a1,…,am=1dTa1⋯amUa1⋯am,∥T∥F2=⟨T,T⟩F.\langle T,U\rangle_F=\sum_{a_1,\ldots,a_m=1}^{d}T_{a_1\cdots a_m}U_{a_1\cdots a_m},\qquad\lVert T\rVert_F^2=\langle T,T\rangle_F.

References

  1. [1]K.-K. Oh, M.-C. Park, and H.-S. Ahn, “A survey of multi-agent formation control,” Automatica, vol. 53, pp. 424–440, 2015.DOI

Paper details

vlnc:W_wqjarss7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Engineering

Not recorded for this paper

View statement
Looking for related papers…
Contents