Large-Scale Agent-Based Simulations
As we acquire an increasing amount of information on the physical world, we have the opportunity to develop new methods for analyzing it, and to develop new simulation models that can capture the underlying properties that shape large-scale, long-term processes such as transportation, pollution, and the impact of new technologies or policy decisions on our environment. This is particularly true in the transportation domain. The interesting challenge here is that much work in science and engineering has developed sophisticated methods for either (1) handling the complex, detailed questions concerned with small or moderate-sized micro-simulations (in the tens, hundreds, or small number of thousands of simulated entities), or (2) handling questions at the aggregate level concerned with macro-simulations where higher-level concepts such as flows abstract away individual simulated entities (SEs), enabling simulations of much larger phenomena. Historically, scaling up micro-simulations to address detailed questions about large-scale transportation systems, when feasible at all, has required supercomputer-class facilities and much specialized hand-optimization of the code.
Our research makes a first step towards tackling the grand challenge of truly scalable transportation micro-simulations. We take the computational ideas that allow database systems to scale to petabytes and apply them to the programming and processing of large-scale transportation micro-simulations. Thus, the use of our computer science techniques will enable detailed simulations on a standard cloud computing infrastructure (a shared nothing cluster) with SEs numbering in the tens of thousands to millions. In particular, we will enable scalable declarative processing of such transportation simulations, which will enable us to use optimizations from databases such as set-at-a-time processing, indexing, and parallel processing. Our declarative processing model does not come with a declarative programming model, but instead allows transportation simulation designers to stay in a traditional imperative programming model as long as they follow certain high-level program design patterns. Thus we use computational ways of thinking about transportation simulations that are only subtly different from existing ways of programming transportation simulations, but that enable researchers to perform transportation micro-simulations at scales that were never imagined before.
As part of our work on simulations, we have begun work on a new programming language -- BRASIL, the Big Red Agent SImulation Language. BRASIL bridges the mental model of simulation developers with our declarative processing techniques. BRASIL is automatically parallelized and processed by our runtime engine, BRACE, the Big Red Agent-based Computation Engine. While our compiler and runtime are not yet available, we make the language specification available to the public. In addition, we also describe the design of BRACE.
- Guozhang Wang, Marcos Vaz Salles, Benjamin Sowell, Xun Wang, Tuan Cao, Alan Demers, Johannes Gehrke, Walker White. Behavioral Simulations in MapReduce. PVLDB 3(1): 952-963 (2010).
- Guozhang Wang, Marcos Vaz Salles, Benjamin Sowell, Xun Wang, Tuan Cao, Alan Demers, Johannes Gehrke, Walker White. Behavioral Simulations in MapReduce. CoRR abs/1005.3773: (2010).
- The BRASIL Language Specification.
- Benjamin Sowell, Alan Demers, Johannes Gehrke, Nitin Gupta, Haoyuan Li, and Walker White, From Declarative Languages to Declarative Processing in Computer Games. In Proc. of the 2009 CIDR Conf. on Innovative Data Systems Research (CIDR 2009).
- Walker White, Benjamin Sowell, Johannes Gehrke, and Alan Demers, Declarative Processing for Computer Games. In Proc. of the 2008 ACM SIGGRAPH Sandbox Symposium (Sandbox 2008).
- Walker White, Alan Demers, Christoph Koch, Johannes Gehrke, and Rajmohan Rajagopalan. Scaling Games to Epic Proportions. In Proceedings of the 2007 ACM SIGMOD Int. Conf. on Management of Data (SIGMOD 2007).
This research has been supported by the National Science Foundation under Grant IIS-0725260, by the Air Force Office of Scientific Research, and by a grant from Microsoft. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the sponsors.