PaperlayerView exact revision on arXiv

Source-linked AI summary

Undirected Rigid Formations are Problematic

Shaoshuai Mou, A. Stephen Morse, Mohamed Ali Belabbas, Zhiyong Sun, Brian D. O. Anderson

arXiv:1503.00812v1eess.SYcs.MAcs.SY

TL;DR

This paper asks how undirected rigid formations behave when neighboring agents disagree about desired or sensed distances, rather than matching distance information exactly. It analyzes these mismatches and reports that, for planar formations of at least three agents, the distorted rigid formation almost surely converges exponentially to a circular orbit traversed at constant angular speed.

  • Problem

    The paper examines how small disagreements in neighboring agents' desired distances—or their estimates of actual distances—affect undirected rigid formations.

    Source: §I · p. 3

  • Method

    The paper analyzes the formation dynamics under mismatched desired distances using an error-system framework.

    Source: §I · p. 3, B. Non-Equilibrium Analysis · p. 36

  • Results

    For planar rigidity-based undirected formations with at least three agents, the distorted rigid formation almost surely converges exponentially to a closed circular orbit traversed at constant angular speed.

    Source: §I · p. 3

  • Takeaways & Limitations

    Distance disagreement can produce persistent periodic motion rather than only the gradual distortion expected as mismatches increase.

    Source: §I · p. 3

    The authors state that Theorem 5 requires an assumption, while conjecturing that it may be unnecessary.

    Source: §VI · p. 38

Abstract

from arXiv · show

By an undirected rigid formation of mobile autonomous agents is meant a formation based on graph rigidity in which each pair of "neighboring" agents is responsible for maintaining a prescribed target distance between them. In a recent paper a systematic method was proposed for devising gradient control laws for asymptotically stabilizing a large class of rigid, undirected formations in two dimensional space assuming all agents are described by kinematic point models. The aim of this paper is to explain what happens to such formations if neighboring agents have slightly different understandings of what the desired distance between them is supposed to be or equivalently if neighboring agents have differing estimates of what the actual distance between them is. In either case, what one would expect would be a gradual distortion of the formation from its target shape as discrepancies in desired or sensed distances increase. While this is observed for the gradient laws in question, something else quite unexpected happens at the same time. It is shown that for any rigidity-based, undirected formation of this type which is comprised of three or more agents, that if some neighboring agents have slightly different understandings of what the desired distances between them are suppose to be, then almost for certain, the trajectory of the resulting distorted but rigid formation will converge exponentially fast to a closed circular orbit in two-dimensional space which is traversed periodically at a constant angular speed.

I. INTRODUCTION

The section studies undirected rigidity-based formations under neighboring agents’ disagreements about desired or sensed distances, and defines the rigidity criteria used to focus on infinitesimally rigid frameworks. It also reports that small desired-distance mismatches can lead formations of three or more agents to converge exponentially to constant-speed circular motion.

I. INTRODUCTION

  • For rigidity-based undirected formations of type with at least three agents, slight neighboring disagreements about desired distances almost for certain lead the distorted rigid formation to exponentially fast convergence to a periodically traversed closed circular orbit in IR2 at constant angular speed.Source: §I · p. 3

A. Organization

  • The paper develops a local error-system analysis and a square subsystem to explain when mismatch errors yield rotating formations and how the overall state converges to circular motion.The error system is locally exponentially stable for sufficiently small mismatch, and, under stated initial-state conditions, the overall error converges exponentially to its equilibrium output; the square subsystem is linear along trajectories with constant error-system output.Source: A. Organization · pp. 3–4

B. Graph Rigidity

  • A framework pairs points in IR2 with an undirected graph; rigidity means the points cannot be slightly deformed while keeping edge lengths constant.Translations and rotations preserve shape, and frameworks with the same edge lengths are equivalent, while rigidity is defined by resistance to small deformations preserving those lengths.Source: B. Graph Rigidity · pp. 4–5
  • Infinitesimal rigidity requires rank R(x)=2n−3; generic frameworks are rigid exactly when infinitesimally rigid, though the converse does not hold for all frameworks.Infinitesimally rigid frameworks are rigid, but examples show that rigid frameworks need not be infinitesimally rigid.Source: B. Graph Rigidity · p. 5
  • Laman’s Theorem provides a combinatorial test for graph rigidity, and a graph is called rigid if some placement yields a generically rigid framework.Source: B. Graph Rigidity · pp. 5–6
  • A framework is minimally infinitesimally rigid exactly when m=2n−3; removing redundant edges can reduce an infinitesimally rigid framework to a minimally rigid spanning subgraph.Source: B. Graph Rigidity · p. 6
  • The paper calls a framework a formation and restricts its analysis to infinitesimally rigid formations.Source: B. Graph Rigidity · p. 6

