Minimal Reachability Problems
For control theorists and engineers, this work extends controllability results to minimal reachability, providing both hardness proofs and efficient algorithms with guarantees.
This paper addresses minimal reachability problems for linear time-invariant systems, designing a zero-one diagonal input matrix with minimal non-zero entries to achieve reachability to a specified state, subspace, or close to a desired state. The authors prove NP-hardness for two problems and provide polynomial-time algorithms with approximation guarantees, demonstrating performance on large random networks.
In this paper, we address a collection of state space reachability problems, for linear time-invariant systems, using a minimal number of actuators. In particular, we design a zero-one diagonal input matrix B, with a minimal number of non-zero entries, so that a specified state vector is reachable from a given initial state. Moreover, we design a B so that a system can be steered either into a given subspace, or sufficiently close to a desired state. This work extends the recent results of Olshevsky and Pequito, where a zero-one diagonal or column matrix B is constructed so that the involved system is controllable. Specifically, we prove that the first two of our aforementioned problems are NP-hard; these results hold for a zero-one column matrix B as well. Then, we provide efficient polynomial time algorithms for their general solution, along with their worst case approximation guarantees. Finally, we illustrate their performance over large random networks.