Efficient Algorithms for Distributed Control

Abstract

Distributed systems are all around us, and they are fascinating, and have an enormous potential to improve our lives, if their complexity can be properly harnessed. All scientists and engineers are aware of the great potential of this subject, since we witness fantastic distributed control systems every day, in the flocks of birds in the sky and fish in the sea. However, the collective behavior of millions of dynamically-coupled heterogeneous subsystems is hard to analyze and control for computational reasons. Our approach to the problems of analysis and control of distributed systems is to exploit the matrix structure of array-interconnected systems in fast iterative algorithms. Since these algorithms preserve the original matrix structure of the system, the resulting centrally optimal controller realizations have the same structure, which can conveniently be ‘redistributed’ into a set of subcontrollers linked in the same interconnection topology as the original system. For P interconnected subsystems, traditional analysis and control synthesis methods are O(P 3 ) computational complexity, but for N heterogeneous subsystems on a line, the above method is only O(N ) complexity. If the system is homogeneous with only heterogeneous boundary conditions, the complexity can be reduced to O(1), independent of the size of the homogeneous section. These results also extend to multiple spatial dimensions: for heterogeneous or homogeneous subsystems on an N ×M 2-D cartesian grid, the complexity is reduced to O(M N ) or O(1) complexity respectively, as compared to O(M 3 N 3 ) complexity of traditional techniques, an impressive improvement for very large systems N, M > 1000. Furthermore, due to the special form of the structured matrix arithmetic, the computations can actually be performed in a distributed way, on a distributed processor and memory system, with only linear complexity communication and memory requirements. Using these efficient structured techniques, one can perform stability and H2 and H? analysis to an arbitrary degree of accuracy, and sub-optimally upper-bound the structured singular value for robustness analysis. For synthesis, controllers with H2 and H? performance arbitrarily close to optimal are possible, and D-K iterations can be performed for robust design. Structure preserving model order reduction, and even system identification are also possible. It is also possible to apply this approach to analysis and synthesis of controllers for linear parameter varying(LPV) systems, and of repetitive controllers for trials with many time steps, T ,in only O(T ) complexity which would otherwise be O(T 3 ).