Design of distributed algorithms via discrete-time blended dynamics theorem

Abstract

In 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.

본 논문에서는 다양한 분산 알고리즘을 설계하는데 사용할 수 있는 이산시간에서 동작하는 혼합 동역학(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) 영역의 부족한 정보는 네트워크 통신을 통해 보완하도록 설계된다. 앞선 혼합 동역학의 결과가 오직 근사적 수렴만을 보장하지만, 제안된 관측기는 점근적인 성능을 보장함을 보인다.