Research

Agent-based simulation (ABS) is an increasingly popular method of solving problems in the domains of finance, telecommunications, robotics, gaming, and military applications. In order for a simulation to be effective, it must be both efficient and easy to implement. Several ABS APIs exist, but require the application programmer to have knowledge of parallel programming to gain maximum performance benefits. My work focuses on developing an easier programming paradigm for ABS systems to make it more accessible to research scientists in all fields. I've built an agent-based middleware library on top of a parallel discrete event simulator (PDES) called SASSY. My approach in developing SASSY's agent-based interface was to explore other popular ABS systems and borrow the most common features offered. I am currently developing simulations in various fields to get an idea of how SASSY will be used, and further improve its usability and performance. This experience will help me as I continue my research in the future. I hope to build on this approach while branching out into new research areas like graphics, augmented reality, and serious games.

Research Background

My first research assistantship involved research in parallel and distributed programming. I began by running several RAxML (a maximum-likelihood based inference model for large phylogenetic trees) benchmarks on a cluster of IBM Cell processors. I studied the ratio of computation to communication and compared these results to more traditional processors to determine whether or not the Cell could be used efficiently without custom reimplementation. My thesis work involved detecting collisions of slow moving objects on the Cell. I parallelized the 3D collision detection algorithm in the open source physics engine Bullet and was able to achieve slight speedup on the Cell processor's dual power processing elements (PPEs). My algorithm used several of the Cell's more specialized synergistic processing elements (SPEs) as well.

Based on my experience with parallel and distributed programming, I transferred into the PhD program and changed my focus to agent-based simulation. I began my work by designing and implementing an agent-based middleware to sit on top of the SASSY (scalable agent-based simulation system) kernel. I based my interface on TeamBots and MASON, two popular ABS systems. This easy-to-use API provides simulation programmers with a method to harness the power of a PDES system without any knowledge of parallel-distributed programming. Once the agent-based interface was implemented, I began to explore several interesting problems in the ABS domain.

As the number of agents in a simulation grows, the amount of communication explodes exponentially, limiting the scalability of ABS systems. In traditional networking applications, clustering several small messages into a single large message solves this problem. Once the clustered message is delivered, the client unpacks it and handles each smaller message separately. In [1], my collaborators and I explored using this technique in an ABS system via interest manager logial processes (IMLPs). Each IMLP is assigned a virtual region within the simulation space. As agents move about, they register with nearby IMLPs and receive updates from neighboring agents. All communication between agents takes place through these IMLPs. By clustering messages coming from IMLPs, we were able to reduce the total number of messages sent between IMLPs and improve the overall performance of the system.

While SASSY was designed to be easy to use, many researchers have already adopted MASON for their simulations. In [2] we explored bytecode transformation to take a program written for MASON and automatically transform it into one that can be run in SASSY. Using the SOOT bytecode optimization framework, we were able to replace key portions of a compiled MASON classfile to allow it to run in SASSY. This effectively takes a sequential simulation and automatically transforms it into a parallel, distributed one. Early results are quite promising, and have led to several improvements in the SASSY kernel and agent-based middleware. This idea can easily be extended to other popular ABS systems, including Clay, which we used to model ant hunting behavior in association with the Georgia Institute of Technology.

Current Research

Simulations are often used in decision-making. Several possible decisions are attempted, and propagated through a model. The branch with the most favorable outcome is often chosen as the best decision. In an ABS this decision-making process is achieved by cloning LPs each time a decision is made, much like branch prediction. At each decision point, a copy of the agent LP is made for each choice and allowed to continue propagating through the system. This can lead to state explosion unless the number of agents is strictly controlled. This has already been researched in time-warp systems, but I am currently implementing it in SASSY to test its application in an ABS environment. This improvement will be used in several applications that our lab is working on.

In association with a professor in the University of Georgia's School of Ecology we are working on an NSF study of the Okefenokee Swamp. Using SASSY and data collected from local residents, we are modeling the changes of behavior and migration patterns of humans due to droughts, fires and floods in the area. This will involve data visualization to interactively view the results of our simulation.

As a game developer, I have a strong interest in using simulation to create learning AI for games. I am currently working on a predator-prey game that will take advantage of ABS to evolve better models for both agents in the game. Using observed biological data, and the crowd sourcing effect of games observed in the Foldit project, this could lead to better methods of tracking prey, and escaping predators. This has applications for biologists as well as military strategists.

[1] C. Sherer, A. Gupta and M. Hybinette. 2011. "Adaptive Message Clustering for Distributed Agent-Based Systems." in 2011 IEEE Workshop on Principles of Advanced and Distributed Simulation (PADS).

[2] C. Sherer, G. Vulov, and M. Hybinette. 2011. "On-the-Fly Parallelization in Agent- Based Simulation Systems." in Proceedings of the 2011 Winter Simulation Conference.