Minimal Actuator Selection for Linear Time Invariant Systems

arXiv:2601.08338 · eess.SY, cs.SY, math.OC · Submitted 2026-01-13 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: I'm Rosa, and with me are Dev and Taro, guest researcher.

Dev: Today's paper: "Minimal Actuator Selection for Linear Time Invariant Systems".

Rosa: Selecting a minimal subset of available actuators to ensure controllability of a linear time-invariant system is a fundamental problem in control theory,

Dev: First, who's behind it and why it matters.

Paper summary: Rosa: So, we're looking at the paper "Minimal Actuator Selection for Linear Time Invariant Systems," and it tackles the fundamental problem of picking the smallest set of actuators needed to keep an LTI system controllable. It claims this problem has a precise characterization by framing it as an integer linear program and linking it to the set multicover problem under certain independence assumptions.

Dev: That sounds like a pretty deep dive, Rosa; I'm interested in how this translates into real-time constraints. The paper suggests that if you can find the minimum number of actuators that satisfy the PopovBelevitch-Hautus test for all eigenvalues, you can solve it using an ILP formulation.

Taro: From an autonomy standpoint, I'm curious about what happens when things go wrong; if we select a minimal set now, how resilient is that selection when the world misbehaves and we have faulty actuators? The paper actually extends this to include robust selection against a certain number of failed actuators by modifying the ILP parameters.

Rosa: Exactly, Taro; that robustness aspect is really interesting because in real-world robotic deployments, actuator failures are a certainty. The authors show that you can maintain that minimal selection if you adjust those input matrices using what they call "full spark frames" for each mode.

Dev: A full spark frame sounds like a specific way to ensure redundancy across the system's dynamics; from my side, I worry about the loop rate and latency when we have to re-evaluate this selection in real time. Does this ILP formulation run fast enough for high-speed control loops?

Taro: The complexity analysis shows that while formulating the problem is polynomial in m and n for certain classes of systems, they prove that the problem itself is NP-complete under a technical assumption about the system matrices. That formal equivalence to the set multicover problem really hammers home how hard this decision-making process gets computationally.

Rosa: It’s fascinating that they connect it so directly to combinatorial optimization; it moves controllability from a purely continuous control concern into something solvable with discrete mathematics, which is always exciting for computation. The paper shows that if the system's state matrix has all distinct eigenvalues, this equivalence simplifies even further to the set cover problem.

Dev: Simplifying to set cover when eigenvalues are distinct makes sense; it means we only need to ensure every single eigenvalue is covered at least once, which is a cleaner combinatorial constraint for us to manage in our control loop design. But what about systems with repeated eigenvalues?

Taro: The paper addresses that by showing the set multicover formulation involves multiplicity constraints related to the geometric multiplicities of those eigenvalues; so it handles the structure of the dynamics properly, even when they aren't all distinct. This gives us a more complete picture for designing systems with complex dynamics.

Paper summary: Rosa: It’s really about giving us a precise tool to determine exactly which actuators are necessary without over-engineering the system unnecessarily; that precision is what makes this characterization so valuable in practice, especially for field robotics where resources are limited. We're looking at how this applies outside the lab environment, and the paper gives us a solid mathematical foundation to test those scenarios.

Dev: From an engineering viewpoint, I'm still focused on the practical implementation details; if we use a greedy selection heuristic to solve this set multicover problem, what are the actual runtime bounds we’re looking at when n or m get quite large? We need to know if that polynomial time approximation is fast enough for our latency requirements.

Taro: The paper mentions that greedy selection is a popular heuristic because it has a polynomially bounded time complexity, and they even provide runtime bounds for exact algorithms, like thirty-one, which are around O(m(G(A) + one)p). That gives us some concrete numbers to compare against existing methods.

Rosa: Those runtime bounds are key for us to judge whether we can actually implement this in a system that needs to react quickly; the fact that they compare the greedy set multicover approach against exact algorithms shows they are thinking about practical performance trade-offs. It really shows how theoretical characterization meets real computational reality.

