PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Control of Vehicular Formations with Nearest Neighbor Interactions

Fu Lin, Makan Fardad, Mihailo R. Jovanović

arXiv:1112.4113v1math.OCcs.MAeess.SY

TL;DR

The paper asks how localized nearest-neighbor feedback can make large one-dimensional vehicular formations behave coherently like rigid lattices. It formulates structured H2 design problems, establishes convex cases, and uses perturbation analysis with homotopy-based Newton computation for unrestricted localized gains. The best performance is achieved by a controller that is both non-symmetric and spatially-varying, with explicit formation-size scaling results for single- and double-integrator models.

  • Problem

    Localized symmetric feedback cannot produce coherent large one-dimensional formations that behave like rigid lattices, motivating structured optimal designs with better scaling.

  • Method

    The paper combines convex structured H2 formulations with perturbation analysis and homotopy-based Newton’s method to design localized gains for single- and double-integrator formations.

  • Results

    The optimal localized controller achieving the best performance is both non-symmetric and spatially-varying, with scaling relationships established for both integrator models.

  • Takeaways & Limitations

    Departing from symmetry can improve coherence, and controller structure may matter more than optimal gain selection within a restricted structure.

Abstract

from arXiv · show

We consider the design of optimal localized feedback gains for one-dimensional formations in which vehicles only use information from their immediate neighbors. The control objective is to enhance coherence of the formation by making it behave like a rigid lattice. For the single-integrator model with symmetric gains, we establish convexity, implying that the globally optimal controller can be computed efficiently. We also identify a class of convex problems for double-integrators by restricting the controller to symmetric position and uniform diagonal velocity gains. To obtain the optimal non-symmetric gains for both the single- and the double-integrator models, we solve a parameterized family of optimal control problems ranging from an easily solvable problem to the problem of interest as the underlying parameter increases. When this parameter is kept small, we employ perturbation analysis to decouple the matrix equations that result from the optimality conditions, thereby rendering the unique optimal feedback gain. This solution is used to initialize a homotopy-based Newton's method to find the optimal localized gain. To investigate the performance of localized controllers, we examine how the coherence of large-scale stochastically forced formations scales with the number of vehicles. We establish several explicit scaling relationships and show that the best performance is achieved by a localized controller that is both non-symmetric and spatially-varying.

I. INTRODUCTION

The paper develops optimal localized feedback for one-dimensional vehicular formations using nearest-neighbor information, targeting coherence and rigid-lattice behavior. It establishes convex formulations for restricted symmetric designs, develops homotopy-based computation for non-symmetric gains, and derives scaling results showing the advantage of non-symmetric, spatially-varying control.

  • The formation objective is to maintain desired velocity and spacing while regulating global vehicle positions using only local neighbor information.
  • Symmetric single-integrator feedback yields a convex structured optimal-control problem with an efficiently computable global minimizer.Analytical expressions can also be derived.
  • For double-integrators, convexity is obtained by restricting gains to symmetric position feedback and uniform diagonal velocity gains.
  • Non-symmetric optimal gains are computed by homotopy from a spatially uniform controller, using perturbation analysis for small parameters and Newton’s method afterward.
  • The paper studies macroscopic rigid-lattice coherence, microscopic spacing regulation, and control-energy scaling as formation size N increases.
  • The best-performing localized controller is both non-symmetric and spatially-varying, while a spatially uniform non-symmetric controller can outperform the optimal symmetric spatially-varying design.

B. Structured H2 problem

The structured H2 problem designs localized feedback gains under a prescribed sparsity pattern to minimize disturbance effects on state and control performance. The formulation applies to single- and double-integrator formations and is characterized by coupled matrix optimality conditions.

  • The feedback law is u = −Fy, with F constrained to the structural subspace imposed by nearest-neighbor information.
  • The state-space model uses local relative-position measurements for single-integrators and relative positions plus absolute velocity errors for double-integrators.
  • The H2 objective minimizes the influence of unit-variance white stochastic disturbances on an output penalizing state and control.
  • The necessary optimality conditions are coupled matrix equations in the feedback gain F and the closed-loop observability and controllability Gramians P and L.
  • The structural identity IS encodes which entries of F may be nonzero under the entry-wise multiplication constraint.Without a fictitious follower, the terminal backward gain is additionally constrained through bN = 0.
  • The design uses Q = I to penalize global position and velocity errors, while the framework also permits other state-weight choices.