II. UNDIRECTED FORMATIONS

The section defines planar, graph-based formations in which neighboring agents maintain target distances, then models how the dynamics change when agents disagree about those distances. It sets out the rigidity and sensing assumptions and writes the formation dynamics in state-space form.

II. UNDIRECTED FORMATIONS

  • Neighboring agents may assign different desired distances, with the discrepancy between their two assignments bounded by an edge-specific tolerance.Each agent is tasked with maintaining the specified distances to its neighbors.Source: §II · p. 6
  • Each agent is modeled kinematically, senses the relative positions of its neighbors, and is assigned target distances along the edges of a formation graph.The unperturbed target distances are assumed realizable by an infinitesimally rigid formation.Source: §II · pp. 6–7
  • The connected formation graph is represented using an oriented incidence matrix, whose rows encode each edge's head and tail.The paper uses this representation to write the control dynamics in state-space form.Source: §II · p. 7
  • The resulting overall dynamics are expressed as a smooth system with agent positions as states and distance mismatches as parameters.The matrix R(z) at z = H̄x is the formation's rigidity matrix.Source: §II · p. 8

III. ERROR SYSTEM

The error-system analysis reduces formation geometry to a smaller set of edge errors near the target. On a suitable local region, this yields dynamics for those reduced errors that include the mismatch term.

III. ERROR SYSTEM

  • The analysis uses a locally defined error system, with the geometric reduction restricted to trajectories in a suitable open region.For a minimally infinitesimally rigid target, the reduction is direct: the reduced error equals the full error.Source: §III · pp. 9, 11
  • Near the target, the full edge-error vector can be expressed as a smooth function of reduced errors on a region where the reduced formation remains minimally infinitesimally rigid.The region is open and invariant under the formation's rigid motions.Source: §III · p. 10
  • On that region, the reduced error obeys a differential equation combining its rigidity-matrix dynamics with a term driven by the mismatch parameter.The displayed equation includes terms involving the reduced rigidity matrix, a function of reduced errors, and μ.Source: §III · pp. 10–11
  • The reduced errors encode local formation geometry: pairwise squared distances can be expressed in terms of them where the reduced formation is minimally rigid.The argument defines an open set around the target formation on which this rigidity condition holds.Source: §III · p. 12

A. Error System Definition

The reduced error obeys a self-contained differential equation on an open region around the target formation. Its smooth dynamics depend on the reduced error and mismatch parameter, not directly on the formation state.

A. Error System Definition

  • Theorem 1 represents the reduced-error dynamics as a smooth function g of the reduced error and mismatch parameter.The theorem gives g explicitly in terms of the reduced error, the formation matrices, and the mismatch.Source: A. Error System Definition · pp. 14–15
  • For trajectories that remain in A, the reduced error satisfies a self-contained differential equation.A is the ambient space on which the error system is valid.Source: A. Error System Definition · pp. 14–15
  • The ambient region A and dynamics g are the same for formations in the target formation’s orbit.Source: A. Error System Definition · p. 15

B. Exponential Stability of the Unperturbed Error System

With zero mismatch, the error-system equilibrium at zero is locally exponentially stable. The proof uses the rigidity of the reduced formation to establish stability of the linearization.

B. Exponential Stability of the Unperturbed Error System

C. Exponential Stability of the Perturbed Error System

For mismatch parameters near zero, the error system has a smoothly varying, exponentially stable equilibrium. The paper also defines an equilibrium output that varies smoothly with the mismatch parameter.

C. Exponential Stability of the Perturbed Error System

D. Exponential Convergence

This section gives conditions under which trajectories remain within specified sets when the error is sufficiently close to the error-system equilibrium. In the stated case for set A, the error also converges exponentially.

