We review existing approaches to mathematical modeling and analysis of multi-agent systems in which complex collective behavior arises out of local interactions between many simple agents. Though the behavior of an individual agent can be considered to be stochastic and unpredictable, the collective behavior of such systems can have a simple probabilistic description. We show that a class of mathematical models that describe the dynamics of collective behavior of multi-agent systems can be written down from the details of the individual agent controller. The models are valid for Markov or memoryless agents, in which each agents future state depends only on its present state and not any of the past states. We illustrate the approach by analyzing in detail applications from the robotics domain: collaboration and foraging in groups of robots.
 Abstract We investigate the effect of predictions upon a model of coevolutionary systems which was originally inspired by computational ecosystems. The model incorporates many of the features of distributed resource allocation in systems comprised of many individual agents, including asynchrony, resource contention, and decision-making based upon incomplete knowledge and delayed information. Previous analyses of a similar model of non-predictive agents have demonstrated that periodic or chaotic oscillations in resource allocation can occur under certain conditions, and that these oscillations can affect the performance of the system adversely. In this work, we show that the system performance can be improved if the agents do an adequate job of predicting the current state of the system. We explore two plausible methods for prediction - technical analysis and system analysis. Technical analysts are responsive to the behavior of the system, but suffer from an inability to take their own behavior into account. System analysts perform extremely well when they have very accurate information about the other agents in the system, but can perform very poorly when their information is even slightly inaccurate. By combining the strengths of both methods, we obtain a successful hybrid of the two prediction methods which adapts its model of other agents in response to the observed behavior of the system. Coalition formation is a desirable behavior in a multiagent system, when a group of agents can perform a task more efficiently than any single agent can. Computational and communications complexity of traditional approaches to coalition formation, e.g., through negotiation, make them impractical for large systems. We propose an alternative, physics-motivated mechanism for coalition formation that treats agents as randomly moving, locally interacting entities. A new coalition may form when two agents encounter one another and it may grow when a single agent encounters it. Such agent-level behavior leads to a macroscopic model that describes how the number and distribution of coalitions change with time. We increase the generality and complexity of the model by letting the agents leave coalitions with some probability. The model is expressed mathematically as a series of differential equations. These equations have steady state solutions that describe the equilibrium distribution of coalitions. Within a context of a specific multi-agent application, we analyze and discuss the connection between the global system utility the parameters of the model.