An assignment problem is a traditional research area of the optimization field. Centralized optimization methodologies such as linear programming has advantage in the assignment problems. Meanwhile, the decentralized approaches for solving assignment problem have emerged recently. Under the decentralization, each entity determines its assignment without any central control. Thus, the efficient interaction between entities is the main issue for the decentralized assignment problem solving methodologies. Distributed constraint optimization problem (DCOP) is a representative methodology for decentralized assignment problem. In DCOP model, each entity determines its actions to optimize the cost generated from relational constraints with other entities. Asynchronous distributed optimization (ADOPT) is an algorithm which finds DCOP solution by message communication between entities. Since the number of required message communication exponentially increases as the problem scale increases, the applications of the algorithm into real problem have not been studied frequently. This research proposes three improvement methods to make the algorithm more adaptable for large-scale problems. The improvements aim to reduce the solution time by relaxing the constraints between entities especially with the spatial properties of the entities. The virtual experiment and analysis will address the influence of the improvements on the original algorithm. The proposed improvement methods improves the execution time performance while maintaining the solution quality as same as the original algorithm.
자원, 임무 등을 사람, 기계와 같은 시스템 구성 요소들에게 효율적으로 할당하는 문제는 최적화 연구의 오랜 연구 분야였다. 오랜 시간의 연구를 통해 선형계획법, 정수계획법 등의 최적화 이론 등이 발전되어 많은 현실 문제를 해결하고 있다. 이러한 방법론들은 중앙 집권적인 정보 공유와 임무 하달을 통해 진행 되므로 강력한 최적해를 보장한다. 한편, 최근들어 임무 할당 문제를 분권적으로 접근하려는 연구가 대두되고 있다. 시스템의 복잡도로 인해 중앙 관리자가 모든 정보를 취합, 제어할 수 없거나, 원초적으로 중앙 통제자가 존재하지 않는 시스템에서 임무 할당 문제를 해결하기 위해서는 분권적인 방법의 접근이 필요하다. 이러한 문제들은 시스템 구성 요소들이 서로간의 의사소통을 통해 스스로 임무를 선택, 수행하는 방법으로 문제를 해결해야 한다. 이러한 문제 해결 방법은 다중 에이전트 시스템 (Multi-agent system, MAS) 분야에서 연구가 시작되었으며, 경매(Auction), 동맹 형성 (Coalition formation), 분산 제약 추론 (Distributed constraint reasoning) 등의 방법론들이 제시되었다. 본 논문에서는 분산 제약 추론의 한 갈래인 분산 제약 최적화 문제 (Distributed constraint optimization problem, DCOP)을 통해 분권적 임무 할당 문제에 접근하였다. DCOP은 에이전트 기반 방법론을 택하고 있으며, 에이전트와 그들의 관계를 통해 임무 할당 문제를 정의한다. 비동기적 분산 최적화 (Asynchronous distributed optimization, ADOPT) 알고리즘은 DCOP 문제를 풀기 위해 제시된 알고리즘으로써, 이론적인 완전성을 바탕으로 대표적인 DCOP 문제 해결 알고리즘으로 알려져있다. 하지만 이론적인 부분의 많은 발전에도 불구하고, 확장성의 제약으로 인해 ADOPT 알고리즘은 실제 문제 해결에서는 많이 적용되지 못하고 있다.본 논문에서는 ADOPT 알고리즘의 확장성 향상을 위한 개선 방안을 제시하고, 가상 실험을 통해 그 효과도를 측정한다. 특히 알고리즘 개선 과정에서 시스템 구성 요소들의 공간적인 제약 사항을 반영하여 문제를 단순화 하여 알고리즘의 실행 속도 향상을 목표로 한다. 가상 실험 결과 제시된 개선안이 알고리즘 실행 속도에 유효한 성능 향상을 나타냄을 확인하였다. 또한 해 탐색 속도가 향상되면서도 탐색된 결과의 유효성은 본래의 알고리즘과 같은 성능을 내는 것 또한 확인되었다. 이러한 결과로부터 본 연구에서 제시하는 개선 방안이 ADOPT 알고리즘을 실제 문제 해결에 활용할 수 있는 가능성을 높일 것으로 기대된다.
