Information Technology Reference
In-Depth Information
10 Summary
Agent-based models are characterized by an inherent parallelism as
all agents act simultaneously. Trying to exploit this parallelism by
an adequate simulation engine seems natural. The main problem
is that agent-based models are not only characterized by agents
acting simultaneously, but also by agents interacting with each other
in complex and manifold ways. The interactions between agents
effectively limit the degree of possible parallelization and demand
appropriate decomposition of a model into independent partitions.
Evaluating constraints defined within an agent-based model and
computing the result of concurrent actions takes
O
(
n
2
)time(with
n
referring to the number of agents). This quadratic growth of runtime
severely limits scalability and needs to be reduced in order to gain
significant speedups. Decomposing the set of agents into sets of agents
whichmaybeexecutedinparallelisanimprovementasthequadratic
growth now applies to smaller sets of agents.
As the choice of a suitable model partitioning strategy is signi-
ficant for achieving a high speedup, various partitioning strategies
are presented. The partitioning strategies are divided into strategies
operating on a
per-agent
basis and on strategies operating on a
per-
action
basis. Per agent means that agents are treated as a whole
whereas per action refers to strategies which operate on the finer
scale of sensor and effector actions of agents. The actual partitioning
may be either uninformed or take into account additional information.
Typical information to be taken into account is the spatial distribution
of agents. The assumption is that agents far away from each other
do not influence each other. Other information which may be taken
into account for creating a good partitioning are communication and
interaction relations between agents.
