David Ward and Dr. Sean Warnick, Computer Science
The research discussed here explores the interplay between dynamical structure functions, the communication structure of a controller and the zero pattern of a controller. Precisely understanding this interplay is a necessary result to utilize dynamical structure functions to help broaden the known tractable class of decentralized control problems. The long term goal of this research is to broaden the set of tractable convex decentralized control problems by utilizing the structure encapsulated in dynamical structure functions. The research highlighted here was presented during the 2010 BYU Spring research conference and published in detail as my undergraduate honors thesis “Decentralized Control Problems: a weak structural approach”. Characterizing tractable decentralized control problems is difficult. Characterizing tractable decentralized control problems means to identify a set of decentralized control problems for which designing an optimal stabilizing controller is tractable1. Hopefully, a convenient check or condition is available to determine if an arbitrary set of problems is a subset of the ones shown to be tractable.
As a qualitative example of a decentralized control problem consider a search and rescue operation, where a large number of individuals are involved in the search. It is not necessary, and probably counterproductive, to have each individual communicate with every other individual. This would represent a centralized control law. On the other hand, if each member of the large search party had no communication with the other members of the party this would represent a strictly decentralized control law. It is intuitive that designing a strategy for each member of a search party operating in a strictly decentralized fashion, meaning no communication between any members is a fundamentally hard problem to solve.
Next, consider a large search party that has been organized into small groups of five individuals. Communication within these groups is allowed, but no communication between groups is permitted. This again is representative of a strictly decentralized system and may be represented by a diagonal transfer function input-output operator. This is also a fundamentally difficult problem.
Next, consider the manner in which search parties are typically organized. The entire party is organized into smaller groups, in which communication may freely take place between individuals, and a leader from that group is used to communicate with the leaders of the other small parties. Not every individual is directly communicating with every individual; however, the entire party still has the capacity to act effectively towards the common goal of finding the missing individual or object. This is representative of a decentralized system, meaning the control is restricted to a specified information pattern. The communication pattern among individuals or agents in the system is restricted to the hierarchical pattern mentioned. Decentralized control seeks to understand how to organize and coordinate systems in an optimal manner considering that communication between agents is often very costly.
Presently, numerous fields face the same complex problem of how to best accomplish a single task with several entities working together. Numerous biological systems can be modeled as a decentralized control system. This problem is faced in parallel processing, the coordination of unmanned vehicles, and the gathering of information over networks.
Weak Structure
Dynamical structure functions2 are a representation of a Linear Time-Invariant (LTI) system that also encapsulates the network structure of the manifest variables of that system. An LTI system may be characterized by a transfer function G from inputs to outputs, u to y . G contains very little and possibly no structural information, meaning that little or no information describing the underling mechanism that produces the transfer function is available. Dynamical structure functions are a factorization of a transfer function as follows, G=(I-Q)-1P and are represented by the pair, (Q,P). Q is a linear causal mapping characterizing how each output variable depends on the others. P is a linear causal mapping from inputs to outputs. The dynamical structure functions contain some structural information about the underlining structure producing the transfer function. For a given transfer function there are numerous (Q,P) pairs that will produce the given transfer function.
Minimum Link Degree
The link degree of a dynamical structure function is the number of causal relationships between the manifest variables of the system. Stated differently, the link degree is the number of nonzero elements of (Q,P). The minimum link degree is the minimum link degree that still enables (Q,P) to be consistent with G. Interestingly, often a transfer function that is represented by a non-minimum link degree (Q,P) has pairs of casual relationships that exactly cancel the affects of each other. If these pairs are eliminated one obtains a minimum link degree representation. It remains to be shown that all non-minimum link degree representation possesses such pathological cancelation; however, no counter examples have been constructed. Also, numerous examples have suggested that if the graph representation of (Q,P) has sufficiently large degree at each node that the minimum link degree representation is unique. This also remains to be proven more generally.
Future Work
The potential significance of these two observations is that under the conditions of sufficient connections between casual relationships that for a given transfer function, it possesses a unique minimum link degree dynamical structure function which posses structural information that is more readily apparent than in its transfer function representation. In the future, this structural information will be used directly to understand which casual relationships are most vital and which may be truncated without producing a large approximation error. A major obstacle that future research must overcome is the difficulty in constructing a minimum link degree representation of given transfer function. Currently the search space of this operation grows combinatorially.
References
- M. Rotkowitz and S. Lall, “A characterization of convex problems in decentralized control,” IEEE Transactions on Automatic Control 51, 274-286 (2006).
- J. Goncalves and S. Warnick. Necessary and Sufficient Conditions for Dynamical Structure Reconstruction of LTI Networks, IEEE Transactions on Automatic Control, August 2008.