Register now After registration you will be able to apply for this opportunity online.

Greedy algorithms in control design for resilient networks

Several fundamental questions for selecting actuators in a large-scale dynamical network remain open. This project analyzes the performance of the reverse greedy algorithm in selecting actuators. This algorithm excludes the least beneficial actuator iteratively starting from the full set of actuators

Large-scale control networks capture many complex systems including power systems, social networks, internet, transportation networks, and epidemics. The issues of controllability and control design have been explored extensively. Nevertheless, several fundamental questions on actuator selection for reachability and optimal controllability metrics remain open.
Actuator selection problem has been shown to be NP-hard. Thus, it is desirable to obtain scalable algorithms with provable performance guarantees. Many recent studies have adopted the forward greedy algorithm. This algorithm extends the actuator set with the most beneficial actuator iteratively to derive an approximate solution. An inherent drawback of the forward greedy algorithm is that any performance guarantee has to involve the objective function evaluated at the empty set as the reference value, since the actuator set expands starting from the empty set. This reference value is in general large if our metric relates to the required control energy. An alternative is to adopt the reverse greedy algorithm, which excludes the least beneficial actuator iteratively starting from the full set. In this case, any potential performance guarantee would instead involve the objective function evaluated at the full set, which is in general small.

Large-scale control networks capture many complex systems including power systems, social networks, internet, transportation networks, and epidemics. The issues of controllability and control design have been explored extensively. Nevertheless, several fundamental questions on actuator selection for reachability and optimal controllability metrics remain open.

Actuator selection problem has been shown to be NP-hard. Thus, it is desirable to obtain scalable algorithms with provable performance guarantees. Many recent studies have adopted the forward greedy algorithm. This algorithm extends the actuator set with the most beneficial actuator iteratively to derive an approximate solution. An inherent drawback of the forward greedy algorithm is that any performance guarantee has to involve the objective function evaluated at the empty set as the reference value, since the actuator set expands starting from the empty set. This reference value is in general large if our metric relates to the required control energy. An alternative is to adopt the reverse greedy algorithm, which excludes the least beneficial actuator iteratively starting from the full set. In this case, any potential performance guarantee would instead involve the objective function evaluated at the full set, which is in general small.

The project will address these two greedy algorithms and aims to deepen the understanding of control design for large-scale networks. The approach is to first develop a fundamental understanding of the notions of structural controllability and its connections with graph theory and matroid theory in [1], and also performance guarantees for submodular optimization problems in [2, 3]. After deepening the understanding of connections of these past work, the aim is to overcome some of the computational tractability limitations in the reverse greedy algorithm and sharpen the bounds in [4] for specific networks. The topic of robustness [5] and stochasticity [6] will be explored in the actuator placement framework.
Required Background: Courses in optimization and linear system theory, and a good working knowledge of MATLAB or Python are required.
Acquired Skills: Student gets a solid grasp of provable approximation techniques for combinatorial optimization problems, and a wide range of control-theoretic and graph-theoretic notions.
References are provided in the attached document

The project will address these two greedy algorithms and aims to deepen the understanding of control design for large-scale networks. The approach is to first develop a fundamental understanding of the notions of structural controllability and its connections with graph theory and matroid theory in [1], and also performance guarantees for submodular optimization problems in [2, 3]. After deepening the understanding of connections of these past work, the aim is to overcome some of the computational tractability limitations in the reverse greedy algorithm and sharpen the bounds in [4] for specific networks. The topic of robustness [5] and stochasticity [6] will be explored in the actuator placement framework.

Required Background: Courses in optimization and linear system theory, and a good working knowledge of MATLAB or Python are required.

Acquired Skills: Student gets a solid grasp of provable approximation techniques for combinatorial optimization problems, and a wide range of control-theoretic and graph-theoretic notions.

References are provided in the attached document

Please apply by writing to Orcun Karaca at okaraca@ethz.ch and including your CV and transcript of grades at Bachelor and Master's level.

Please apply by writing to Orcun Karaca at okaraca@ethz.ch and including your CV and transcript of grades at Bachelor and Master's level.