PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Distance-based Multi-Agent Relative State Estimation via Block Multiconvex Optimization

Tianyue Wu, Gongye Zaitian, Qianhao Wang, Fei Gao

arXiv:2405.20883v1cs.RO

TL;DR

Large-scale distance-based relative state estimation is difficult because it is high-dimensional and non-convex, while existing relaxation methods can be hard to scale. The paper combines generalized graph realization with collaborative convex relaxation and local refinement using block coordinate descent; the authors report competitive precision and scalability beyond previous convex relaxation methods.

  • Problem

    Large-scale distance-based relative state estimation is high-dimensional and non-convex, while centralized semidefinite relaxations are difficult to scale and local-search accuracy and efficiency vary.

    Source: §I · p. 1

  • Method

    The paper formulates estimation as generalized graph realization and solves decomposable multiconvex relaxation and refinement models with block coordinate descent.

    Source: §I · pp. 1–2

  • Results

    The proposed methods provide better or comparable precision to alternatives and scalability beyond previous convex relaxation methods.

    Source: §I · p. 2, §VIII · p. 13

  • Takeaways & Limitations

    The authors conclude that combining scalable global estimation with robust local search can yield a more robust estimation pipeline.

    Source: §VIII · p. 13

    The current results cover only formulations with certain terms in the canonical polynomial basis, and generalizing the multiconvex, decomposable construction to general polynomial optimization problems may be nontrivial.

    Source: §VIII · p. 13

Abstract

from arXiv · show

This paper explores the distance-based relative state estimation problem in large-scale systems, which is hard to solve effectively due to its high-dimensionality and non-convexity. In this paper, we alleviate this inherent hardness to simultaneously achieve scalability and robustness of inference on this problem. Our idea is launched from a universal geometric formulation, called \emph{generalized graph realization}, for the distance-based relative state estimation problem. Based on this formulation, we introduce two collaborative optimization models, one of which is convex and thus globally solvable, and the other enables fast searching on non-convex landscapes to refine the solution offered by the convex one. Importantly, both models enjoy \emph{multiconvex} and \emph{decomposable} structures, allowing efficient and safe solutions using \emph{block coordinate descent} that enjoys scalability and a distributed nature. The proposed algorithms collaborate to demonstrate superior or comparable solution precision to the current centralized convex relaxation-based methods, which are known for their high optimality. Distinctly, the proposed methods demonstrate scalability beyond the reach of previous convex relaxation-based methods. We also demonstrate that the combination of the two proposed algorithms achieves a more robust pipeline than deploying the local search method alone in a continuous-time scenario.

I. INTRODUCTION

The introduction frames large-scale distance-based relative state estimation as a high-dimensional, non-convex problem where scalable, robust inference remains difficult. It proposes a generalized graph realization formulation and collaborative multiconvex, decomposable optimization models solved by block coordinate descent.

I. INTRODUCTION

  • Distance sensors support long-range measurements and many tags, but the resulting estimation problem is high-dimensional and non-convex, making inference initialization-sensitive and time-consuming.Centralized semidefinite relaxations can be difficult to scale, while local-search methods vary in accuracy and efficiency.Source: §I · p. 1
  • Generalized graph realization represents distance-only and distance-proprioception estimation geometrically, while multiconvex, decomposable models support block-coordinate solution of relaxation and refinement stages.The stated design allows exact subproblem solutions and formally guaranteed convergence of the iteration sequence.Source: §I · pp. 1–2
  • The proposed methods combine a robust convex relaxation with fast local refinement, targeting scalable inference where centralized relaxations and initialization-sensitive local search face difficulties.The paper reports better or comparable precision to alternatives and scalability beyond previous convex relaxation methods.Source: §I · pp. 1–2

A. Relative State Estimation

  • Prior relative-state methods target few-agent systems; odometry-free distance-sensor approaches have not explicitly addressed large-scale computational challenges.The paper presents its techniques as complementary to those distance-sensor setups.Source: A. Relative State Estimation · p. 2

1) Pose Graph Optimization:

  • Riemannian Staircase methods used for pose-graph optimization are not applicable to this formulation, so the paper instead uses a structurally decomposable relaxation suited to block coordinate descent.The cited Staircase approach requires distinctive semidefinite-matrix geometry that this formulation does not have.Source: 1) Pose Graph Optimization · p. 2

