Research

Research

HOME

Topic 1

지능형 에이전트가 공유하는 시스템 자원의 관리 알고리즘 연구

                                                                                                                                                                                                                               

문제 정의 및 해결 방안

여러 에이전트가 공존하는 다양한 시스템(통신 네트워크, 멀티에이전트 플랫폼 등)은 시스템의 자원을 공유해야만 함. 이때 공유된 자원은 일반적으로 유한하기 때문에, 이를 최적으로 활용하기 위한 방안이 필요함. 협력 게임이론의 협상 해법(bargaining solution)을 이용하여 각 에이전트의 자원 활용 정도, 즉 효용(utility)를 반영하여 파레토 최적이며(Pareto optimality) 공평한(fairness) 자원 배분을 할 수 있음.
                                                                                                                                                                                                                               

활용 범위

5G/6G 무선 네트워크 시스템
스마트팩토리 시스템
자율주행 시스템
                                                                                                                                                                                                                               
연구 결과

▪️대표적으로 NBS(Nash Bargaining Solution)이 있으며 KSBS(Kalai-Smorondinsky Bargaining Solution), Egalitarian bargaining solution 등이 있음. 서로 다른 협상 해법은 서로 다른 공평성에 대한 원칙을 가지고 있어 각 협상 해법마다 결정되는 자원 분배는 서로 다른 특징을 가지게 됨. NBS 및 KSBS를 이용하여 멀티미디어 사용자들이 공유하고 있는 통신 네트워크 자원을 배분하는 경우, NBS는 전체 사용자들의 화질 총합이 가장 높도록 자원 분배를 하고, KSBS는 각 사용자들의 화질 열화가 모두 동일하도록 자원 분배를 하는 것을 보였음. 

Hyunggon Park and Mihaela van der Schaar, "Bargaining Strategies for Networked Multimedia Resource Management," IEEE Transactions on Signal Processing, vol. 55, no. 7, pp. 3496-3511, Jul. 2007.

▪️NBS의 경우 사용자 또는 자원이 변하는 동적 시스템에서는 NBS 기반 최적의 자원 분배 지점을 찾는데 높은 계산 복잡도가 필요하여 이를 해결하기 위한 연구를 수행함. NBS가 포함되는 유효 효용 집합(feasible utility set)을 작은 부 유효 효용 집합(sub-feasible utility set)으로 나누어 검색 공간(search space)이 작은 부 유효 효용 집합에서 각각 NBS를 찾는 방법을 제안하였음. 

Eunji Kim, Hyunggon Park and Pascal Frossard, "Low Complexity Iterative Multimedia Resource Allocation Based on Game Theoretic Approach," IEEE International Symposium on Circuits & Systems (ISCAS 2012), May 2012, pp. 1099-1102.

▪️위 방법은 부 유효 효용 집합에서 발생하는 오차가 지속적으로 누적되는 문제가 발생하는 한계점을 가지고 있음. 이를 해결하기 위하여 방향 벡터(direction vector)를 이용하여 NBS를 볼록 최적화 및 Bi-section 기법을 이용하여 해결하였음. CRRA(Constant Relative Risk Aversion) 효용 함수를 가진 사용자의 경우, 동적인 시스템에서도 매우 낮은 속도로 NBS를 찾을 수 있는 알고리즘을 개발하였음. 

Jisoo Choi and Hyunggon Park, "Direction Vector based Algorithm for the Nash Bargaining Solution in Dynamic Networks," IEEE Communications Letters, vol. 22, no. 7, pp. 1342-1345, Jul. 2018.

▪️NBS의 공리를 이용하여 closed-form 해법을 찾아내어 CRRA 효용 함수 사용자의 경우 가장 낮은 복잡도로 NBS를 구하는 방안을 제안하였음. 
Chaeyeon Cha and Hyunggon Park, "ECS-NBS: Exact Computation of Sequential Nash Bargaining Solutions,"  IEEE Transactions on Vehicular Technology, vol. 71, no. 12, pp. 13453-13457, Dec. 2022.

▪️일반적인 효용 함수에서도 적용할 수 있도록 동적인 유효 효용 집합 자체를 축소하여 검색 공간을 줄이는 알고리즘을 제안하였음. 
Chaeyeon Cha and Hyunggon Park, "Reduced-RSS: Reduced Residual Search Space for Nash Bargaining Solutions,"  IEEE Transactions on Vehicular Technology, vol. 74, no. 5, pp. 8215-8225, May 2025.