Controllability and Controllable Subspaces of Structured Networks: A Graph-Theoretical Approach

Abstract

본 학위논문은 다개체 시스템의 가제어성을 탐구하며, 시스템이 상호 연결된 구조화된 네 트워크로 모델링될 때 나타나는 특성에 초점을 맞춘다. 구조화된 네트워크를 노드과 간선으로 구성된 그래프로 모델링함으로써, 그래프 이론을 기반으로 구조화된 네트워크의 가제어성을 분석 한다. 본 학위논문은 네트워크 내에서 전체 노드 혹은 단일 노드가 독립적인 제어 목표를 달성할 수 있는 조건을 탐구하는 것에 중점을 둔다. 본 학위논문의 첫 번째 부분에서는 구조화된 네트워크의 가제어성을 나타내는 행렬이 그래프 이론적 관점에서 가지는 특성을 탐구한다. 이 과정에서 가제어성 행렬을 형성하는 주요 부분공간 두 가지와 그 차원을 정하는 방법을 소개한다. 두 번째 부분에서는 단일 노드의 구조적 제어 가능성 을 설명하고, 그래프 이론을 통해 이러한 노드들을 결정하는 방법을 제시한다. 세 번째 부분에서는 네트워크 전체 및 단일 노드의 강한 구조적 가제어성을 심도 있게 탐구한다. 특히, 기본적인 경로 형태의 그래프에 대한 이해를 바탕으로, 합병 규칙을 통해 더 큰 네트워크에 대한 강한 구조적 제어 가능성 조건을 확장한다. 이를 통해 네트워크에서 필요한 최소한의 외부 입력 노드 수를 결정하는 다항 시간 복잡도의 알고리즘을 소개하며, 이를 통해 네트워크의 강한 구조적 제어 가능성을 효 율적으로 달성하는 방안을 제안한다. 나아가, 본 학위논문은 구조화된 네트워크에서의 파라미터 불확실성에 대응하여 가장 강한 제어 가능한 부분공간의 개념인 고정된 강력 구조적 제어 가능 부분공간을 새롭게 정의하고, 이를 그래프 이론적 관점에서 해석한다. 또한, 비순환 그래프에서의 단일 노드의 강한 구조적 제어 가능성을 탐구하고, 이러한 노드의 가제어성 개념을 가관측성으로 확장하여, 파라미터의 불확실성에 대한 분석이 가능하게 하는 구조적 칼만 분해 방식을 제안한다.|This dissertation explores the controllability of multi-agent systems modeled as structured networks with interconnected agents. By modeling the structured network as a graph composed of nodes and edges, the dissertation leverages graph theory to analyze the network controllability. The dissertation emphasizes the conditions that enable the achievement of independent control objectives by the network as a whole or by individual nodes within it. In the first part, this dissertation investigates the properties of the controllability matrix within the context of graph theory when describing structured networks. It introduces the two principal subspaces formed by the controllability matrix and discusses methodologies to determine their dimensions. The second part describes the structural controllability of individual nodes and presents methods to identify such nodes using graph theory. The third part of the paper delves into the strong structural controllability of both the entire network and its individual nodes. It expands on how an understanding of basic path graph structures underpins the development of conditions for strong structural controllability, and how these conditions can be generalized for larger networks using graph merging rules. Building upon this foundation, the paper introduces an algorithm with polynomial time complexity designed to ascertain the minimum number of external input nodes necessary for ensuring strong structural controllability of a network, offering an efficient strategy to achieve robust control over the network. Furthermore, this dissertation introduces the concept of the fixed strongly structurally controllable subspace, defining it and exploring its implications within structured networks from a graph-theoretical perspective. This includes a detailed examination of the strong structural controllability of individual nodes within acyclic graphs. Lastly, this dissertation expands on the controllability of individual nodes introduced in the third section to observability, presenting a structural Kalman decomposition method for the analysis considering parameter uncertainty.