2) Distance-based Robotic Localization:

  • For noisy distance measurements, rank relaxation is often not guaranteed tight; this paper explores a further relaxation of SDR and reports practical observations about its tightness.Related work also includes distance-based relaxation and certification approaches, and sequential greedy methods; this paper uses coloring for parallelization and establishes convergence formally.Source: 2) Distance-based Robotic Localization · pp. 2–3

III. PROBLEM STATEMENT AND REFORMULATION

  • The problem is transformed into generalized graph realization, compactly formulated as a rank-constrained SDP, to recover agent states that best explain distance-only or distance-proprioception measurements.The states are expressed in a common reference system, which may be arbitrary without proprioception and aligned with gravity or geographic east when the corresponding sensors are used.Source: §III · p. 3, A. Problem Setup · p. 3

B. Notions and Preliminaries

  • The setup models agents and inter-agent measurements with an undirected graph and uses noisy distance measurements, with a quadratic surrogate introduced for optimization.The MLE model is derived from the noisy measurements.Source: B. Notions and Preliminaries · p. 3

C. From Relative State Estimation to Graph Realization

The generalized graph realization formulation recasts distance-based relative state estimation as finding sensor-point coordinates that satisfy the measurements and rigid-body constraints. The formulation is equivalent to the original state-estimation problem and supports distance-only and proprioception setups.

C. From Relative State Estimation to Graph Realization

  • The formulation covers distance-only, 4-axis-proprioception, and 6-axis-proprioception setups.The distance-only setup assumes coplanar sensors; the proprioception setups use attitude information.Source: C. From Relative State Estimation to… · p. 4
  • Problem 1 and Problem 2 are equivalent in feasible states and objective values, allowing agent states to be recovered from sensor-point coordinates.The formulation preserves calibration and proprioception constraints while finding points consistent with the measurements.Source: C. From Relative State Estimation to… · p. 4
  • In the distance-only setup, noncoplanar sensors create handedness ambiguity because distance constraints cannot distinguish the true realization from its handedness alternative.The paper notes that additional constraints can eliminate this ambiguity.Source: C. From Relative State Estimation to… · p. 4
  • Extending the formulation to noncoplanar sensor constraints is a future direction because those constraints are cubic.The authors describe extending their results to these constraints as nontrivial.Source: C. From Relative State Estimation to… · p. 4

D. Problem 2 as Rank-constrained SDP

Problem 2 is rewritten as a rank-constrained semidefinite program by lifting the sensor-point coordinates into a matrix variable. Linear operators represent the distance terms and remaining constraints, while the rank restriction leaves the formulation non-convex.

D. Problem 2 as Rank-constrained SDP

IV. BLOCK COORDINATE DESCENT FOR MULTICONVEX OPTIMIZATION

The paper uses block coordinate descent (BCD) to solve block-multiconvex problems, with updates that can exploit dependencies between blocks for parallel and distributed computation. Under stated conditions, the generated sequence approaches a Nash equilibrium.

A. Block Coordinate Descent

  • BCD cyclically optimizes one variable block while holding the others fixed; the prox-linear update is more robust to initialization but takes longer to converge.The paper also uses extrapolation because it significantly accelerates BCD convergence in this application.Source: A. Block Coordinate Descent · p. 5

B. The Scalability and Distributed Nature of BCD

  • A dependency graph identifies which blocks can update in parallel, and graph coloring groups internally independent blocks for parallel updates.In this problem, an agent’s point variables depend only on variables associated with neighboring agents.Source: B. The Scalability and Distributed… · p. 5
  • When block degree and the number of graph-coloring groups stay constant as the system scales, BCD’s per-cycle computation time is approximately scale-independent.Each sweep requires computation tied to a block’s degree and communication with neighboring blocks.Source: B. The Scalability and Distributed… · p. 5

C. Convergence of BCD in Multiconvex Optimization

  • The paper exploits block multiconvex structure because BCD does not generally guarantee convergence on arbitrary problems.When the objective and feasible set are block multiconvex, the block subproblems are convex.Source: C. Convergence of BCD in Multiconvex… · pp. 5–6
  • Under Assumption 1, a bounded sequence generated by either BCD update approaches the set of Nash equilibria.The paper applies this result to establish convergence to a critical point for its proposed methods.Source: C. Convergence of BCD in Multiconvex… · p. 6

V. PRACTICAL OPTIMIZATION MODELS FOR GENERALIZED GRAPH REALIZATION

