An Evolutionary Algorithm for Actuator-Sensor-Communication Co-Design in Distributed Control

This paper proposes an evolutionary algorithm for the co-design of actuators, sensors, and communication in distributed control systems that jointly minimizes control and material costs by selectively pruning a dense LQR controller, offering stability guarantees and demonstrating superior performance and computational efficiency compared to naive pruning methods.

The Gist

Imagine you are the mayor of a massive, interconnected city. Your goal is to keep the city running smoothly (like traffic flowing or power grids staying stable) while spending as little money as possible.

In the world of engineering, this "city" is a distributed control system. It's made up of many smaller neighborhoods (subsystems) that need to talk to each other to stay in sync. To manage this, you need three things:

1. Sensors: To listen to what's happening in the neighborhoods.
2. Actuators: To push buttons and make things move (like traffic lights or power valves).
3. Communication Links: The phone lines or internet cables connecting the neighborhoods so they can share information.

The Problem: The "Over-Engineered" City

Traditionally, engineers build these systems by connecting everything to everything. They install sensors on every street corner, actuators on every pole, and run cables between every single neighborhood.

This works great for stability, but it's incredibly expensive. It's like hiring a security guard for every single tree in the park and installing a phone line between every leaf. The paper calls this the "Dense LQR Controller." It's perfect performance, but it breaks the bank.

The challenge is to find the "Goldilocks" zone: a system that is cheap (few sensors, few cables) but still keeps the city from crashing. This is a Co-Design problem. You can't just design the controller first and then cut costs; you have to design them together.