D. Exponential Convergence

  • For sufficiently small µ, the error-system equilibrium ǫµ is locally exponentially stable, and errors starting sufficiently near it remain in B and converge exponentially.The proof uses a positive radius around ǫµ whose error-system trajectories stay within B and converge to ǫµ.Source: D. Exponential Convergence · pp. 17, 20, 21
  • An error close or equal to ǫµ does not guarantee x(0) ∈ A; only for a globally rigid target formation does zero projected error imply membership in A [13].The paper notes that this prevents the problem from being treated as a standard local stability problem in error space.Source: D. Exponential Convergence · p. 18
  • For sufficiently small µ and x(0) ∈ A with error sufficiently close to eµ, the trajectory exists for all time, stays in A, and e converges exponentially to eµ.The theorem requires the initial error to be sufficiently close to the error-system equilibrium.Source: D. Exponential Convergence · p. 18
  • If e(¯Hx(0)) is sufficiently close to eµ, the overall system trajectory lies wholly within AB for all time.The paper states that this fact is used repeatedly in the remainder.Source: D. Exponential Convergence · pp. 21–22

IV. SQUARE SUBSYSTEM

The section reduces analysis of the full edge-vector dynamics to a two-dimensional square subsystem. Near the target formation, two independent edge vectors provide coordinates that determine the remaining edge vectors.

IV. SQUARE SUBSYSTEM

  • The subsystem is obtained by selecting two edge-vector coordinates and expressing their dynamics through a 2×2 matrix depending on the error and mismatch.The matrix is A(e, µ) = Q(e)M(e, µ)L.Source: §IV · p. 22
  • On the stated interval, the full edge-vector vector z is determined by the square subsystem formed from two selected components.The selected components correspond to vectors that are linearly independent at the target; the associated matrix remains nonsingular in the specified neighborhood.Source: §IV · pp. 22–23
  • Infinitesimal rigidity ensures that a pair of edge vectors sharing a vertex is non-collinear, supporting the independent-coordinate construction.The proof uses this property to establish nonsingularity over the neighborhood under consideration.Source: §IV · p. 23

V. ANALYSIS OF THE OVERALL SYSTEM

The error signal converges exponentially to the mismatch-dependent equilibrium output for initial states whose error is sufficiently close. The section then asks what this convergence implies for the formation’s state itself.

V. ANALYSIS OF THE OVERALL SYSTEM

  • For sufficiently small mismatch and initial error close to the equilibrium output, the error signal converges exponentially to that output.The trajectory’s velocity is also bounded on [0, ∞).Source: §V · p. 25
  • Bounded velocity and convergent error do not settle the behavior of x(t), which the remainder of the paper addresses.The analysis first treats trajectories whose error has already converged, then those starting close to equilibrium.Source: §V · p. 25
  • The stated convergence result concerns the error signal, not convergence of the full formation state.The paper explicitly poses the state trajectory as the next question.Source: §V · p. 25

A. Equilibrium Analysis

For unaligned target formations, an open dense set of sufficiently small mismatch values makes the edge-vector state nonconstant along equilibrium-error trajectories. This establishes the generic case used to analyze the resulting formation motion.

A. Equilibrium Analysis

  • For the nonconstant-z case, the section concludes that the distorted rigid formation moves in a circular orbit about the origin at fixed angular speed.The result is stated for the mismatch values identified in the preceding analysis.Source: A. Equilibrium Analysis · p. 26
  • An unaligned formation has no parallel pair among the lines joining any two pairs of its points, and such formations form an open dense set.The stated criterion is that each corresponding pair of difference vectors has nonzero wedge product.Source: A. Equilibrium Analysis · p. 26
  • For unaligned targets, an open dense set of sufficiently small mismatch values yields nonconstant z along trajectories with error fixed at its equilibrium output.The proposition states this for mismatch values in a neighborhood of the origin.Source: A. Equilibrium Analysis · p. 26
  • A lemma gives a pointwise condition for the edge-vector derivative to vanish when the error derivative is zero.Its characterization is only partial because the state in the condition depends on the mismatch value.Source: A. Equilibrium Analysis · pp. 27–28

2) Equilibrium Solutions:

At equilibrium error, constant z corresponds to a stationary formation or one drifting at constant velocity, while nonconstant z produces formation-wide circular motion. For unaligned targets, almost any sufficiently small mismatch leads to the rotating case.