Dev: And looking at their numerical validation, the tests on random geometric graphs show that undirected graphs nearly always satisfy that technical assumption for the set multicover equivalence even when the connectivity is low, which is reassuring for our uncertain field deployments. The directed graphs, though, require denser connections to maintain that property.

Taro: That’s important because it suggests we might be able to apply this selection logic more broadly across different types of network structures in our autonomy hardware. It moves the discussion beyond just theoretical examples and into structural applicability.

Rosa: So, to wrap up this part, we've seen how the paper precisely characterizes minimal actuator selection as an ILP and a set multicover problem under independence assumptions, and they’ve shown how to handle faults by adapting those formulations. This opens up new avenues for control system design that are currently too complex for simpler methods.

Dev: It really does provide a rigorous framework, but the challenge remains in translating that mathematical structure into low-latency software that can handle the inherent uncertainty of real-world operations and actuator failures without introducing unacceptable delays.

Taro: And as we look toward future work, the paper hints at exploring timevarying actuator schedules and trading minimal sets for something else, like optimal performance or lower average control energy; that suggests a path for more dynamic, adaptive autonomy systems.

Rosa: That sounds like the next big area of interest for field robotics; moving from just finding the minimum number to optimizing performance under changing conditions is where the real challenge lies. The paper gives us a strong starting point for that exploration, showing how to build robust minimal sets first.

Conclusion: Rosa: I think the title itself really captures the essence of what we're looking at here, focusing on minimizing those actuators for LTI systems. The authors who put this paper out have done some solid work by providing a mathematical framework that connects controllability directly to optimization problems.

Dev: From my end, it’s interesting how they've framed this as an integer linear program, which is something I can actually work with in the control loop design phase. The implications for us engineers are that we have a formal way to determine the minimum hardware required for stability before we even start coding complex controllers.

Taro: What excites me most is the connection they make to set multicover problems; it suggests that this isn't just some abstract math exercise, but something directly related to how we need to cover all the system's dynamic modes. That kind of combinatorial link feels like it has real-world traction for autonomy design.

Rosa: Exactly, Taro; that connection is what makes this paper so compelling for field robotics where every component counts. It moves the conversation from just theoretical control theory into a concrete resource allocation problem we can actually tackle when designing physical systems.

Dev: And regarding the loop rate, the ILP formulation gives us a clear objective function to minimize, which should make it feasible to solve for smaller systems within tight latency constraints, provided we use an efficient solver. The authors' work on runtime bounds for exact algorithms gives us some concrete numbers to look at when we try to implement this on embedded hardware.

Taro: I’m still focused on the robustness aspect they introduce; if the system has faults, can this formulation handle that without completely breaking down? That's where the link to fault-aware selection and those full spark frames becomes really important for autonomous operation in uncertain environments.

Rosa: That’s a big part of it, Taro; we're not just looking at a perfect, idealized system anymore but something that has to survive real-world wear and tear. The paper shows how to build in that resilience right from the start by accounting for potential failures.

Dev: It’s promising because it gives us a systematic approach to managing hardware limitations, rather than just tweaking parameters until something works. This level of formal characterization is exactly what we need when dealing with complex, high-stakes control systems.

Taro: So, this paper provides a rigorous mathematical foundation for making smarter decisions about which parts of the actuator set are truly necessary for system safety and performance. It really shows that resource allocation in control isn't just guesswork; it's an optimization problem waiting to be solved.

Department of Information Engineering, University of Padova · Signal Processing Systems Group, Delft University of Technology

eess.SY, cs.SY, math.OC

Submitted: 2026-01-13

Updated: 2026-10-05

Comments: Published on IEEE Transactions on Control of Network Systems. Final accepted version

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 80/100

The gist: Selecting a minimal subset of available actuators to ensure controllability of a linear time-invariant system is a fundamental problem in control theory, and this work provides a precise

Key concepts

