A design space exploration method for Identifying emergent behavior in complex systems
MetadataShow full item record
This research seeks to gain insight into the design of distributed multi-agent systems. Distributed multi-agent systems present opportunities for accomplishing a goal using multiple simple systems rather than a more complicated monolithic system. Distributed systems, if properly designed, have the potential to exhibit self-organizing behavior which can lead to systems that require less centralized control in addition to improved robustness, reliability, scalability, and adaptability than traditional monolithic, centralized systems. As engineered systems become more complex, their behavior is more difficult to characterize and predict. Self-organizing systems are difficult to analyze and design since the system behavior is emergent, i.e., the collective behavior only becomes apparent once the system is integrated. The collective behavior is primarily driven by the local interactions of the agents and their environment. This poses an enormous challenge for engineering these systems. The task of system design---selecting the right rules and system parameters---is difficult due to the opaque connection between inputs and responses. The goal of this research is to develop a methodology that provides a way of systematically exploring the design space in order to identify the conditions that give rise to emergent behavior. This information can be used as part of the scientific process of providing feedback through the iterative design process. In order to address this goal, this research seeks to answer the question on how to define, measure, and use the concept of emergence in the design of a multi-agent system. Similarly, it will address the more general question about how to understand "complex systems" in order to analyze and engineer them. This will be used to guide the development of an appropriate methodology. This research develops the Systematic Exploration for Emergence Detection (SEED) methodology for evaluating computer simulations of complex systems in order to identify conditions that lead to emergent behavior. This research proposes a new quantitative measure of emergence which can identify critical transitions in macro-level performance/function of the system due to changes in system context (i.e., environmental conditions or system parameters). The methodology provides the framework for performing a design space exploration using this measure of emergence to identify critical regions in the design space. These regions help to characterize the design space and will help guide the design process by providing insight into design points where the system behavior is unexpected or changing rapidly, which are possible indicators of emergent behavior. The SEED methodology is based on a statistical analysis approach. The design space is efficiently sampled using Design of Experiments methods. At each of these design points, the system behavior is characterized statistically using repeated runs of the simulation. The proposed measure of emergence, Design Space Divergence, is then evaluated across the design space and critical regions are identified using data visualization and clustering methods. A case study is performed on a multi-UAV distributed surveillance problem to investigate whether this framework is capable of identifying emergent behavior. The SEED methodology is used to explore the system design space, including the number of UAVs used in the system and influential vehicle and system parameters. The results show that this methodology provides insights into the landscape of system performance across the design space. More specifically, it identifies a number of candidate designs which exhibit emergent behavior where the system performance rapidly improves as the system undergoes a transition from disorganized to organized behavior. The SEED methodology provides for a more rigorous, traceable, and thorough design process for systems which have been difficult to understand and design using traditional engineering methods.