Publications

Detailed Information

Design of distributed algorithms via discrete-time blended dynamics theorem : 이산시간 혼합 동역학 정리를 통한 분산 알고리즘의 설계

DC Field Value Language
dc.contributor.advisor심형보-
dc.contributor.author김정우-
dc.date.accessioned2023-06-29T01:56:02Z-
dc.date.available2023-06-29T01:56:02Z-
dc.date.issued2023-
dc.identifier.other000000174604-
dc.identifier.urihttps://hdl.handle.net/10371/193244-
dc.identifier.urihttps://dcollection.snu.ac.kr/common/orgView/000000174604ko_KR
dc.description학위논문(박사) -- 서울대학교대학원 : 공과대학 전기·정보공학부, 2023. 2. 심형보.-
dc.description.abstractIn this thesis, a discrete-time version of the blended dynamics theorem is developed for the use of designing distributed computation algorithms. The blended dynamics theorem enables to predict the behavior of heterogeneous multi-agent systems. Therefore, once we get a blended dynamics for a particular computational task, design idea of node dynamics for individual heterogeneous agents can easily occur. In the continuous-time case, prediction by blended dynamics was enabled by high coupling gain among neighboring agents. In the discrete-time case, we propose an equivalent action, which we call multi-step coupling in this thesis. The discrete-time approach maintains the advantages of the continuous-time case, such as the plug-and-play operation, and that the individual node dynamics need not be stable as long as the blended dynamics is stable.
Compared to the continuous-time case, the discrete-time blended dynamics can have more variety depending on the coupling matrix. This benefit is demonstrated with applications including distributed PageRank estimation problem where each node estimates its relative importance in a network which is possibly agent-wise different. In particular, the proposed algorithm does not require an initialization process, while most of other distributed PageRank algorithms have assumed.
Furthermore, the previous result of the discrete-time version of the blended dynamics theorem is extended to a heterogeneous multi-agent system under the limited exchange of state information (we call this as rank-deficient coupling). To achieve this, a coordinate change which separates the system into vanishing and non-vanishing dynamics as each agent repeats the coupling dynamics for multiple times is presented. Based on the non-vanishing part, the blended dynamics for the rank-deficient coupling is derived, which could predict the behavior of the heterogeneous network.
Again to emphasize the practical utility of the blended dynamics, the extended result is applied to a distributed state estimation problem where numerous sensors monitor a target plant with partial measurements. The distributed state observer is designed such that the local observer of each agent estimates the plant state on its detectable part while compensating the lacking information on undetectable space through the network communication. Even though the previous blended dynamics results only guarantee the approximate convergence, it is shown that the proposed observer guarantees the asymptotic performance.
-
dc.description.abstract본 논문에서는 다양한 분산 알고리즘을 설계하는데 사용할 수 있는 이산시간에서 동작하는 혼합 동역학(blended dynamics) 이론을 개발한다. 혼합 동역학 이론은 이 기종 다개체 시스템의 행동을 예측할 수 있다. 따라서, 만약 특정한 연산을 수행하는 혼합 동역학이 주어진다면, 이기종 개체의 개별 동역학을 설계하는 방법을 쉽게 얻을 수 있다. 연속시간 이론의 경우, 혼합 동역학에 의한 예측은 이웃한 개체들 사이의 높은 결합 이득(high coupling gain)에 의해서 가능했다. 본 논문의 이산시간 이론에서는 이와 상응하는 개념으로서 다단계 결합(multi-step coupling)을 제안한다. 이러한 이 산시간 접근법은 플러그 앤 플레이(plug-and-play) 연산이 가능하거나 혼합 동역학이 안정하다면 개별 동역학이 안정하지 않아도 된다는 연속시간 이론의 장점들을 그대로 가진다.
한편, 연속시간 이론과 비교했을 때, 이산시간 혼합 동역학은 결합 행렬(coupling matrix)에 따라 더 많은 변형을 가질 수 있다. 이러한 장점은 네트워크 안에서 개별 노드의 상대적 중요도를 추정하는 PageRank를 분산적으로 추정하는 문제 등의 예제 들을 통해 보여된다. 특히, 대부분의 다른 PageRank 분산 알고리즘들이 초기화 과정 (initialization process)을 가정하는 반면에, 다단계 결합 접근법을 기반으로 제안된 알고리즘은 초기화 과정이 필요없다는 장점을 가진다.
더 나아가, 앞선 이산시간 혼합 동역학 이론의 결과를 상태정보의 교환이 제한된 환경(이러한 결합을 랭크 부족 결합(rank-deficient coupling)이라고 부른다)에서의 이 기종 다개체 시스템에 대하여 확장한다. 이를 위해서, 다개체 시스템을 각 개체가 결 합 동역학(coupling dynamics)을 다수 반복할수록 사라지는 동역학과 사라지지 않는 동역학을 분리하는 좌표 변환이 소개된다. 이러한 사라지지 않는 동역학을 기반으로 랭크 부족 결합에 대한 혼합 동역학을 유도하여 이기종 네트워크의 행동을 예측할 수 있다.
다시 한번 혼합 동역학의 실용적인 유용성을 강조하기 위하여, 다수의 센서가 부 분적인 관측치를 통해 대상 플랜트의 상태변수를 분산적으로 추정하는 문제에 앞서 소개된 확장 결과를 적용한다. 분산 관측기(distributed observer)는 각 개체가 측정가 능한(detectable) 영역에서의 상태정보를 추정하되 측정가능하지 않은(undetectable) 영역의 부족한 정보는 네트워크 통신을 통해 보완하도록 설계된다. 앞선 혼합 동역학의 결과가 오직 근사적 수렴만을 보장하지만, 제안된 관측기는 점근적인 성능을 보장함을 보인다.
-
dc.description.tableofcontents1 Introduction 1
1.1 Research Background 1
1.2 Outline and Contributions of Dissertation 4