PopovBelevitch-Hautus (PBH) test: This is a mathematical condition used to determine if a linear time-invariant system is controllable. The PBH test requires that the rank of the matrix $A - heta I B S$ equals the system dimension $n$ for every eigenvalue $ heta$ in the spectrum of A. Satisfying this ensures that all modes of the system can be influenced by at least one actuator.
Integer Linear Program (ILP): The authors reformulate minimal actuator selection into an ILP. This means finding a subset of actuators that minimizes the number chosen, subject to linear constraints derived from controllability tests. The solution involves minimizing a linear objective function while respecting binary variables representing whether each actuator is selected.
Set Multicover Problem: The minimal actuator problem can be mapped to the set multicover problem. This combinatorial problem involves finding the smallest collection of sets (actuators) such that every distinct eigenvalue of the system is covered at least once, potentially with specific multiplicity constraints related to geometric multiplicities.

Terminology

Robustness — 5× in this paper · explained in 5 episodes
Redundancy — 4× in this paper · explained in 2 episodes
Combinatorial Optimization — 2× in this paper · explained in 2 episodes
Multi-Agent System — 2× in this paper · explained in 5 episodes
Adjacency Matrix — 1× in this paper · explained in 1 episode
Core — 1× in this paper · explained in 2 episodes
Generalization — 1× in this paper · explained in 13 episodes
Objective Function — 1× in this paper · explained in 2 episodes
Paper Review — 1× in this paper · explained in 2 episodes
Pruning — 1× in this paper · explained in 4 episodes
Sparsity — 1× in this paper · explained in 4 episodes

Summary

Selecting a minimal subset of available actuators to ensure controllability of a linear time-invariant system is a fundamental problem in control theory, and this work provides a precise characterization by casting it as an integer linear program and relating it to the set multicover problem.

Problem Formulation and ILP Characterization

The core problem involves choosing the fewest actuators from a given set that make the system controllable, formalized as finding a subset of actuators where the resulting system remains controllable. This is equivalent to minimizing the cardinality of this subset under controllability constraints, specifically satisfying the PopovBelevitch-Hautus (PBH) test: rk A − λI BS = n ∀λ ∈ σ(A) for all eigenvalues in the spectrum of A. The authors show that this problem can be rewritten as an integer linear program (ILP). Theorem 1 presents the formulation, stating that the minimal actuator selection problem is equivalent to minimizing a linear objective subject to constraints derived from selection matrices W(i) and binary slack variables d(i): y∗ ∈ arg min y∈0,1m d(i)∈0,1 αi 1 Ty s.t. W(i)y ≥ W(i) 1⊙d(i) ∀i ∈ [p] 1⊤d(i) ≥ 1 ∀i ∈ [p].

Equivalence to Set Multicover Problem

The paper establishes a crucial link between the actuator selection problem and combinatorial problems. Under the technical assumption that actuation channels are sufficiently independent with respect to the dynamics to be controlled, the minimal actuator selection problem is equivalent to a set multicover problem. This equivalence simplifies further: The latter equivalence is always true if the state matrix has all distinct eigenvalues, in which case it simplifies to the set cover problem. The set multicover formulation involves finding a smallest subset collection where each element (distinct eigenvalue) must be covered at least once, with multiplicity constraints related to the geometric multiplicities of the eigenvalues.

Robust Actuator Selection Formulation

The study extends the characterization to handle system faults, addressing robustness against faulty actuators. The robust minimal actuator selection problem is formulated as finding a subset of actuators that maintains controllability even if some fail: rk A − λI BSa F = n ∀λ ∈ σ(A), ∀F ⊂ S: F ≤ f. Theorem 4 demonstrates that this robust version is equivalent to the nominal ILP formulation (5) by modifying the parameter matrices W(i). This modification requires selecting redundant actuators to counterbalance faults, specifically requiring a construction based on full spark frames for each mode.

Complexity and Algorithmic Approaches