The Solution: The "Evolutionary Algorithm" (Nature's Way)

The authors propose a solution inspired by evolution. Think of it like a game of "Survival of the Fittest" for city planners.

1. The Starting Point: They start with the "perfect" but expensive controller (the one that connects everything).
2. The Population: They create a "population" of 20 different, slightly messy versions of this controller. Some have fewer cables, some have fewer sensors, some have different connections.
3. The Test (The Fitness Test): They run a simulation.
   • If a version crashes the city (instability), it gets a terrible score.
   • If it keeps the city running but uses too many cables, it gets a medium score.
   • If it keeps the city running and uses very few resources, it gets a high score.
4. Breeding (Crossover & Mutation):
   • Selection: The best-performing controllers are chosen as "parents."
   • Crossover: They mix the "genes" of two parents. Maybe Parent A has great sensors, and Parent B has great cable placement. The baby controller gets the best of both.
   • Mutation: They randomly tweak a few things (maybe remove one more cable or change a connection) to see if they can get even better.
5. Repetition: They repeat this process for 150 generations. Over time, the "population" evolves from a messy, expensive system into a lean, efficient, and stable one.

The Twist: The "Unstable" City

There's a catch. If the city is naturally unstable (like a wobbly tower of blocks), trying to cut cables often makes it fall over immediately. In a standard evolutionary game, these "fallen" controllers would just be discarded, and the algorithm would get stuck because it can't find any good candidates.

The Fix: The "Repair Mechanism"
The authors added a clever trick. If a controller falls over (becomes unstable), instead of throwing it away, they send in a repair crew.

• This crew uses a mathematical tool (based on something called the Gershgorin disk theorem) to tweak the numbers on the controller just enough to make it stand up again, without adding any new cables or sensors.
• It's like taking a wobbly table and shoving a little wedge under one leg to make it stable, rather than buying a whole new table.
• This allows the algorithm to keep exploring "risky" ideas that might turn out to be the most efficient solution once they are stabilized.

The Results: Fast and Cheap

The paper tested this on a model of a power grid (the "swing equation") with nearly 100 different states (a very complex city).

• Speed: They ran the whole simulation on a standard laptop in about 60 seconds.
• Efficiency: Their method found solutions that were 50% better than just blindly cutting cables.
• Simplicity: For one specific city (the IEEE 13-bus system), the algorithm figured out that you only needed one sensor, one actuator, and one communication link to keep the whole system stable. That's a massive reduction from the hundreds of connections usually required.

The Big Picture

This paper is about teaching computers to be smart shoppers. Instead of buying the most expensive, over-engineered solution, the computer "evolves" a solution that buys just enough sensors and cables to get the job done, saving massive amounts of money and resources while keeping the system safe. It's a mix of nature's trial-and-error and a clever repair crew to handle the tough cases.

Technical Summary

1. Problem Statement

The paper addresses the co-design problem in distributed control systems, specifically for large-scale networked dynamical systems (e.g., power grids, traffic networks). The goal is to jointly optimize:

1. Control Performance: Measured by the Linear Quadratic (LQ) cost.
2. Material Costs: Measured by the number of actuators, sensors, and inter-subsystem communication links used.

Mathematical Formulation:
Given a discrete-time linear time-invariant (LTI) system $x_{k+1} = Ax_k + Bu_k$ partitioned into $N$ subsystems, the objective is to find a state-feedback controller $K$ that minimizes:
$$J(K) + w_a N_a(K) + w_s N_s(K) + w_c N_c(K)$$
Where:

• $J(K)$ is the LQ control cost.
• $N_a, N_s, N_c$ are the counts of non-zero rows (actuators), non-zero columns (sensors), and non-zero off-diagonal entries in the controller adjacency matrix (communication links), respectively.
• $w_a, w_s, w_c$ are scalar penalty weights.

This problem is a Nonlinear Mixed-Integer Programming (NLMIP) problem, which is computationally intractable for large-scale systems using traditional optimization methods.

2. Methodology

The authors propose an Evolutionary Algorithm (EA) to solve this co-design problem by selectively "pruning" a baseline dense optimal LQR controller ($K_d$).

A. Optimization Vector and Pruning Strategy

Instead of optimizing the full matrix $K$, the algorithm optimizes a parameter vector $\theta = [\ell, a, s]$:

• $\ell$ (Link Count): An integer determining how many of the largest magnitude entries from the dense $K_d$ are retained.
• $a$ (Actuator Mask): A binary vector selecting which actuators to keep.
• $s$ (Sensor Mask): A binary vector selecting which sensors to keep.

The sparse controller $K_s(\theta)$ is generated by:

1. Sorting non-zero elements of $K_d$ by magnitude and keeping the top $\ell$.
2. Zeroing out rows/columns corresponding to the inverse of masks $a$ and $s$.

B. The Evolutionary Algorithm (Algorithm 1)

The EA operates on a population of $\theta$ vectors:

1. Initialization: Randomly generate a population.
2. Selection: Use Boltzmann selection (temperature $\tau$) to choose parents based on cost $J_{EA}$. Lower cost individuals have higher selection probability.
3. Crossover: Uniformly split parent genes to create offspring.
4. Mutation: Randomly flip bits in masks $a$ and $s$, and perturb $\ell$ within a range $d$.
5. Elitism: The best $n_e$ individuals are carried over to the next generation.

C. Stability Analysis and Convergence

The paper provides rigorous theoretical guarantees:

• Convergence: The authors prove that the EA cost decreases probabilistically until it reaches a lower bound determined by a critical truncation distance $h^*$. This relies on the spatial decay properties of optimal LQR gains (Lemma 1) and the Lipschitz continuity of the LQR cost.
• Stability: They derive a stability margin $\sigma_{crit}$. If the perturbation between the dense controller and the pruned controller ($\|K_d - K_s\|_F$) is within this margin, the closed-loop system remains stable. They define a "stable truncation distance" $h_{stab}$; if the pruning depth is shallower than $h_{stab}$, stability is guaranteed.

D. Handling Unstable Plants (Algorithm 2)

For open-loop unstable plants, random pruning often results in unstable controllers with infinite cost, stalling the EA.

• Solution: A Controller Repair Mechanism based on the Gershgorin Disk Theorem.
• Process: If a candidate controller is unstable, the algorithm projects the controller onto the set of controllers with the same sparsity pattern but modified values to satisfy the Gershgorin condition ($\bar{R}(A+BK) < 1$).
• Implementation: A Polyak subgradient iteration is used to find a stable controller $K_r$ within the same sparsity pattern, allowing the EA to evaluate the cost of "unstable" genes effectively.

3. Key Contributions

1. Novel Co-Design Framework: A unified approach to jointly optimize control performance, actuator placement, sensor placement, and communication topology using an EA, avoiding the reduction of the design space common in convex relaxations.
2. Theoretical Guarantees:
   • Proof of probabilistic convergence for the EA.
   • Derivation of explicit stability margins ($\sigma_{crit}$) linking controller sparsity to closed-loop stability.
3. Stability Repair Mechanism: A novel method to handle unstable open-loop plants by repairing unstable candidate controllers via Gershgorin-based projection, significantly improving the search efficiency for unstable systems.
4. Scalability: Demonstration that the method can solve co-design for a 98-state system (swing equation model) on a standard laptop in seconds.

4. Simulation Results

The method was validated on three systems:

• 5x5 Grid (50 states, 25 inputs)
• 7x7 Grid (98 states, 49 inputs)
• IEEE 13-bus (26 states, 13 inputs)

Key Findings:

• Performance Improvement: The EA outperformed naive baselines (Dense LQR and Diagonal LQR) by 47–72% and 28–52% respectively in terms of total cost.
• Sparsity: The resulting controllers were highly sparse. For the IEEE 13-bus system, the optimal solution used only one sensor, one actuator, and one communication link.
• Unstable Plant Repair: On an unstable 5x5 grid (spectral radius 1.1), the repair mechanism increased performance improvement over the baseline from 25% to 35% and prevented the population from stagnating due to infinite costs.
• Convergence Match: The theoretical convergence bounds derived in Section IV closely matched the empirical cost reduction observed in simulations.

5. Significance

This work bridges the gap between theoretical control design and practical implementation constraints in networked systems. By treating actuator, sensor, and communication selection as a joint optimization problem solvable via evolutionary heuristics, the authors provide a scalable tool for designing efficient distributed controllers. The inclusion of stability analysis and a repair mechanism for unstable systems makes the approach robust and applicable to real-world critical infrastructure (like power grids) where stability is non-negotiable. The ability to run these complex co-designs on standard hardware in seconds suggests immediate potential for engineering applications.