Research

Research

HOME

Topic 1

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

문제 정의 및 해결 방안

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

활용 범위








5G/6G 무선 네트워크 시스템,

스마트 그리드 및 에너지 관리
스마트팩토리 시스템, 
군집 로봇 태스크 배분 시스템
자율자동차 및 군집 드론 시스템, 
도로 교통 시스템

연구 결과

◦ 대표적으로 내쉬 협상 해법(Nash bargaining solution, NBS)이 있으며 Kalai-Smorondinsky bargaining solution(KSBS), 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.

◦ 그리고 이를 일반적인 효용 함수에서도 적용할 수 있도록 동적인 유효 효용 집합 자체를 축소하여 검색 공간을 줄이는 알고리즘을 제안하였음.