C. Performance of optimal localized controller

Performance is evaluated through formation-size-normalized H2 measures for global coherence, local spacing regulation, and control energy. The paper distinguishes macroscopic rigid-lattice behavior from microscopic neighbor-spacing behavior.

  • The microscopic weight Ql = T penalizes relative position errors between neighboring vehicles and defines the local-regulation measure Πl.
  • The macroscopic weight Qg = I penalizes global absolute position errors and defines the formation-coherence measure Πg.
  • The macroscopic performance measure quantifies resemblance to a rigid lattice, whereas the microscopic measure quantifies regulation of neighboring distances.
  • Formation-size-normalized control energy is evaluated from the H2 norm of the disturbance-to-control transfer function.
  • The same performance framework is extended to the double-integrator model using corresponding performance weights.

D. Closed-loop stability: the role of fictitious vehicles

At least one fictitious vehicle with global-position access is required for closed-loop stability, while the symmetric single-integrator design can be formulated and solved as a convex optimization problem.

  • Stability requirement: If f1 = bN = 0, the single-integrator gain has zero eigenvalue 1, making the system non-asymptotically stable for every feedback-gain choice.Under stochastic disturbances, the corresponding average mode undergoes a random walk and its absolute-position variance becomes unbounded.
  • Stability requirement: At least one vehicle with access to its global position is necessary for closed-loop stability in both integrator models.Without such access, the closed-loop system has a zero eigenvalue associated with the uniform mode.
  • Symmetric design: The symmetric single-integrator problem is convex, so its global minimum can be computed efficiently; without a fictitious follower, analytical optimal gains are available.The gain structure is represented by a linear constraint, and an auxiliary matrix converts the problem into a semidefinite program.
  • Symmetric design: For symmetric single-integrator gains, closed-loop stability is equivalent to positive definiteness of the symmetric tridiagonal gain matrix K.The closed-loop dynamics satisfy Acl = −K, and the Lyapunov equation reduces to KP + PK = Q + rK^2.
  • Gain profile: For N = 50, Q = I, and r = 1, symmetric gains are larger near fictitious boundary vehicles and decrease with distance from the fictitious leader when no follower is present.The figure compares follower and no-follower formations using gradient-computed and formula-based gains, respectively.

IV. HOMOTOPY-BASED NEWTON’S METHOD

The method removes the symmetric-gain restriction by tracing a parameterized family from an easily solvable problem to the target structured H2 problem. Perturbation analysis initializes Newton iterations, which continue until the desired homotopy parameter is reached.

  • Method: A homotopy-based Newton method solves a parameterized family connecting an easily solvable problem to the structured problem of interest.The approach is applied after removing the symmetric feedback-gain restriction.
  • Initialization: At ε = 0, the method selects an initial weight Q0 for which a spatially uniform gain F0 is inversely optimal.This initial problem can be solved analytically.
  • Perturbation step: For 0 < ε ≪ 1, perturbation analysis expands F(ε) and supplies an approximate structured gain.The desired weight is Qd, with Q = Q0 at ε = 0 and Q = Qd at ε = 1.
  • Continuation step: For larger ε, Newton’s method uses the gain from the previous homotopy value to initialize the next iteration until ε = 1.The procedure is described for the single-integrator model here and extended to the double-integrator model later.

A. Spatially uniform symmetric gain: inverse optimality for ε = 0

The ε = 0 starting point uses a spatially uniform symmetric gain whose performance weight is chosen by inverse optimality. Perturbation analysis then provides the small-ε solution used to initialize the larger-ε computation.

  • Inverse optimality: A spatially uniform strategy sets the diagonal gains uniformly, and Ff = Fb = I yields a closed-loop-stable gain with an analytically determined inverse-optimal weight.Inverse optimality finds the performance weight Q0 for which a specified gain is the optimal state-feedback gain.
  • Inverse optimality: For the single-integrator model, Q0 = rK0^2 guarantees inverse optimality of the spatially uniform symmetric gain K0.This follows from A = 0, B2 = I, R = rI, and the associated Riccati equation.
  • Inverse optimality: The same inverse-optimality procedure applies to any structured gain F0 that produces a symmetric positive definite K0, including the optimal symmetric gain.This provides the initialization used in the homotopy construction.
  • Perturbation analysis: For small ε, perturbation analysis decouples the matrix equations order by order, with each O(ε^n) system depending only on solutions through order n.The coefficients L0, P1, F1, and L1 are obtained sequentially from the equations at successive orders.
  • Perturbation analysis: Under convergence for small ε, the perturbation procedure yields the unique optimal solution F(ε) of the structured control problem.The resulting F(ε) is then used to initialize Newton’s method for larger ε.