The complexity of the problem is analyzed based on technical assumptions regarding the system matrices. The problem is shown to be NP-complete under certain conditions, as demonstrated by Theorem 2, which relies on the existence of a set Ti such that B¯Gi,Ti is a full spark frame and B¯Gi,Ta = 0. The concept of a full spark frame relates to the independence of actuators affecting the same eigenvalue. For practical solutions, the paper reviews algorithms for both ILP and set multicover problems. Greedy selection is presented as a popular heuristic due to its polynomially bounded time complexity, while exact algorithms are available, such as those in [31], which have runtime bounds like O(m(G(A) + 1)p).

Numerical Validation and Performance

The theoretical results are validated through numerical experiments on various system structures. The authors test the technical assumption by constructing systems with increasing state dimension n and varying connectivity in random geometric graphs, showing that undirected graphs nearly always satisfy the assumption even under low connectivity (small n), while directed graphs require denser connections. Comparisons between ILP, greedy set multicover, and exact set multicover algorithms reveal runtime differences as system size increases. For instance, the greedy selection can select up to three times the number of actuators w.r.t. ILP for n ≤ 50, but reaches the same minimal number (one) for larger systems (n ≥ 50). The numerical tests confirm the validity of the technical assumption and compare computational performance across different approaches.

Conclusion

The study successfully reformulates minimal actuator selection as an ILP and proves its equivalence to set multicover under specific conditions. Furthermore, it extends this framework to a robust setting, showing that fault-aware selection is achievable by modifying the ILP parameters using full spark frame constructions. This work strengthens the connection between control-theoretic resource allocation and combinatorial optimization problems. Future directions include exploring timevarying actuator schedules and trading minimal actuator sets for optimal performance or minimal (average) control energy.

The gist

Selecting a few available actuators to ensure the controllability of a linear system is equivalent to solving an integer linear program that, under certain conditions, can be characterized as a set multicover problem.

Improvements for AI systems

Based on the provided research paper, here are specific improvements that can be made to AI systems, along with what those improved systems could achieve:

) The core contribution of this work is establishing a formal mathematical bridge between the control theory problem of Minimal Actuator Selection and combinatorial optimization problems like Set Multicover. This allows for the design of AI/ML architectures that are inherently constrained by physical actuator limitations in a provably optimal way.

) The improved AI system can perform:

Precise, minimal hardware configuration selection for complex dynamic systems (e.g., robotics, autonomous vehicles).
Real-time resource allocation where the system must select the absolute minimum necessary actuators from a pre-defined set to maintain guaranteed controllability under fault scenarios.

) Specific improvements derived from the paper:

The system can use an Integer Linear Program (ILP) formulation (Theorem 1/5) to solve for actuator selection.
This ILP is then recast as a Set Multicover problem, allowing the use of established combinatorial optimization algorithms (Greedy or Exact solvers from Tables I and II).
The system can incorporate robustness: By modifying the formulation using full spark frame conditions (Theorem 4), the AI can guarantee that a certain number of actuators remain functional even if up to 'f' faults occur, by selecting redundant components for each dynamic mode.

) Detailed capabilities of the improved system:

A robot controller could dynamically reconfigure its control inputs (actuators) in a network to ensure stability and controllability despite hardware failures.
An AI system managing a modular swarm of agents could select the smallest subset of communication/control links required to maintain global network controllability, even if some links fail.
In an autonomous vehicle, it could determine the minimum set of steering/braking actuators needed to ensure the vehicle remains controllable within specified safety margins under sensor or actuator failure conditions.

) Summary of specific technical outcomes:

The AI system will output a binary selection vector that precisely identifies which physical actuators should be active.
It will achieve the mathematically proven minimum number of actuators required for controllability, rather than relying on heuristic methods or brute-force searches.
For robust systems, it will select an actuator set that is guaranteed to maintain controllability even when a specified number of actuators fail (e.g., selecting exactly one extra actuator for every mode if up to 'f' failures are possible).