by Sau-ming Lau. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1995. / Includes bibliographical references (leaves 131-134). / Abstract --- p.i / Acknowledgement --- p.iii / List of Tables --- p.viii / List of Figures --- p.x / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Basic Concepts and Related Work --- p.9 / Chapter 2.1 --- Components of Dynamic Load Balancing Algorithms --- p.10 / Chapter 2.2 --- Classification of Load Balancing Algorithms --- p.11 / Chapter 2.2.1 --- Casavant and Kuhl's Taxonomy --- p.12 / Chapter 3 --- System Model and Assumptions --- p.19 / Chapter 3.1 --- The System Model and Assumptions --- p.19 / Chapter 3.2 --- Survey on Cost Models --- p.21 / Chapter 3.2.1 --- "Eager, Lazowska, and Zahorjan's Model" --- p.22 / Chapter 3.2.2 --- "Shivaratri, Krueger, and Singhal's Model" --- p.23 / Chapter 3.3 --- Our Cost Model --- p.24 / Chapter 3.3.1 --- Design Philosophy --- p.24 / Chapter 3.3.2 --- Polling Query Cost Model --- p.25 / Chapter 3.3.3 --- Load State Broadcasting Cost Model --- p.26 / Chapter 3.3.4 --- Task Assignment Cost Model --- p.27 / Chapter 3.3.5 --- Task Migration Cost Model --- p.28 / Chapter 3.3.6 --- Execution Priority --- p.29 / Chapter 3.3.7 --- Simulation Parameter Values --- p.31 / Chapter 3.4 --- Performance Metrics --- p.33 / Chapter 4 --- A Performance Study on Load Information Dissemination Strategies --- p.36 / Chapter 4.1 --- Algorithm Descriptions --- p.37 / Chapter 4.1.1 --- Transfer Policy --- p.37 / Chapter 4.1.2 --- Information Policy --- p.40 / Chapter 4.1.3 --- Location Policy --- p.40 / Chapter 4.1.4 --- Categorization of the Algorithms --- p.43 / Chapter 4.2 --- Simulations and Analysis of Results --- p.43 / Chapter 4.2.1 --- Performance Comparisons --- p.44 / Chapter 4.2.2 --- Effect of Imbalance Factor on AWLT Algorithms --- p.49 / Chapter 4.2.3 --- Comparison of Average Performance --- p.52 / Chapter 4.2.4 --- Raw Simulation Results --- p.54 / Chapter 4.3 --- Discussions --- p.55 / Chapter 5 --- Resolving Processor Thrashing with Batch Assignment --- p.56 / Chapter 5.1 --- The GR.batch Algorithm --- p.57 / Chapter 5.1.1 --- The Guarantee and Reservation Protocol --- p.57 / Chapter 5.1.2 --- The Location Policy --- p.58 / Chapter 5.1.3 --- Batch Size Determination --- p.60 / Chapter 5.1.4 --- The Complete GR.batch Description --- p.62 / Chapter 5.2 --- Additional Performance Metrics --- p.66 / Chapter 5.3 --- Simulations and Analysis of Results --- p.67 / Chapter 5.4 --- Discussions --- p.73 / Chapter 6 --- Applying Batch Assignment to Systems with Bursty Task Arrival Patterns --- p.75 / Chapter 6.1 --- Bursty Workload Pattern Characterization Model --- p.76 / Chapter 6.2 --- Algorithm Descriptions --- p.77 / Chapter 6.2.1 --- The GR.batch Algorithm --- p.77 / Chapter 6.2.2 --- The SK .single Algorithm --- p.77 / Chapter 6.2.3 --- Summary of Algorithm Properties --- p.77 / Chapter 6.3 --- Analysis of Simulation Results --- p.77 / Chapter 6.3.1 --- Performance Comparison --- p.79 / Chapter 6.3.2 --- Time Trace --- p.80 / Chapter 6.4 --- Discussions --- p.80 / Chapter 7 --- A Preliminary Study on Task Assignment Augmented with Migration --- p.87 / Chapter 7.1 --- Algorithm Descriptions --- p.87 / Chapter 7.1.1 --- Information Policy --- p.88 / Chapter 7.1.2 --- Location Policy --- p.88 / Chapter 7.1.3 --- Transfer Policy --- p.88 / Chapter 7.1.4 --- The Three Load Balancing Algorithms --- p.89 / Chapter 7.2 --- Simulations and Analysis of Results --- p.90 / Chapter 7.2.1 --- Even Task Service Time --- p.90 / Chapter 7.2.2 --- Uneven Task Service Time --- p.94 / Chapter 7.3 --- Discussions --- p.99 / Chapter 8 --- Assignment Augmented with Migration Revisited --- p.100 / Chapter 8.1 --- Algorithm Descriptions --- p.100 / Chapter 8.1.1 --- The GR.BATCH.A Algorithm --- p.101 / Chapter 8.1.2 --- The SK.SINGLE.AM Algorithm --- p.101 / Chapter 8.1.3 --- Summary of Algorithm Properties --- p.101 / Chapter 8.2 --- Simulations and Analysis of Results --- p.101 / Chapter 8.2.1 --- Performance Comparisons --- p.102 / Chapter 8.2.2 --- Effect of Workload Imbalance --- p.105 / Chapter 8.3 --- Discussions --- p.106 / Chapter 9 --- Applying Batch Transfer to Heterogeneous Systems with Many Task Classes --- p.108 / Chapter 9.1 --- Heterogeneous System Model --- p.109 / Chapter 9.1.1 --- Processing Node Specification --- p.110 / Chapter 9.1.2 --- Task Type Specification --- p.111 / Chapter 9.1.3 --- Workload State Measurement --- p.112 / Chapter 9.1.4 --- Task Selection Candidates --- p.113 / Chapter 9.2 --- Algorithm Descriptions --- p.115 / Chapter 9.2.1 --- First Category ´ؤ The Sk .single Variations --- p.115 / Chapter 9.2.2 --- Second Category ´ؤ The GR. batch Variation Modeled with SSP --- p.117 / Chapter 9.3 --- Analysis of Simulation Results --- p.123 / Chapter 10 --- Conclusions and Future Work --- p.127 / Bibliography --- p.131 / Appendix A System Model Notations and Definitions --- p.131 / Appendix A.1 Processing Node Model --- p.131 / Appendix A.2 Cost Models --- p.132 / Appendix A.3 Load Measurement --- p.134 / Appendix A.4 Batch Size Determination Rules --- p.135 / Appendix A.5 Bursty Arrivals Modeling --- p.135 / Appendix A.6 Heterogeneous Systems Modeling --- p.135 / Appendix B Shivaratri and Krueger's Location Policy --- p.137