The section develops an edge-based convex relaxation to make the estimation problem decomposable, while addressing how to extract useful estimates from its solution. It also examines how anchor information supports the relaxation.

A. Dilemma of Estimating with Problem 3

  • The vanilla SDP’s dense semidefinite constraint scales poorly, and its solution’s first-order component does not provide an informed estimate for rounding.Rank-d decomposition of the other component preserves the optimization behavior but may violate constraints on the first-order component.Source: A. Dilemma of Estimating with Problem 3 · p. 6

B. An Edge-based Semidefinite Relaxation Model

  • ESDP decomposes the full semidefinite constraint into lower-dimensional constraints associated with measurement edges and sensor pairs on the same agent.The resulting relaxation is reported to achieve accuracy similar to SDP in evaluation.Source: B. An Edge-based Semidefinite… · p. 6
  • Anchors—sensors with known locations—can supply enough information for ESDP to yield informed estimates, even when only a small number are imperfectly localized.The paper notes that one agent can be anchored using calibrated sensor coordinates, or that imperfect relative positions from existing methods can provide anchors.Source: B. An Edge-based Semidefinite… · pp. 6–7
  • With only d + 1 anchor sensors, experiments found near-perfect estimates for most agents, although absolute tightness was difficult to guarantee.The figure defines tightness using localization error below 10^-3 m and near tightness below 5 × 10^-2 m.Source: B. An Edge-based Semidefinite… · p. 7, Figure 3 · p. 7

C. A Low-Rank Factors-based Local Search Model

This section introduces a low-rank-factor local-search model for refining convex-relaxation estimates. Its factorization yields blockwise structure, while fixed projection and surrogate constraints simplify optimization.

C. A Low-Rank Factors-based Local Search Model

  • The model is intended for local search to refine convex-relaxation solutions or perform online estimation.The authors state that the specialized model has favorable computational and convergence properties.Source: C. A Low-Rank Factors-based Local… · p. 7
  • A low-rank factorization introduces bi-convexity into the semidefinite matrix while preserving its positive semidefiniteness.The paper draws on collaborative prediction to make alternating optimization over the two factors possible.Source: C. A Low-Rank Factors-based Local… · p. 7
  • Fixing the projection operator leaves optimization over the realization factor and avoids preserving an orthogonality constraint.The model replaces constraints coupling U and V with objective surrogates, while preserving the separable constraints on each factor.Source: C. A Low-Rank Factors-based Local… · p. 8

VI. SOLUTIONS VIA BLOCK COORDINATE DESCENT

The paper solves its two multiconvex models with block coordinate descent (BCD), using distinct block updates for the convex relaxation and the low-rank local-search model. The resulting algorithms have different convergence guarantees and update costs.

VI. SOLUTIONS VIA BLOCK COORDINATE DESCENT

  • The block rules separate variables with equality constraints and, for Problem 5, keep U and V variables in different blocks.The evaluation groups sensor variables by agent and uses graph coloring to enable parallel execution.Source: §VI · p. 8

A. ESDP-BCD for Convex Block Updating on Problem 4

  • ESDP-BCD globally solves Problem 4; each convex quadratic-conic block update depends in complexity only on the updated agent’s number of neighbors.Its subproblems can be solved using off-the-shelf solvers.Source: A. ESDP-BCD for Convex Block Updating… · pp. 8–9

VI. SOLUTIONS VIA BLOCK COORDINATE DESCENT

  • For Problem 4, lines 2–10 of Algorithm 1 converge to a global minimizer under Rules 1–2, with Assumption 2’s bounded-sensor connectivity and Assumption 3’s surrogate replacement of constraints (33).Source: A. ESDP-BCD for Convex Block Updating… · p. 9

A. ESDP-BCD for Convex Block Updating on Problem 4

B. BM-BCD for Fast Local Searching on Problem 5

  • BM-BCD’s updates are linearly constrained linear least-squares problems with closed-form solutions, requiring only low-dimensional linear systems under the proposed block division.The method is shown to converge to KKT points under the stated rules and boundedness assumption.Source: B. BM-BCD for Fast Local Searching on… · p. 9

C. Convergence Guarantees

The convergence analysis gives global-minimizer guarantees for the convex model and critical-point guarantees for the non-convex models under stated conditions. In experiments, BM-BCD methods show initialization robustness, with a stability–iteration trade-off for the prox-linear variant.

