Minimal Reachability Problems
Vasileios Tzoumas, Ali Jadbabaie, George Pappas

Citation
Vasileios Tzoumas, Ali Jadbabaie, George Pappas. "Minimal Reachability Problems". 54th IEEE Conference on Decision and Control (CDC 2015), 4220-4225, 15, December, 2015.

Abstract
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, 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.

Electronic downloads

Internal. This publication has been marked by the author for TerraSwarm-only distribution, so electronic downloads are not available without logging in.

Citation formats

• HTML

  Vasileios Tzoumas, Ali Jadbabaie, George Pappas. <a
  href="http://www.terraswarm.org/pubs/520.html"
  >Minimal Reachability Problems</a>, 54th IEEE
  Conference on Decision and Control (CDC 2015), 4220-4225,
  15, December, 2015.

• Plain text

  Vasileios Tzoumas, Ali Jadbabaie, George Pappas.
  "Minimal Reachability Problems". 54th IEEE
  Conference on Decision and Control (CDC 2015), 4220-4225,
  15, December, 2015.

• BibTeX

  @inproceedings{TzoumasJadbabaiePappas15_MinimalReachabilityProblems,
      author = {Vasileios Tzoumas and Ali Jadbabaie and George
                Pappas},
      title = {Minimal Reachability Problems},
      booktitle = {54th IEEE Conference on Decision and Control (CDC
                2015)},
      pages = {4220-4225},
      day = {15},
      month = {December},
      year = {2015},
      abstract = {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, 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.},
      URL = {http://terraswarm.org/pubs/520.html}
  }
  

Posted by Vasileios Tzoumas on 24 Mar 2015.
Groups: terraswarm