在过去十年左右的时间里, 随着在无线传感网络, 群体机器人及无人飞行器编队等问题的广泛应用, 多智能体系统的协作控制问题已成为控制理论中的一个热点问题. 本论文将研究两类基本的协作控制问题: 多智能体趋同问题与多智能体协作式输出调节问题. / 作为多智能体系统协作控制的一个基本问题, 多智能体趋同问题是其它诸如蜂拥, 聚类, 编队等协作控制问题的基础. 目前趋同问题主要分为两类: 无领导者的趋同问题与有领导者的趋同问题. 无领导者的趋同问题的控制目标是设计分布式的控制器使得所有子系统的状态渐近地趋于一个共同但未知的轨迹, 而有领导者的趋同问题的控制目标是设计分布式的控制器使得所有子系统的状态渐近地趋于一个特殊的轨迹, 这个轨迹由一个特别的被称作领导者的子系统产生. 分布式的控制器常常由系统的拓扑连接图决定.连接图一般是时变的, 并包含固定图与切换图作为特例. 本论文的第一部分, 我们将研究连续时间一般线性多智能体系统与离散时间一般线性多智能体系统在联合连通假设下的切换拓扑网络的趋同问题. 该问题包含其它一些特殊的诸如一阶积分器系统, 筒谐振子系统的趋同问题作为特例. 这一部分的主要贡献概括为以下两点: / 1. 研究连续时间线性临界稳定多智能体系统在切换网络下的两类趋同问题. 为研究这两类问题, 我们将首先建立一类包含Kronecker 乘积的线性切换系统的稳定性结果. 该系统特别之处在于其系统矩阵在任何时刻都可以不是Hurwitz 稳定的. 我们将结合Lyapunov 稳定性理论与一类适用于分段连续线性系统的广义Barbalat 引理来研究该切换系统的稳定性. 作为该稳定性结果的直接应用, 我们分别给出求解两类趋同问题的静态状态反馈控制率. 与现有结果比较, 该结果仅假设动态图是联合连通的, 因而严格弱化了动态图的假设. / 2. 研究离散时间线性多智能体系统在切换网络下的两类趋同问题. 在系统矩阵是临界稳定的假设下, 我们证明如果动态图是联合连通的, 则都存在静态的分布式状态反馈控制器以达到两类趋同. 该趋同分析是基于一类自守线性离散时间切换系统的稳定性结果. 研究该切换系统的稳定性的主要困难在于系统矩阵在任何时刻都可以不是Schur 稳定的. 我们将结合共同Lyapunov 函数与一些新技巧来实现稳定性分析. 该结果将包含一些现有结果作为特例. / 论文的第二部分将研究多智能体系统的协作式输出调节问题. 该问题允许各子系统有不同的动态, 允许各子系统模型存在不确定性, 并且允许各子系统存在外部干扰, 因此该问题的描述较有领导者的趋同问题更为一般于实际. 该问题的控制目标是要利用分布式的控制策略来实现不确定多智能体系统的渐近跟踪和干扰抑制. 由于该问题描述的一般性, 其结论将包含其它一些诸如趋同, 同步, 编队等多智能体协同控制问题作为特例.就技术路线而言, 我们将建立分布式的观测器与分布式的内模来处理该问题. 这部分的主要贡献总结为以下三点: / 1. 研究线性多智能体系统分别在静态与切换拓扑网络下的协作式输出调节问题. 全系统包含两类子系统. 第一类子系统可以接收到外部系统的信号, 而第二类子系统不能接收到外部系统的信号. 因此, 传统的集中式的控制器与分散式的控制器都不适用于该系统. 我们将建立分布式的观测器实现外部系统的信息从第一类子系统向第二类子系统传递. 对静态拓扑网络情况, 我们分别给出分布式动态全状态反馈控制器与分布式动态测量输出反馈控制器求解该问题的充分必要条件. 对切换拓扑网络情况, 我们则给出分布式动态全状态反馈控制器与包含前馈项的分布式动态测量输出反馈控制器求解该问题的充分条件. 该结果可以作为多智能体有领导者的趋同问题的直接推广,并将应用于求解群体机器人有领导者的编队问题. / 2. 研究不确定线性多智能体系统在静态拓扑网络下的协作式鲁棒输出调节问题. 相对前一问题, 该问题允许多智能体系统的模型具有不确定参数. 因此前馈设计方案不适用于该问题. 通过建立分布式的内模, 我们将该问题转换成其增广系统的同时极点配置问题. 利用LQR 设计方法, 我们分别给出分布式动态状态反馈控制器与分布式输出反馈控制器求解该问题的充分必要条件. 由于极点配置具有鲁棒性, 这两类控制器均能容忍系统不确定参数的微小变化. 该结果也包含一些有领导者的趋同问题作为特例. / 3. 研究一类具有参数不确定性的混杂的多智能体系统在静态拓扑网络下的协作式鲁棒输出调节问题. 与前一问题比较, 这里我们允许系统参数在一个任意大的规定的紧集内变化. 为实现这一目标, 我们引入一类新的内模, 它能将协作式输出调节问题转化成其增广系统的鲁棒镇定问题. 我们将结合共同高增益状态反馈技巧与分布式高增益观测器技巧来设计分布式动态输出反馈控制器以求解该问题, 并同时给出其可解性的充分必要条件. 该结果可应用于求解一大类不确定多智能体系统的有领导者的鲁棒趋同问题. / Over the past decade, the extensive applications of wireless sensor networks, cooperative robotics, unmanned aerial vehicle formations and so on have made the cooperative control of the multi-agent system a trendy topic. This thesis will concentrate on two basic cooperative control problems: consensus and cooperative output regulation. / Consensus problem is one of the basic cooperative control problems of multi-agent systems. It is the foundation of many other cooperative control problems such as flocking, rendezvous, and formation control. There are two types of consensus problems: leaderless consensus problem and leader-following consensus problem. While the leaderless consensus problem aims to design a distributed controller for a multi-agent system so that the states of all agents asymptotically approach a common trajectory, leader-following consensus problem further requires that the distributed controller is such that the states of all agents converge to a specified trajectory which is usually produced by another agent called leader. The distributed controller is defined by a communication graph which is in general time-varying and contains both the fixed graph and switching graph as special cases. In the first part of this thesis, we will consider these two consensus problems for both continuous-time and discrete-time general linear multi-agent systems subject to the switching network topology under the jointly connected assumption. Our problem formulation includes the consensus of many typical physical multi-agent systems such as single-integrators and harmonic oscillators as special cases. The main results of this part are summarized as follows: / 1. Two consensus problems of continuous-time marginally stable linear multi-agent systems under switching network topology are studied. We first establish a stability result for a class of linear switched systems involving Kronecker product. The problem is intriguing in that the system matrix does not have to be Hurwitz at any time instant. We then establish the main stability result by a combination of the Lyapunov stability analysis and a generalized Barbalat’s Lemma applicable to piecewise continuous linear systems. As applications of this stability result, we present two distributed static state feedback controllers to solve the two consensus problems, respectively. In contrast with existing results, our result only assumes that the dynamic graph is jointly connected which is strictly weaker than any other assumptions. / 2. Two consensus problems of linear discrete-time multi-agent systems under switching network topology are studied. Under the assumption that the system matrix is marginally stable, we show that both leaderless consensus problem and leaderfollowing consensus problem can be achieved via the distributed static state feedback controllers provided that the dynamic graph is jointly connected. The consensus analysis is based on the stability analysis of a class of linear autonomous discretetime switched systems. The main difficulty to overcome is that the system matrix of such linear switched system may not be Schur at any time instant. We combine the common Lyapunov function approach with some novel technique to complete such stability analysis. Our result contains several existing results as special cases. / The second part of this thesis addresses the cooperative output regulation of linear multi-agent systems. The formulation of the cooperative output regulation problem is much more general than the leader-following consensus problem in that it deals with agents with different dynamics, allows model uncertainty, and accommodates external disturbance. The direct objective of this problem is to handle the asymptotic tracking and disturbance rejection problem in an uncertain multi-agent system via a distributed control approach. Due to the generality of this problem formulation, our result will also contain many control problems of multi-agent systems such as consensus, synchronization, and formation as special cases, thus leading to a unified solution to several different control problems of multi-agent systems. Technically, the distributed observer and the distributed internal model will be established for handling this problem. The main contributions of this part are summarized as follows: / 1. The cooperative output regulation of linear multi-agent systems under both static and switching communication network topologies is studied. The overall system consists of two groups of subsystems. While the first group of subsystems can access the exogenous signal, the second cannot. As a result, the problem cannot be solved by either the centralized approach or the decentralized approach. A distributed observer is devised so that it can relay the information of the exosystem from the first group to the second group. For the static network case, we present the sufficient and necessary solvability conditions via distributed dynamic state feedback control law and the distributed dynamic measurement output feedback control law. For the switching network case, we give the sufficient solvability condition via distributed dynamic state feedback control law and the distributed dynamic measurement output feedback with feedforward control law. This result can be viewed as a generalization of some leader-following consensus problems of multi-agent systems. It can also be applied to solve the leader-following formation problem of a group of mobil robots. / 2. The cooperative robust output regulation problem of linear uncertain multi-agent systems under static network topology is studied. In this problem, the structural plant uncertainty is further taken into consideration. Then the feedforward design is no longer applicable to this problem. By utilizing a distributed internal model, this problem is converted into a simultaneous eigenvalue placement problem of the so called augmented system. Using the LQR design method, we present the sufficient and necessary solvability conditions of this problem via both distributed dynamic state feedback control law and distributed dynamic output feedback control law. Due to the robustness of eigenvalue placement, such control laws can tolerate small plant uncertainty. This result also contains the leader-following consensus problem for several systems as special cases. / 3. The cooperative robust output regulation of a class of heterogeneous linear multiagent systems with parameter uncertainties under static network topology is studied. In contrast with the previous problem, here we allow the plant uncertain parameters to lie on an arbitrarily large prescribed compact subset. For this purpose, we introduce a new type of internal model that allows the cooperative robust output regulation problem of the given plant to be converted into a robust stabilization problem of an augmented multi-agent system. We then solve this problem via distributed dynamic output feedback control law by combining a simultaneous high gain state feedback control technique and a distributed high gain observer technique. The sufficient and necessary solvability conditions are also given. A special case of our result leads to the solution of the leader-following robust consensus problem for a large class of uncertain multi-agent systems. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Su, Youfeng. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 155-164). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.vi / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Literature Review --- p.1 / Chapter 1.2 --- Thesis Contributions --- p.5 / Chapter 1.3 --- Thesis Organization --- p.7 / Chapter 2 --- Preliminaries --- p.10 / Chapter 2.1 --- Review of Graph Notation --- p.10 / Chapter 2.2 --- Review of Linear Output Regulation --- p.12 / Chapter 3 --- Continuous-Time Consensus under Switching Network Topology --- p.20 / Chapter 3.1 --- Introduction --- p.20 / Chapter 3.2 --- A Stability Result --- p.22 / Chapter 3.3 --- Problem Statement --- p.29 / Chapter 3.4 --- Solvability of Two Continuous-Time Consensus Problems --- p.32 / Chapter 3.4.1 --- Leaderless Consensus --- p.32 / Chapter 3.4.2 --- Leader-Following Consensus --- p.35 / Chapter 3.5 --- Examples --- p.38 / Chapter 3.6 --- Conclusion --- p.43 / Chapter 4 --- Discrete-Time Consensus under Switching Network Topology --- p.44 / Chapter 4.1 --- Introduction --- p.44 / Chapter 4.2 --- Problem Statement --- p.45 / Chapter 4.3 --- A Stability Result --- p.48 / Chapter 4.4 --- Solvability of Two Discrete-Time Consensus Problems --- p.53 / Chapter 4.4.1 --- Leaderless Consensus --- p.53 / Chapter 4.4.2 --- Leader-Following Consensus --- p.55 / Chapter 4.5 --- Examples --- p.57 / Chapter 4.6 --- Conclusion --- p.64 / Chapter 5 --- Linear Cooperative Output Regulation under Static Network --- p.67 / Chapter 5.1 --- Introduction --- p.67 / Chapter 5.2 --- Problem Statement --- p.70 / Chapter 5.3 --- Solvability of the Problem --- p.71 / Chapter 5.3.1 --- Distributed State Feedback --- p.71 / Chapter 5.3.2 --- Distributed Measurement Output Feedback --- p.76 / Chapter 5.4 --- An Example --- p.82 / Chapter 5.5 --- Conclusion --- p.86 / Chapter 6 --- Linear Cooperative Output Regulation under Switching Network --- p.87 / Chapter 6.1 --- Introduction --- p.87 / Chapter 6.2 --- Problem Statement --- p.88 / Chapter 6.3 --- Solvability of the Problem --- p.90 / Chapter 6.3.1 --- Some Lemmas --- p.90 / Chapter 6.3.2 --- Distributed State Feedback --- p.96 / Chapter 6.3.3 --- Distributed Measurement Output Feedback with Feedforward --- p.97 / Chapter 6.4 --- Application to Leader-Following Consensus --- p.100 / Chapter 6.5 --- Two Examples --- p.103 / Chapter 6.6 --- Conclusion --- p.113 / Chapter 7 --- Linear Cooperative Robust Output Regulation: A Structurally Stable Approach --- p.114 / Chapter 7.1 --- Introduction --- p.114 / Chapter 7.2 --- Problem Statement --- p.116 / Chapter 7.3 --- Solvability of the Problem --- p.117 / Chapter 7.4 --- An Example --- p.123 / Chapter 7.5 --- Conclusion --- p.125 / Chapter 8 --- Cooperative Robust Output Regulation of Heterogeneous Linear Uncertain Multi-Agent Systems --- p.128 / Chapter 8.1 --- Introduction --- p.128 / Chapter 8.2 --- Problem Statement --- p.130 / Chapter 8.3 --- From Output Regulation to Stabilization --- p.131 / Chapter 8.4 --- Stabilization of the Augmented System --- p.134 / Chapter 8.4.1 --- Two Lemmas --- p.135 / Chapter 8.4.2 --- Stabilization via State Feedback --- p.137 / Chapter 8.4.3 --- Stabilization via Output Feedback --- p.140 / Chapter 8.5 --- Solvability of Cooperative Output Regulation --- p.142 / Chapter 8.6 --- Examples --- p.144 / Chapter 8.6.1 --- Leader-Following Tracking of Mass-Damper-Spring Systems --- p.145 / Chapter 8.6.2 --- Formation of Multi Vehicles with Unknown Amplitude Disturbance --- p.148 / Chapter 8.7 --- Conclusion --- p.151 / Chapter 9 --- Conclusions --- p.152 / Bibliography --- p.155 / Biography --- p.165

