[논문 리뷰] Distributed neighbor selection in multi agent network

분산형 multi agent 제어 분야에서는 주로 agent들의 합의(consensus)가 얼마나 빨리 이뤄지는 지가 주된 관심사이다.

예를 들어, formation 제어에서 모든 agent들이 정해진 거리를 유지하는 것과, randezvous 제어에서 공통된 위치로 모이는 것과 같은 일들이 중요한 것이다.

 

multi agent 제어 분야가 일반적인 single agent제어와 가장 다른점은 agent간의 통신을 고려해야 한다는 점이다. 이 때 agent들이 어떤 모양으로 연결되어 통신 가능한지 나타낸 것이 network topology인데, 이 형상이 consensus가 이뤄지는 수렴 속도에 큰 영향을 미친다. 이 network topology는 무선 통신의 경우 통신 거리에 따라 다르게 형성 될 수 도 있고, 운용자가 특정 network protocol을 사용해서 고정된 topology를 유지하도록 만들 수 도 있다.

 

이런 network topology는 보통 graph로써 표현하는데, vertex는 agent, edge는 통신 여부를 나타낸다. 쌍방향 통신을 하는 경우 undirected graph, 단방향 통신을 허용하는 경우 directed graph로써 나타낼 수 있다. 이때 특정 vertex에서 직접적으로 edge로 연결되어있는 vertex집합을 그 vertex의 이웃이라고 표현한다.

 

논문에서 관심 있는 문제는, 특정 network topology가 주어졌을 때 agent들이 통신가능한 이웃 중 특정 subset의 이웃을 선택하여 전체 수렴 속도를 증가시킬 수 있는 방법을 찾고 그것이 분산적으로 이뤄질 수 있도록 만드는 것을 목표로한다. 여기서 분산적으로 이뤄진다는 것은, 각 agent들이 전체 network 상태를 알지 못해도, 나 자신과 이웃의 정보만을 가지고 의사결정을 하는 형태를 말한다.

 

multi agent 제어에서 분산적 의사결정을 할 수 있다는 것은, 모든 agent의 행동을 결정하는 central agent가 없기 때문에 single point failure같은 문제에 대응가능하고, network의 agent 수가 상황에 따라 가변적이어도 확장적으로 적용이 가능한 장점을 갖기 때문에, 많은 multi agent 제어 연구자들이 이런 특성을 갖는 알고리즘을 개발하려고 한다.

 

그런데, 이웃 set의 subset을 고르는 것으로 수렴속도를 높인다는 것은 꽤나 직관에 반하는, counter intuitive한 발상이긴하다. 왜냐하면 consensus를 하기위해서 최대한 많은 수의 이웃과 통신을 하기 위해 노력해도 모자를 판에, 더 적은 이웃과 소통 해야한다는 것을 저자들이 주장하고있는 것이다.  그러나 실제 생활에서도 집단이 효율적으로 협업을 하기위해 소통 구조를 체계화 하는 것이 더 효과적인 경우들이 많은 것을 경험적으로 생각해볼 수 있다.

 

그렇다면 저자들은 어떻게 알고리즘을 디자인 했을까? 단계별로 보면 주어진 network graph에서 저자들의 직관에 따라 생각해낸 subgraph형태를 적용했을 때 consensus가 더 빨리 수렴한다는 것을 수학적으로 증명하고, 이 subgraph를 개별 agent단계에서 분산적 neighbor selection을 통해 달성할 수 있도록 하는 수학적 아이디어들을 제시하고, 그것이 달성가능함을 이론적/실험적으로 보인다. 참고로 consensus 수렴 속도에대한 증명은 network의 정보에 끊김이 없다는 것을 증명하기 위한 rechability 증명이 consensus rate증명과 함께 이뤄진다. Reachability가 보장되어야만 기존에 이루고자 했던 consensus가 정상적으로 이뤄지는 것이다.

 

Multi agent control 문제

저자들은 간단한 consensus문제인 randezvou 문제를 가지고 제안한 알고리즘을 검증한다. randevou (랑데뷰) 문제는 모든 agent들이 같은 상태가 되도록 만드는 일정의 synchronization 문제이며, 도킹같은 일을 위해 사용한다. 2가지 network 타입에 대해 적용해보려하는데, network에서 외부 제어 입력을 받아들여 움직이는 agent가 일부 존재하는 semi autonomous network (SAN)과 모든 agent가 외부 제어 입력을 받지않고 이웃 상태에만 의존해 움직이는 fully autonomous network (FAN)에 대해 다룬다. SAN같은 경우는 일종의 리더 agent가 있다고 보면 될 것 같다. 

 