2) Equilibrium Solutions:

  • When z is nonconstant, its components vary sinusoidally at a single frequency, and the individual agent positions share a common center of rotation.The shared center follows from equality of the position offsets across edges of the connected graph.Source: 2) Equilibrium Solutions · pp. 30, 32, 33
  • When z is constant, the formation’s points have constant velocity; with zero mismatch, the formation is stationary and has the desired shape.The triangle example also exhibits constant-velocity drift under mismatch in the constant-z case.Source: 2) Equilibrium Solutions · p. 31
  • With equilibrium error, constant z leaves the formation either fixed or moving to infinity at constant velocity, while nonconstant z makes all points rotate at one positive angular speed on circles about a common center.The nonconstant case rotates clockwise or counterclockwise, and the distorted formation itself follows the circular motion.Source: 2) Equilibrium Solutions · p. 33
  • For unaligned targets, almost any sufficiently small mismatch produces the nonconstant-z rotating case.The result specifies a sufficiently small norm for the mismatch.Source: 2) Equilibrium Solutions · p. 33

B. Non-Equilibrium Analysis

The analysis shows that, under a local attraction condition, trajectories of the overall system converge exponentially to a solution whose error is fixed at the mismatch equilibrium. The limiting formation's motion depends on whether its associated vector is constant or nonconstant.

B. Non-Equilibrium Analysis

  • The proof constructs a limiting equilibrium solution with error eµ and shows the original state converges to it exponentially.The error dynamics approach their equilibrium exponentially; the associated matrices and formation vectors then approach periodic limits in the nonconstant case.Source: B. Non-Equilibrium Analysis · pp. 33–35
  • Trajectories starting in A with reduced error in the attraction domain converge exponentially to a solution of the overall system along which the error equals eµ.The theorem states convergence to this solution, not necessarily to a stationary formation.Source: B. Non-Equilibrium Analysis · p. 36
  • For a mismatch with constant z̄, formation points either converge exponentially to constant positions or drift to infinity, depending on the mismatch.The triangular formation with mismatch is specifically stated to drift at constant velocity.Source: B. Non-Equilibrium Analysis · p. 37
  • For a mismatch with nonconstant z̄, formation points converge exponentially to a formation rotating clockwise or counterclockwise at constant angular speed around a fixed center.When the target formation is unaligned, almost any sufficiently small mismatch produces this behavior.Source: B. Non-Equilibrium Analysis · p. 37

VI. CONCLUDING REMARKS

The concluding remarks identify mismatch sensitivity as a robustness problem for formation control and point to unresolved extensions and remedies. They also connect differing agent understandings of shared data to broader distributed optimization and control.

VI. CONCLUDING REMARKS

  • The paper identifies a robustness problem in formation control when agents have differing understandings of shared data.The authors argue that such discrepancies may cause significant changes when exponential stability does not protect the system.Source: §VI · pp. 37–38
  • Mismatch-estimating controls inspired by adaptive control may address the problem, but the cited results remain limited in scope.The conclusion points to and, as examples of this approach.Source: §VI · p. 37
  • In three dimensions, mismatch errors can produce rotation plus linear drift, yielding helical motion; the authors leave full justification to future work.The conclusion derives this behavior from the added zero eigenvalue alongside an imaginary eigenvalue pair.Source: §VI · p. 37
  • Whether more realistic agent dynamics preserve the findings remains unproved, especially when agents have nonidentical model parameters.The authors conjecture that more elaborate models will not significantly change the results.Source: §VI · p. 38
  • The authors conjecture that unaligned targets may not be necessary for the final statement of Theorem 5.Whether alignment is required remains an open question in the conclusion.Source: §VI · p. 38

VII. APPENDIX

The appendix supports the analysis with rank arguments and auxiliary lemmas connecting stationary error vectors, rigidity, and exceptional mismatch sets. In particular, collinear edge vectors are incompatible with the stated infinitesimal-rigidity rank condition for connected formations of at least three vertices.

VII. APPENDIX

  • For a connected graph with at least three vertices, the rank bound n−1 contradicts the rank 2n−3 required by infinitesimal rigidity.This contradiction is used in the proof of Lemma 5.Source: §VII · p. 38
  • The appendix establishes that ż=0 is equivalent to the stated orthogonality condition on S′µ.The argument rewrites the condition using a projection onto the complement of the relevant column span.Source: §VII · p. 39
  • The appendix uses a measure-zero argument to show that the exceptional set T has measure zero, so its complement is dense near the origin.This follows from the regular-value argument and Sard’s theorem.Source: §VII · pp. 40–41
Loading 1503.00812v1…