Distributed Control of Heterogeneous Systems

View Full Record
Description: In this study a method for allocating tasks to a group of distributed heterogeneous systems is developed. The method utilizes a combinatorial auction to perform the allocations. The systems performing the tasks evaluate their own suitability for performing these tasks by first developing the optimal control policy that they would use if they won that particular group, or bundle of tasks in the auction. Once the control policy is established, the nonlinear dynamics of the systems are used to calculate the amount of energy that would be consumed if they were to perform each bundle of tasks on which they are bidding. This is how the bids are generated. The bids are then entered into the auction and the winner determination problem is solved resulting in an allocation of tasks to the systems. The computational complexity of the above described method is an issue because of both the NP-completeness of the winner determination problem in a combinatorial auction and the time it takes to perform all the numerical integrations associated with solving multiple nonlinear optimal control problems. For this reason, clustering methods are used to generate bundles of tasks. The purpose of the clustering algorithms is to generate a limited number of bundles that are likely to result in a high valued auction. The main parameter in the clustering algorithms that is varied is the number of clusters that is returned. Numerical experiments were performed for a range of numbers of clusters per system, and for a range of numbers of systems. Other methods that can reduce the time to compute solutions were explored as well. For example, linearizing the dynamics of the systems results in a speed up in the numerical integration used to compute the control energy consumed in a given evolution. The results of the experimentation were evaluated based on a number of metrics that were developed for this work. These metrics include the total value of the auction as a percentage of the maximum possible value, the return per task performed, and the percentage of the total tasks performed. These metrics allow the potential user of the system to select the parameters of the clustering algorithms to best suit his or her particular needs.
Language: English
Format: Degree Work