Data structures and processing methods for highly scalable simulation platforms

Abstract

Disclosed herein are systems and methods for simulating an environment over a plurality of intervals of in-simulation time by using a two-part data structure to represent agents or entities in the simulation. A system may create and store a data structure representing an agent in the simulation, wherein a first portion of the data structure represents characteristics of the agent at a present interval and a second portion of data structure represents characteristics of the agent at a future interval of the simulation. Also disclosed herein are systems and methods for executing a multi-agent simulation using multiple processing threads. A system may group a plurality of agents in the simulated environment into subsets associated respectively with nodes of the simulated environment, assign the subsets to respective separate processors of the system, and execute the simulation using separate processing threads associated respectively with the separate processors.

The invention claimed is: 
     
       1. A system for executing a simulation comprising a plurality of agents using multiple processing threads, comprising:
 two or more processors; 
 memory storing one or more programs, wherein the one or more programs are configured to be executable by one or more of the two or more processors to cause the system to:
 group a plurality of agents in the simulated environment into a first subset and a second subset, wherein the first subset is associated with a first node of the simulated environment and the second subset is associated with a second node of the simulated environment; 
 assign the first subset to a first processor of the two or more processors; 
 assign the second subset to a second processor of the two or more processors; and 
 execute the simulation using a first processing thread associated with the first processor to perform calculations for agents in the first subset and using a second processing thread associated with the second processor to perform calculations for agents in the second subset. 
 
 
     
     
       2. The system of  claim 1 , wherein grouping the plurality of agents into the first subset and the second subset comprises:
 performing a first query to identify all agents associated with the first node to be grouped into the first subset; and 
 performing a second query to identify all agents associated with the second node to be grouped into the second subset. 
 
     
     
       3. The system of  claim 2 , wherein the first query and the second query are performed against a flat-query-time database. 
     
     
       4. The system of  claim 1 , wherein:
 the first node is a first inflection point in the simulated environment; 
 the second node is a second inflection point in the simulated environment; and 
 grouping the plurality of agents into the first subset and the second subset comprises grouping agents associated with the first inflection point into the first subset and grouping agents associated with the second inflection point into the second subset. 
 
     
     
       5. The system of  claim 4 , wherein the one or more programs are further configured to be executable by one or more of the two or more processors to cause the system to:
 if the system determines that an agent will reach the first inflection point during a current interval of the simulation, determine that the agent is associated with the first inflection point; and 
 if the system determines that the agent will reach the second inflection point during the current interval of the simulation, determine that the agent is associated with the second inflection point. 
 
     
     
       6. The system of  claim 4 , wherein the one or more programs are further configured to be executable by one or more of the two or more processors to cause the system to:
 if the system determines that an agent will reach more than one inflection point during a current interval of the simulation, reduce a simulated speed of the agent such that the agent will reach only one inflection point during the current interval of the simulation. 
 
     
     
       7. The system of  claim 1 , wherein the one or more programs are further configured to be executable by one or more of the two or more processors to cause the system to:
 generate and store data representing a variable associated with both the first node and the second node; 
 increment the variable, by the first processor, without locking the variable and without preventing access to the variable by the second processor; 
 increment the variable, by the second processor, without locking the variable and without preventing access to the variable by the first processor. 
 
     
     
       8. The system of  claim 1 , wherein the one or more programs are executed using a single in-process in-memory database. 
     
     
       9. A method for executing a simulation comprising a plurality of agents using multiple processing threads, comprising:
 at a system comprising two or more processors and storage:
 grouping a plurality of agents in the simulated environment into a first subset and a second subset, wherein the first subset is associated with a first node of the simulated environment and the second subset is associated with a second node of the simulated environment; 
 assigning the first subset to a first processor of the two or more processors; 
 assigning the second subset to a second processor of the two or more processors; and 
 executing the simulation using a first processing thread associated with the first processor to perform calculations for agents in the first subset and using a second processing thread associated with the second processor to perform calculations for agents in the second subset. 
 
 
     
     
       10. A non-transitory computer-readable storage medium for executing a simulation comprising a plurality of agents using multiple processing threads, wherein the storage medium stores instructions that, when executed by a simulation system comprising two or more processors, cause the simulation system to:
 group a plurality of agents in the simulated environment into a first subset and a second subset, wherein the first subset is associated with a first node of the simulated environment and the second subset is associated with a second node of the simulated environment; 
 assign the first subset to a first processor of the two or more processors; 
 assign the second subset to a second processor of the two or more processors; and 
 execute the simulation using a first processing thread associated with the first processor to perform calculations for agents in the first subset and using a second processing thread associated with the second processor to perform calculations for agents in the second subset. 
 
     
     
       11. The system of  claim 4 , wherein the one or more programs are further configured to be executable by one or more of the two or more processors to cause the system to:
 if the system determines that an agent will not reach any inflection points during a current interval of the simulation, not assign the agent to any subsets for the current interval of the simulation. 
 
     
     
       12. The system of  claim 4 , wherein the one or more programs are further configured to be executable by one or more of the two or more processors to cause the system to:
 if the system determines that an agent will not reach any inflection points during a current interval of the simulation, assign the agent to a subset associated with a next inflection point that the agent is projected to reach. 
 
     
     
       13. The system of  claim 4 , wherein the one or more programs are further configured to be executable by one or more of the two or more processors to cause the system to:
 if the system determines that an agent will not reach any inflection points during a current interval of the simulation, assign the agent to a subset with one or more other agents that are nearby to the agent. 
 
     
     
       14. The system of  claim 4 , wherein the one or more programs are further configured to be executable by one or more of the two or more processors to cause the system to:
 if the system determines that an agent will not reach any inflection points during a current interval of the simulation, assign the agent to a subset associated with an inflection point that is nearby to the agent. 
 
     
     
       15. The system of  claim 4 , wherein the one or more programs are further configured to be executable by one or more of the two or more processors to cause the system to:
 if the system determines that an agent will not reach any inflection points during a current interval of the simulation, assign the agent to a subset that includes one or more other agents that are not projected to reach any inflection points during the current interval of the simulation.