C. Convergence Guarantees

  • Under Assumption 2, level sets for Problems 4 and 5 are bounded, supporting the bounded-sequence condition used in the convergence analysis.The paper states this assumption holds in practice when the graph is connected and a sensor is anchored.Source: C. Convergence Guarantees · p. 9
  • The proposed BCD methods converge to critical points under the stated rules and assumptions; for convex Problem 4, those points are global minimizers.The argument combines strong convexity of subproblems, bounded sequences, and equivalence between Nash equilibria and KKT points.Source: C. Convergence Guarantees · pp. 9–10

VII. EXPERIMENTS

  • Evaluation measures relative-translation accuracy by average RMSE across methods and reports parallel subproblem-solving time and serial time per subproblem; Fig. 6 evaluates 125 randomly distributed agents over 100 data generations.Source: §VII · p. 10, Figure 6 · p. 11

1) Comparison of local search methods:

  • For the tested distance-proprioception systems, BM-BCD and QN attain desired precision under mild initialization, while Riemannian methods more often reach worse local minima.BM-BCD is reported to be much more computationally efficient than QN; BCGD also iterates quickly but sometimes fails to reach the desired termination condition.Source: 1) Comparison of local search methods · pp. 10–11
  • BM-BCD methods show initialization robustness unmatched by the other tested methods, and the prox-linear variant is most stable within the family at the cost of more iterations.The authors suggest local linearization may help it escape certain local minima.Source: 1) Comparison of local search methods · p. 11

2) Comparison of convex relaxation methods:

The convex-relaxation comparisons show ESDP-BCD close to SDP in accuracy, while the distance-only and continuous-time experiments highlight scalability and the benefit of combining the methods. The conclusion emphasizes that scalable global estimation and robust local search both contribute to the approach.

2) Comparison of convex relaxation methods:

  • After refinement, ESDP-BCD and SDP perform similarly in precision, although SDP has the lowest pre-refinement RMSE and ESDP-BCD is second.SOCP-BCD is highly suboptimal with too little anchor information; the authors also report higher computational efficiency for ESDP-BCD and SOCP-BCD than SDP on large problems.Source: 2) Comparison of convex relaxation… · p. 11
  • Increasing the number of anchors or measurements per anchor improves accuracy, while SOCP-BCD is most sensitive to these conditions.The evaluation varies anchor counts and, with six anchors, measurements per anchor under different noise levels.Source: 2) Comparison of convex relaxation… · p. 11, Figure 7 · p. 12

B. Distance-only Systems

  • The RE relaxation gives the best accuracy, but BM-BCD refinement lets ESDP-BCD and SDP finish better or quite precise compared with RE, unlike RTR refinement.The authors attribute RE's relaxation accuracy to its rank restriction, whereas SDP and ESDP-BCD use a standard interior-point solver that yields a max-rank solution in their solution sets.Source: B. Distance-only Systems · p. 12
  • ESDP-BCD's iteration counts remain approximately constant as the system scales, and SDP and RE run out of memory beyond 216 agents.The figure reports scalability under varying agent counts; ESDP-BCD's decomposable structure and BCD framework are identified as the basis for this scalability.Source: Figure 8 · p. 12, B. Distance-only Systems · p. 12

C. A Heterogeneous System in a Continuous-Time Scenario

  • In the continuous-time experiment, the combined pipeline yields more consistent relative error over time than Process 1-only.The relative error η can increase over time with Process 1-only; the authors suggest periodic ESDP-BCD helps alleviate local-search drift by shuffling estimates.Source: C. A Heterogeneous System in a… · p. 13, Figure 10 · p. 13

VIII. CONCLUSION AND FUTURE WORK

  • The paper concludes that scalable global estimation and robust local search both contribute to combining scalability with robustness.BCD on multiconvex structures is identified as key to efficient, safe implementation and scalability.Source: §VIII · p. 13

APPENDIX A PROOF OF PROPOSITION 1

The proof establishes when sensor-coordinate constraints correspond to rigid-body states across distance-only and proprioception setups. It also identifies cases where rotations are non-unique or the required point configuration must be coplanar.