Typescript (photocopy). / Digitized by Kansas Correctional Industries

Digitized by Kansas Correctional Industries

Digitized by Kansas Correctional Industries

Digitized by Kansas Correctional Industries

Typescript (photocopy). / Digitized by Kansas Correctional Industries

Typescript, etc. / Digitized by Kansas Correctional Industries

Photocopy of typescript. / Digitized by Kansas Correctional Industries

This thesis describes research that was conducted into the potential of modeling the activities of the Data Processing Department as an aid to the computer auditor. A methodology is composed to aid in the evaluation of the Internal Controls, particularly the General Controls relative to computer processing. Consisting of three major components, the methodology enables the auditor to model the presumed activities of the Data Processing Department against the actual activities, as recorded on the Operating System Log. The first component of the methodology is the construction and loading of a model of the presumed activities of the Data Processing Department from its verbal, scheduled, and reported activities. The second component is the generation of a description of the actual activities of the Data Processing Department from the information recorded on the Operating System Log. This is effected by reducing the Operating System Log to the format described by the Standard Audit File concept. Finally, the third component in the methodology is the modeling process itself. This is in fact a new analysis technique proposed for use by the EDP auditor. The modeling process is composed of software that compares the model developed and loaded in the first component, with the description of actual activity as collated by the second component. Results from this comparison are then reviewed by the auditor, who determines if they adequately depict the situation, or whether the models description as specified in the first component requires to be altered, and the modeling process re-initiated. In conducting the research, information and data from a production installation was used. Use of the ‘real-world’ input proved both the feasibility of developing a model of the reported activities of the Data Processing Department, and the adequacy of the operating system log as a source of information to report the departments actual activities. Additionally, it enabled the involvement and comment of practicing auditors. The research involved analysis of the effect of EDP on the audit process, structure of the EDP audit process, data reduction, data structures, model formalization, and model processing software. Additionally, the Standard Audit File concept was verified through its use by practising auditors, and expanded by the development of an indexed data structure, which enabled its analysis to be conducted interactively. Results from the trial implementation of the research software and methodology at a production installation confirmed the research hypothesis that the activities of the Data Processing Department could be modelled, and that there are substantial benefits from the EDP auditor in analysing this process. The research in fact provides a new source of information, and develops a new analysis technique for the EDP auditor. It demonstrates the utilization of computer technology to monitor itself for the audit function, and reasserts auditor independence by providing access to technical detail describing the processing activities of the computer.