Distributed model predictive control without terminal cost under inexact distributed optimization

Technical Summary: Distributed Model Predictive Control without Terminal Cost under Inexact Distributed Optimization

Problem Statement
This paper addresses the control of distributed linear discrete-time systems subject to coupled constraints. The primary challenge lies in designing a Distributed Model Predictive Control (DMPC) scheme that guarantees closed-loop stability without relying on terminal costs or terminal sets. Traditional DMPC approaches often depend on separable terminal costs and sets to ensure stability; however, these can encounter compatibility issues when constraints involve all state variables and cannot be easily separated. Furthermore, in practical real-time applications, distributed optimization algorithms often terminate iterations early due to computational or communication limits, resulting in "inexact" minimization. This early termination can lead to constraint violations during the optimization process, which is critical for safety-critical systems. The paper aims to develop a parallel DMPC approach that ensures stability and maintains feasibility throughout the optimization iterations, even under inexact distributed optimization.

Methodology
The proposed framework integrates three core components: a novel stability formulation, a distributed synthesis approach, and a violation-free optimization algorithm.

1. Stability without Terminal Cost:
   Instead of using a terminal cost, the authors introduce an explicit stability condition based on Relaxed Dynamic Programming (RDP). For each agent $i$, an additional inequality constraint is added to the local optimization problem:
   $$\ell_i(x_i(k+N|k), u_i(k+N|k)) \leq (1-\alpha)\|x_i(k)\|^2_{Q_i} + v_i(k)$$
   where $\ell_i$ is the stage cost, $\alpha \in (0,1]$ is a relaxation parameter, and $v_i(k)$ is a slack variable. A global constraint $\sum v_i(k) \leq 0$ ensures that the sum of local costs acts as a Lyapunov function for the overall system. This formulation allows the stability of the closed-loop system to be guaranteed without designing a terminal cost or terminal set.

2. Distributed Synthesis:
   To handle the coupled constraints and the new stability constraint locally, the problem is decomposed. The authors introduce slack variables $z^{[s]}$ to decouple the coupled inequality constraints. The global optimization problem is reformulated into local sub-problems where each agent minimizes a quadratic cost subject to local dynamics, local constraints, and a modified version of the coupled constraints involving the slack variables.

3. Violation-Free Distributed Optimization:
   To address the issue of constraint violations during iterative optimization (inexact minimization), the paper proposes a constraint tightening approach.

   • Constraint Tightening: A tightening parameter $\delta_s \in (0,1]$ is introduced. The constraints are tightened during iterations to ensure that even if the optimization is terminated early, the solution remains feasible for the original problem.
   • Adaptive Update: The method employs an adaptive mechanism to update the distribution of the coupled constraints among agents. If the gap between the distributed constraint and the actual constraint value is significant, the constraint bounds are updated to maintain feasibility.
   • Algorithm: A parallel algorithm (Algorithm 1) is developed where agents iteratively solve local convex optimization problems, exchange information regarding slack variables and Lagrange multipliers, and update their local constraints. The algorithm guarantees that a feasible solution exists at every iteration and converges to the optimal solution of the tightened problem.

Key Contributions
The paper makes the following specific contributions:

1. Novel DMPC Formulation: Development of a DMPC approach without terminal costs. An explicit stability condition derived from RDP is incorporated as an additional constraint, eliminating the need for separable terminal costs and sets.
2. Local Stability Handling: Introduction of a distributed synthesis approach that allows each agent to handle the stability constraint locally using slack variables.
3. Violation-Free Optimization: Development of a distributed optimization method that ensures feasibility throughout the iterations. This is achieved through constraint tightening and an adaptive update mechanism, addressing the constraint violation issues common in early-terminated distributed optimization.
4. Theoretical Guarantees: Proof that the proposed optimization problem is convex and that the distributed synthesis approach yields a feasible solution for the original problem at every iteration. Theoretical analysis confirms that the closed-loop system is stable and the cost function decreases monotonically.

Results
The proposed approach was validated through a numerical example involving a platoon of three autonomous vehicles following a leader on a highway.

• Simulation Setup: The system consisted of a leader vehicle and three follower vehicles with coupled distance constraints, velocity limits, and control input limits. The goal was to maintain a desired distance and speed.
• Performance: Simulations were conducted for 200 control steps with varying prediction horizons ($N$) and RDP parameters ($\alpha$).
  • Stability: The cost per step converged to zero, and the speed and position tracking errors remained bounded, demonstrating closed-loop stability.
  • Feasibility: The method successfully found feasible solutions for various horizon lengths and $\alpha$ values where standard approaches might fail (e.g., $N=5, \alpha=0.5$).
  • Trade-offs: Results indicated that larger horizons ($N$) and smaller $\alpha$ values generally improved performance (lower total cost) and increased the region of attraction, at the cost of increased computation time.
  • Parallel Computation: The simulation confirmed that each agent could compute its control input in parallel, validating the distributed nature of the synthesis.

Significance and Claims
The paper claims that the developed distributed MPC approach offers a robust alternative to standard terminal-cost-based methods. By removing the dependency on terminal costs, the method avoids the compatibility issues associated with separating terminal sets in systems with coupled constraints. Crucially, the proposed "violation-free" optimization approach ensures that safety-critical systems do not violate constraints during the iterative solution process, even when optimization is terminated early due to real-time limitations. The authors state that the approach ensures closed-loop stability for every feasible control sequence while enabling parallel computation by agents. The work is presented as a step toward more practical and safe distributed control for multi-agent systems, with future work suggested for extending the framework to nonlinear systems and handling uncertainties.