APPENDIX A PROOF OF PROPOSITION 1

  • With only two sensors per agent, or when all sensor points are colinear, infinitely many rotations satisfy the distance-only constraints.The proof links sensor coordinates satisfying the calibration and related constraints to recoverable rigid-body states.Source: Appendix A · pp. 15–16
  • In the 6-axis proprioception setup, three sensors yield a unique rigid transform when coplanar, but coplanarity is necessary when there are more than three sensors.Non-coplanar additional points can admit a handedness-symmetric alternative that fails the required state condition.Source: Appendix A · pp. 15–16
  • The 4-axis proprioception proof derives calibration constraints by eliminating the unknown rotation angle while preserving the relations implied by the measured rotation components.The resulting sensor-coordinate relations support recovery of the rigid-body states.Source: Appendix A · p. 16

APPENDIX B FINDING A EQUIVALENT SUBSET OF CONSTRAINTS IN

The appendix reduces Problem 2 to equivalent subsets of constraints chosen around anchor sensors. The construction varies with sensor geometry and proprioception setup, and the proof notes when a relaxation is not tight.

APPENDIX B FINDING A EQUIVALENT SUBSET OF CONSTRAINTS IN

  • For distance-only agents with at least four sensors and three non-collinear sensors, constraints to the chosen three anchors form a minimum equivalent subset; colinear sensors need only two anchors.For coplanar sensors, the appendix first characterizes three anchor sensors and derives an analogous constraint set.Source: Appendix B · pp. 16–17
  • With four non-coplanar anchors in the 4-axis proprioception setup, retain necessary constraints among the anchors and calibration constraints from other sensors to those anchors.This allows proprioception constraints between non-anchor sensors and anchors to be discarded; the 6-axis setup also gives a result for at least five sensors.Source: Appendix B · pp. 16–17

A. Proof of Proposition 3

  • If a sensor is not uniquely localizable, the relaxation is not tight under constraint (24).The proof uses invariance of the corresponding matrix quantity across the solution set.Source: A. Proof of Proposition 3 · p. 17

B. Derivation of Eq. (32) and Eq. (33)

The appendix derives constraints (32) and (33) by rewriting a constraint and fixing components associated with a sensor. It also proves boundedness by propagating bounds through measurement-graph connections from a prior-known bounded-sequence sensor.

B. Derivation of Eq. (32) and Eq. (33)

  • Rewriting constraint (24) in a form like (12), then fixing the components for sensor j, yields constraint (33).The derivation organizes the leading principal minor conditions after fixing the corresponding sensor variables.Source: B. Derivation of Eq. (32) and Eq. (33) · p. 17

A. Proof of Lemma 3

  • Under Assumption 2, bounds on a prior-known sequence-bounded sensor propagate through neighboring sensors and along graph paths to bound every sensor variable.The proof establishes boundedness first for a connected sensor pair and then applies the argument successively through the graph.Source: A. Proof of Lemma 3 · p. 17
  • For Problem 4, a bound on the connected prior-known sensor bounds p_i^u and the associated matrix terms.The proof applies the relation in (49) and then obtains bounds on X_ii^uu and X_ia^uu.Source: A. Proof of Lemma 3 · p. 17

B. Proof of Lemma 4

The appendix establishes Lemma 4’s local-solution implication and reports rank sensitivity, experimental setup, UWB bias handling, and continuous-time estimation observations.

B. Proof of Lemma 4

  • A Nash equilibrium of (17) is a local solution under the tangent-cone argument and, under a constraint qualification, can be written as the KKT condition.Source: B. Proof of Lemma 4 · p. 18

APPENDIX E VARIOUS r IN BM-BCD

  • Higher rank r tends to reduce failure rates and yields more consistent projected initializations, though not necessarily better ones; this robustness is empirical.Failure is defined as RMSE exceeding 60 cm under poor initializations.Source: Appendix E · p. 18

A. Hardware Platform

  • Experiments use a DJI FlyCart 30 mothership, parasite platforms, Nooploop LTP-AS2 UWB ranging, and mocap ground truth.The parasite sensor baselines are around 0.7 m.Source: A. Hardware Platform · pp. 18–19

B. Data Processing

  • UWB biases are relatively stable under similar conditions but vary across sensor pairs; occlusion or large attitude differences can produce differences greater than 10 cm.The experiment controls relative altitude to avoid occlusion and subtracts each sensor pair’s average calibration bias.Source: B. Data Processing · p. 19

C. Notes on the Results

  • Near-perfect mocap initialization at t=0 helps avoid early shallow minima; higher-rate local search mitigates drift but raises onboard computation and communication demands.The authors see convex relaxation as useful for time-consistent estimates when local-search frequency is not high.Source: C. Notes on the Results · p. 19

Related papers

Loading 2405.20883v1…