> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 1 Verification &Validation of Agent Based Simulations using the VOMAS (Virtual Overlay Multi-agent System) approach Muaz A. Niazi, Amir Hussain and Mario Kolberg have been used [3]. Of all the simulation models, agent-based Abstract—Agent Based Models are very popular in a number modeling and simulation paradigm has recently gained a lot of of different areas. For example, they have been used in a range of popularity by being applied to a very wide range of domains domains ranging from modeling of tumor growth, immune such as [4-9]. Validation of models typically requires experts systems, molecules to models of social networks, crowds and to look at data or animation as errors and un-wanted artifacts computer and mobile self-organizing networks. One reason for can appear in the development of agent-based models [10]. their success is their intuitiveness and similarity to human cognition. However, with this power of abstraction, in spite of However, because of the complex nature of agent-based being easily applicable to such a wide number of domains, it is models comprising of multiple interacting entities and the hard to validate agent-based models. In addition, building valid strong dynamics and frequent emergence patterns in the and credible simulations is not just a challenging task but also a system, it can be hard to validate agent-based models in the crucial exercise to ensure that what we are modeling is, at some same way as traditional simulation models. level of abstraction, a model of our conceptual system; the system In the case of agent-based simulations, it is even easier to that we have in mind. In this paper, we address this important fall into the trap of tweaking the variables, especially since area of validation of agent based models by presenting a novel occasionally, the inputs can tend to be quite numerous [11]. technique which has broad applicability and can be applied to all Because of the complex nature of agent based models and kinds of agent-based models. We present a framework, where a resulting emergence as shown in [12-14], coupled with an virtual overlay multi-agent system can be used to validate simulation models. In addition, since agent-based models have enormous variation possibility of the variables, the results of been typically growing, in parallel, in multiple domains, to cater the simulation study can vary considerably by changing the for all of these, we present a new single validation technique range or even the step size of just one or two variables. Thus, applicable to all agent based models. Our technique, which it is vitally important to be able to validate the agent-based allows for the validation of agent based simulations uses simulation. The problem however, comes from the grounds up VOMAS: a Virtual Overlay Multi-agent System. This overlay since validation is not to be an after-thought; it needs to be multi-agent system can comprise various types of agents, which initiated alongside at the start of the simulation study. Now, form an overlay on top of the agent based simulation model that validation of agent based models can be quite a challenging needs to be validated. Other than being able to watch and log, task [15, 16]. One problem lies in the fact that validation each of these agents contains clearly defined constraints, which, if violated, can be logged in real time. To demonstrate its typically requires SME (Subject Matter Experts) to analyze effectiveness, we show its broad applicability in a wide variety of [3] the simulation data or animation for comparison with simulation models ranging from social sciences to computer another system or model. However, because of appearance of networks in spatial and non-spatial conceptual models. complex phenomenon such as emergence of behavior, where one plus one is not necessarily two as it depends more on the Index Terms—Agent-based Modeling and Simulation, two “ones” and the behavior of the addition operation as is the Multiagent System, Verification, Validation, Agent Oriented norm in complex systems as compared to complicated systems Software Engineering [17]. Thus it can be very difficult to be sure if the behavior that we are observing is truly representative of the actual system[18]. Also, it is important to note here that even I. INTRODUCTION models, which cannot be validated might have merit and use such as bookkeeping devices or as an aid in selling ideas or as V ALIDATION of any simulation model is a crucial task[1, 2]. Simulations, however well-designed, are always only an approximation of the system and if it was so easy to a training aid or even as part of an automatic management system. In the social sciences literature and ACE (Agents in build the actual system, the simulation approach would never Computation Economics), empirical validation of agent-based models has been described in [19]. Alternate approaches to empirical validation are discussed in [20]. Replication of Manuscript received. agent-based models has been considered very important by M. A. Niazi, A. Hussain and M. Kolberg are with the Department of Computing Science and Mathematics, University of Stirling, Scotland, UK. some authors and has been discussed in [21]. An approach of (Tel: +92-321-5310906; e-mail: {man, ahu, mko}@ cs.stir.ac.uk ). validation based on philosophical truth theories in simulations > REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 2 has been discussed in [22]. Another approach called else interact with each other. These computational entities, "companion modeling" is an iterative participatory approach which are typically, simplifications of real-world counter- where multidisciplinary researchers and stakeholders work parts, need to have some meaningful semantics which can together continuously throughout a four-stage cycle: field include anywhere from simple behaviors as well as variables study and data analysis; role-playing games; agent-based for storing different items, such as states, to complex model design and implementation; and intensive representations such as artificial neural networks, artificial computational experiments [23]. Agent-based social immune systems, cognitive models etc. simulation has also been used for validation and calibration B. Definitions of the terms: [24]. In the past, although agent-based simulation has been Validation is the process by which we can determine if the shown to be useful in the validation of multi-agent model is a representation of the system.[3]. This is always systems[25, 26], multi-agent systems have not been used to performed while keeping the specific abstraction by the validate agent-based models. On the other hand, simulations designer in mind. Verification is basically the debugging of have been used in conjunction with software engineering for a the system where we ensure that the model that we build is long time[27]. Our work can be considered as pertaining to working correctly. Credibility is achieved when the decision- the last two stages of “Companion Modeling” i.e. Agent- makers and other key project personnel accept the model as Based Model Design/Implementation as well as Intensive well as its results as “correct”. Computational Experiments. Specifically, in this paper, we C. Correlation with VOMAS? present the following innovations: VOMAS approach has been designed to cater for all kind of agent-based models. As such, it has capability to monitor • We show how to develop a VOMAS (Virtual Overlay spatial as well as non-spatial concepts in agent-based models. Multi-Agent System), which can be used for the validation of agent based simulation models. • We thus further develop social science based validation techniques that can be applicable to both social science as well as other relevant domains. • We present an object-oriented software engineering based methodology for validation of agent-base models, which provides for both logging as well as animation based validation approaches in addition to test-case/invariant based approaches. The rest of the paper is structured as following: First we give an overview of the terms “Verification”, “Validation” and “Credibility” as discussed in the literature. We also discuss how these terms have been considered traditionally in simulation models. Next, we give an overview of performing Validation using VOMAS. We show the design of VO (Virtual Overlay) and Logger agents. Next, we show an example of developing a VOMAS for an existing model from Agent-Based Modeling literature, and demonstrate its usefulness, and ease in validation. Finally we conclude the paper. II. VERIFICATION, VALIDATION AND CREDIBILITY Fig. 1 VOMAS relation with an Agent Based Model Researchers transform real-world systems to models by D. Verification & Validation of agent-based models applying abstraction. This transformation requires propagating One sure way to establish the validity of agent-based model is concepts from the real world to useful computational models. to have Subject Matter Experts, who give the specification as These, in turn, are used to develop simulations. Simulation well as examine the results and logs of simulation runs. models, in essence end up giving back results which can be VOMAS approach allows experts to be involved in the design useful for the real world. As such, the more effective the of the agent-based model as well as the custom-built VOMAS abstraction mechanism, the better would be the expected real from scratch. By involving SMEs from the start of the project, world benefits. which are essentially equivalent to clients in the software engineering domain, VOMAS approach allows the simulation A. Peculiarities of Agent-Based Models study to be a stronger candidate for success. In case of agent-based models, the simulation comprises of one or more agents. These agents can work independently or > REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 3 III. VALIDATION USING VOMAS SME can examine the animation to see if the behavior appears to be similar to that expected in the A. Validation in agent based simulations actual domain. To understand VOMAS, let us examine figure 1. The Virtual 2. Validation using VOMAS: Overlay Multi-agent System is created for each simulation In case of VOMAS, we can validate both spatially as model separately by a discussion between the simulation well as non-spatially. specialist as well as the SMEs (Subject Matter Expert). When 3. Spatial Validation: the actual simulation is executed, the VOMAS agents perform In spatial validation, the placement of agents in the monitoring as well as logging tasks and can even validate simulation is important. This includes the placement constraints given by the system designer at design time. of some of the VOMAS agents, which interact with the actual agent based simulation. B. A Taxonomy of Agent-Based Validation techniques 4. Non-Spatial Validation: using VOMAS In non-spatial validation, the actual distance is not Now, let us examine how agent-based models are structured. important. These could be used to validate for Since agent based models have one or more agents, what these aggregate data and constraints/invariants etc. agents really mean in the real-world is entirely up to the 5. Networked or Link-Based Validation designer of the simulation. These elements can be spatial in In spatial validation, it is possible that the actual nature, where distance between agents in the simulation is placement is less important than the links between important or else non-spatial, where there is no concept of them. In case of social simulation, the example could distance in the simulation as shown in Fig. 2. In case of spatial be links to show social network friendships. In case models, it is also entirely possible that the exact distance may of computer science based networks, these could not be important, but the links between agents could be represent e.g. Connectivity of Peer-to-Peer overlay important. An example of this is HIV based models, where networks. interaction between agents can be shown as links. 6. Proximity Based Validation A detailed description of each of these follows. In this case, the actual proximity of agents to each other and especially to VOMAS agents is important. Fig. 2 A Taxonomy of Agent Based Validation techniques An example of this is pred-prey models where 1. Visual Validation: VOMAS agents can verify certain characteristics of Visual validation is a face validation technique based agents passing by them at a certain time. on an animation based validation technique where the 7. Log based validation: > REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 4 In log based validation, the SME can specify what things to be watched and logged so that they can be 1) Verify the Model examined after the fact and see how e.g. the The SME verifies the model by means of execution populations evolved over time, or else how wireless of the simulations by the Simulation Specialist. The sensor networks lost their power over time etc. detailed verification (debugging) is checked by the 8. Constraint-based validation or Invariant Based simulation specialist but in case of any ambiguity, the Validation: SME can be referred. It is entirely possible that the SME says that there 2) Validate the Model are certain constraints, which should never be This validation is done in three ways violated in a certain simulation experiment. If these a. Validation using animations: were ever to be violated, then the simulation system This validation is face validation by the should notify the user via some console or else log SME by means of analyzing the animations. the event as a b. Validation using Logs In this case, logs are generated based on Fig. 3 Use case model of simulation model design and V&V watches specified by the SME. These logs special case. E.g. Wolves must never all die in a wolf-sheep show after the fact, the entire scenarios like predation. If all of the wolves die, then the simulation needs black boxes from airplanes. to be stopped etc. as further data collection exercise might c. Validation using Invariants not be useful. These can be cases where the SME wants either immediate feedback even while C. Analysis of VOMAS running large scale parameter sweeps. So, if the invariants or constraints are ever The analysis of VOMAS has been conducted based on a violated, the user can be notified. Or at least, scenario-modeling approach. In figure 3, we see the use cases, this is definitely logged in the simulation some of which are described below. The rest should be self- log. explanatory and we are not listing them for shortage of space: > REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 5 3) Design and Develop Models b) Virtual Console Fig. 4 Class diagram of agents in a VOMAS Virtual Console agent is an agent, which can be used to dynamically display various messages at run-time. This use case is to be conducted by the simulation specialist in conjunction with the SME. c) Invariant D. Design of VOMAS Invariant is any condition, which the designer of the VOMAS 1) Motivation and the agent-based simulation, feels that must not be violated One of the most popular approaches in Validation is the three during the execution of the simulation. If the Invariant is step approach given in [28] . The approach has the following violated, the violation is logged. steps: a) Build a model that has high face validity. d) Logger Agent The logging capability is provided by the Logger Agent. b) Validate model assumptions e) Watch c) Compare the model input-out transformations to corresponding input-output transformations for the If the designer of the system wants some value to be observed, real system. it can be made a watch. VOMAS has been designed to cater for both face validity as well as model assumptions and io-transformations. Model f) Watch Log Entry assumptions are ensured by the use of invariants. Face validation is ensured by means of various techniques based on Each watch can also be logged as a logged entry. spatial and non-spatial validation and animation-based validation. IO-transformations are ensured by means of essential logging components. Thus, in other words VOMAS g) Invariant Violation provides the complete validation package. Invariant violations can be logged at run-time to the Console Virtual agent or else the log as a log entry. 2) Description of Class Diagram In figure 4, we see the class diagram of the VOMAS agents and how they interact with the agents in the simulation. The h) Log Entry description of each of these agents is given below: The base class of all log entries. a) VO Manager VO manager agent is the key agent handling the interaction of i) Sim Agent all of the other agents. This is an agent which is part of the agent based simulation model. > REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 6 j) VO Agent These are agents which can be located spatially or non- spatially to monitor the entire simulation. IV. CASE STUDY Here, we present application of a VOMAS to an agent-based simulation mode of the “Simulation of the research process”. Recently an agent-based simulation model of researchers attempting to present research in International publication venues was presented in [5]. We demonstrate how to develop and use the associated VOMAS on this model. A. The Publishing Researchers’ model In the publishing researcher model, the abstraction is that researchers are modeled as agents in the simulation. The higher the publications of an agent, the higher the agent goes. Thus space in this simulation model is essentially used to show the capability of the researcher. A screenshot of the simulation model is shown in fig 5. For more details, the interested reader is advised to consult the original article. The Fig. 5 Screenshot of the researchers’ model [5] showing researchers model has been developed using NetLogo [29]. So, let us according to their publication count. (Lime = Conference preferring, Red = formally define some of the entities involved: Journal Preferring, Cyan = No Preference) SME: An Expert Researcher with experience of publishing in various venues. V. CONCLUSION AND FUTURE WORK Objective of Simulation Study: To examine how the policies of In this paper, we have presented a novel framework for the researchers in selection of publication venues impacts an validation of agent based simulation models. We have given a overall organization. description of how VOMAS agents can be constructed for validation. As a case study, we have shown its application on Example Invariant: an existing published model. In the future, we shall apply Basis: In a particular simulation experiment, enough time of VOMAS on various types of simulation models and simulation run should be given to ensure that journal demonstrate how it can be effective in validation. Some of the preferring researchers publish at least ten times during the models we intend to explore VOMAS application on, include simulation. pred-prey models, tumor growth models, Peer-to-Peer Invariant: If simulation stops before each journal preferring unstructured overlay network models. researcher is able to publish at least ten times, note an invariant violation in the console and/or the log. REFERENCES Example watches: Measure the total number of researchers with the best policy. [1] O. Balci, "Verification, validation, and accreditation," in Measure the number of researchers above a certain threshold. Proceedings of the 30th conference on Winter simulation Washington, D.C., United States: IEEE Computer Society Press, Measure the number of overall publications. 1998. [2] J. Banks, J. S. C. II, B. L. Nelson, and D. M. Nicol, Discrete-Event System Simulation, Fourth ed.: Peason Education, 2005. [3] A. M. Law, "How to build valid and credible simulation models," in Simulation Conference, 2008. WSC 2008. Winter, 2008, pp. 39- 47. [4] M. Niazi and A. Hussain, " Agent based Tools for Modeling and Simulation of Self-Organization in Peer-to-Peer, Ad-Hoc and other Complex Networks," IEEE Communications Magazine, vol. 47, No. 3, pp. 163 - 173., March 2009. [5] M. Niazi, A. Hussain, A. R. Baig, and S. Bhatti, "Simulation of the research process," in Winter Simulation Conference, Miami, FL, 2008, pp. 1326-1334. [6] M. Niazi, "Self-organized customized content delivery architecture for ambient assisted environments," in Proceedings of the third international workshop on Use of P2P, grid and agents for the development of content networks, Boston, MA, USA, 2008, pp. 45- 54. > REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 7 [7] N. Gilbert and K. G. Troitzsch, Simulation for the social Scientist, [28] T. H. Naylor and J. M. Finger, "Verification of Computer Second ed.: McGraw Hill Education, 2005. Simulation Models," Management Science, vol. 2, pp. B92-B101, [8] C. M. Macal and M. J. North, "Agent-based modeling and 1967. simulation: desktop ABMS," in Proceedings of the 39th [29] U. Wilensky, "NetLogo," Evanston, IL, 1999: Center for conference on Winter simulation: 40 years! The best is yet to come Connected Learning Comp.-Based Modeling, Northwestern Washington D.C.: IEEE Press, 2007. University, 1999. [9] A. Siddiqa, M. Niazi, F. Mustafa, H. Bokhari, A. Hussain, Noreen Akram, S. Shaheen, F. Ahmed, and S. Iqbal, " A New Hybrid Agent-Based Modeling & Simulation Decision Support System for Breast Cancer Data Analysis " in ICICT Karachi, Pakistan: IEEE Press, 2009. [10] J. M. Galán, L. R. Izquierdo, S. S. Izquierdo, J. I. Santos, R. d. Olmo, A. López-Paredes, and B. Edmonds, "Errors and Artefacts in Agent-Based Modelling," Journal of Artificial Societies and Social Simulation, vol. 12, no. 11, 2009. [11] T. W. Lucas, S. M. Sanchez, F. Martinez, L. R. Sickinger, and J. W. Roginski, "Defense and homeland security applications of multi-agent simulations," in Proceedings of the 39th conference on Winter simulation: 40 years! The best is yet to come Washington D.C.: IEEE Press, 2007. [12] A. Ilachinski, "Exploring self-organized emergence in an agent- based synthetic warfare lab," Kybernetes, vol. 32, pp. 38 - 76, 2003. [13] M. Chli and P. De Wilde, "The Emergence of Knowledge Exchange: An Agent-Based Model of a Software Market," Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, vol. 38, pp. 1056-1067, 2008. [14] M. Cartier, "An Agent-Based Model of Innovation Emergence in Organizations: Renault and Ford Through the Lens of Evolutionism," Comput. Math. Organ. Theory, vol. 10, pp. 147- 153, 2004. [15] C. Bianchi, P. Cirillo, M. Gallegati, and P. A. Vagliasindi, "Validating and Calibrating Agent-Based Models: A Case Study," Comput. Econ., vol. 30, pp. 245-264, 2007. [16] C. Bianchi, P. Cirillo, M. Gallegati, and P. Vagliasindi, "Validating and Calibrating Agent-Based Models: A Case Study," Computational Economics. [17] J. H. Miller and S. E. Page, Complex Adaptive Systems: An Introduction to Computational Models of Social Life: Princeton University Press, 2007. [18] J. S. Hodges and J. A. Dewar, "Is It You or Your Model Talking? A Framework for Model Validation," RAND Corporation, Santa Monica, California. [19] G. Fagiolo, C. Birchenhall, and P. Windrum, "Empirical Validation in Agent-based Models: Introduction to the Special Issue " Computational Economics, vol. 30, pp. 189-194, October, 2007 2007. [20] S. Moss, "Alternative Approaches to the Empirical Validation of Agent-Based Models," Journal of Artificial Societies and Social Simulation, vol. 11, no. 15, 2008. [21] U. Wilensky and W. Rand, "Making Models Match: Replicating an Agent-Based Model," Journal of Artificial Societies and Social Simulation, vol. 10, p. 2, 10/31 2007. [22] A. Schmid, "What is the Truth of Simulation?," Journal of Artificial Societies and Social Simulation, vol. 8, p. 5, 10/31 2005. [23] O. Barreteau and e. al., "Our Companion Modelling Approach " Journal of Artificial Societies and Social Simulation, vol. 6, 2003. [24] M. Makowsky, "An Agent-Based Model of Mortality Shocks, Intergenerational Effects, and Urban Crime," Journal of Artificial Societies and Social Simulation, vol. 9, No. 2, 2006. [25] M. Cossentino, G. Fortino, A. Garro, S. Mascillaro, and W. Russo, "PASSIM; a simulation-based process for the development of multi-agent systems," Int. J. Agent-Oriented Softw. Eng., vol. 2, pp. 132-170, 2008. [26] G. Fortino, A. Garro, and W. Russo, "From Modeling to Simulation of Multi-Agent Systems: An Integrated Approach and a Case Study," in Multiagent System Technologies, LNAI 3187: Springer-Verlag, 2004, pp. 213-227 [27] R. S. Pressman, Software Engineering, A Practitioner's Approach, Sixth ed.: McGraw Hill, 2005.