C. Newton’s method for larger values of ε

Homotopy-based Newton iterations continue the optimal-gain path from small ε to ε=1, using perturbation solutions and previous optima as initializations. The resulting gains vary spatially and, without a fictitious follower, become asymmetric between forward and backward interactions.

  • Newton continuation: Newton’s method gradually increases ε to 1 while descending the objective from an initial stabilizing structured gain.The Newton direction is combined with a step size to generate a decreasing objective sequence.
  • Newton continuation: Perturbation expansions initialize the small-ε solve, after which each previous optimum initializes the next ε value.The expansion uses F(ε)=F0+εF1 and continuation proceeds until the desired Qd is reached at ε=1.
  • Fictitious follower: With a fictitious follower, the normalized forward-gain profile changes from almost sinusoidal at ε=10^-4 to almost piecewise linear at ε=1.The homotopy method reaches the same ε=1 gains when initialized with the optimal symmetric controller.
  • Fictitious follower: With a fictitious follower, forward and backward gains satisfy central symmetry, while forward gains decrease away from the fictitious leader.The first vehicle has the largest forward gain because it neighbors the fictitious leader.
  • No fictitious follower: Without a fictitious follower, forward gains exceed backward gains, and backward gains first increase before decreasing toward the constrained boundary bN=0.The asymmetry reflects greater emphasis on vehicles ahead and the terminal constraint.
  • Performance evaluation: Formation-size studies compare global, local, and control-energy measures to assess how symmetry and spatial variation affect large-scale coherence.The analysis explicitly examines Πg, Πl, and Πctr and compares optimal controllers with spatially uniform gains.

A. Spatially uniform symmetric gain

Spatially uniform symmetric feedback yields analytically tractable scaling laws: global coherence grows affinely with formation size, while local performance and asymptotic control energy remain size-independent.

  • Scaling laws: For the spatially uniform symmetric controller, Πg is affine in N, regardless of the positive uniform gain α.The result holds with or without a fictitious follower.
  • Single-integrator analysis: For the single-integrator model with a fictitious follower, L=T^-1/(2α) solves the Lyapunov equation.The diagonal of T^-1 is given by (T^-1)nn=n(N+1-n)/(N+1).
  • Scaling laws: The resulting global performance measure is affine in N, while Πl and Πctr are formation-size-independent.These conclusions follow from the Lyapunov solution and the diagonal entries of T^-1.
  • Look-ahead comparison: The spatially uniform non-symmetric look-ahead controller gives square-root scaling of Πg and formation-size-independent Πl and asymptotic Πctr.This behavior is established analytically for the single-integrator model.

C. Optimal symmetric and non-symmetric controllers

Spatial variation improves the coherence scaling of localized single-integrator controllers, with optimal non-symmetric gains achieving fourth-root rather than square-root growth of Πg. Bounding control energy through N-dependent penalties changes these scalings.

  • N-independent control penalty: For N-independent r, optimal symmetric gains yield square-root Πg scaling, while optimal non-symmetric gains yield fourth-root Πg scaling.The symmetric result is analytically established in the no-follower case and numerically confirmed with a fictitious follower.
  • N-independent control penalty: For the optimal symmetric gain, Πl scales as O(1/N), whereas for the optimal non-symmetric gain it scales as O(1/4√N).These local-performance trends are reported for formations with a fictitious follower.
  • Control energy: With r=1, control energy scales like Πg for both optimal symmetric and non-symmetric controllers.The equality Πctr=Πg is analytically shown for the optimal symmetric no-follower case and indicated computationally more broadly.
  • Control-energy limitation: Optimal structured controllers with N-independent r do not uniformly bound formation-size-normalized control energy, creating a coherence–control-energy trade-off.The H2 formulation treats control effort as a soft constraint.
  • Bounded control energy: N-dependent penalties that maintain approximately unit control energy increase Πg scaling to linear for optimal symmetric gains and square-root for optimal non-symmetric gains.The paper reports these trends for controllers with bounded control variance per vehicle.
  • Bounded control energy: Under approximately unit control energy, a uniform look-ahead controller can outperform the optimal symmetric gain, indicating that network topology can matter more than gain optimization.The comparison contrasts uniform non-symmetric feedback with spatially varying feedback restricted to symmetric gains.

