×

Algorithms for joint sensor and control nodes selection in dynamic networks. (English) Zbl 1429.93288

Summary: The problem of placing or selecting sensors and control nodes plays a pivotal role in the operation of dynamic networks. This paper proposes optimal algorithms and heuristics to solve the simultaneous sensor and actuator selection problem (SSASP) in linear dynamic networks. In particular, a sufficiency condition of static output feedback stabilizability is used to obtain the minimal set of sensors and control nodes needed to stabilize an unstable network. We then show that SSASP can be written as a mixed-integer nonconvex problem. To solve this nonconvex combinatorial problem, three methods based on (i) mixed-integer nonlinear programming, (ii) binary search algorithms, and (iii) simple heuristics are proposed. The first method yields optimal solutions to SSASP – given that some constants are appropriately selected. The second method requires a database of binary sensor/actuator combinations, returns optimal solutions, and necessitates no tuning parameters. The third approach is a heuristic that yields suboptimal solutions but is computationally attractive. The theoretical properties of these methods are discussed and numerical tests on dynamic networks showcase the trade-off between optimality and computational time.

MSC:

93D15 Stabilization of systems by feedback
90C11 Mixed integer programming
90C30 Nonlinear programming
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Software:

Mosek; YALMIP; SCIP-SDP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Andersen, E. D.; Andersen, K. D., The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm, (High performance optimization (2000), Springer), 197-232 · Zbl 1028.90022
[2] Argha, A.; Su, S. W.; Savkin, A.; Celler, B., A framework for optimal actuator/sensor selection in a control system, International Journal of Control, 1-19 (2017)
[3] Astolfi, A.; Colaneri, P., Static output feedback stabilization of linear and nonlinear systems, (Proceedings of the 39th IEEE conference on decision and control (Cat. No.00CH37187), vol. 3 (2000)), 2920-2925 vol.3
[4] Boyd, S. P.; El Ghaoui, L.; Feron, E.; Balakrishnan, V., Linear matrix inequalities in system and control theory, vol. 15 (1994), SIAM
[5] Crusius, C. A.R.; Trofino, A., Sufficient LMI conditions for output feedback control problems, IEEE Transactions on Automatic Control, 44, 5, 1053-1057 (1999) · Zbl 0956.93028
[6] De Oliveira, M. C.; Geromei, J., Linear output feedback controller design with joint selection of sensors and actuators, IEEE Transactions on Automatic Control, 45, 12, 2412-2419 (2000) · Zbl 0990.93038
[7] Gally, T.; Pfetsch, M. E.; Ulbrich, S., A framework for solving mixed-integer semidefinite programs, Optimization Methods & Software, 1-39 (2017)
[8] Gamrath, G., Fischer, T., Gally, T., Gleixner, A. M., Hendel, G., & Koch, T., et al. (2016). The scip optimization suite 3.2, ZIB Report.; Gamrath, G., Fischer, T., Gally, T., Gleixner, A. M., Hendel, G., & Koch, T., et al. (2016). The scip optimization suite 3.2, ZIB Report.
[9] Horn, R. A.; Johnson, C. R., Matrix Analysis (2013), Cambridge University Press: Cambridge University Press New York, NY · Zbl 1267.15001
[10] Integer Programming, YALMIP Wiki, (2015). http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.IntegerProgramming; Integer Programming, YALMIP Wiki, (2015). http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.IntegerProgramming
[11] Jovanović, M. Network with 100 unstable nodes, http://people.ece.umn.edu/ mihailo/software/lqrsp/dist_sys.html; Jovanović, M. Network with 100 unstable nodes, http://people.ece.umn.edu/ mihailo/software/lqrsp/dist_sys.html
[12] Kobayashi, K., & Takano, Y. A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems, http://www.optimization-online.org/DB_FILE/2018/09/6808.pdf; Kobayashi, K., & Takano, Y. A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems, http://www.optimization-online.org/DB_FILE/2018/09/6808.pdf
[13] Kučera, V.; Souza, C. D., A necessary and sufficient condition for output feedback stabilizability, Automatica, 31, 9, 1357-1359 (1995), URL http://www.sciencedirect.com/science/article/pii/0005109895000482 · Zbl 0831.93056
[14] Lin, F.; Fardad, M.; Jovanović, M. R., Design of optimal sparse feedback gains via the alternating direction method of multipliers, IEEE Transactions on Automatic Control, 58, 9, 2426-2431 (2013) · Zbl 1369.93215
[15] Löfberg, J., YALMIP: A toolbox for modeling and optimization in MATLAB, (Proc. IEEE int. symp. computer aided control systems design (2004), IEEE), 284-289
[16] Lubin, M.; Yamangil, E.; Bent, R.; Vielma, J. P., Extended Formulations in Mixed-Integer Convex Programming, 102-113 (2016), Springer International Publishing: Springer International Publishing Cham · Zbl 1419.90078
[17] Motee, N.; Jadbabaie, A., Optimal control of spatially distributed systems, IEEE Transactions on Automatic Control, 53, 7, 1616-1629 (2008) · Zbl 1367.93279
[18] Nugroho, S. A., Taha, A. F., Gatsis, N., Summers, T. H., & Krishnan, R. Algorithms for joint sensor and control nodes selection in dynamic networks, arXiv preprint arXiv:1811.11792; Nugroho, S. A., Taha, A. F., Gatsis, N., Summers, T. H., & Krishnan, R. Algorithms for joint sensor and control nodes selection in dynamic networks, arXiv preprint arXiv:1811.11792
[19] Nugroho, S.; Taha, A. F.; Summers, T.; Gatsis, N., Simultaneous sensor and actuator selection/placement through output feedback control, (2018 annual American control conference (ACC) (2018)), 4159-4164
[20] Pequito, S. D.; Kar, S.; Pappas, G. J., Minimum cost constrained input-output and control configuration co-design problem: A structural systems approach, (2015 American control conference (ACC) (2015)), 4099-4105
[21] Peretz, Y. J., A randomized approximation algorithm for the minimal-norm static-output-feedback problem, Automatica, 63, 221-234 (2016), URL http://www.sciencedirect.com/science/article/pii/S000510981500401X · Zbl 1329.93112
[22] Singh, T.; Swevers, J.; Pipeleers, G., Concurrent \(H_2/H_\infty\) feedback control design with optimal sensor and actuator selection, (2018 IEEE 15th international workshop on advanced motion control (AMC) (2018)), 223-228
[23] Skelton, R., Iwasaki, T., & Grigoriadis, K. M. (2013). A unified algebraic approach to linear control design, https://www.researchgate.net/publication/225075682; Skelton, R., Iwasaki, T., & Grigoriadis, K. M. (2013). A unified algebraic approach to linear control design, https://www.researchgate.net/publication/225075682
[24] Syrmos, V. L.; Abdallah, C. T.; Dorato, P.; Grigoriadis, K., Static output feedbacka survey, Automatica, 33, 2, 125-137 (1997) · Zbl 0872.93036
[25] Taha, A.; Gatsis, N.; Summers, T. H.; Nugroho, S. A., Time-varying sensor and actuator selection for uncertain cyber-physical systems, IEEE Transactions on Control of Network Systems (2018), 1-1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.