Synchronization문제에서 SAN과 FAN의 각 agent들은 자신들의 local rule을 따라 움직이는데, 자신과 이웃의 상태 차이를 제어 입력으로 가져간다. 

SAN synchronization 제어

 

FAN synchronization 제어

Subgraph 선택 예시 및 효과

저자들은 기존 network에서 각 개체들이 자신보다 상태가 느리게 변화중인 개체의 정보만을 선택적으로 받아들이면 더 나은 수렴성을 보이는 graph를 만들 수 있을 것 이라고 주장했다. 이때 각 개체의 상태변화 속도는 graph의 Laplacian matrix의 가장작은 eigen value의 eigen vector에 encoding되는데, 이를 알아들으려면 graph theoretic multi agent system에 대한 이해가 있어야 한다. network의 각 개체에 해당하는 eigen vector속 값들을 비교해 더 낮은 값을 나타내는 edge부분만을 살려 놓으면 저자들이 원하는 following slower neighbor (FSN) network가 완성이 된다. 

SAN에서 subgraph 선택 예시

subgraph G'이 더 빨리 수렴한다.

Relative tempo

여기서 오는 challenge는 Laplacian matrix의 eigen vector를 구하려면 전체 network구조를 알고 있어야한다는 것이다. 개별 agent는 이웃의 정보만 받을 수 있고 전체 network구조는 알 수 없기 때문에 이를 근사하여 알 수 있는 방법이 필요하다. 여기서 저자들이 활용한 것이 relative temp이다. Relative tempo는 이웃 개체의 상대적 변화율과 Laplacian eigenvector의 양적인 관계를 정의한 것이다. 좀 더 자세히 설명하자면 각 agent의 상태변화값의 상대적 비율의 limitation이 Laplaician eigen vector 값의 상대적 비율에 수렴한다는 개념이다.

Relative tempo

 

저자들은 이 결과를 numerical하게도 보이는데,  multi agent consensus의 dynamics에서 상태 변화 비율을 매 time step마다 계산하면, relative tempo 개념이 실제로 어느정도 들어맞도록 수렴한다는 것을 보인다.

 

SAN에서의 FSN예시

 

 

SAN의 distributed neighbor selection 알고리즘

이 relative tempo 개념을 활용한 SAN의 분산적 neighbor selection 알고리즘은 다음과 같다.

SAN의 neighbor selection 알고리즘

 

요약하자면, relative temp의 근사값을 iteration을 통해 구해낸 후, 어느정도 수렴했다고 판단돠면 그 값의 결과에 따라 이웃을 선택하는 것이다. g_ik값이 relative temp이고, 이값이 1보다 클 때의 decision을 보면, 나의 상태변화율이 이웃 j의 상태 변화율보다 빠르다고 판단하여 이 이웃과의 edge를 유지함으로써 FSN을 분산적으로 구축한다는 의미이다.

 

그 이후 이 알고리즘의 reachability와 convergence rate enhancement에 대해 저자들은 수학적으로 증명한다. 개인적으로는 이 부분이 가장 흥미롭고 관심가는 부분이라 나중에 따로 정리를 해볼 예정이다. 

 

여기서 보통 기대되는 바는 FAN에서는 어떻게 적용 되는지인데, 문제는 reachability를 유지하기 위해서는 SAN에서 처럼 단순하게 알고리즘이 적용되지 않고, 트릭들이 많이 들어가게된다. 또한 논문에서 제안된 분산적 알고리즘 적용은 FAN이 tree 형태의 topology를 가질때만 가능하기 때문에 이부분에 있어서 유연성은 좀 떨어진다고 볼 수 있다.

 

내가 연구중 찾아낸 발견은 FAN이 tree형태가 아닐때도 consensus의 수렴속도를 높일 수 있는 selected topology를 만들어 낼 수 있다는 것이다. 이 논문에서 좀 더 확장된 형태의 알고리즘을 고안할 수 도 있을 것 같고, 여기서 사용된 증명 과정을 응용해서 새로운 알고리즘의 설명을 보강하는데도 사용해 볼 수 있을 것으로 보인다.