VI. DOUBLE-INTEGRATOR MODEL

For double-integrator formations, the paper uses homotopy-based Newton optimization and finds position-gain profiles resembling the single-integrator case. The optimal localized controller achieves fourth-root global-performance scaling, while controller structure strongly affects look-ahead behavior.

  • Optimization method: The double-integrator optimization uses perturbation initialization followed by homotopy-based Newton continuation from a stabilizing structured gain.For positive α and β with β^2>8α, the spatially uniform initialization is stabilizing.
  • Optimal gain profiles: For α=1, β=3, N=50, Q=I, and r=1, the optimal double-integrator position gains closely resemble the single-integrator position gains.The comparison is made for formations with a fictitious follower.
  • Performance scaling: The optimal localized double-integrator controller gives fourth-root Πg scaling, with Πl and Πctr also exhibiting fourth-root asymptotic behavior.These results use Q=I and r=1 and are obtained computationally.
  • Controller comparisons: The spatially uniform symmetric double-integrator gain gives linear Πg scaling and formation-size-independent Πl and Πctr.This parallels the corresponding single-integrator uniform-symmetric results.
  • Controller comparisons: Look-ahead performance depends strongly on α and β; α=1 and β=1 can produce exponential Πg dependence, whereas α=1/4 and β=1 yields square-root Πg scaling.The paper therefore describes look-ahead design as more subtle for double-integrators than for single-integrators.
  • Convexity: For fixed β>0, the double-integrator problem is convex in symmetric position gains Kp=Kp^T>0 under the stated controller restriction.The convexity argument rewrites the Lyapunov equations in block form and uses trace linearity.

VII. CONCLUDING REMARKS

The paper develops optimal localized feedback design for one-dimensional formations with nearest-neighbor information, covering single- and double-integrator models. Its results identify efficient solution methods and show that the best large-scale coherence is achieved by non-symmetric, spatially varying control.

  • VII. CONCLUDING REMARKS: Nearest-neighbor information imposes structural constraints on feedback gains for both single- and double-integrator formation models.The design problem targets localized control using relative-position information from immediate neighbors.
  • VII. CONCLUDING REMARKS: Symmetric gains for the single-integrator model form a convex optimization problem with an analytical solution for formations without fictitious followers.Convexity enables efficient computation of the globally optimal controller.
  • VII. CONCLUDING REMARKS: Single- and double-integrator models have similar optimal structured position gains and the same asymptotic scalings of global, local, and control performance measures.The paper concludes that the more tractable single-integrator model captures essential features of optimal localized design when vehicles access their own velocities.
  • VII. CONCLUDING REMARKS: Homotopy-based Newton’s methods compute optimal structured gains, while perturbation analysis identifies the departure from a stabilizing spatially uniform profile.The perturbation solution initializes the homotopy procedure for obtaining non-infinitesimal gain variation.
  • VII. CONCLUDING REMARKS: The best performance is achieved by an optimal localized controller that is both non-symmetric and spatially-varying.The paper focuses on one-dimensional formations with path-graph topology, while noting that its methods can extend to more general network topologies.

APPENDIX

The appendix derives analytical performance expressions for a single-integrator look-ahead strategy and obtains asymptotic scaling laws for formation coherence and control effort.

  • APPENDIX: The appendix derives analytical expressions for global, local, and control performance measures using the solution of a Lyapunov equation.The derivation uses entries of a lower triangular Toeplitz matrix and inverse Laplace transforms.
  • APPENDIX: The matrix entries are evaluated through gamma-function and factorial expressions, including diagonal and off-diagonal relations.The relations include Ln(n+1) = L(n+1)(n+1) − α/2 for n = 1, . . . , N − 1.
  • APPENDIX: lim N→∞ Πctr(N) = α, so control performance is formation-size-independent as N increases.The limiting control-performance value is α.
  • APPENDIX: Πg = (2α)/(3√π) asymptotically, and Πg scales as a square-root function of N.The appendix also uses the limit (n/(n − 1))^(n − 1) = e in the asymptotic calculation.
Loading 1112.4113v1…