Asynchronous Modeling and Simulation with Orthogonal Agents

Asynchronous Modeling and Simulation with Orthogonal Agents

Roman Tankelevich (Department of Electrical Engineering and Computer Science, Colorado School of Mines, Golden, CO, USA)
Copyright: © 2012 |Pages: 21
DOI: 10.4018/jats.2012100102
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

This paper considers a class of systems of autonomous self-governed agents with purpose-specific behavior. Agents of this class contribute most to the overall performance if they have an unobstructed (transparent) access to the environment. Many examples of such systems can be found in swarm technologies and asynchronous simulation of discrete and continuous systems. An efficiency metric for a multi-agent system operating within a given environment is proposed as a dot product of the system’s characteristic time-vectors: one of an agent’s demands for resources and the other of the resources’ availability. It is shown that the smaller the dot product the higher the efficiency of the agents. In some cases, the better efficiency of individual agents translates into improvement of the overall performance of the system. This observation is postulated as the principle of orthogonality: under some conditions, the asynchronous, ungoverned systems outperform the systems with synchronized actions. It is shown that the asynchronous (“chaotic”) multi-agent models, properly devised to achieve a higher level of transparency, can produce a better throughput beyond the level achieved by simply improving the latency of the system. Examples of orthogonal systems include many discrete-continuous physical, financial, control and some machine learning multi-agent models. Conditions of convergence of asynchronous models are presented. Some experimental results are shown, as well. More general observations are made in the context of natural decomposition.
Article Preview

Introduction

Many natural objects have a structure such that all their components work independently, asynchronously, and are self-governed. When we analyze these systems using multi-agent simulators this structure is most likely to be preserved. Recently, many research ideas in this area are dealing with the environment of agents’ operation as well as with their internal organization and method of functioning. The paradigm of Agent-directed simulation seems to be an appropriate framework for discussing the related issues (Yilmaz & Ören, 2009; Ören 2001). There are many aspects of such simulation techniques that need to be addressed:

  • How to decompose the original system to be reproduced as a multi-agent simulator?

  • What protocol should the agents use to communicate with each other and their operating environment?

  • How to make the agents self-adaptive and learning entities?

  • What metric should be applied to measure the performance of the multi-agent simulation system?

In his seminal work, Micromotives and macrobehavior, T.C. Shelling introduced the principles of human motivation and interaction within a societal environment (Shelling, 1978). He argued that:

…the situations in which people’s behavior or people’s choices depend on the behavior or the choices of other people, are the ones that usually don’t permit any simple summation or extrapolation to the aggregates. To make that connection we usually have to look at the system of interaction between individuals and their environment, that is, between individuals and other individuals or between individuals and the collectivity.

By extrapolating this observation onto general simulation cases concerning presence of many agents, some assumptions can be postulated about the performance of an aggregate as a function of individual performances.

The asynchronous multi-agent aggregate is a form of parallel computational systems. Asynchronous simulation, although has been widely considered, is not completely accepted for parallel computations because of the dominant idea of work load balancing. As it is noticed in Frommer and Szyld (2000):

An important concept in the design of parallel algorithms is that of load balancing, which simply means that the work has to be approximately equally distributed among processors. Otherwise, some processors finish their task much earlier than others, and the waiting (idle) time degrades the performance of the algorithm.

In the multi-agent models, this observation is not valid (Wooldridge, 2002). Agents are assigned specific tasks that most commonly stay unchanged. The balance of workload is not required. The multi-agent aggregates are essentially asynchronous and should cooperate via their environment without any balancing of the workload. That makes the consideration of their asynchronous behavior an essential part of the design of such models.

It seems reasonable to assume that any individual element of a system experiences the highest level of “satisfaction” when its demand for a needed resource is instantly available from its operating environment. Since such an environment depends on other individuals' actions, this utility has to be considered at the system’s level. The degree of transparency provided by the system for its individual entities, that is their abilities to fulfill the tasks with minimal impediment from the environment, can be used as a metric of the system.

We will call a multi-agent system orthogonal if it has the highest level of transparency. The distance function for such systems will be introduced here as a dot product of the system’s characteristic time-vectors of demand for system’s resources and appropriate time-vectors of the system resource’s availability (Tankelevich, 1992).

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 2 Issues (2017): Forthcoming, Available for Pre-Order
Volume 8: 1 Issue (2016)
Volume 7: 3 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing