Agent-based modeling and simulation (ABMS) has been applied to complex systems. Complex systems consist of multiple components and their intricate relationships, and this trait is similar to the structure of agent-based model (ABM), which is one reason that ABM is considered as a representative method for modeling complex systems. However, as systems to be modeled are getting more complex, ABMS should be performed more efficient manner.
Opposed to the prosperity of ABMs, the current practices of ABMS have inefficiently conducted: from the perspective of ABM development, most of ABM has been developed without reusing existing components of others'. Considering ABM development is considerable, model reuse is a key for reducing the cost.
Meanwhile, from the perspective of ABM simulation, the prolonged execution time of simulating ABM is a critical factor. ABM generally holds lots of components and their intricate relationships. This complex structure eventually results in the prolonged simulation execution. It causes heavy cost for ABM simulation because the simulation execution would be performed repeatedly to obtain statistical insights.
This dissertation suggests a formalism-based approach to resolve those inefficiencies. Formalism is a mathematic-based representation for model specification and should involve unambiguity and completeness. Such model specifications can increase model reusability in ABM development. Also, in the view of ABM simulation, model specifications in formalism are used to simplify ABM structure with reduction technique, and this simplification leads to the reduction of the simulation execution time.
To realize the suggested approach, this dissertation proposes a formalism for efficient ABM development, called Large-scale, Dynamic, Extensible, and Flexible (LDEF) formalism. LDEF adopts the structured modeling technique from DEVS, so it supports to build a larger model by the composition of other models. Also, LDEF inscribes ABM contexts, such as agents, environments, and their relationships, and dynamic interaction changes into its model specification, so ABMs are explicitly represented by LDEF.
Also, this dissertation proposes a method for accelerating the simulation execution of ABMs that has hierarchical and dynamic structure. To do this, a meta-model structure for the event exchanges, called Coupling Relation Graph (CRG) is suggested. CRG is a directed graph that represents coupling relations among components of ABM. The proposed method abstracts model structures represented in CRG with techniques in graph theory so that it aids to reduce the procedure for event exchanges and eventually reduces the simulation execution time.
To evaluate and prove the efficiency of the proposed methods, theoretical and empirical methods are applied to the example models that are developed by LDEF and simulated by the proposed method. The evaluation results prove that the proposed methods provide significant efficiency on ABMS, in particular, when a model holds a lot of components and frequent interaction changes. In addition, as a case study for ABMS, analyzing evacuation situation during bombardment is introduced.
복잡계(complex system)의 특성은 많은 수의 구성요소(component)와 그들 간의 복잡한 상호작용 및 관계가 존재하는 것이다. 이러한 복잡계의 특성은 에이전트 기반 모델 (agent-based model)의 구조와 연관성이 있어, 에이전트 기반 모델링 및 시뮬레이션 (agent-based modeling and simulation)은 복잡계에서 발생하는 문제를 재현하고, 이해하고, 분석하는데 널리 사용되고 있다. 그러나, 복잡계의 구조와 규모가 점점 복잡해짐에 따라, 에이전트 기반 모델링 및 시뮬레이션의 효율성에 대한 고려가 필요하다.
에이전트 기반 모델링 및 시뮬레이션의 효율성은 어디서 확인할 수 있을까? 이를 위해, 본 학위논문에서는 모델링 과 시뮬레이션 두 가지 측면에서 효율성의 요소를 정의하였다. 모델링 측면의 효율성은 모델 재사용으로 정의하였다. 높은 모델 재사용성 에이전트 기반 모델의 개발에 있어 이전에 개발되어 있던 모델의 활용을 촉진하여, 결과적으로는 개발 비용의 감소라는 결과로 이어 진다. 이를 위해서는, 형식적으로는 모델 조합 (model composition)을 이용한 모델 개발등을 지원하며, 내용적으로는 에이전트 기반 모델의 요소가 분명히 드러나는 모델링이 수행되어야 한다.
시뮬레이션 측면의 효율성은 시뮬레이션의 실행 속도의 증가로 정의하였다. 에이전트 기반 모델링 및 시뮬레이션을 포함한 일반적인 모델링 및 시뮬레이션은 반복적인 시뮬레이션을 통한 통계적인 결과 분석으로 모델링한 시스템에 대한 이해를 얻을 수 있다. 그러나 에이전트 기반 모델의 복잡한 구조와 많은 구성요소를 시뮬레이션 하기 위해서는 일반적으로 많은 시간이 필요하고, 이는 전체적인 에이전트 기반 모델링 및 시뮬레이션의 시간과 비용을 증가시키는 원인으로 작용된다. 따라서, 시뮬레이션의 실행 속도 증가는 전체적인 에이전트 기반 모델링 및 시뮬레이션의 분석 시간을 줄일 수 있다.
본 학위논문에서는 이러한 에이전트 기반 모델링 및 시뮬레이션의 효율성을 높이기 위해 형식론 (formalism) 기반의 접근 방법을 제안한다. 형식론은 수학적인 방법으로 모델의 명세를 정형적으로 기술할 수 있게 해준다. 이러한 형식론을 이용한 에이전트 기반 모델의 개발은 많이 이루어지고 있었지만, 모델의 재사용성과 에이전트 기반 모델의 분명한 표현이라는 두 가지 목적을 달성하는 형식론은 없었다.
특히, 본 학위논문에서는 에이전트 기반 모델의 개발을 위한 LDEF 형식론(Large-scale, Dynamic, and Extensible, Flexible formalism, LDEF formalism)을 제안하고, 시뮬레이션의 실행 속도를 높이기 위하여 제안된 형식론을 활용한 Coupling Relation Graph (CRG) 라는 방법을 제안한다. LDEF 형식론은 시스템 공학 형식론의 특징을 반영하여 모델 재사용을 장려하는 동시에, 에이전트 기반 모델의 요소 (예를 들어, 동적인 관계 변화와 에이전트의 행동 결정 과정)를 모델 명세에 직접적으로 표현하였다. 또한, CRG 방법에서는 수학적으로 표현된 구성 요소들의 상호작용을 추상화하여 그 과정을 간단하게 할 수 있는 데이터 구조를 제안한다. 특히, CRG를 이용하여 동적으로 변하는 구조의 모델에서 효율적인 상호작용 방법을 제안한다.
본 학위논문에서 제안하는 방법은 예제 모델과 가상 실험을 이용하여 그 효율성이 측정되었다. 예제 모델에서는 LDEF 형식론을 통해서 에이전트 기반 모델이 분명히 표현되고, 이에 따라 모델 재사용이 증대될 수 있다는 것을 보여준다. 가상 실험에서는 두 개의 예제 모델에 대하여, 제안하는 방법과 기존의 시뮬레이션 방법을 적용하여 성능을 비교하였고, 성능 비교 결과를 통해 제안하는 방법이 구성요소의 수가 많고 상호작용의 변화가 많은 모델에서 제안하는 방법의 성능이 더 좋은 것을 보였다. 추가적으로, 제안하는 방법들을 실제 프로젝트에 적용하여 분석한 결과를 보여준다.
본 학위 논문을 통해서, 제안하는 방법들이 복잡계를 분석하는데 이용되는 에이전트 기반 모델링 및 시뮬레이션의 효율성을 높이는데 사용될 수 있고, 특히 복잡계의 구성요소의 수가 많고 그들 사이의 상호작용이나 관계의 변화가 많은 경우에 더 높은 효율성을 보여줄 것으로 기대한다.