2. Preliminaries 9
2.1 Graph Theory 9
2.1.1 Basic Definitions in Graph Theory 9
2.1.2 Connectivity and Periodicity of the Graph 10
2.1.3 Laplacian Matrix and Its Properties 11
2.2 Matrix Analysis 12
2.2.1 Stochastic Matrix 12
2.2.2 Irreducible and Primitive Matrix 13
2.2.3 Graph Theoretical Characterization 14
2.3 Kronecker Product 15

3 Behavior of Continuous-time Heterogeneous Multi-agent System under Strong Coupling 17
3.1 Problem Formulation 17
3.2 Synchronization of Multi-agent System due to Strong Coupling 18
3.3 Utility of the Blended Dynamics Theory 21
3.4 Necessity of Discrete-time Blended Dynamics Theory 22

4 Behavior of Discrete-time Heterogeneous Multi-agent System under Multi-step Coupling 25
4.1 Problem Formulation 25
4.2 Prediction on Emergent Behavior under Multi-step Coupling 26
4.3 Network Synthesis with Examples 42
4.3.1 Distributed Estimation of the Number of Agents in Network 42
4.3.2 Initialization-free Distributed PageRank Estimation for Strongly Connected Network 45
4.3.3 Distributed Estimation of Degree Sequence of Network 48

5 Application to Initialization-free Distributed PageRank Estimation for Network of Web-pages 53
5.1 Problem Formulation 53
5.2 Basic Definitions of PageRank for Teleportation Model 55
5.3 Distributed PageRank Estimation without Initialization 58
5.4 Simulation Results 63

6 Behavior of Discrete-time Heterogeneous Multi-agent System under Rank-deficient Coupling 67
6.1 Problem Formulation 67
6.2 Coordinate Change 70
6.3 Prediction on Emergent Behavior under Rank-deficient Coupling 80
6.3.1 Approximation by Blended Dynamics for Simplified Cases 86

7. Application to Distributed State Estimation 91
7.1 Problem Formulation 91
7.2 Distributed Observer for State Estimation 92
7.2.1 Detectability Decomposition 92
7.2.2 Distributed Observer Design 93
7.3 Simulation Results 98

8 Conclusions and Further Issues 103
8.1 Conclusions 103
8.2 Further Issues 105
8.2.1 Extension to Asynchronous Communication 105
8.2.2 Generalization of Multi-step Approach 107
8.2.3 Extension to Nonlinear Coupling 110
-
dc.format.extentxiii, 122-
dc.language.isoeng-
dc.publisher서울대학교 대학원-
dc.subjectdiscrete-time heterogeneous multi-agent system-
dc.subjectmulti-step coupling-
dc.subjectblended dynamics-
dc.subjectmulti-time scale-
dc.subjectopen multi-agent system-
dc.subject.ddc621.3-
dc.titleDesign of distributed algorithms via discrete-time blended dynamics theorem-
dc.title.alternative이산시간 혼합 동역학 정리를 통한 분산 알고리즘의 설계-
dc.typeThesis-
dc.typeDissertation-
dc.contributor.AlternativeAuthorKim, Jeong Woo-
dc.contributor.department공과대학 전기·정보공학부-
dc.description.degree박사-
dc.date.awarded2023-02-
dc.identifier.uciI804:11032-000000174604-
dc.identifier.holdings000000000049▲000000000056▲000000174604▲-
Appears in Collections:
Files in This Item:

Altmetrics

Item View & Download Count

  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Share